-2

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.

Community
  • 1
  • 1
mike
  • 791
  • 11
  • 26
  • That sounds like a trivial line-line intersection. –  May 09 '15 at 07:44
  • Use a library that takes care of it for you. One such library is the Boost Geometry library: http://www.boost.org/doc/libs/1_58_0/libs/geometry/doc/html/index.html – Steve May 09 '15 at 08:04
  • If I intersect lines, I'd need to check for each bounding line, that the intersection is lower/higher than another bounding line,.. 2 concerns: I don't know how this is done properly 2nd: is this any fast? A library is not an option since I'm really programming in Matlab and using mex functions, which need to be as plain as possible. Also this should be real-time usable speed on a flying cpu (slow). – mike May 09 '15 at 08:40
  • As you traverse the polygon, if a point on the line is inside the polygon the direction to that point will go through a full circle. But if the line point is outside, the polygon traversal will not go around the point. – Cheers and hth. - Alf May 09 '15 at 09:15
  • This would only be useful to check pointwise, I think? However pointwise checking would be slow and inaccurate. – mike May 09 '15 at 09:25

1 Answers1

0

I'll assume it is 2D.

Outline (quick/dirty solution).

  1. Compute axis aligned bounding box for line and polygon. If those boxes do not intersect, line is not within polygon.

For convex polygon:

  1. 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.

  1. (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.

  2. 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.

  3. Using edge/edge collision (outlined in 2.2..2.3) determine if it intersects any edges. If it does, report collision.

  4. 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.

SigTerm
  • 26,089
  • 6
  • 66
  • 115
  • Thanks for the detailed answer. I guess an extension to 3D can be done by using the 3D the dot-product. I'll look it up. Thanks! – mike May 09 '15 at 18:15
  • @mike: If you only needed ray/triangle intersection (as for picking triangles with ray) in 3D space, then there's "Fast Minimum Storage Ray/Triangle Intersection by Moller" algorithm. Ray vs Triangle. If you extend what I wrote to 3d space, you'll get generic MESH vs ray collision routine. I had impression you're doing 2d pathfinding or something like that. For arbitrary polygon (non-convex flat shape with N vertices, where N > 3) in 3d you'll need first to determine if ray intersects shape's plane, and then it'll become 2D problem I outlined. There's more than one way to do it, though. – SigTerm May 09 '15 at 19:22
  • As stated, the algorithm is used to find paths for cars and helicopters, so 3D is needed aswell. You gave me a first impression, of what this could look like and how to search properly so thanks! – mike May 09 '15 at 19:30
  • 3D fast version can be found [here](http://stackoverflow.com/questions/3106666/intersection-of-line-segment-with-axis-aligned-box-in-c-sharp#3115514). – mike May 11 '15 at 07:50