algorithm - 从直骨架中提取的最小 Cyle 基

Question

我正在尝试实现一种算法，该算法可找到以下形状给出的外多边形的每个单独边的对应区域。也就是说，1,2 边的相应区域是 [1,6,7,8,2]，2,3 边的区域是 [2,8,3] 等等，CCW 或 CW 在这里不是问题。在这里要详细一点，黑色粗体线是外部多边形，内部蓝色虚线是给定外部多边形的直骨架，我无法控制这里的内部节点编号方案，这意味着从左到右的节点可以是 8,7 ,6 或 6,8,7 或 7,6,8 等..

谷歌搜索几天后，我发现最小循环基础与 Floyd Warshall 算法的组合被命名为这种技术，可用于提取所需的最小循环图，我认为我至少在正确的道路上，拜托确认？

我遵循“Ferreira Manuel J. Fonseca Joaquim A. Jorge 的一组线 Alfredo 的多边形检测”命名法中给出的说明。

下面给出提取最小循环路径的伪代码，

***MINIMUM-CYCLE-BASIS(G)***
1 Γ ← empty set
2 Π ← ALL-PAIRS-SHORTEST-PATHS(G)
3 for each v in VERTICES(G)
4 do for each (x, y) in EDGES(G)
5 do if Π x,v ∩ Π v,y = {v}
6 then C ← Π x,v ∪ Π v,y ∪ (x, y)
7 add C to Γ
8 ORDER-BY-LENGTH(Γ)
9 return SELECT-CYCLES(Γ)

• 在第 2 行 **Π ← ALL-PAIRS-SHORTEST-PATHS(G)** 是 Fl​​oyd Warshall 算法，它将解释具有所有最短路径的 Π。但是有些路径不需要计算，例如我不需要并且在 2,4-7,5-1,7 等顶点之间有任何直接关系？
• 发起者在第 5 行和第 6 行的条件检查意味着什么/strong>，来自给定伪代码片段的 AFAIU，Π 的内容结构必须是二维数组，它保持给定距离的最短距离，例如 Π[2,7] = length_of_vertices(2,7)。那么在Π_x,v中有横坐标和顶点是什么意思，它到底代表什么？

谢谢

Answer 1

我建议采用更简单的方法。从任何外边缘开始，比如 P1->P2。然后检查连接到 P2 的每个节点 PX，并选择角度 (P1,P2,PX) 具有最小正值的节点。该节点 PX 是多边形中的下一个节点。然后继续寻找与PX相连的节点PY，其中角度(P2，PX，PY)具有最小的正值。
有几种可能的方法来计算角度。一个是:

c = inner_product( P1-P2, PX-P2 ) / ( abs(P1-P2) * abs(PX-P2) ) # cosine of the angle
s = cross_product( P1-P2, PX-P2 ) / ( abs(P1-P2) * abs(PX-P2) ) # sine of the angle
angle = atan2( s, c ) # arc tangent with correct sign

与:

def cross_product( a, b ):
    return a.x*b.y - a.y * b.x

def inner_product( a, b ):
    return a.x*b.x + a.y*b.y

注意符号，这取决于 CW 与 CCW。当然，您可以省略规范化项 (abs...)，因为它们相互抵消。
如果允许凹多边形，则必须重新归一化反正切的结果以确保角度始终为正:

def atan2_normalized( y, x ):
    angle = atan2( y, x )
    if angle < 0:
        return angle + 2 * Pi
    else:
        return angle