0

初めての投稿です、よろしくお願いします。

3〜10個の座標を持つマトリックスがあり、これらのポイントを接続して最大サイズのポリゴンにしたいと考えています。

プロットを生成するために fill() [1] を試しましたが、このプロットの面積を計算するにはどうすればよいですか? プロットを行列に戻す方法はありますか?

あなたは私に何をすすめますか？

前もって感謝します！

[1]

x1 = [0.0、0.5、0.5];
y1 = [0.5、0.5、1.0];
塗りつぶし ( x1, y1, 'r' );

[アップデート]

MatlabDoug さん、ご回答ありがとうございます。これらすべてのポイントを接続して、最大サイズのポリゴンにしたいと考えています。

新しいアイデアはありますか？

4

4 に答える 4

3 
 x1 = rand(1,10)
 y1 = rand(1,10)

 vi = convhull(x1,y1)
 polyarea(x1(vi),y1(vi))

 fill ( x1(vi), y1(vi), 'r' ); 
 hold on
 plot(x1,y1,'.')
 hold off

ここで何が起こっているかというと、CONVHULL はどの頂点 (vi) が凸包 (すべての点を囲む最小の多角形) 上にあるかを教えてくれます。どれが凸包上にあるかを知っているので、MATLAB に POLYAREA で領域を尋ねます。

最後に、FILL コマンドを使用してポリゴンを描画し、PLOT を使用してそこにポイントを配置して確認します。

于 2009-10-02T15:57:12.580 に答える
1

接続するポイントは 3 ～ 10 個しかないとおっしゃいました。この場合、すべての可能な組み合わせを取得し、polyarea で領域を計算して、最大のものを取得することをお勧めします。

ポイントの数が増えた場合、または計算時間が重要になるように頻繁に計算する必要がある場合にのみ、より良いアルゴリズムに時間を投資する価値があります。しかし、アルゴリズムを考え出し、その完全性を証明するのは難しいと思います。

于 2009-10-06T09:21:09.180 に答える
1

すべてのポリゴンを試すという groovingandi の提案に賛成します。ポリゴンの有効性を確認する必要があります（自己交差などはありません）。

さて、たくさんのポイントで作業したい場合... MatlabDoug が指摘したように、凸包は始めるのに適した場所です。凸包は、面積が可能な最大の多角形を与えることに注意してください。もちろん、問題は、ポリゴンの一部ではない船体の内部にポイントが存在する可能性があることです。次の貪欲なアルゴリズムを提案しますが、それが最大面積ポリゴンを保証するかどうかはわかりません。

基本的な考え方は、凸包を最終ポリゴンの候補として開始し、すべてのポイントが最終ポリゴンに属するまで、未使用のポイントに対応する三角形を切り出すことです。各段階で、可能な限り小さい三角形が削除されます。

Given: Points P = {p1, ... pN}, convex hull H = {h1, ..., hM}
       where each h is a point that lies on the convex hull.
       H is a subset of P, and it is also ordered such that adjacent
       points in the list of H are edges of the convex hull, and the
       first and last points form an edge.
Let Q = H
while(Q.size < P.size)
    % For each point, compute minimum area triangle
    T = empty heap of triangles with value of their area
    For each P not in Q
        For each edge E of Q
            If triangle formed by P and E does not contain any other point
                Add triangle(P,E) with value area(triangle(P,E))
    % Modify the current polygon Q to carve out the triangle
    Let t=(P,E) be the element of T with minimum area
    Find the ordered pair of points that form the edge E within Q
    (denote them Pa and Pb)
    Replace the pair (Pa,Pb) with (Pa,E,Pb)

さて、実際には のヒープは必要ありませんT。データを 4 つのリストに追加するだけです。1 つは P 用、もう 1 つは Pa 用、もう 1 つは Pb 用、もう 1 つは領域用です。ポイントが三角形内にあるかどうかをテストするには、三角形の辺を形成する線に対して各ポイントをテストするだけでよく、まだ Q に含まれていないポイントをテストするだけで済みます。最後に、最終的なポリゴンの面積を計算するには、あなたはそれを三角測量することができます（delaunay関数のように、三角測量の各三角形の面積を合計します）、または凸包の面積を見つけて、それらを切り取るときに三角形の面積を差し引くことができます。

繰り返しになりますが、この貪欲なアルゴリズムが最大面積のポリゴンを見つけることが保証されているかどうかはわかりませんが、ほとんどの場合は機能するはずであり、それでも興味深いものです。

于 2009-10-06T09:29:10.210 に答える
0

アムロがコメントしたように、ポイントの正しい順序を見つけるのは難しい部分です。この機能で十分ですか？

function [idx] = Polyfy(x, y)
% [idx] = Polyfy(x, y)
% Given vectors x and y that contain pairs of points, find the order that
% joins them into a polygon. fill(x(idx),y(idx),'r') should show no holes.

%ensure column vectors
if (size(x,1) == 1)
  x = x';
end
if (size(y,1) == 1)
  y = y';
end

% vectors from centroid of points to each point
vx = x - mean(x);
vy = y - mean(y);
% unit vectors from centroid towards each point
v = (vx + 1i*vy)./abs(vx + 1i*vy);
vx = real(v);
vy = imag(v);

% rotate all unit vectors by first
rot = [vx(1) vy(1) ; -vy(1) vx(1)];
v = (rot*[vx vy]')';

% find angles from first vector to each vector
angles = atan2(v(:,2), v(:,1));
[angles, idx] = sort(angles);
end

アイデアは、点の重心を見つけてから、重心から各点へのベクトルを見つけることです。これらのベクトルは、三角形の辺と考えることができます。ポリゴンは、各ベクトルが「左」と「右」として一度だけ使用され、ベクトルがスキップされない三角形のセットで構成されます。これは、重心の周りの角度によってベクトルを並べ替えることに要約されます。

ベクトルを単位長に正規化し、そのうちの 1 つを回転ベクトルとして選択し、残りを回転させることでこれを行うことにしました。これにより、単純に atan2 を使用して角度を見つけることができました。おそらく、これを行うためのより高速かつ/またはよりエレガントな方法がありますが、私はトリガーのアイデンティティと混同していました。最後に、これらの角度を並べ替えると、ポイントが目的のポリゴンを形成するための正しい順序が提供されます。

これはテスト関数です:

function [x, y] = TestPolyArea(N)
x = rand(N,1);
y = rand(N,1);
[indexes] = Polyfy(x, y);
x2 = x(indexes);
y2 = y(indexes);
a = polyarea(x2, y2);
disp(num2str(a));
fill(x2, y2, 'r');
hold on
plot(x2, y2, '.');
hold off
end

N = 100 程度を渡すと、かなりワイルドな写真が得られます。

于 2009-10-06T09:05:35.237 に答える