Clever Geek Handbook

Point between the two polygons, how to find what it belongs to?

enter image description here

Which algorithm to use so that we can determine if the red point belongs to Area1 or Area2. my initial idea was to divide polygons into triangles using consecutive points and then use a known algorithm to determine if a point belongs to one of these triangles, however there is a problem shown in the picture. p4 p5 p6 are points in Region 1, but they make a triangle in Region 2.

+3


source to share


3 answers


Continue inifite ray from the red point to any direction. Consider the intesections of such a ray with any polygon. Even counting intersections indicates that the point lies outside the polygon



+4


source


For this you can use the idea of ​​the polygon filling algorithm. If you know the vertices of the polygon, you can trace a horizontal ray through the red point and count the vertices that it crosses. If the count is even, it is outside, otherwise it is inside.



If you imagine that you are exiting the left edge of that ray, the first intersection enters the polygon, the second exits, the third enters again ... and so on. So if the number is odd (1,3,5, ...) you hit the polygon when you hit the point, otherwise you are outside.

+2


source


Here is the idea -

  • Draw a horizontal line to the right of the red dot and extend it to infinity

  • Count how many times the line intersects with the edges of the polygon.

  • The point is inside the polygon if either the number of intersections is odd or the point lies on an edge

See Check if the point is inside or outside the polygon .

0


source






More articles:


All Articles