绘制一个多边形 [英] Drawing a Polygon
问题描述
我使用Google Maps API V3根据路径绘制多边形，该路径是随机未分类的坐标点数组（LatLng）。这产生下面的形状：
多段线相交!!
问题：由于多边形的形状取决于路径中的点，如何排序路径以创建一个没有线相交且没有形成孔的多边形？还有一个参考点（图中未显示）多边形必须包含在内。
没有交集：） //i.stack.imgur.com/tRrMl.jpgalt = 尽管Javascript被用来产生这个多边形，请随时使用任何语言来解决此问题编辑：有一个参考点即多边形必须包含，但这一点不会是多边形的任何顶点 有趣的问题。我相信这是有效的，但请测试一下。自trig以来已经很长时间了。 这些评论基本解释了它。我找到了一个中心点（不确定这是否是防弹的，可能有更好的方法来计算这个或者它可能没有多大关系），找出每个点在那点附近有多少度，然后按这个点排序。 编辑： 阅读完编辑后，如果此参考点已知并且在多边形内，则应该用此点替换center。 I am using Google Maps API V3 to draw a polygon based on a path, which is an array of random unsorted coordinate points (LatLng). This produces the shape below: Polylines intersect!!
Problem: Since the shape of the Polygon depends on the order of the points in the path, how can I sort the path to create a polygon where no line intersects and no holes are formed? There is also a reference point (not shown in images) that the polygon must enclose. I believe this require a sorting algorithm, which I cannot find! No intersection :)
Although Javascript is used to produce this polygon, please feel free to use any language to solve this problem EDIT: There is a reference point that the polygon must enclose, but this point will not be any vertex of the polygon Fun question. I believe this works, but please test it out. It's been a long long time since trig. The comments basically explain it. I find a "central" point (not sure if this is bulletproof, there may be a better way of calculating this or it may not matter that much), figure out how many degrees around that point each point is and then order them by that. Tested it with various points and it seems to work.
EDIT: After reading your edit, if this "reference point" is known and within the polygon, you should replace "center" with this point. 这篇关于绘制一个多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
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}
];
//使用DOM获取画布元素
var canvas = document.getElementById（'canvas'）;
//确保在不支持canvas的情况下执行
if（canvas.getContext）{
//使用getContext使用画布绘制
var ctx = canvas.getContext（'2d'）;
ctx.fillStyle =red;
//计算最大和最小x和y
var minX = points [0] .x;
var maxX = points [0] .x;
var minY = points [0] .y;
var maxY = points [0] .y;如果（points [i] .x
if（points [i] .y
}
//选择一个中心点
var center = {
x：minX +（maxX - minX）/ 2，
y：minY +（maxY - minY）/ 2
};
//预先计算每个点的角度，以避免在
上进行多次计算（var i = 0; i
if（points [i] .y> center.y）{
points [i] .angle = Math.PI + Math.PI - points [i] .angle;
//按角度排序
points = points.sort（function（a，b）{
return a.angle - b .angle;
}）;
//绘制形状
ctx.beginPath（）;
ctx.moveTo（points [0] .x，points [0] .y）;
for（var i = 1; i
}
ctx.lineTo（points [0] .x，points [0] .y）;
ctx.stroke（）;
ctx.fill（）;
}
函数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;
返回Math.sqrt（xs + ys）;
$ / code $ / pre
$ hr
$ b 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);
}
