Currently I am using the ray casting algorithm, however it has some limitations like when the ray passes a vertex it's impossible to determine whether it's inside or not.
What algorithm can I use that will always work in any kind of polygon?
Asked
Active
Viewed 976 times
0
-
[here](http://geomalgorithms.com/a03-_inclusion.html) might help – Ed Heal May 01 '16 at 02:00
-
1Possible duplicate of [How can I determine whether a 2D Point is within a Polygon?](http://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon) – m69's been on strike for years May 01 '16 at 02:27
-
integer or floating point numbers? – maxim1000 May 01 '16 at 06:27
-
@maxim1000 Doesn't really matter, can be float can be integer depending on which one is easier/more accurate. – Eagle May 01 '16 at 09:17
1 Answers
1
You can select ray direction depending on polygon itself so that it doesn't cross any vertex.
For integer coordinates it would be enough to cast a ray along (1,0.5/deltaX), where deltaX is the maximum difference between x-coordinates of polygon vertices. The first point with integer coordinates on the ray will be its start. The next one will have x-coordinate startX+2*deltaX which is outside of the polygon and cannot be its vertex. With exact arithmetic you can robustly determine whether the point inside or outside.
For floating point numbers exact arithmetic is a problem, so you want the ray to be as far from polygon vertices as possible. For this you can calculate direction to every polygon vertex atan2(y[n]-y,x[n]-x) and sort the vertices by it. Then select the biggest difference between neighbor vertices in this sorted sequence and cast the ray between them.
maxim1000
- 6,297
- 1
- 23
- 19