Рисование многоугольника

Question

Я использую Google Maps API V3 для рисования многоугольника на основе пути, который представляет собой массив случайных несортированных координатных точек (LatLng).Это дает следующую форму:

Полилинии пересекаются !!

Проблема: Поскольку форма многоугольника зависит от порядкаточки на пути, как я могу отсортировать путь, чтобы создать многоугольник, в котором ни одна линия не пересекается и отверстия не образуются?Существует также контрольная точка (не показана на изображениях), которую должен заключать многоугольник.Я считаю, что для этого требуется алгоритм сортировки, который я не могу найти!

Без пересеченияПожалуйста, не стесняйтесь использовать любой язык, чтобы решить эту проблемумногоугольника

Answer 1

Забавный вопрос.Я считаю, что это работает, но, пожалуйста, проверьте это.Прошло очень много времени с момента запуска.

http://jsfiddle.net/9DHSf/3/

Комментарии в основном объясняют это.Я нахожу «центральную» точку (не уверен, что это пуленепробиваемый, может быть, есть лучший способ рассчитать это, или это может не иметь большого значения), выяснить, сколько градусов вокруг этой точки находится в каждой точке, а затем упорядочить их по,Протестировал его с различными точками, и он, кажется, работает.

var points = [
                {x: 40, y: 40},
                {x: 60, y: 40},
                {x: 60, y: 60},
                {x: 40, y: 60},                
                {x: 0, y: 50},
                {x: 50, y: 0},
                {x: 50, y: 100},
                {x: 100, y: 50}
            ];



// get the canvas element using the DOM
var canvas = document.getElementById('canvas');

// Make sure we don't execute when canvas isn't supported
if (canvas.getContext) {

    // use getContext to use the canvas for drawing
    var ctx = canvas.getContext('2d');

    ctx.fillStyle = "red";


    // calculate max and min x and y
    var minX = points[0].x;
    var maxX = points[0].x;
    var minY = points[0].y;
    var maxY = points[0].y;

    for (var i = 1; i < points.length; i++) {
        if (points[i].x < minX) minX = points[i].x;
        if (points[i].x > maxX) maxX = points[i].x;
        if (points[i].y < minY) minY = points[i].y;
        if (points[i].y > maxY) maxY = points[i].y;
    }


    // choose a "central" point
    var center = {
        x: minX + (maxX - minX) / 2,
        y: minY + (maxY - minY) / 2
    };

    // precalculate the angles of each point to avoid multiple calculations on sort
    for (var i = 0; i < points.length; i++) {
        points[i].angle = Math.acos((points[i].x - center.x) / lineDistance(center, points[i]));

        if (points[i].y > center.y) {
            points[i].angle = Math.PI + Math.PI - points[i].angle;
        }
    }

    // sort by angle
    points = points.sort(function(a, b) {
        return a.angle - b.angle;
    });

    // Draw shape
    ctx.beginPath();
    ctx.moveTo(points[0].x, points[0].y);

    for (var i = 1; i < points.length; i++) {
        ctx.lineTo(points[i].x, points[i].y);
    }

    ctx.lineTo(points[0].x, points[0].y);

    ctx.stroke();
    ctx.fill();
}


function lineDistance(point1, point2) {
    var xs = 0;
    var ys = 0;

    xs = point2.x - point1.x;
    xs = xs * xs;

    ys = point2.y - point1.y;
    ys = ys * ys;

    return Math.sqrt(xs + ys);
}

---

РЕДАКТИРОВАТЬ: После прочтения вашего редактирования, если эта «контрольная точка» известна и находится внутри многоугольника, выследует заменить «центр» на эту точку.

Answer 2

Если у вас есть не более нескольких десятков точек для рассмотрения, используйте алгоритм TSP (задача коммивояжера), чтобы упорядочить точки.Для путей TSP с евклидовым расстоянием путь не пересекает сам себя.Большое количество кода TSP доступно онлайн , включая апплеты.

Путь TSP проходит через все представленные точки.Если вы хотите пройти только «внешние» точки, используйте алгоритм выпуклой оболочки.Это даст точки по порядку на самом маленьком выпуклом многоугольнике, охватывающем все точки.

Answer 3

Кажется, что "альфа-форма" и "вогнутый корпус" заслуживают внимания