3

我正在尝试创建一个 Javascript Web 应用程序，用户在其中单击画布以放置无限量的点。有解决按钮，当点击时在点之间画线，这样所有的点都由另外两个点连接，没有线可以交叉。到目前为止，使用我的代码，在某些情况下线条仍然交叉，我无法以编程方式找出将所有点连接起来而没有任何线条交叉的逻辑。

到目前为止，我收集了所有点（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

这是一个算法：

  • 找到质心（ O(n) 时间，其中 n 是点数）
  • 对于每个点，计算从中心到该点的角度（ O(n) 时间）。这可以Math.atan2(p.y-c.y, p.x-c.x)在 JS 中完成，其中 p 是当前点，c 是中心。
  • 按角度排序（ O(n log n) 时间）。对于任何完全相同的角度，接下来按半径排序，从小到大。
  • 对于从 0 到 n-1 的每个 i 以及从 n -1到0的每个点，连接点对 a i到 a i+1

这应该会产生一个连通图，其中没有两条线在 O(n log n) 时间内相交。

更新：

这段代码应该可以工作。

//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 回答