2

一个多边形由两个列表表示。列表xs包含按降序排列的 x 坐标。对于每个 x 值，列表中的对应元素regions是一个切片列表。每个切片表示属于多边形内部的范围。对于每个 x 值，切片按升序排序。

我想使用 Matplotlib 的fill函数绘制填充的多边形。该函数需要对点进行排序，以便从点到点描述多边形的轮廓。如何对数据集中的点进行排序以获得正确的多边形？

这是我拥有的数据类型的示例。

xs = range(10, 0, -1)
regions = [[slice(0, 3)],
           [slice(0, 4), slice(5.2, 5.8)],
           [slice(1, 5), slice(5.4, 5.8)],
           [slice(1.3, 6)],
           [slice(1.8, 6)],
           [slice(1.9, 3), slice(3.1, 6.1)],
           [slice(2, 2.9), slice(3.2, 5), slice(6, 6.2)],
           [slice(2.1, 2.7), slice(3.4, 5.1), slice(5.9, 6.3)],
           [slice(3.5, 5.2), slice(5.7, 6.4)],
           [slice(3.8, 5.3), slice(5.8, 6.1)]]

正确的点数排序方法如下

xx = [10, 9, 8, 7, 6, 5, 4, 3, 3, 4, 5, 5, 4, 3, 2, 1,
   1, 2, 3, 4, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8,
   9, 9, 8, 8, 9, 10]
yy = [0, 0, 1, 1.3, 1.8, 1.9, 2, 2.1, 2.7, 2.9, 3, 3.1,
      3.2, 3.4, 3.5, 3.8, 5.3, 5.2, 5.1, 5, 6, 5.9, 5.7,
      5.8, 6.1, 6.4, 6.3, 6.2, 6.3, 6, 6, 5.8, 5.8, 5.2,
      5.4, 5, 4, 3]

并且这个数字应该看起来像这样 填充多边形

到目前为止，我已经尝试定义转折点，即轮廓改变方向的 x 值。这可以通过numpy.diff应用于包含每个 x 值的切片数的数组来完成。如果差异不为零，则该 x 值是一个转折点。这可能可以用来找出下一点。困难在于确定下一个切片以及是使用切片的开头还是结尾。

这个问题很相似，但在我的情况下，多边形的形状要复杂得多。另一方面，我确实有关于多边形内部的信息。

编辑

我刚刚意识到，上述问题并不总是有唯一的解决方案。例如，上面示例中的点集也承认解决方案

xx = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 5,
       4, 3, 3, 4, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8,
       9, 9, 8, 8, 9, 10]
yy = [0, 0, 1, 1.3, 1.8, 1.9, 2, 2.1, 3.5, 3.8, 5.3, 5.2,
      2.7, 2.9, 3, 3.1, 3.2, 3.4, 5.1, 5, 6, 5.9, 5.7,
      5.8, 6.1, 6.4, 6.3, 6.2, 6.1, 6, 6, 5.8, 5.8, 5.2,
      5.4, 5, 4, 3]

替代多边形

我正在寻找的解决方案是最小化每个边缘斜率的绝对值（垂直段除外）的解决方案。在上面的示例中，这对应于第一个解决方案。

4

1 回答 1

0

这是完成这项工作的功能。它是一个生成器，可以生成所有找到的多边形（如果有多个连接的多边形）。

首先，必须将区域重写为元组：

regions = [[(sl.start, sl.stop) for sl in sllist] for sllist in regions]

排序是通过调用生成器（在循环中或以其他方式）完成的。该函数产生一个多边形作为 (x, y) 点的列表。获取单独的xx和yy列表很容易：

for polygon in order_points(xs, regions):
    xx, yy = zip(*polygon)

函数本身有详细的注释。

def order_points(x, regions):
    """Given two lists of the same length, one of x values and one of regions,
    determine how to order the points so that they describe a polygon that
    contains the interior of all regions.

    This function is a generator that yields disjoint polygons.

    Parameters
    ==========

    x: list
       x values at which the regions are defined

    regions: list of lists of tuples
       Each list contains information for one x value.  The sublist contains
       so-called regions that are described by tuples corresponding to the
       bottom and the top of the region.  The y values between the bottom and
       the top of each region are in the interior of a polygon.

       Each list of tuples should be sorted by increasing y value.

    Yields
    ======

    polygon: list of tuples
       Ordered list of (x, y) coordinated of the points on the polygon.

    """
    # Make sure the x values are in ascending order.
    xvals, yregions = zip(*sorted(zip(x, regions)))

    # Direction is -1 when going toward low x, 1 when going toward high x.
    direction = 1
    # Indicate whether the inside of the polygon is below, 0, or above, 1, the
    # current point.
    inside = 1

    # List all possible combinations of x index, region index.
    tovisit = [(pos, rpos) for pos in range(len(xvals))
                            for rpos in range(len(yregions[pos]))]
    pos, rpos = tovisit.pop(0)
    ycur = yregions[pos][rpos][0]

    # Keep track of already visited points.
    visited = set()
    # Keep track of current polygon.
    polygon = []
    while True:
        # Keep track of ordered points.
        xcur = xvals[pos]
        polygon.append((xcur, ycur))
        visited.add((xcur, ycur))

        # Find the minimum vertical distance between the current position and
        # the following points: points at the next (as specified by direction)
        # x value, and points at the current x value

        # For points at the next x, if the polygon is currently above, inside =
        # 1, the points considered are at the bottom of a region, i.e., at
        # index 0 of the tuple.
        next_pos = pos + direction
        if next_pos < 0 or next_pos >= len(xvals):
            next_pos = pos
        distance = -1
        for ri, region in enumerate(yregions[pos]):
            if (xcur, region[inside]) not in visited:
                d = abs(ycur - region[inside])
                if d < distance or distance == -1:
                    distance = d
                    move = ('vertical', (pos, ri, inside))

        # For points at the same x, if the polygon is currently above, the
        # points considered are at the top of a region, i.e., at index 1 of the
        # tuple.
        for ri, region in enumerate(yregions[next_pos]):
            polypos = (not inside)
            if (xvals[next_pos], region[polypos]) not in visited:
                d = abs(ycur - region[polypos])
                if d < distance or distance == -1:
                    distance = d
                    move = ('next', (next_pos, ri, polypos))

        # If no suitable next point is found, the polygon is complete. Yield
        # the polygon and try to find a separate polygon.
        if distance < 0:
            yield polygon
            polygon = []
            direction = 10  # dummy value to detect if no next point is found
            while tovisit:
                pos, slpos = tovisit.pop(0)
                ycur = yregions[pos][slpos][0]
                if (xvals[pos], ycur) not in visited:
                    direction = 1
                    inside = 1
                    break
            if direction == 10:
                break
            continue

        # Make the move.
        if move[0] == 'vertical':
            # Vertical move changes the direction (unless it is the very first
            # move) and toggles inside/outside.
            if len(polygon) > 1:
                direction *= -1
            inside = int(not inside)
        pos, rpos, end = move[1]
        ycur = yregions[pos][rpos][end]
于 2013-04-25T02:03:46.717 回答