Point in Polygon C++ Algorithm implementation

Question

I have tried two algorithms that were answers in other StackOverflow questions:

Check point within polygon

Point in Polygon Algorithm

Both were showing some points in as out or out as in while other points were correct. This test cast assumes that there are always only 4 vertices (rectangle)

bool PointInPolygon(Coordinate point, vector<Coordinate> points) {
cout << "x,y" << point.getX() << "," << point.getY() << endl;
cout << "TEST COOR ARRAY" << endl;
for (int i=0; i<4; i++) {
    cout << points[i].getX() << "," << points[i].getY() << endl;
}
   
int i, j, nvert = points.size();
bool c = false;

for(i = 0, j = nvert - 1; i < nvert; j = i++) {
  if( ( (points[i].getY() > point.getY() ) != (points[j].getY() > point.getY()) ) &&
      (point.getX() < (points[j].getX() - points[i].getX()) * (point.getY() - points[i].getY()) / (points[j].getY() - points[i].getY()) + points[i].getX())
    )
    c = !c;
}

cout << c << "======================" << endl;

return c;
}

And the output was wrong where (2,3) and (1,1) shouldn't be in. Lines on the perimeter are not considered to be in. But even so, then 2,3 should always be in.

x,y1,1
TEST COOR ARRAY
1,1
1,3
4,3
4,1
1======================
IN
x,y2,2
TEST COOR ARRAY
1,1
1,3
4,3
4,1
1======================
IN
x,y2,3
TEST COOR ARRAY
1,1
1,3
4,3
4,1
0======================
OUT
x,y3,2
TEST COOR ARRAY
1,1
1,3
4,3
4,1
1======================
IN
x,y3,3
TEST COOR ARRAY
1,1
1,3
4,3
4,1
0======================
OUT

I have similar issues in using the other algorithms I found as well. If anyone could point me in the right direction, I'd appreciate it a lot thanks!

The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. — πάντα ῥεῖ, Oct 30 '16 at 09:17
You are dividing by `somepoint.y-someotherpoint.y`, do you think it's OK? What if the difference is zero? — n. m. could be an AI, Oct 30 '16 at 10:16
Thanks guys for your kind suggestions! I manage to get what I needed. I used the algo in the second link "Point in Polygon Algorithm" and realized that it's output does not consist of points outside of the shape, but has all points IN and some points ON the shape. Thus, I went to remove points that were ON the shape from the output and got my desired output. — CNG, Oct 31 '16 at 02:55

score 0 · Accepted Answer · answered Oct 30 '16 at 09:41

The Algorithm is based on the concept:
For any closed polygon, any straight line should intersect it's edges Even number of times (not taking line on line situation into account)...
think of it as (Enter, Exit, Enter, Exit, ...).

so, If you draw a Line from your Test-Point to basically infinity, depending on where it started, it should intersect Even times if the point was outside, and Odd if it was in!

As i see, by the test cases, and the "4 vertices" note: you are seeking
PointInRectangle(Coord c, Rect r) which is much simpler, faster and seems fit.

For your test case where (2,3) in (1,1)-(1,3)-(3,4)-(4,1) = TRUE
it is parallel on your bottom line, and probobally is "Disregarded",
but most likely, the intersections with your verticals are there because of Floating Point Inaccuracy.
you should split the Expression in parts, or Debug it as is to see what actual values are calculated There.

Point in Polygon C++ Algorithm implementation

1 Answers1