I'm doing path planning, where a vehicle should follow a path through a cluttered environment. My algorithm is really forgiving, such that I only need a boolean answer for the following question: Is this line within a polygon (the polygon is an obstacle). Naturally any intersection of polygon and line is to be avoided. I did my research on the web, but I only find things like those (in tons): wrong cases, valid for points only, more points.
My algorithm generates paths by connecting two points, which in turn are checked to not be inside the polygon upon generation.
Checking pointwise is not precise enought, since I can't risk any collisions. Intersecting lines of the polygon and the line was my first guess, but since each (endless) line intersects another (except for parallel ones) I'd have to check the intersection point to be outside all other edges. This seems very slow to me and the questions is, is there a better way or is this a "good" solution? [Or how do I check finite length line segments against each other?]
After the good comments, it boils down to: I need a fast way to check line segment-segment intersections. (I'm aware of bounding boxes and I will do that first.)
I'm using C++, if that matters.
I'll assume it is 2D.
Outline (quick/dirty solution).
For convex polygon:
For each edge:
2.1 Compute normal pointing outside of it (in 2d it is matter of rotating edge vector by 90 degrees, which is trivial normal = vector2(-edgeVector.y, edgeVector.x)), but your edges should go in uniform order for that to work (clockwise or counterclockwise).
2.2. Using 2d version of plane equation, determine if both start/end points of line segment lie "outside" of edge. Point is "outside" if dotProduct(point - edgeStart, edgeNormal) > 0.
2.3. If BOTH points are outside, terminate loop and report that there is no collision.
2.4. If both points are below plane, move to the next plane/edge.
2.5. Otherwise compute interscection point using interpolation (endPos - startPos)* startDistance/(endDistance- startDistance) where start/end distances are computed as distance = dotProduct(point - edgeStart, edgeNormal)
2.6. Determine if point lies on edge ( 0 <= dotProduct (intersectionPoint - edgeStart, edgeEnd - edgeStart) <= dotProduct(edgeEnd - edgeStart, edgeEnd - edgeStart)). If it lies on edge, collision occurs. Terminate the loop and report collision.
2.7. Upon completing the loop, report collision if both start/end points are "below" planes for all edges.
2.8. Report no collision.
For concave polygon.
(optional) You can can compute convex hull and check collision with it first. If convex hull does not collide with line segment, there is no collision.
Pick arbitrary point outside of polygon, and (using 2.3..2.4 steps for edge/edge collision) count how many polygon edges it intersects. If the number is not divisible by 2 ((edgeCount % 2) != 0), return report collision (line segment lies within polygon). Do not omit this step.
Using edge/edge collision (outlined in 2.2..2.3) determine if it intersects any edges. If it does, report collision.
Report no collision.
To optimize collision query on large/complex polygons use space partitioning algorithms (like bsp trees, octtrees) or sweep and prune method.
That's a quick outline of edge/polygon intersection (may have occasional typo).
Faster methods may exist and be available on the web.