Segment Polygon Intersection

Alan Balkany

The above algorithm won't detect the case where the segment is entirely contained in the polygon, without intersecting any edge. Let me know if you need to detect this case too.

hockymot2008_2009

Plz show me if that is the most optimal algorithm ? I really want to know the most optimal algorithm to solve this problem. So, would you mind helping me ?

Alan Balkany

If it isn't optimal it's pretty close. The calculation to determine if two segments intersect isn't time consuming. The only case it doesn't handle, as I've mentioned, is when the segment is entirely contained within the polygon.

modified on Friday, October 17, 2008 9:55 AM

hockymot2008_2009 · modified on Friday, October 17, 2008 9:55 AM

OK. Thanks so much for replying :D

darrellp

Depends on your situation. You should probably do a bounding box check first since it's simple, quick and will eliminate a lot of lines. There's an entire book essentially on this subject: http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&s=books&qid=1227945892&sr=1-1[^] Some of the things you need to think about: Are your polygons convex or can they be concave? Are you testing fixed polygons against a series of lines or does the polygon change with each test? Are your lines more likely to miss than not? BSP trees are worth looking into if you really want to squeeze every last drop of performance. They're a bit complex, though and mostly good for lots of lines testing against a single polygon.

Member 4194593 · modified on Friday, October 17, 2008 9:55 AM

Alan, Does it handle the case where the intersection is at the node between two line segments of the polygon? Dave.

Alan Balkany

It does if your algorithm to detect line-segment intersection will detect a segment intersecting the end point of another segment.

Member 4194593

Alan, My question was about the suggested algorithm you gave above and whether it returned an intersection for a crossing at a node. Dave.

Alan Balkany

Yes it does; if you follow the link there's a Java applet that lets you draw two line segments and tells you if they intersect. You can draw two segments that intersect at an end, and it does detect the intersection.

Member 4194593

Alan, Thank you for the answer. I did start to try the link. First it wanted to install a plugin in FF, OK, I'll go with that. That failed, and the next thing it wanted to do was install a Sun DLL. I decided to quit at that point because the next thing it would want to do would be enable Java Script which I have disabled. I'm happy that that solution will work if I ever need it. Dave.