连接点没有交叉线

Question

我正在尝试创建一个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]);

Answer 1

这是一个算法:

• 找到质心(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的每个i,连接点a _i到_{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]);
}