computational geometry

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 in 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?

链接地址: http://www.djcxy.com/p/48106.html

上一篇: EJB测试策略？

下一篇: 计算几何