连接两个盒子之间的连线避免传递其他人

Question

我有几个随机分散的盒子（x，y，宽度，高度），其中一些需要从box1中的点（x1，y1）链接到点（x2， y2）通过画一条线。我试图想出一种方法，通过绘制几条直的相互连接的线来绕过任何一个盒子（如果不可能用一条直线走向），避免通过任何其他盒子（box1和box2除外） ）。问题是我不知道这样的算法（更不用说有一个技术/通用名称）。希望能够以算法或表达的想法的形式提供任何帮助。

感谢

Answer 1

1. 把所有（X，Y）的一组V

2. 添加的起点和终点的箱子的角落 COORDS坐标V 。

3. 创建一组边缘E连接每个不与任何盒子边交叉的角落（盒子中的对角线除外）。

   如何检查，如果线穿过一个侧箱可以用this algorithm

4. 做现在使用您所选择的路径搜索算法，找出图中的路径（V，E）。

   如果您需要一个简单的算法找到最短路径，只需使用BFS即可。

（这将产生沿的一些箱子边走一段路，如果这是不可取的，你可以在步骤1中放点，从实际的角落一段距离三角洲。）

---

如果边缘可能不是对角线：

1. 创建线的大电网，这些箱子之间去。

2. 丢弃穿过盒子边的网格边缘。

3. 使用您选择的路径查找算法在网格中查找路径。

Answer 2

假设线不能是对角线，这是一个简单的方法。它是基于BFS也将找到连接点的最短路线：

只需创建一个图表，包含一个顶点的每个点（x，y）和每个点的边缘：

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

但每个边缘必须存在，只要它不与盒子重叠。

现在只是从点（X1，Y1）到（x2，y2）做一个简单的BFS

这是真的，也容易获得对角线方式相同，但你需要为每个顶点8层的边缘，这是，除了先前的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)) 

但是，每个边缘必须存在，只有当它不与盒子重叠。

编辑

如果可以不考虑空间划分为一个网格，这里的另一种可能性，它不会给你很最短路径，虽然。

创建一个图形，其中每个方框都是一个顶点，并且对于任何其他可以到达而没有线条重叠第三个方框的方框具有边缘。现在使用包含两点的box1和box2之间的dijkstra找到短路径。

现在考虑每个盒子有一个小的计数，不与任何其他盒子重叠。通过这种方式，您可以链接通过dijistra发现的路径中每个框的进入点和退出点，并通过计数。