Point in polygon

[gayathri81]

I am trying to find out whether a point is inside a polygon.I am using vector std c++.

My program till now:

Polygon.h
class Polygon {
public:
Polygon();
virtual ~Polygon();
virtual bool Inside(Point p);
private:
std::vector<Point> pts;
 
Polygon.cc
Polygon::Polygon()
{
}
Polygon::~Polygon()
{
}
bool Polygon Inside(Point p)
{
int nvert=pts.size;
}

--------
I liked the ray casting algorithm but I dont know how to do in C++. Could anyone help out?

[weaknessforcats]

Here again, polygon is a general word. Use it as a base class. Then derive your polygons: Square, Triangle, Rectangle, Pentagon, etc. Try to not start out to solve all polygons in one class.

Then in each derived class write a convert method to build the database. Each derived class can have a different algorithm and database. All that's in the base class is the function prototype that you override in the derived class.

Your square is just rectangle so maybe you derive square from rectangle to allow the square to use the same database as the rectangle. Maybe there is a parallogram class deriving from polygon and then square and rectangle derive from that.

The idea is that you implement a shape at a time. Figuring out if a point is inside or outside a rectangle or triangle is pretty straightforward so solve those first. You can just calculate these. No database required.

later when you have a polygon that's a rectangle with a triangle punched out of it you can use the already written rectangle and triangle code to find out of your point is inside our outside the shape. Like if it is inside the rectangle and also inside the triangle, then it is outside the shape. In your class are member variables that are Rectangle and Triangle objects.

C++ expects you to write a little and get that working. Then write a little more and get that working. By repeated improvement cycles you have this humongous capability and all along the way the program has been working. Any errors are probably in just the last improvement cycle.

[gayathri81]

Thanks for your suggestion. I did as you told. First I created a base class called Shape and a derived class called Polygon. In the base class, I used a function calculateDistance to calculate distance between 2 points.
Shape.cc

inline double Shape::calculateDistance(Point &a,Point &b)
{
//formula to calculate distance between two points
}
 

When I compile it, I get error as:
Extra qualification Shape on member calculateDistance.

I wrote the point in polygon algorithm in derived class and when I compile it, it refers to the same error as above.

Please help me out.
----------
@weaknessforcats

[weaknessforcats]

There is no error in the code you posted.

Post the exact error your compiler gave you.

[gayathri81]

The error got solved when I removed the keyword inline. There were 4 lines inside the braces. So I removed it and now I have solved it.

[weaknessforcats]

That may be but the code word inline was not your problem.

An inline function is not called. Rather the compiler makes a copy of the code and pastes the copy where you make your call. To do that the compiler must have seen the inline function before you call it so it can make a copy.

I suspect you made a call using a function protototype and not the function itself.

[gayathri81]

As you told, I made polygon as a sub class and used the algorithm below to find whether a point is inside or not.
Polygon.h

class Polygon: public Shape
{
public:
virtual bool inside(Point& p)
private:
std::vector<Point&> points;
};

Polygon.cc

bool Polygon::inside(Point& p) 
{   
int i, j, c = 0; 
  int nvert = poly.size();   
 for (i = 0, j = nvert-1; i < nvert; j = i++)
 { 
     if ( ((poly[i].y> p.y) != (poly[j].y> p.y)) && (p.x < (poly[j].x-poly[i].x) * (p.y-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) )       
 c = !c;   
 } 
  return c;
 } 

This is the ray casting algorithm. But on compiling I am gettting plenty of errors like:
error: forming pointer to referenece type 'Point&'

Where am I going wrong? Can you help me.

[weaknessforcats]

This code:

std::vector<Point&> points;

won't fly. A vector is an array. An array contains objects or pointers.

A reference is not an object. Rather it is an alias for an already existing object.

What your vector needs is a type and not a reference to a type.

Just do this:

std::vector<Point> points;

and your error will go away.

[weaknessforcats]

OOPS.

The codeword inline was a problem after all.

Everything I said about inline functions is true but in addition since inline functions are not called they have no address. They have just been pasted around as needed.

Virtual functions, on the other hand, need an address so they can be overriden wherever they may be called.

Hence, inline functions cannot be virtual.

Sorry I didn't pick up on this sooner.

[gayathri81]

Thank you very much . I removed the & and the error went away.

[gayathri81]

Hello Sir

I am still not able to get sms frm polygonal geofence. As I told you, I tried to make Shape as a base class and Polygon as derived class. I have created a class called DataProcessor.cc

DataProcessor.cc

void DataProcessor::run()
{
std::vector<Geofence> geofences= DBCon->getGeofences(deviceID);
/*Geofence is a struct in another file by the name DataObjects.h and geofences is a object of Geofence.I am writing the query in DBCon to get geofences which is also working fine and no errors are there.
*/
}
void DataProcessor::checkGeofence()
{
if(geofences.empty())
{
return null;
}
else
{
std::vector<Geofence>::iterator it_GF;
std::vector<Geofence> curGeofences;
std::vector<Shape> shapes;
std::vector<Shape>::iterator shapeIt=shapes.begin();
for (; shapeIt != shapes.end(); shapeIt++) 
{
if (shapeIt->isInside(curPosition.position))
{
curGeofences.push_back(*it_GF);
}
}
}
}

/*Shape is a base class and has the formula to calculate distance between two points. I want to assign the value of "geofences" into "shapes". I think that shapes.begin is always empty.
*/
How should I do it? Please help me out.

[weaknessforcats]

You are not implementing polymorphism correctly.

If your Shapes class is a base class then your ocde using Shapes objects can only use a Shapes* or a Shapes&.

The Shapes class will define the interface and the derived classes will define the implementation.

Your best course here is to write a small test program so see how this all works. Polymorphism in C++ will require that you study up so I woulds look for articles on the web or perhaps get a textbook and actually implement the polymorphism examples to see them working.

Understanding how a virtual function works will be key in your being able to progress with your geofences project.

AS I see it you have a Shape with a derived class called Polygon which itself may have a derived class Pentagon.

Only the Pentagon class knows how to work with Pentagons.

You create a Pentagon and use it indirectly as a Shape:

Shape* s = new Pentagon;
Myfunction(s);

Inside MyFunction, which has a Shape* argument you code:

void MyFunction(Shape* arg)
{
   bool result = arg->isInside();
etc....

When you call MyFunction with a Pentagon, arg->isInside() is a call to Pentagon::isInside.

This works because Shape::isInside is a virtual function. The Pentago class overrides Shape::isInside with Pentagon::isInside. Then when you access a Pentagon object using as Shaoe* you gt the call to Pentagon::isInside.

If you use a Pentagon object as a Shape object, this does not work because a Pentagon object only partly a Shape object. Pentagon has more stuff than Shape. You lose the extra stuff in Pentagon when tu treat it as a Shape. You must treat it as a Shape* or Shape&.

[gayathri81]

Thanks a lot for your comments. I found out the mistake. I have edited my program and now in the process of compilation.

[gayathri81]

I think I am making mistake in designing the polygon algorithm. This is the algorithm which I have written. Is it correct?
Polygon.h

class Polygon : public Shape {
public:
 
    Polygon(points_polygon p);
    Polygon();
    Polygon(const Polygon& orig);
    virtual ~Polygon();
 
    virtual bool isInside(const Point& p);
 
    std::vector<Point> points;
    int _ID;
    int _userID;
    std::string _deviceID;
    std::string _name;
    Point _polygon;
    int _side;
 
};

Polygon.cc

Polygon::Polygon(points_polygon p)
{
   _name = p.name;
   _ID = p.ID;
   _side = p.side;
   _userID = p.userID;
   _deviceID = p.deviceID;
   _polygon = p.polygon;
 
}
 
Polygon::Polygon() {
}
 
Polygon::Polygon(const Polygon& orig) {
}
 
Polygon::~Polygon() {
}
// Function to check whether the point is inside or outside the polygon : concept of ray casting algorithm
 bool Polygon::isInside(const Point& p) {
    int i,j,c=0;
 
    for(i=0,j=this->points.size()-1;i<this->points.size();j=i++)
    {
        if(((this->points[i].longitude > p.longitude) != (this->points[j].longitude > p.longitude))
       &&(p.latitude < (this->points[j].latitude - points[i].latitude) * 
          (p.longitude - this->points[i].longitude) / 
          (this->points[j].longitude - this->points[i].longitude) + this->points[i].latitude))
            c!=c;
    }
    return c;
}

[weaknessforcats]

This code:

(((this->points[i].longitude > p.longitude) != (this->points[j].longitude > p.longitude))
 &&(p.latitude < (this->points[j].latitude - points[i].latitude) * 
(p.longitude - this->points[i].longitude) / 
(this->points[j].longitude - this->points[i].longitude) + this->points[i].latitude))
 c!=c;
etc...
 

Is non-readable. Generally, compact code like this means smaller executable programs that run faster. Unfortunuately, the program has to work first.

Break this into sections:

int A;
int B;
int C;
int D;
int E;
     A = this->points[i].longitude > p.longitude;
     B = this->points[j].longitude > p.longitude;
     C = p.latitude < (this->points[j].latitude - points[i].latitude;
     D = p.longitude - this->points[i].longitude;
     E = this->points[j].longitude - this->points[i].longitude) + this->points[i].latitude;

Using your debugger, verify each of these variables have the correct value.

Change the if statement to use A,B,C,D and E.

I was not able to understand this:

c!=c;
 

since that will always be false.

I have no idea if the algorithm is correct. But remember with int calculations there are no fractional parts. 6/100 is zero. So code like X/Y where X is smaller than Y wil always be zero. Just be aware of this.

Also, you have public data members. These should be private. The reason is that should these get screwed up, the functions that did ir are the class member functions whose main job is to guarantee these values are never screwed up. That's a better deal as opposed to having screwed up values and not have anu idea where in the program that happened.

[gayathri81]

Hello Sir

I did as you told. First made as executable statements and wrote as
((A!=B)&&(C*D/E)); However I found that it does not enter the function at all in the main program DataProcessor.cc(I checked this by giving some statements like hello1, hello2 etc...). Does this mean my algorithm is wrong or there is some problem in calling function in main program? Please help me out.

[weaknessforcats]

Have you set a breakpoint in your function to verify that it is not called? Your algorithm can't be wrong unless it is actually used to produce a result.

Sometimes a comiler omits code that can never be reached:

if (A is true) do this and return.
if (A is not true) do this and return.
Do some other processsing and return.

The Do some other processing will never be reached so wile it may be in your code, the compile will generally drop it from the compiled code.

[gayathri81]

I just modified the algorithm in Polygon.cc

bool Polygon::isInside(const Point& p)
 {
    int i,j= this->points.size()-1;
    bool oddnodes=false;
    for(i=0;i<this->points.size();i++)
    {
        if((this->points[i].longitude < p.longitude &&this->points[j].longitude>=p.longitude || this->points[j].longitude< p.longitude &&this->points[i].longitude>=p.longitude)&&
                (this->points[i].latitude<=p.latitude|| this->points[j].latitude<=p.latitude))
        {
            if(this->points[i].latitude+(p.longitude-this->points[i].longitude)/(this->points[j].longitude-this->points[i].longitude)*(this->points[j].latitude-this->points[i].latitude)<p.latitude)
            {
                oddnodes!=oddnodes;
 
            }
        }
        j=i;
    }
    return oddnodes;
}

However now I get an error "unable to resolve identifier points", though I have declared
std::vector<Point>points;

Why is this hapening now? I never got this error before.

[weaknessforcats]

Does polygon.cc #include polygon.h?

[Banfa]

weaknessforcats is away for a bit and has asked me to look after this thread.

I have tried compiling your code (as given in this thread) and it compiles without the error you are getting which suggests that you may have failed to properly include the header for Polygon or some other file structural issue.

Is this the only error you are getting? If not lets see them all please.

What compiler are you using? Have you set it to produce all possible warnings.

When I compile the above code I get these warnings

Line 7 that it would be best to use parentheses () to make sure the logic of the if statement happens correctly.

Line 12 the statement has no effect

In oddnodes!=oddnodes; != is the comparison operator that produces a boolean result, it does not change the value of its parameters. I believe that you where trying to toggle the value of oddnotes that would be oddnodes = !oddnodes;

[gayathri81]

Yes. It is also included. But I have found out where the mistake is. Thanks a lot.

[gayathri81]

I also found that I have to convert into degrees because of latitude and logitude. So I used this:

 double Dataprocessor::calculateDistance(const Point& a, const Point& b) 
{
    double lat = (a.latitude + b.latitude) / 2 * 0.01745;
    double dLat = 111.3 * cos(lat) * (a.longitude -b.longitude);
    double dLng = 111.3 * (a.latitude - b.latitude);
 
    return sqrt(pow(dLat, 2) + pow(dLng, 2));
}

Now I want to find out whether a point is inside the polygon or not. So I used the above function and the polygon.cc and wrote:

if(calculateDistance(position,.....))
{
// push back to geofence
}

In the above part, position is the position of test point and the other parameter would be the vertices of polygon. But it is not clear what should be written there? I want to compare the latitude and longitude of test point with each of the vertices of polygon using the ray casting algorithm.

I wrote points but showed me an error , failing to recognise it. What should be written?

[Banfa]

points is a vector of Point, but calculateDistance is expecting a reference to a single Point.

You need to iterate through your vector of points and individually call the function for each one

for(std::vector<Point>::iterator iter = points.begin(); iter != points.end(); iter++)
{
  double distance = calculateDistance(position, *iter);
 
  // Do something with distance
}
 

[gayathri81]

Hello
I perfectly agree with you. I have done what you have told. Now I want to call the polygon algorithm. I tried this out but did not work.

if(isInside(curPosition.position))
{
//push geofences inside.
}
// Function to check whether the point is inside or outside the 
//polygon : concept of ray casting algorithm
bool DataProcessor::isInside(Point& p)
 {
 
    int i,j= this->points.size()-1;
    bool oddnodes=false;
    for(i=0;i<this->points.size();i++)
    {
        if((this->points[i].longitude < p.longitude && this->points[j].longitude >= p.longitude || this->points[j].longitude< p.longitude && this->points[i].longitude >= p.longitude)&&
                (this->points[i].latitude <= p.latitude|| this->points[j].latitude <= p.latitude))
        {
            if(this->points[i].latitude + (p.longitude-this->points[i].longitude) / (this->points[j].longitude-this->points[i].longitude) * (this->points[j].latitude-this->points[i].latitude) < p.latitude)
            {
                oddnodes!=oddnodes;
 
            }
        }
        j=i;
    }
       return oddnodes;
}

//All the code is in DataProcessor.cc.
//curPosition.position is the current position of GPS device.

Where am I going wrong? There are no syntax errors. But I am no getting sms.

[Banfa]

As I already pointed out in post #20 you have some errors that are causing your code to go wrong, for example oddnodes!=oddnodes; does nothing.

[gayathri81]

Hallo

Yes you are right. This statement always returns me 0 even if the point is outside or inside. Or how should I modify the code above to get even for outside and odd for inside ( ray casting method)? Please help me out.

[Banfa]

As I already said I gave the solution to this in post #20

[gayathri81]

Hello

Thank you for the solution. But I could not understand this :
double distance = calculateDistance(position, *iter);

I am a starter with vector in C++ and I am trying to develop myself.

[Banfa]

This is just a call to a function

double distance = calculateDistance(position, *iter);

double distance = - we are declaring a variable to hold the result called distance and we will initialise it with something.

calculateDistance(position, *iter); the thing we are going to initialise it, the return value of the function calculateDistance, 2 parameters are being passed to this function, position (which came from your own post) and *iter. Sinceiter is an iterator into your vector by dereferencing iter (*iter) we get the value that the iterator is currently pointing at.

When using a standard container, such as std::vector iterators are used to address each entry in the container in turn, a little like using a pointer you access members of an array. Iterators can be incremented to access the next member and there are a variety of stand-library methods which can help, for example std::distance the distance between 2 iterators into the same container. All containers have methods begin and end to get the iterator to the first entry and the iterator just after the last entry and rbegin and rend which gets elements in reverse order.

Look at this example (run and compile and understand)

#include <iostream>
#include <vector>
#include <algorithm>
 
 
int main()
{
    // Declare my vector
    std::vector<int> numbers;
 
    // Populate it
    for(int ix = 0; ix < 10; ix++)
    {
        numbers.push_back(ix);
    }
 
    // Iterate through the vector and print out its values
    for(std::vector<int>::iterator iter = numbers.begin(); iter != numbers.end(); iter++)
    {
        std::cout << "Forward Iterate: " << *iter << std:: endl;
    }
 
    // Iterate in reverse order through the vector and print out its values
    for(std::vector<int>::reverse_iterator riter = numbers.rbegin(); riter != numbers.rend(); riter++)
    {
        std::cout << "Reverse Iterate: " << *riter << std:: endl;
    }
 
    // Check size
    std::cout << "Count: " << numbers.size() << " = " << std::distance(numbers.begin(), numbers.end()) << std::endl;
 
    return 0;
}