-4

Consider a polygon with two loops i.e. Outer loop& inner loop as shown in the images attached with this question(One can think of an English letter "e" for example). Can someone please explain how exactly the Ray-casting algorithm will work in such cases.? If possible, please put some images/drawings in answer, for better visualization and understanding.

Example enter image description here

enter image description here

Shreekant
  • 297
  • 2
  • 3
  • 10
  • 1
    see [hit test](https://stackoverflow.com/a/24465094/2521214) It does not matter if you got holes or not the LSB of count of the intersections will tell yo if you are inside or outside polygon. The only problem is if your ray is touching an edge in single point instead of going through. You need to detect such things and either do not count them or count them twice ... or change ray direction so it does not happen at all. – Spektre Oct 27 '17 at 07:48

1 Answers1

1

Imagine a point moving from infinity to the target point along a straight line (will also work with a curve).

The point at infinity is outside the shape. Whenever an outline is met, you switch from outside to inside or conversely. This rule defines internal and external points. In the given case, the inside of the rounded rectangle, inner circles excluded.

enter image description here

Algorithmically, you count the intersections of the segments that define the shape with the half-line to the target.

  • I read in some articles and also personally observed in some cases this approach will fail on polyline with irregular shapes, i.e. if the ray crosses once and then just “touches” one point on the outside, forming something like a “tangent”. Or what if the polyline crosses itself and the ray crosses exactly through such a crossing point. Or if the ray crosses a section of a polyline where two lines of the this same polyline are drawn exactly on top of each other. In these 3 examples above logic returns the wrong result. – Shreekant Nov 01 '17 at 12:14
  • Can someone suggest a solution for cases mentioned in my above comment. If in case Ray-casting algorithm can't handle these, please suggest other possible ways to solve the stated issue. – Shreekant Nov 01 '17 at 12:15
  • "returns the wrong result": provided you define what is the expected result in such cases. Note that for practical applications, these points form a zero set measure and struggling to handle them is a little pointless (by the way, the results returned by ray casting are very *coherent*). –  Nov 01 '17 at 12:16
  • Thanks Yves.! PFA image in which 'e' kind of polygon is there. Please have a look at it carefully and help me to get correct result for point-containment check in such type of polygons. – Shreekant Nov 01 '17 at 12:30