Shortest path between points, avoiding line segments

Artificial Intelligence Programming

Started by DauntlessCrowd November 13, 2008 10:00 AM

13 comments, last by ToohrVyk 15 years, 5 months ago

2,152

November 14, 2008 04:11 AM

Quote:Original post by DauntlessCrowd
The endpoints will not collide (no polygons are formed) but they can intersect. Why would a vertex from crossing segments be added twice? I can see how this would be the case if they have the same endpoint, but not when they simply cross ?

Draw the following situation:
A=(0,0)
B=(10,0)
Line L1=x_1->y_1=(0,5)->(5,-5)
Line L2=x_2->y_2=(0,-5)->(5,5)

Now, when trying to find the neighbors of A to start with, you get that both L1 and L2 intersect A->B, i.e. L := {L1, L2}. Then you pick all their endpoints for further processing, V:= {x_1, x_2, y_1, y_2}. Now A->x_1 and A->x_2 are unobstructed, and are added to F, like they are supposed to. But then, you find that L1 intersects A->y_2 and L2 intersects A->y_1, so if you don't keep any track of these additions, you'll add L1 and L2 again to L, and add the same endpoints to V again, and will end up looping forever. To break this loop, don't add to V any endpoints that have been added to it in an earlier iteration, so you'll end up discarding y_1 and y_2 from being visible from A.

Quote:
Also: "L:= the set of segments that intersect C->". Is this done by brute-forcing?

If you've got lots of lines (>50), I think you might fare better by constructing a quadtree or a 2D kD-tree to accelerate the intersection tests.
Also you might try a structure where you store the lines sorted by increasing x or y-coordinates to be quickly able to cull out lines that possibly can't intersect.
Even if doing brute-forcing, you can exploit the observation you said that after passing line i, lines 0->i-1 don't need to be considered.
It's hard to tell which of these would be the fastest in practice.

DauntlessCrowd

122

Author

November 14, 2008 04:19 AM

Thanks Clb, it's all clear to me now ! :)

ToohrVyk

1,596

November 14, 2008 06:26 AM

There are several optimizations you can apply due to the nature of the problem.

A* sorts the nodes by h + g where g(X) is the shortest path from the start to X, and h(X) is the shortest possible distance from X to the end. This means that if g(Z) + h(X) > g(Y) + h(Y), you don't need to even consider X as a destination from Z until you're done with Y. And since h(X) is a constant (it's the straight-line distance from X to the end) you can sort your points by increasing h(X) and stop every expansion when you reach an h(X) that's greater than your current g(Y) + h(Y) - g(Z). Of course, you have to remember that you were computing the nodes outgoing from g(Z), and resume that computation when either Y or g(Y) changes.

The result of this is that you greatly reduce the number of useless outgoing edges from every explored node: you don't even have to think about testing if these edges intersect segments, because these edges cannot possibly be part of the shortest path even if they exist.

Another optimization is that you don't need to test for intersection until you actually explore a node. That is, for every node, you would store in the priority queue both that node (and its distance) and the edge that goes to that node. If that edge ever appears as the "next edge", you test if it is actually passable, and eliminate it if it intersects segments.

This greatly reduces the number of useless edge intersection tests: you don't really care whether an edge exists or not, until you actually need to pass through it, and you only need to pass through a small number of edges on a typical A* search.

Blog — Facebook

ghost0

122

November 26, 2008 05:20 AM

I have a similar problem except I deal with a circle entity and line intersections or lines sharing the same point. How would I go about this?