javascript - 来自多边形的连接顶点，如何获得新的多边形

Question

我有一个多边形，其中一些顶点用线连接(起点和终点是多边形的一个顶点)。每条线(连接顶点)有 4 条规则:

• 该线不与其他线相交
• 直线不与多边形相交
• 该线完全包含在多边形中
• 这条线不是多边形的边

例子: 图中红线是坏线，黑线是多边形的边，绿线是好的线。

• h 行很好
• 线 i 不好，因为它与多边形相交
• 行 j 是错误的，因为它与行 h 和 i 相交
• k 线不好，因为它是多边形的一条边
• g 线不好，因为它不包含在多边形中

我有一个包含多边形顶点的数组和一个包含线的数组，如下所示:

polygon = [
  {x: ..., y: ...},
  ...
]
lines = [
  {
    p1: {x: ..., y: ...},
    p2: {x: ..., y: ...}
  },
  ...
]

lines 数组只包含有效的行。

如何获得被线切割的多边形。

我想要这样的东西:

function getSlicedPolygons(polygon, lines){
  // No check for valid lines, they are already valid
  // Do the algorithm...
}

---

到目前为止我尝试了什么

我从第一个顶点开始，然后继续前进，直到到达连接的顶点。从那个顶点，我转到在线另一端连接的顶点。现在我继续下一步，直到另一个连接的顶点，依此类推，直到到达我开始的顶点。现在我有了第一个多边形。我找不到其他人...

代码(实现，不是真正的代码):

function getSlicedPolygons(polygon, line){
    var results = []
    var ofl = 0; // Overflow counter, to prevent infinite looping
    while(lines.length > 0){
        // Iterate through polygon
        var i = 0;
        var r = []; // Array of new indices
        var iterations = 0; // An overflow counter again
        while(i < polygon.length){
            r.push[i]
            // findNextConnectionIndex(...) searches for a line
            // that connects with this vertex and returns the index of
            // the other connected vertex
            var n = findNextConnectionIndex(i, polygon, lines) || i+1
            i=n;
            // Don't loop infinite
            iterations++;
            if(iterations > 10) break;
        }
        var result = [];
        for(var z = 0; z<r.length; z++){
            result.push(polygon[r[z]])
        }
        results.push(result)
        // Now I should do something to get another polygon next 
        // time ...
        // Don't loop infinite
        ofl++;
        if(ofl >= 10) break;
    }
    return results;
}

它在一个数组中返回同一个多边形 10 次...

Answer 1

将多边形及其相交线视为带环的无向图，并对其应用环检测算法。由于我们知道连接线，事情变得更简单了，我们实际上可以在 O(V) 中解决问题。

这将是一个足以解释基本原理的模型。我们可以将我们的多边形转换为一个由线列表切片的矩形。由于没有线可能相交，这也将适用于生成的矩形。现在可以从图的一个 Angular 开始，沿着两条边行进，直到在两条路径上都到达 3 度的顶点。因此，我们找到了第一个由原始多边形切片得到的多边形。从上一步到达的两个点继续，直到再次到达 3 度的顶点。当两条路径相遇并且您已列出所有可能的多边形时终止此步骤。

该流程单步运行示意图:

寻找“Angular ”顶点

从图形/多边形中的任意点开始，沿多边形沿任意方向遍历顶点，直到到达 3 度的顶点。存储对应的切片线，沿着多边形继续前进，直到到达3度的顶点。如果是相同的切片线，则您找到了一个“Angular ”顶点，否则存储新的切片线并重复。

编辑

Python 中的工作实现:

def slice_polygon(poly, part):
    # find the "corner point"
    last_slice = None
    last_pt = None

    for pt in poly:
        s = [x for x in part if pt in x]

        if s:
            if last_slice in s:
                break

            last_slice = s[0]

        last_pt = pt

    # find slicing starting from border-point
    a = poly.index(last_pt)
    b = (a + 1) % len(poly) # current positions on the polygon
    sliced_poly = []    # current polygon
    slicing = []    # list of all polygons that are created by the slicing
    while a != b:
        if not [x for x in part if poly[a] in x]:
            # point doesn't lie on slicing-line => add to current polygon
            sliced_poly.insert(0, poly[a])             # prepend point
            a = (a - 1 + len(poly)) % len(poly)  # advance a by one
        elif not [x for x in part if poly[b] in x]:
            # point doesn't lie on slicing-line => add to current polygon
            sliced_poly.append(poly[b])                # append point
            b = (b + 1 + len(poly)) % len(poly)  # advance by one
        else:
            # append points of slicing line
            sliced_poly.insert(0, poly[a])
            sliced_poly.append(poly[b])

            # store created polygon and start over
            slicing.append(sliced_poly)
            sliced_poly = []

            # remove partitioning-line at which the algorithm stopped
            part.remove([x for x in part if poly[a] in x and poly[b] in x][0])

    # add last point to the current polygon, as it's not yet added to it
    sliced_poly.append(poly[a])
    # add last polygon to result-set
    slicing.append(sliced_poly)

    return slicing


# test
polygon = [(150, 110), (270, 40), (425, 90), (560, 150), (465, 290), (250, 290), (90, 220)]
partition = [((270, 40), (250, 290)), ((425, 90), (250, 290))]
print(slice_polygon(polygon, partition))

输出:

[[(425, 90), (560, 150), (465, 290), (250, 290)], [(270, 40), (425, 90), (250, 290)], [(90, 220), (150, 110), (270, 40), (250, 290)]]

输入:

由于总共有两个“Angular 点”(至少)，如果我们遍历多边形一次，我们保证至少找到一个。