Подключение точек без пересекающихся линий

Question

Я пытаюсь создать веб-приложение Javascript, где пользователь нажимает на холст, чтобы удалить бесконечное количество точек. Существует кнопка разрешения, которая при нажатии рисует линии между точками, так что все точки соединяются ровно двумя другими точками, и никакие строки не пересекаются. С моим кодом до сих пор есть определенные случаи, когда линии все еще пересекаются, и я не могу программно вычислить логику, которая будет соединять все точки без каких-либо линий, когда-либо пересекающихся.

До сих пор я собирал все точки (координаты X-Y) и помещал их в массив объектов JavaScript. Затем мне нужно отсортировать массив так, чтобы он был в правильном порядке. Все работает в этот момент, за исключением того, что заказ не всегда удовлетворяет требованиям.

Мой вопрос: Есть ли у кого-нибудь идеи по набору правил, которые будут упорядочивать эти точки (координаты X-Y), чтобы все они соединялись, но никогда не пересекались, что будет работать в каждом сценарии?

Благодарим за помощь.

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)). Это можно сделать с помощью Math.atan2(p.y-c.y, p.x-c.x) в JS, где p - текущая точка, а c - центр.
• Сортировка по углу (O (n log n)). Для любых углов, которые являются точно же, сортируйте по радиусу дальше, от самого маленького до самого большого.
• Connect пары точек а _я к _{I + 1} для каждого г от 0 до N-1, а также _п-1 к

Это должно привести к связанный граф, где две прямые не пересекаются в O (n log n) времени.

---

Update:

Этот код должен работать.

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