检查2D平面上两点之间的连接

Question

所以,

问题

我有一个关于确定两个点是否连接在2D平面上的算法的问题.我有:

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

现在,所有线L都在平面上绘制.然后,S和E也拉,我需要回答的问题- 可以从S为达到ê不以L任何线的交叉？而且,更具体一点 - 哪种算法最优？通过"可达到"我的意思是,有在飞机上的方式从S以E没有任何交集的线L-和,事业,这种方法可以是任何东西,而不仅仅是行.

样品

-as你看,在样品S和E未连接.同样在样本中存在一条线完全属于另一条线(灰线和紫线)的情况 - 以及一条线在另一条线(绿线和玫瑰线)上具有开始/结束的情况.

我的方法

目前,我有非确定性多项式(NP)算法来做到这一点.它的步骤是:

• 查找每对线的所有交叉点.
• 从第一步的点创建新的一组线.如果两条线有一个交叉点,则每条新线的起点将有4条新线与交叉点 - 如果第一条线在第二条线上有它的开始/结束,它可以是3条新线 - 或者它可以是2条新线如果第一行的开头/结尾与第二行的开头/结尾完全匹配.即:

因此,第一种情况将导致4条新线,3条新线中的2-4例和2条新线中的5例.(线是[A, B]和[C, D])

• 接下来,在第2步的第一步中,我搜索所有多边形.多边形是一个闭合线集(即它保持封闭的部分区域)
• 我正在确定S包含这些多边形的子集S.要做到这一点,我正在使用简单的算法 - 计算多边形边缘的交点数和从S外到平面的一些线(如果它是奇数,那么S在多边形内,如果它是偶数 - 那么在外面).这是一种光线投射算法.然后我这样做E
• 现在,当我为两者设置多边形时S,E我只是比较两组.如果他们是平等的,那么E就可以S从而无法达到 - 否则.

为什么这是NP？

答案很简单:在第3步,我正在2D图中搜索所有循环.由于在NP中找到最大/最小循环长度的问题,因此我也是(因为我可以简单地通过排序结果循环设置获得最大/最小循环长度).关于此的良好信息位于此处.

这个问题

由于我目前的解决方案是NP,我想知道 - 可能我的解决方案是一个矫枉过正？也许有更简单的解决方案会导致多项式时间？

Answer 1

基本上问题归结为:
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)具有最小CrossProductValue的A中的边是相邻多边形中的下一个边.具有最大CrossProductValue的A中的边是另一个多边形中的下一个边.

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

所以用它来找到你的多边形.查看交叉产品和正弦曲线之间的关系,以了解其工作原理.

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

既然你拥有了所有的多边形,那么要做的就是检查是否有一个S在里面而E在外面,或者反过来.

执行此操作的简单方法是从S到E绘制一条直线.如果它与任何多边形(从上面循环)相交偶数次,则它们都在多边形内部或两者之外,因此请继续检查.

如果该线与一个循环相交一个奇数次,那么一个在多边形内,一个在外面,所以你可以说没有路径.

Answer 2

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

您将遇到的主要困难是处理拐角情况,因此您不能在段的另一侧(共享段,端点作为交叉点等)的某个不正确的交叉点"泄漏".处理这种转角情况在算法上并不困难,但需要耐心.

编辑:

所以让我更正式:构建一个图表G(Ver, Edg),其中Ver包含所有段的端点,S以及E; 并Edg包含所有直接可见的顶点对(包括在段后面).