473,836 Members | 2,180 Online

# Point in polygon

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

My program till now:
Expand|Select|Wrap|Line Numbers
1. Polygon.h
2. class Polygon {
3. public:
4. Polygon();
5. virtual ~Polygon();
6. virtual bool Inside(Point p);
7. private:
8. std::vector<Point> pts;
9.
10. Polygon.cc
11. Polygon::Polygon()
12. {
13. }
14. Polygon::~Polygon()
15. {
16. }
17. bool Polygon Inside(Point p)
18. {
19. int nvert=pts.size;
20. }
--------
I liked the ray casting algorithm but I dont know how to do in C++. Could anyone help out?
Jul 17 '12 #1
28 33768
weaknessforcats
9,208 Recognized Expert Moderator Expert
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.
Jul 17 '12 #2
gayathri81
25 New Member
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 calculateDistan ce to calculate distance between 2 points.
Shape.cc
Expand|Select|Wrap|Line Numbers
1. inline double Shape::calculateDistance(Point &a,Point &b)
2. {
3. //formula to calculate distance between two points
4. }
5.
When I compile it, I get error as:
Extra qualification Shape on member calculateDistan ce.

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

----------
@weaknessforcats
Jul 18 '12 #3
weaknessforcats
9,208 Recognized Expert Moderator Expert
There is no error in the code you posted.

Post the exact error your compiler gave you.
Jul 20 '12 #4
gayathri81
25 New Member
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.
Jul 23 '12 #5
weaknessforcats
9,208 Recognized Expert Moderator Expert
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.
Jul 23 '12 #6
gayathri81
25 New Member
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
Expand|Select|Wrap|Line Numbers
1. class Polygon: public Shape
2. {
3. public:
4. virtual bool inside(Point& p)
5. private:
6. std::vector<Point&> points;
7. };
Polygon.cc

Expand|Select|Wrap|Line Numbers
1. bool Polygon::inside(Point& p)
2. {
3. int i, j, c = 0;
4.   int nvert = poly.size();
5.  for (i = 0, j = nvert-1; i < nvert; j = i++)
6.  {
7.      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) )
8.  c = !c;
9.  }
10.   return c;
11.  }
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.
Jul 23 '12 #7
weaknessforcats
9,208 Recognized Expert Moderator Expert
This code:
Expand|Select|Wrap|Line Numbers
1. 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:

Expand|Select|Wrap|Line Numbers
1. std::vector<Point> points;
and your error will go away.
Jul 23 '12 #8
weaknessforcats
9,208 Recognized Expert Moderator Expert
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.
Jul 23 '12 #9
gayathri81
25 New Member
Thank you very much . I removed the & and the error went away.
Aug 2 '12 #10