3

ユーザーがキャンバスをクリックして無限のドットをドロップする Javascript Web アプリケーションを作成しようとしています。解決ボタンがあり、クリックするとドット間に線が描画され、すべてのドットが正確に 2 つの他のドットで接続され、線が交差することはありません。これまでのコードでは、線がまだ交差している特定のインスタンスがあり、線が交差することなくすべてのドットを接続するロジックをプログラムで把握することはできません。

これまでのところ、すべてのポイント (XY 座標) を収集し、オブジェクトの JavaScript 配列に配置しました。次に、正しい順序で描画されるように配列を並べ替える必要があります。この時点で、注文が常に要件を満たしているとは限らないことを除いて、すべてが機能します。

私の質問: すべてのシナリオで機能するように、これらのポイント (XY 座標) をすべて接続するが決して交差しないように順序付けする一連のルールについてアイデアを持っている人はいますか?

ご協力いただきありがとうございます。

    var centroid = get_polygon_centroid($points);

    $points = _.sortBy($points, function(p){
        var dx = p.coords.x-centroid.x;
        var dy = p.coords.y-centroid.y;
        return dx*dx + dy*dy;
    });

    $points = _.sortBy($points, function(p){
        var dx = p.coords.x-centroid.x;
        var dy = p.coords.y-centroid.y;
        return Math.atan2(dy, dx);
    });

    $points.push($points[0]);
4

1 に答える 1

7

Here's an algorithm:

  • Find the center of mass ( O(n) time, where n is the number of points)
  • For each point, compute the angle from the center to that point ( O(n) time). This can be done with Math.atan2(p.y-c.y, p.x-c.x) in JS where p is the current point and c is the center.
  • Sort by angle ( O(n log n) time). For any angles that are exactly the same, sort by radius next, smallest to largest.
  • Connect pairs of points ai to ai+1 for every i from 0 to n-1 and also an-1 to a0

This should result in a connected graph where no two lines intersect in O(n log n) time.

Update:

This code should work.

//iterate through all points and calculate the center, c
var c = {x:0, y:0}, p;
for (p : points) {
    c.x+=p.coords.x;
    c.y+=p.coords.y;
}

c.x/=points.length;
c.y/=points.length;


points.sort(function(p1, p2){
    var dx1 = p1.coords.x-c.x;
    var dy1 = p1.coords.y-c.y;
    var a1 = Math.atan2(dy1, dx1);

    var dx2 = p2.coords.x-c.x;
    var dy2 = p2.coords.y-c.y;
    var a2 = Math.atan2(dy2, dx2);

    //If angles are the same, sort by length
    if (a1===a2){
        var d1 = dx1*dx1 + dy1*dy1;
        var d2 = dx2*dx2 + dy2*dy2;

        return d1-d2;
    }

    //otherwise sort by angle
    return a1-a2;
}

//Iterate through all Points and draw lines between them
var i;
for (i=0;i<n;i++){
    //This is not real code \/
    line(p[i], p[(i+1)%n]);
}
于 2013-06-15T17:56:44.883 に答える