-1

重複の可能性:
繰り返し発生する matlab コードの最適化

ベクトル化は、このコードを最適化するための適切なオプションですか? コードをベクトル化するかどうかを決定する基準は何ですか? 他に何ができますか？

function [oddNodes] = pointInPolygon (point,thePolygon)
% determine if a point is in the polygon (faster than matlab "inpolygon"
% command

 polyPoints=size(thePolygon,1);     %number of polygon points
 oddNodes = false;

j=polyPoints;
x=point(1); y=point(2);

for i=1:polyPoints
if (thePolygon(i,2)<y && thePolygon(j,2)>=y ||  thePolygon(j,2)<y && thePolygon(i,2)>=y)
    if (thePolygon(i,1)+(y-thePolygon(i,2))/(thePolygon(j,2)-thePolygon(i,2))*(thePolygon(j,1)-thePolygon(i,1))<x)
        oddNodes=~oddNodes;
    end
end
j=i; 
end
4

1 に答える 1

2

いくつかの調査をしてください、グーグルでの有用なヒットの量は文字通り圧倒的です：

  1. http://www.softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
  2. http://www.mathworks.com/matlabcentral/fileexchange/10391-fast-points-in-polygon-test
  3. ジオフェンシング-ポリゴンの内側/外側を指す
  4. http://www.mathworks.com/matlabcentral/fileexchange/12744-distance-from-a-point-to-polygon

等

そうは言っても、あなたのコードは、単一の点がポリゴンの内側にあるかどうかだけを判断したいことを示唆しています。inpolygonその場合、 100万頂点のポリゴンの場合、5秒以内にそれを判断できるので、なぜわざわざする必要があります。

ここで、多数のポイントに対してこれを実行したいが、ポリゴン内の頂点はそれほど多くない場合（またはその逆の場合）、ポイント配列を関数に渡すことをお勧めします。

function in = pointInPolygon(points, poly)

    nn = size(poly,1);
    in = false(nn,1);

    for ii = 1:size(points,2)

        x = points(ii,1);
        y = points(ii,2);

        yn = false;
        for jj = 1:size(poly,1)

            if (poly(jj,2)<y && poly(nn,2)>=y || ...
                poly(nn,2)<y && poly(jj,2)>=y)

                if (poly(jj,1)+(y-poly(jj,2))/(poly(nn,2)-poly(jj,2))*...
                   (poly(nn,1)-poly(jj,1))<x)
                    yn = ~yn;
                end

            end
            nn = jj;
        end

        in(ii) = yn;

    end

end

これにより、Matlabは両方のループでJITを使用できるようになりました。簡単なテスト：

poly = rand(6e6,2);
poly = [poly ; poly(1,:)];

xy   = rand(1e3,2);

tic         
    in = pointInPolygon(xy, poly);
toc

結果：

Elapsed time is 0.324801 seconds.

ここで、ポリゴン内に多数の頂点がある多数のポイントのテストを実行する場合は、これらすべてをCに変換して、mexファイルを作成することをお勧めします。結局のところ、これはかなり重いアルゴリズムであり、それに大きな要求を課す場合は、ツールセットを切り替える必要があります。

于 2012-10-18T15:42:23.150 に答える