Here’s a quick code snippet to know if given a point, the point is inside an array of polygon vertices. Based on the crossing number algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// In Unity Vector2 is implemented with a pair of _floats_ x and y! // if you are not working with unity make sure to implement Vector2 with _double_ to avoid // precision errors. private bool PointInsidePolygon(Vector2 point, Vector2[] polygonVertices) { if(polygonVertices.Length < 3) //not a valid polygon return false; int nCounter= 0; int nPoints = polygonVertices.Length; Vector2 p1, p2; p1 = polygonVertices[0]; for(int i = 1; i < nPoints; i++) { p2 = polygonVertices[i%nPoints]; if(point.y > Mathf.Min(p1.y, p2.y)) { if(point.y <= Mathf.Max(p1.y, p2.y)) { if(point.x <= Mathf.Max(p1.x, p2.x)) { if(p1.y != p2.y) { double xInters = (point.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x; if((p1.x == p2.x) || (point.x <= xInters)) { nCounter ++; } } } } } p1 = p2; } if((nCounter%2) == 0) return false; else return true; } |
This can also be extended to 3D space if necessary, but that’s for the reader.
