我使用Google Maps API V3根據路徑繪製多邊形，該路徑是隨機未分類的座標點（LatLng）的數組。這產生下面的形狀：繪製多邊形
多義線相交！ 
問題：由於多邊形的形狀取決於路徑的點的順序上，我怎麼可以排序的路徑，創造一個沒有線相交，並形成無孔多邊形？還有一個參考點（圖中未顯示）多邊形必須包含在內。我相信這需要一個排序算法，我找不到！
沒有交集:) 
雖然JavaScript是用來生產這種多邊形，請隨意使用任何語言來解決這個問題
編輯：有一個參考點多邊形必須包含，但這一點不會是多邊形的任何頂點
有趣的問題。我相信這是有效的，但請測試一下。自trig以來已經很長時間了。
的意見基本解釋。我找到了一個「中心點」（不確定這是否是防彈的，可能有更好的方法來計算這個或者它可能沒有多大關係），找出每個點在那點附近有多少度，然後按這個點排序。測試它與各種觀點，它似乎工作。
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);
}
編輯：閱讀您的編輯，如果這個「基準點」是已知的，多邊形內，應更換「中心」這個點之後。
我發現如果兩個以上的點的角度完全相同，有趣的事情可能會發生，因此您可能需要添加距離「中心」的第二類距離。可能還有其他可能導致問題的特殊情況，比如某個點完全處於「中心」。 –
會試試這個！對我而言，沒有一點與參考點位於同一位置，謝謝指出:) – Nyxynyx
似乎「alpha shape」和「concave hull」值得注意
可以從這些點創建多個多邊形。照片中的人是你正在尋找的人嗎？如果是這樣，什麼定義這一個是正確的？ –
我正在尋找的右側多邊形是所有點都映射出一個沒有孔或線相交的連續區域的多邊形。如果有不同的解決方案，所有人都應該工作。 – Nyxynyx
@Nyxynyx - 你認爲「所有人都應該工作」是什麼意思？你的意思是算法應該確定所有有效的解決方案，或者任何有效的解決方案？ – mbeckish