Please help with this algorithm. It is necessary that it works not only with convex ones. If you can sample code or pseudocode.

  • 2
    Checking belonging to the 2nd triangles?) - Sh4dow
  • But really .. :) I will try ... - ilayer
  • I still advise you to use the option from the answer) In oem, to determine the angle, look for any cosines for every 3 points. - Sh4dow
  • Just option with triangles easier to implement. A point check on a triangle is a calculation of 2 vector products and a comparison of their Z coordinates by a sign (since the triangles lie in a plane): blackpawn.com/texts/pointinpoly/default.html - AlexeyM
  • There is something fresher: the same for the polygon - Yuri Negometyanov

1 answer 1

We draw a ray from the checked point to any infinitely remote.

For each edge, we check if the given edge intersects this ray.

If the number of edges that the ray intersects is even, then the point is outside the polygon.

If odd, then inside.

The only thing is that if this beam passes through the intersection of neighboring edges, then it is impossible to determine or try to do it with a tambourine ... For sure there is a way out of this situation.

PS @ Sh4dow your proposal will work, only for a convex polygon. If I misunderstand, please explain :)

UPD: here is the implementation of hardfire.far.ru

  • Enter the points clockwise. In a nonconvex 4-gon, one of the four angles will be negative or more than 180 (depending on how you count). If there is one, we take this point as the first, if not, then any. We build 2 triangles: (1, 2, 3) and (1, 3, 4). If the point belongs to any of them, it belongs to the 4-gon. Although your option is most likely easier in terms of memory consumption and load. - Sh4dow
  • 2
    Something like this: .4 .1 (angle> 180) .3 * our point .2 - Sh4dow
  • @ilayer, for the @BogolyubskiyAlexey variant, you need one formula - the intersection of two segments) for example , on dolphies. any point — yes, take { 10000, 10000 } . Count the number of intersections of the sides of the polygon and the segment (the desired point, any point). Parity to determine it should not be difficult)) - Sh4dow
  • Well, thank you, at first I was confused about the beam a bit, it did not fit in my head)) - ilayer
  • By the way, that nifiga implementation does not work correctly ... If we assume that there are four polygons and each one of the points has the same coordinates, then checking this point to each polygon will show that it belongs to only one polygon)) The ambush is shorter .. example - i074.radikal.ru/1112/b2/2118c7ac645e.png - ilayer