Suggested pointInPolygon algorithm works counterclockwise only

Question

Once I tested the algorithm explained here and here, I was as excited as the comments below it.

But after my test cases failed then a lot of debugging and tracing, that I realized it has a condition for it to work properly.

This algorithm needs the polygon List<Point> to have its' points sorted counterclockwise, otherwise the output is incorrect.

This is a very simple test case to validate my claim :

(You can use this to plot and test)

Polygon: Points sorted counterclockwise.

inputPoints.Add(new Point(1, 3));
inputPoints.Add(new Point(2, 1));
inputPoints.Add(new Point(6, 2));
inputPoints.Add(new Point(3, 6));

Test points:

Point testP1 = new Point(3, 3); //inside,  algorithm output :correct
Point testP2 = new Point(6, 3); //outside, algorithm output :correct
Point testP3 = new Point(9, 9); //outside, algorithm output :correct

Polygon: Points sorted clockwise.

inputPoints.Add(new Point(1, 3));
inputPoints.Add(new Point(2, 1));
inputPoints.Add(new Point(6, 2));
inputPoints.Add(new Point(3, 6));

Test points:

Point testP1 = new Point(3, 3); //inside,  algorithm output :correct
Point testP2 = new Point(6, 3); //outside, algorithm output :wrong answer
Point testP3 = new Point(9, 9); //outside, algorithm output :correct

Polygon: Points in random order (they're only 4 points, but when scaled, will result incorrect as well).

inputPoints.Add(new Point(2, 1));
inputPoints.Add(new Point(6, 2));
inputPoints.Add(new Point(1, 3));
inputPoints.Add(new Point(3, 6));

Test points:

 Point testP1 = new Point(3, 3); //inside,  algorithm output :wrong answer
 Point testP2 = new Point(6, 3); //outside, algorithm output :correct
 Point testP3 = new Point(9, 9); //outside, algorithm output :correct

You can't have a polygon "in random order" and expect which points are inside it to be constant, even with an algorithm that doesn't expect a particular direction. A bow-tie is not the same as a square. — Jon Hanna, Mar 21 '17 at 10:48
@JonHanna its not a polygon in random order, its a set of points that can construct a polygon, and they could be randomly input. — Sanjo Emad, May 07 '17 at 15:36

score 0 · Answer 1 · answered Mar 21 '17 at 09:15

This is a pretty standard concept with geometry and point in polygon algorithms from my own experience.

For example, even the SQL Server Spatial libraries have a function to ensure that the GEOMETRY imported is oriented correctly to work with their functions.

SQL Server Spatial ReorientObject(geography) method: https://msdn.microsoft.com/en-us/library/ff929311.aspx

Suggested pointInPolygon algorithm works counterclockwise only

1 Answers1