python - Matplotlib の fill 関数のポイントを注文するには?

Question

多角形は 2 つのリストで表されます。リストxsには x 座標が降順で含まれます。各 x 値について、list 内の対応する要素regionsはスライスのリストです。各スライスは、ポリゴンの内部に属する範囲を示します。x 値ごとに、スライスは昇順で並べ替えられます。

fillMatplotlib の関数を使用して、塗りつぶされたポリゴンを描画したいと考えています。この関数では、ポイントからポイントへの移動がポリゴンの輪郭を表すように、ポイントを順序付けする必要があります。データ セット内のポイントを並べ替えて正しいポリゴンを取得するにはどうすればよいですか?

これは私が持っているデータの種類の例です。

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]

私が探している解決策は、各エッジの勾配の絶対値を最小化するものです (垂直セグメントは別として)。上記の例では、これは最初のソリューションに対応します。

Answer 1

これが仕事をする関数です。これは、見つかったすべてのポリゴンを生成するジェネレータです (複数の接続されたポリゴンがある場合)。

まず、領域をタプルとして書き換える必要があります。

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]