segment-polygon intersection

Greetings,

I would like to detect if a segment only 'touches' a polygon or cross it.

The Figure

explains my doubt. How to know the difference between cases A and B? Note that in both situations the red line crosses the polygons i开发者_运维百科n two vertices, one touching by outside and other crossing by inside. I have a segment-segment intersection algorithm, but I don't know how to use it properly. Any help is appreciated.

---

I think there might not be any approach much easier than computing the details at a low level. First, you will need robust code to compute the intersection between two segments. This is discussed (with code) here. Once you have the intersection points, you need to compute how the polygon boundary interacts with your segment in the neighborhoods of those intersection points. This is essentially repeated LeftOf( ) computations, using the notation in my book. In your image, the segment passes through vertex b, while the adjacent vertices a and c (in a consecutive sequence (a,b,c)) are both to the same side of b. Therefore, the segment does not penetrate to the interior of the polygon in the neighborhood of b. But if a and c were on opposite sides of the segment, then it must penetrate.

---

Generalizing, an intersection may comprise many points. For example, see http://cagd.cs.byu.edu/~557/text/ch7.pdf which discusses how planar curves intersect, and says tangent curves intersect at two points "properly counted", which is counter-intuitive. In the case of a convex polygon with a grazing line, does the intersection have two points "properly counted?" In your case, are there two intersections with two points each?

So Prof. O'Rourke gives an algorithm for computing the number of points in the intersection, so to speak. Pragmatically, should a package for computing intersections return the count of points in each intersection?