algorithm - 将相邻的梯形合并为一个多边形

Question

给定 2 或 3 个梯形(橙色)。每个梯形至少有一条边与另一个梯形相邻，形成一个简单的多边形。

矩形表示为四个点的列表，从最左上角开始顺时针方向，例如

[
  {x: 0,  y: 0},
  {x: 50, y: 0}, 
  {x: 75, y: 30},
  {x: 60, y: 30}
]

任务是制作一个多边形(绿色)，表示为点列表:

[
  {x: 0,  y: 0},
  {x: 50, y: 0}, 
  {x: 75, y: 30},
  {x: 60, y: 30},
  {x: 60, y: 170}
  …
  {x: 0, y: 0}
]

Answer 1

由于梯形上的所有点都按顺时针顺序排列，因此让我们将这些点视为有向边集或“弧”(连续点之间的箭头，环绕)。

我们要排除的弧就是多边形内部的弧，都是成对出现的。 IE。如果 [a,b,c,d] 是一个梯形，而 [d,c,x,y] 是另一个梯形，那么我的多边形应该是 [a,b,c,x,y,d]，这排除了对弧 (c,d) 和 (d,c)。

您可以在线性时间内找到要排除的弧(通过散列或邻接矩阵)。然后找到你的多边形只是将剩余的弧按顺序拼接在一起的问题。

假设我们正在将点映射到它们的邻居。在我上面的例子中，这看起来像: a->(b), b->(c), c->(d,x), d->(a,c), x->(y), y->(d)

排除一对不良弧线(两个方向上的 c 到 d)后，我们有: a->(b)、b->(c)、c->(x)、d->(a)、x->(y)、y->(d)，根据需要。