连接两个盒子之间的线，避免经过其他盒子
我有几个随机散布的盒子（x，y，宽度，高度），其中一些需要通过画线从盒子1中的点（x1，y1）链接到盒子2中的点（x2，y2）。
我试图找到一种方法，通过绘制几条相互连接的直线来绕过任何盒子（如果不可能使用一条直线），从而使这条线避免穿过任何其他盒子（盒子1和盒子2除外） ）。
问题是我不知道此类事情的算法（更不用说为其提供技术/通用名称）。将不胜感激任何算法或表达想法形式的帮助。
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 don'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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
假设线条不能是对角线，这是一种简单的方法。它基于 BFS，并且还会找到连接点的最短线：
只需创建一个图，其中每个点 (x, y) 包含一个顶点，每个点包含边：
但是，只有在不存在的情况下，每条边都必须存在不要重叠盒子。
现在只需从点 (x1,y1) 到 (x2,y2) 执行一个普通的 BFS
就可以很容易地以相同的方式获得对角线，但每个顶点将需要 8 条边，即，除了前面的 4 条边：
尽管如此，只有当每条边不与盒子重叠时才必须存在。
编辑
如果您不能考虑将空间划分为网格，那么还有另一种可能性，但它不会为您提供最短的路径。
创建一个图形，其中每个框都是一个顶点，并且具有到任何其他框的边，无需与第三个框重叠的线即可到达该边。现在使用 dijkstra 找到包含这两个点的 box1 和 box2 之间的最短路径。
现在考虑每个盒子都有一个不与任何其他盒子重叠的小计数。这样您就可以链接通过 dijistra 找到的路径中每个框的进入点和退出点，穿过 countour。
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:
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:
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.
将所有盒子角点的(x,y)坐标放入一组V
将开始和结束坐标添加到 V >.
创建一组边E连接每个不与任何盒子边相交的角（盒子中的对角线除外）。
如何检查一条线是否穿过盒子边可以使用此算法
现在使用您选择的路径查找算法，用于在图中查找路径(V, E)。
如果您需要一个简单的算法来查找最短路径，只需使用 BFS。
（这将产生一条沿着某些盒子侧面的路径。如果这是不可取的，您可以在步骤 1 中将点放置在距实际角一定距离 delta 处。）
如果边缘可能不是对角线：
创建框之间的大网格线。
扔掉穿过盒子侧面的网格边缘。
使用您选择的路径查找算法在网格中查找路径。
Put all (x,y) coords of the corners of the boxes in a set V
Add the start- and end coordinates to V.
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
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:
Create a large grid of lines that goes between the boxes.
Throw away the grid-edges that cross a box-side.
Find a path in the grid using a path-finding algorithm of your choice.