0 
point a  = [1,0]   
point b  = [3,0]
point c  = [3,3]
point b' = [3,0]

连接这些点将给出线路径 a->b->c<-b' b 到 c 和返回 b` 到 c 之间有重叠。我想找到所有重叠的路径。

我要解决的问题是识别这些重叠线并将它们绘制为曲线，以便用户可以区分它们。

情况1

a = [1,0]
b = [5, 0]
c = [3, 0]

有重叠，但用户可以清楚地看到重叠，所以我忽略了这个重叠。

案例2

a = [3,0]
b = [5, 0]
c = [1, 0]

在这里，如果我画直线 ab 路径将被隐藏。所以在这种情况下画一条曲线。

在此处输入图像描述 我通过考虑每个 N^2 行组合并比较它们的开始和结束 lat long 来实现代码。

line AB = [ [1,0], [3,0]]
line BC = [ [3,0], [3,3]]
(AB == BC || AB == flip(BC))

下面是代码链接

http://jsbin.com/qibarevodi/edit?js,console

http://bl.ocks.org/d/d21a0d3e6df2cd4bb08fbe2a6e66ceb8

是否有更有效的方法来查找重叠线。

4

2 回答 2

0

让我们从您的示例中假设您只需要消除一条折线的视觉歧义：一组由线段连接的点。处理多个并不困难，但我不会讨论它。

你真的有两个不同的问题。

  1. 识别位于同一无限线上的线段集。
  2. 对于每条带有线段的无限线，确定那些需要表示为曲线的线，以消除点的遍历顺序的歧义。

第 1 部分很简单。以规范形式表示每个线段所在的无限线。然后构建一个从规范形式到位于其上的线段列表（按折线顺序稍后）的映射。任意无限线的一个有用的规范形式是一个单位方向向量d和离原点最近的唯一点p。这些计算起来既简单又快速。对于点a和之间的段b，

d = d' / length(d') where d' = [b.x - a.x, b.y - a.y]
p = d_perp (d_perp dot a) where d_perp = [d.y, -d.x]

处理点几乎在同一条线上但不完全一致的情况是一个很大的附加主题。如果您对解决方案感兴趣，我可以进一步讨论。

对于第 2 部分，我们可以将同一条无限线 L 上的每组线段视为一维问题。看来您是说在跟踪折线时，如果 L 上的任何段覆盖L 上已经被跟踪的顶点，则覆盖段应该是曲线。如果这个定义是准确的，它直接导致简单的算法：

for each line L
  let S be the subset of L already traced
  for each segment a->b lying in L (in polyline order taken from the map above)
    if a in S and b in S, then
      draw a->b with a curve
    else
      draw a->b with a straight segment
      add [a->b) to S

该符号add [a->b) to S表示将线段添加a到b，但不包括点b本身。这考虑到您的情况 1。

上面的伪代码非常抽象。如何表示集合 S？也许最简单的是将点旋转到 x 轴上。这很简单，因为您已经拥有该行的规范形式。获取每个点所需的 xp坐标

x = d dot p

现在您可以将 S 存储为一组 1d x 坐标区间的并集。这可以通过平衡的二叉树轻松完成，其中键是不同的间隔。（您不需要像区间树那样复杂的东西，因为您存储的是联合，而不是重叠区间。）

让我知道您是否在制定详细信息时遇到问题。这是一个不错的小问题。例如，有一些边缘情况需要考虑。如果同一段在同一折线内重复怎么办？您没有提供有关该问题的足够信息来确定是否会发生这种情况。

于 2018-01-07T04:36:10.637 回答
0

这就是我要做的。我将重点简化您的问题，即如果每条线与任何其他线重叠，我会将其标记为“要弯曲”-重叠是不好的。我不会做出你所做的区分，因为它们是额外的而不是简化的。然后，您的问题基本上采用以下形式：

给定平面中的一组线段，找到与其他线段重叠的线段

如果您仍然想区分您制作的案例，您将不得不考虑它们是订购的并做一些额外的检查。您可以为它们的方向使用额外的二进制坐标。

第一个问题是，我们如何存储线段？您似乎将它们指定为两个点 (x1,y1) 和 (x2,y2)，这就是您进行 N^2 比较的原因。我建议您将它们作为起点和终点的线来威胁。这意味着，我们将使用它们的斜率 m、y 轴截距 y 以及 x1、x2 作为坐标，找到 y 和 m 应该不难。不幸的是，这不适用于 y 轴本身。如果您不能确定在 y 轴上有段，您可能需要修改此方法或为这种特定情况考虑一些替代方法。也许给这些一个特殊的键并保留 (y1,y2) 值。

我现在的建议是将您的行存储在带有键 (m,y) 和列表内容 [(x1,x2),(x1',x2'),...] 的哈希表中（可能类似于 pythons 字典） . 这允许您对每个段仅检查位于同一延长线上的段。然后，您可以遍历所有行并标记与另一个相同键重叠的行。不要忘记使用快速重叠测试来执行此操作。

如果您想进一步提高效率，您可能需要查看区间树。我自己对它们不太熟悉，但理论上你可以使用这个数据结构，或者它的一些修改，为你在列表中的间隔为一个给定的键优化查找重叠的。如果您在一个特定的行上有许多步骤，这将很重要。只要一条线与这棵树中的另一条线重叠，您就可以将其标记为弯曲。

您的算法可能类似于：

  • 将线段投影到斜率和 y 相交上（即制作哈希表）
  • 遍历哈希键
  • 对于列表中的每个元素，检查它是否与另一个元素重叠（这是区间树可以帮助您进一步加快速度的地方。这也是您的案例区分可能出现的地方）
  • 如果支票为正，则将该线标记为“要弯曲”

解决一些评论：仅使用 x 轴的角度无济于事。此外，记住您来自的方向也无济于事，如下例所示。

图表

请注意，您测试的具体内容取决于您想要的结果。您可以测试重叠，或者您可以测试一个区间是否完全包含在另一个区间中。阅读一下图形库及其可视化可能也是值得的，因为您的问题本质上描述了具有固定节点位置的有向图。希望其中的一些对您有所帮助。

于 2018-01-07T02:31:09.620 回答