connect line between two boxes avoiding passing others

I have several boxes (x,y,width,height) randomly scattered around, and some of them need to be linked from point (x1,y1) in box1 to point (x2,y2) in box2 by drawing a line. I am trying to figure a way to make such line avoid passing through any other boxes (other than box1 and box2) by drawing several straight interconnected lines to go around any box in the way (if it is not possible to go with one straight line). The problem is that I do开发者_Python百科n't know an algorithm for such thing (let alone having a technical/common name for it). Would appreciate any help in the form of algorithm or expressed ideas.

Thanks

Assuming that the lines can't be diagonal, here's one simple way. It's based on BFS and will also find the shortest line connecting the points:

Just create a graph, containing one vertex for each point (x, y) and for each point the edges:

((x,y),(x+1,y))    ((x,y),(x-1,y))     ((x,y),(x,y+1))     ((x,y),(x,y-1))

But each of this edges must be present only if it doesn't overlap a box.

Now just do a plain BFS from point (x1,y1) to (x2,y2)

It's really easy to obtain also diagonal lines the same way but you will need 8 edges for each vertex, that are, in addition to the previouses 4:

((x,y),(x-1,y+1))    ((x,y),(x-1,y-1))     ((x,y),(x+1,y-1))     ((x,y),(x+1,y+1))

Still, each edge must be present only if it doesn't overlap a box.

EDIT

If you can't consider space divided into a grid, here's another possibility, it won't give you the very shortest path, though.

Create a graph, in which each box is a vertex and has an edge to any other box that can be reached without the line to overlap a third box. Now find the shortet path using dijkstra between box1 and box2 containing the two points.

Now consider each box to have a small countour that doesn't overlap any other box. This way you can link the entering and the exiting point of each box in the path found through dijistra, passing through the countour.

1. Put all (x,y) coords of the corners of the boxes in a set V

2. Add the start- and end coordinates to V.

3. Create a set of edges E connecting each corner that does not cross any box-side (except for the diagonals in the boxes).

   How to check if a line crosses a box side can be done with this algorithm

4. Now use a path-finding algorithm of your choice, to find a path in the graph (V, E).

   If you need a simple algorithm that finds the shortest path, just go with a BFS.

(This will produce a path that goes along the sides of some boxes. If this is undesirable, you could in step 1 put the points at some distance delta from the actual corners.)

If the edges may not be diagonal:

1. Create a large grid of lines that goes between the boxes.

2. Throw away the grid-edges that cross a box-side.

3. Find a path in the grid using a path-finding algorithm of your choice.