52

のマニュアルページからXFillPolygon：

  • shapeがComplexの場合、パスは自己交差する可能性があります。パス内の隣接する一致点は、自己交差として扱われないことに注意してください。

  • shapeが凸である場合、ポリゴン内のポイントのすべてのペアについて、それらを結ぶ線分はパスと交差しません。クライアントに認識されている場合は、Convexを指定するとパフォーマンスを向上させることができます。凸状ではないパスに凸状を指定すると、グラフィックスの結果は未定義になります。

  • shapeが非凸の場合、パスは自己交差しませんが、形状は完全に凸ではありません。クライアントに認識されている場合、Complexの代わりにNonconvexを指定すると、パフォーマンスが向上する場合があります。自己交差パスに非凸を指定した場合、グラフィックスの結果は未定義です。

塗りつぶしでパフォーマンスの問題が発生してXFillPolygonいます。マニュアルページに示されているように、最初に実行したいステップは、ポリゴンの正しい形状を指定することです。私は現在、安全のためにComplexを使用しています。

ポリゴン（一連の座標で定義される）が凸型、非凸型、または複雑であるかどうかを判断するための効率的なアルゴリズムはありますか？

4

9 に答える 9

114

ギフトラッピングアルゴリズムよりもはるかに簡単にすることができます...特定の境界のない一連のポイントがあり、凸包を見つける必要がある場合、これは良い答えです。

対照的に、多角形が自己交差しておらず、連続した点が境界を形成するリスト内の一連の点で構成されている場合を考えてみましょう。この場合、多角形が凸であるかどうかを判断するのははるかに簡単です (また、角度を計算する必要もありません)。

ポリゴンのエッジの連続するペア (ポイントの各トリプレット) ごとに、昇順でポイントに向かって指しているエッジによって定義されるベクトルの外積の z コンポーネントを計算します。これらのベクトルの外積をとります。

 given p[k], p[k+1], p[k+2] each with coordinates x, y:
 dx1 = x[k+1]-x[k]
 dy1 = y[k+1]-y[k]
 dx2 = x[k+2]-x[k+1]
 dy2 = y[k+2]-y[k+1]
 zcrossproduct = dx1*dy2 - dy1*dx2

外積の z 成分がすべて正またはすべて負の場合、多角形は凸面です。それ以外の場合、多角形は非凸です。

N 個の点がある場合は、必ず N の外積を計算してください。たとえば、トリプレット (p[N-2],p[N-1],p[0]) と (p[N-1], p[0]、p[1])。

多角形が自己交差している場合、有向角がすべて同じ方向であっても、凸性の技術的定義に失敗します。この場合、上記のアプローチでは正しい結果が得られません。

于 2009-12-10T14:06:43.463 に答える
15

次の Java 関数/メソッドは、この回答で説明されているアルゴリズムの実装です。

public boolean isConvex()
{
    if (_vertices.size() < 4)
        return true;

    boolean sign = false;
    int n = _vertices.size();

    for(int i = 0; i < n; i++)
    {
        double dx1 = _vertices.get((i + 2) % n).X - _vertices.get((i + 1) % n).X;
        double dy1 = _vertices.get((i + 2) % n).Y - _vertices.get((i + 1) % n).Y;
        double dx2 = _vertices.get(i).X - _vertices.get((i + 1) % n).X;
        double dy2 = _vertices.get(i).Y - _vertices.get((i + 1) % n).Y;
        double zcrossproduct = dx1 * dy2 - dy1 * dx2;

        if (i == 0)
            sign = zcrossproduct > 0;
        else if (sign != (zcrossproduct > 0))
            return false;
    }

    return true;
}

このアルゴリズムは、頂点が (時計回りまたは反時計回りのいずれかで) 順序付けられていて、自己交差するエッジがない (単純なポリゴンに対してのみ機能する) 限り、動作することが保証されています。

于 2014-08-14T09:04:24.403 に答える
10

これは、ポリゴンが凸面であるかどうかを確認するためのテストです。

ポリゴンに沿った3つのポイントの各セット（頂点、前の頂点、後の頂点）について考えてみます。すべての角度が180度以下の場合、凸多角形になります。それぞれの角度を計算するときは、現在の合計（180-角度）も維持してください。凸多角形の場合、これは合計360になります。

このテストはO（n）時間で実行されます。

また、ほとんどの場合、この計算は一度実行して節約できるものであることに注意してください。ほとんどの場合、使用するポリゴンのセットがあり、常に変化するわけではありません。

于 2009-01-23T05:37:30.060 に答える
4

多角形が凸面かどうかをテストするには、多角形のすべての点が各線と同じ高さか後ろにある必要があります。

例の写真を次に示します。

ここに画像の説明を入力

于 2011-10-28T13:54:13.127 に答える
3

@RoryDaultonによる回答 は私にとって最良のようですが、角度の 1 つが正確​​に 0 の場合はどうでしょうか? このような極端なケースで True を返したい場合があるかもしれません。その場合は、次の行で "<=" を "<" に変更します。

if orientation * angle < 0.0:  # not both pos. or both neg.

問題を強調する私のテストケースは次のとおりです。

# A square    
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )

# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )

2 番目のアサートは元の回答で失敗します。それはすべきですか？私のユースケースでは、そうしない方がいいと思います。

于 2017-12-31T21:53:17.620 に答える
0

Uri のコードを matlab に適合させました。これが役立つことを願っています。

Uri のアルゴリズムは 単純なポリゴンに対してのみ機能することに注意してください。そのため、最初にポリゴンが単純かどうかを必ずテストしてください。

% M [ x1 x2 x3 ...
%     y1 y2 y3 ...]
% test if a polygon is convex

function ret = isConvex(M)
    N = size(M,2);
    if (N<4)
        ret = 1;
        return;
    end

    x0 = M(1, 1:end);
    x1 = [x0(2:end), x0(1)];
    x2 = [x0(3:end), x0(1:2)];
    y0 = M(2, 1:end);
    y1 = [y0(2:end), y0(1)];
    y2 = [y0(3:end), y0(1:2)];
    dx1 = x2 - x1;
    dy1 = y2 - y1;
    dx2 = x0 - x1;
    dy2 = y0 - y1;
    zcrossproduct = dx1 .* dy2 - dy1 .* dx2;

    % equality allows two consecutive edges to be parallel
    t1 = sum(zcrossproduct >= 0);  
    t2 = sum(zcrossproduct <= 0);  
    ret = t1 == N || t2 == N;

end
于 2014-11-15T02:31:30.427 に答える