28

所以，

问题

我有一个关于确定两个点是否在二维平面上连接的算法的问题。我有：

  • 二维线阵列。每条线都受其起点终点二维点的限制。每个点都是两个元素的简单数组[x,y]- 即每条线看起来像['start'=>[X0, Y0], 'end'=>[X1, Y1]]让这条线集被命名为L。线可以属于另一条线（即一条线可以是另一条线的一部分），它们只能与一个点相交，等等 - 即它们在 2D 平面上没有限制。但是线不能是一个点——即线的起点不能等于线的终点。
  • 两点S和E，即数组[Xs, Ys]和[Xe, Ye]

现在，所有的线L都画在平面上。然后，S并且E也被绘制了，我需要回答这个问题 -可以从 S 到达 E 而不与 L 中的任何线相交吗？而且，更具体地说——哪种算法是最优的？通过“可以到达”，我的意思是飞机上有一条从S到E没有交叉线的路L- 而且，当然，这条路可以是任何东西，而不仅仅是线。

样本

在此处输入图像描述

- 如您所见，在示例中S并且E未连接。同样在示例中，存在一条线完全属于另一条线（灰色和紫色线）的情况 - 以及一条线在另一条线上有开始/结束的情况（绿色和玫瑰线）。

我的方法

目前，我有非确定性多项式（NP）算法来做到这一点。它的步骤是：

  • 查找每对线的所有交点。
  • 从第一步的点创建新的线集。如果两条线有一个交点，则在每条新线的开头将有 4 条新线与交点 - 或者如果第一条线的开始/结束在第二条线上，则它可以是 3 条新线 - 或者它可以是 2 条新线如果第一行的开始/结束与第二行的开始/结束完全匹配，则行。IE：

两条线路的五种一般情况

所以 1-st case 将产生 4 个新行，2-4 个 case 产生 3 个新行，5 个 case 产生 2 个新行。（线是[A, B]和[C, D]）

  • 接下来，从第二步开始，我正在搜索所有多边形。多边形是一个封闭的线集（即它包含区域的封闭部分）
  • 我正在确定S包含S. 为此，我使用简单的算法 - 计算与多边形边缘的交叉点数以及从S外平面到外平面的一些线（如果它是奇数，则S在多边形内部，如果它是偶数 - 然后在外部）。这是一种光线投射算法。然后我这样做是为了E
  • 现在，当我为两者设置多边形时S，E我只是比较两组。如果它们相等，则E可以到达S并且不能到达 - 否则。

为什么是这个NP？

答案很简单：在第三步，我正在搜索 2D 图中的所有循环。由于如果 NP 存在寻找最大/最小循环长度的问题，那么我的也是（因为我可以简单地通过对结果循环集进行排序来获得最大/最小循环长度）。关于此的良好信息位于此处。

问题

由于我目前的解决方案是 NP，我想知道 - 可能我的问题解决方案是矫枉过正？即可能有更简单的解决方案会导致多项式时间？

4

5 回答 5

9

基本上问题归结为：
1) 确定包含一些空间的所有多边形，这些空间不包含任何其他多边形。在您上面的示例中，您有 3 个不包含任何其他形状/循环/多边形：包含 S 的四边形、包含 E 的四边形以及其中 2 个下方的三角形。
2) 确定 S 和 E 是否在任何这些多边形的相反内部/外部。

对于第 1 部分，您必须构建一个图表：

创建给定线的交点数组，这是 N^2。记住每个交点来自哪两条线。这些交点是图形的顶点。

如果两个顶点来自同一条线并且它们之间没有其他交点，则它们是“连接的”。显然，不要依赖浮点的准确性来确定这一点。

现在您希望在布局中找到多边形。图通常可以包含指数数量的循环。但是，每条边可能只与 2 个“内部”多边形接壤，因此我们只对循环的多项式子集感兴趣。所以选择一条边，然后在多边形中找到下一条边，并不断重复，直到你回到你开始的地方或确定第一条边不是多边形的一部分。

因此，假设您来自边 E = (U, V)，并且想要在多边形中找到下一条边（共享相同的顶点 V）。
1) 创建一个向量 T 作为 U - V。
2) 创建与顶点 V 相邻的边 A 的集合。从该集合中删除 E。
3) 如果集合为空，则边不是多边形的一部分。
4）对于A中的每条边（Q，V），构造一个向量R作为Q - V。（记住Q和V代表2D平面中的点）。
5) 归一化 R：除以它的长度以创建长度为 1 的向量。
6) 确定 CrossProductValue(T, R)。
7) A 中具有最小 CrossProductValue 的边是相邻多边形中的下一条边。A 中具有最大 CrossProductValue 的边是另一个多边形中的下一条边。

CrossProductChecker(2D T, 2D R) {
  return (T.x*R.y - T.y*R.x); // cross product for 2 dimensions
}

所以用它来找到你的多边形。查找叉积和正弦曲线之间的关系以了解其工作原理。

=============

现在你已经有了所有的多边形，所有要做的就是检查是否有一个 S 在里面，E 在外面，或者相反。

做到这一点的简单方法是从 S 到 E 画一条线。如果它与任何多边形（从上方循环）相交偶数次，它们都在多边形内部或都在多边形外部，因此请继续检查。

如果这条线与一个环相交奇数次，则一个在多边形内部，一个在多边形外部，因此可以说没有路径。

于 2013-09-27T11:29:30.377 回答
6

您可以构建一个所谓的“可见性图”，将两个障碍物顶点连接起来（如果它们是直接可见的）。此图中的最短路径（添加了 S 和 E）将是您的配置空间中 S 和 E 之间的最短无障碍路径。关于可见性图的算法和优化是众所周知的并且被广泛描述。

您将遇到的主要困难是处理极端情况，因此您不能在某些不正确的交叉点“泄漏”到线段的另一侧（共享线段、端点作为交叉点等）。处理这种极端情况在算法上并不困难，但需要耐心。

编辑：

所以让我更正式一点：构建一个包含所有段的端点的图G(Ver, Edg)，并且; 并包含所有直接可见的顶点对（包括跟随线段）。VerSEEdg

于 2013-09-27T11:11:04.823 回答
4

该算法有两个步骤。

1. Find out the maximum polyogn encompassing S and E 
    (which could possibly be an open polygon, so convex hull algorithm needs 
    to be modified)
2. E can be reached from S if
    (Case 1) The polygons are the same
    (Case 2) Both are open polygons.

解释：

步骤 1：找到点 P 的最大包围多边形

Form a set of points by adding the end-points and all possible 
    intersections. (O(n^2))
Eliminate points that can only be reached from P by crossing another line. 
    This can be done by finding the intersection of the line joining P to each 
    point with all other lines (O (n^3)).
Form a convex hull of the remaining points. 
    Here it should be noted that the resulting polygon may not be closed. 
    So, the convex hull algorithm needs to be modified to get rid of 
    those possible edges which don't have a direct connection. 
    This can be efficiently done by an appropriate data structure 
    like a graph (O(n^2) in worst case)

第 2 步：比较需要对多边形顶点进行某种排序。这将是最大 O(n long n)

所以得到的算法复杂度将是 O (n^3)

看图

于 2013-09-27T15:18:54.513 回答
2
  1. 找到线段之间的所有交点
  2. 删除所有 rank = 1 的点；即它是一个端点，只有一个线段连接到这个点
  3. 找到最接近点 S 的线段
  4. 使用以下方法查找其一侧是先前找到的线段的多边形：
    1. 给定起始线段
    2. 标记起始段的两端，开始 = lsS，结束 =lsE
    3. 查找连接到 的所有线段lsE，不包括起始线段
    4. 从找到的线段中选择最接近点 S 的线段最近的线是那条线，其中心可以与点 S 连接而不与任何检查线相交
    5. 从问题空间中删除所有其他检查的线段
    6. 重复直到你有完整的多边形
  5. 如果完整的多边形同时包含点 E 和 S，则它们是连通的

这有点类似于深度优先搜索。

我的想法非常糟糕的例证。

在每个步骤中，您只与您成功解决的最后一点的直接邻居一起工作。

于 2013-09-27T12:09:09.247 回答
2

计算由线段形成的平面直线图，并定位 S 和 E 所属的面。当且仅当 S 和 E 属于同一面时，存在一条路径。前两个步骤是来自计算几何的标准多项式时间算法，有许多可用的描述和实现。

于 2013-09-27T17:38:13.770 回答