I am trying to create a Javascript web application where a user clicks on a canvas to drop an infinite amount of dots. There is solve button, that when clicked draws lines between the dots so that all dots are connected by exactly 2 other dots, and no lines can cross. With my code so far, there are certain instances where the lines still cross, and I can't programmatically figure out logic that will connect all the dots without any lines ever crossing.

So far, I collect all the points (X-Y coordinates) and put them in a JavaScript array of objects. I then need to sort the array so that it is in the correct order to be drawn. Everything works at this point except the order does not always satisfy the requirements.

My Question: Does anyone have any ideas on a set of rules that will order these points (X-Y coordinates) so that they all connect but never cross, that will work in every scenario?

Thanks for your help.

    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]);

I am trying to create a Javascript web application where a user clicks on a canvas to drop an infinite amount of dots. There is solve button, that when clicked draws lines between the dots so that all dots are connected by exactly 2 other dots, and no lines can cross. With my code so far, there are certain instances where the lines still cross, and I can't programmatically figure out logic that will connect all the dots without any lines ever crossing.

So far, I collect all the points (X-Y coordinates) and put them in a JavaScript array of objects. I then need to sort the array so that it is in the correct order to be drawn. Everything works at this point except the order does not always satisfy the requirements.

My Question: Does anyone have any ideas on a set of rules that will order these points (X-Y coordinates) so that they all connect but never cross, that will work in every scenario?

Thanks for your help.

    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]);

• javascript
• graph

1 Answer 1

Here's an algorithm:

• Find the center of mass ( O(n) time, where n is the number of points)
• For each point, pute 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 a_i to a_i+1 for every i from 0 to n-1 and also a_n-1 to a₀

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]);
}