我使用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