Menu
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.
409
A segment crosses a polygon if it cuts or is inside that polygon. A segment cuts a polygon if it has at least one intersection that is not the end point of the segment. A segment is inside a polygon if every point of the segment is inside the polygon (end points of the segment can lay on the boundary of the polygon).
Polygons are two-dimensional shapes consisting of a cycle of line segments. The segments are edges which meet in pairs at corners called vertices.
We can determine a region in which the points for each polygon lie, and this line is a separating axis if these regions do not overlap. If, after checking each line from both polygons, no separating axis was found, it has been proven that the polygons intersect and something has to be done about it.
Define b = q1 - p1 and x = (s,t). If the solution of the linear system A*x = b is in the unit square, then the segments intersect. If the solution is not in the unit square, the segments do not intersect.
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.
155
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
