7

2次元平面上に特定の位置と半径を持つ一連の円があります。すべての円について、他の円と交差しているかどうか、および 2 つを分離するために必要な距離を判断したいと考えています。私の現在の実装では、考えられるすべての円の組み合わせを調べてから計算を行います。残念ながら、このアルゴリズムは O(n^2) であり、低速です。

円は通常、グループにまとめられ、半径は似ていますが異なります。円の数のおおよその最大値は約 200 です。アルゴリズムは正確である必要はありませんが、それに近い必要があります。

これは私が現在 JavaScript で持っている (遅い) 実装です:

// Makes a new circle
var circle = function(x,y,radius) {
    return {
        x:x,
        y:y,
        radius:radius
    };
};

// These points are not representative of the true data set. I just made them up.
var points = [
    circle(3,3,2),
    circle(7,5,4),
    circle(16,6,4),
    circle(17,12,3),
    circle(26,20,1)
];


var k = 0,
    len = points.length;
for (var i = 0; i < len; i++) {
    for (var j = k; j < len; j++) {
        if (i !== j) {
            var c1 = points[i],
                c2 = points[j],
                radiiSum = c1.radius+c2.radius,
                deltaX = Math.abs(c1.x-c2.x);

            if (deltaX < radiiSum) {
                var deltaY = Math.abs(c1.y-c2.y);

                if (deltaY < radiiSum) {
                    var distance = Math.sqrt(deltaX*deltaX+deltaY*deltaY);

                    if (distance < radiiSum) {
                        var separation = radiiSum - distance;
                        console.log(c1,c2,separation);
                    }
                }
            }
        }
    }

    k++;
}

また、よいアルゴリズム(KD Tree?)を分かりやすい英語で説明していただけるとありがたいです:-/

4

2 に答える 2

3

まず、SQRT 呼び出しをスキップした場合、上記のアルゴリズムは大幅に高速化されます。これは、距離を比較するための最もよく知られた単純な最適化です。「二乗半径」距離を事前計算して、重複して再計算しないようにすることもできます。

また、いくつかのアルゴリズムには他にも小さなバグがたくさんあるようです。以下に、それを修正する方法についての私の見解を示します。

また、O(N-Squared) アルゴリズムを取り除きたい場合は、kd-tree の使用を検討できます。KD-Tree の構築には初期費用がかかりますが、最近傍をより高速に検索できるという利点があります。

function Distance_Squared(c1, c2) {

    var deltaX = (c1.x - c2.x);
    var deltaY = (c1.y - c2.y);
    return (deltaX * deltaX + deltaY * deltaY);
}



// returns false if it's possible that the circles intersect.  Returns true if the bounding box test proves there is no chance for intersection
function TrivialRejectIntersection(c1, c2) {
    return ((c1.left >= c2.right) || (c2.right <= c1.left) || (c1.top >= c2.bottom) || (c2.bottom <= c1.top));
}

    var circle = function(x,y,radius) {
        return {
            x:x,
            y:y,
            radius:radius,

            // some helper properties
            radius_squared : (radius*radius), // precompute the "squared distance"
            left : (x-radius),
            right: (x+radius),
            top : (y - radius),
            bottom : (y+radius)
        };
    };

    // These points are not representative of the true data set. I just made them up.
    var points = [
        circle(3,3,2),
        circle(7,5,4),
        circle(16,6,4),
        circle(17,12,3),
        circle(26,20,1)
    ];


    var k = 0;
    var len = points.length;
    var c1, c2;
    var distance_squared;
    var deltaX, deltaY;
    var min_distance;
    var seperation;

    for (var i = 0; i < len; i++) {
        for (var j = (i+1); j < len; j++) {
            c1 = points[i];
            c2 = points[j];

            // try for trivial rejections first. Jury is still out if this will help
            if (TrivialRejectIntesection(c1, c2)) {
                 continue;
            }



            //distance_squared is the actual distance between c1 and c2 'squared'
            distance_squared = Distance_Squared(c1, c2);

            // min_distance_squared is how much "squared distance" is required for these two circles to not intersect
            min_distance_squared = (c1.radius_squared + c2.radius_squared + (c1.radius*c2.radius*2)); // D**2 == deltaX*deltaX + deltaY*deltaY + 2*deltaX*deltaY

            // and so it follows
            if (distance_squared < min_distance_squared) {

                // intersection detected

                // now subtract actual distance from "min distance"
                seperation = c1.radius + c2.radius - Math.sqrt(distance_squared);
                Console.log(c1, c2, seperation);
            }
        }
    }
于 2011-01-31T04:06:34.327 に答える
0

この記事は長い間休眠状態でしたが、私はこの問題に出くわし、かなりうまく解決したので、他の人が同じ頭を悩ませる必要がないように投稿します.

最近傍円問題は、kd ツリーまたは octree での 3 次元点最近傍探索として扱うことができます。2 つの円 A と B の間の距離を次のように定義します。

D(A,B) =  sqrt( (xA - xB)^2 + (yA - yB)^2 ) - rA - rB

円が重なっている場合、これは負の量です。この説明では八分木を想定しますが、k=3 の kd 木も同様です。

各円の octree にトリプル (x、y、r) を格納します。

ターゲット円 T の最近傍を見つけるには、標準アルゴリズムを使用します。

def search(node, T, nst)
  if node is a leaf
    update nst with node's (x,y,r) nearest to T
  else
    for each cuboid C subdividing node (there are 8 of them)
       if C contains any point nearer to T than nst
          search(C, T, nst)
  end
end

これnstは、これまでに見つかった T に最も近い円への参照です。最初はヌルです。

少しトリッキーな部分は決定if C contains any point nearer to T than nstです。このためには、x と y で T に最も近いユークリッドであり、直方体に含まれる r 範囲の最大値を持つ C 内の一意の点 (x,y,r) を考慮するだけで十分です。言い換えると、立方体は、中心が x と y の長方形領域にまたがり、半径の範囲を持つ一連の円を表します。確認したい点は、中心が T に最も近く、半径が最大の円を表す点です。

T の半径は、アルゴリズムにはまったく関与しないことに注意してください。Tの中心が他の円の内側にどれだけ離れているかだけに関心があります。(これが今のように最初から明白だったらよかったのに...)

于 2014-04-24T21:00:03.367 に答える