最近一直在思考如何将复杂的多边形转化为非复杂的多边形。这是怎么做到的？
这是我想做的事情：
完成后我将使用 JavaScript 结束，但任何形式的解决方案都可以（语言、算法或只是简单的英语）。
user263078
问问题
3458 次
6 回答
6
我将使用与手动绘制多边形时相同的启发式方法（这可能不是计算该多边形的最数学有效的方法，但可能是最容易理解/实现的方法）。
- 从一点开始
- 找到我当前点和我要到达的点之间的所有交点
- 如果不存在，则绘制到下一点
- 如果有，则绘制到那里，然后将下一个点设置为从那里开始的下一个点
- 如果您没有回到起点，请转到 2。
这是 jsfiddle 上的示例实现。注意：它没有优化。
于 2012-05-20T12:45:18.127 回答
3
我相信最简单的路线是执行平面扫描以检测所有边缘边缘交叉点。增加一个基本的平面扫描算法实现来保持最外层边界并不难，这正是你想要的。几乎所有关于计算几何的教科书都很好地解释了这一点。
于 2012-05-20T16:52:46.333 回答
2
这是一个较晚的答案，但这可以使用Javascript Clipper Library来完成。所需的操作是简化（内部使用联合操作），它会删除边与其他边相交的自相交。
笔记！Javascript Clipper 5 不能确保在所有情况下解决方案都只包含真正简单的多边形。这种特殊情况是顶点接触边缘。Clipper 6（Javascript 版本尚未准备好）也可以处理这些特殊情况。
使用 Javascript Clipper 简化多边形主演示
您可以使用Javascript Clipper Main Demo来玩 Clipper 。单击多边形-自定义，您可以在此处输入自己的多边形，然后进行所需的操作。
让我们举个例子：
[[7,86, 196,24, 199,177, 47,169, 51,21, 224,102, 223,146, 7,140, 7,86]]
如果您在演示中输入这些点（作为主题或剪辑），您将获得以下多边形：
然后进行简化操作，产生以下解决方案：
在多边形资源管理器中点击求解，可以看到简化多边形的坐标：[[199,177, 47,169, 47.75,141.13, 7,140, 7,86, 49.62,72.02, 51,21, 114.51,50.73, 196,24, 197.28 ,89.49, 224,102, 223,146, 198.38,145.32]]
简化多边形的代码示例
最后，我将完整的功能代码放在JSBIN中，其中包括 SVG 绘图功能，因此相当长：
<html>
<head>
<title>Javascript Clipper Library / Simplifying Polygons</title>
<script src="clipper.js"></script>
<script>
function draw() {
var subj_polygons = [[{"X":7,"Y":86},{"X":196,"Y":24},{"X":199,"Y":177},{"X":47,"Y":169},{"X":51,"Y":21},{"X":224,"Y":102},{"X":223,"Y":146},{"X":7,"Y":140},{"X":7,"Y":86}]];
var scale = 100;
subj_polygons = scaleup(subj_polygons, scale);
var cpr = new ClipperLib.Clipper();
cpr.AddPolygons(subj_polygons, ClipperLib.PolyType.ptSubject);
var solution_polygons = new ClipperLib.Polygons();
solution_polygons = cpr.SimplifyPolygons(subj_polygons, ClipperLib.PolyFillType.pftNonZero);
//console.log(JSON.stringify(solution_polygons));
var svg = '<svg style="margin-top:10px; margin-right:10px;margin-bottom:10px;background-color:#dddddd" width="240" height="200">';
svg += '<path stroke="black" fill="yellow" stroke-width="2" d="' + polys2path(solution_polygons, scale) + '"/>';
svg += '</svg>';
document.getElementById('svgcontainer').innerHTML = svg;
}
// helper function to scale up polygon coordinates
function scaleup(poly, scale) {
var i, j;
if (!scale) scale = 1;
for(i = 0; i < poly.length; i++) {
for(j = 0; j < poly[i].length; j++) {
poly[i][j].X *= scale;
poly[i][j].Y *= scale;
}
}
return poly;
}
// converts polygons to SVG path string
function polys2path (poly, scale) {
var path = "", i, j;
if (!scale) scale = 1;
for(i = 0; i < poly.length; i++) {
for(j = 0; j < poly[i].length; j++) {
if (!j) path += "M";
else path += "L";
path += (poly[i][j].X / scale) + ", " + (poly[i][j].Y / scale);
}
path += "Z";
}
return path;
}
</script>
</head>
<body onload="draw()">
<h2>Javascript Clipper Library / Simplifying Polygons</h2>
This page shows an example of simplifying polygon and drawing it using SVG.
<div id="svgcontainer"></div>
</body>
</html>
于 2013-10-08T09:37:09.060 回答
1
您应该维护每个交点的事件边列表。
然后永远选择边缘（输出），它与前一个（输入）边缘的角度最小（逆时针）。
于 2012-05-20T11:58:04.127 回答
0
看来您将要研究Convex Hull 算法。这是一些 Convex Hull 算法的小程序。您也许可以修改其中一种算法以获取您的极值点并从那里开始。
于 2012-05-20T06:45:13.167 回答
0
好的，看来我提出了可行的解决方案：
http://mrpyo.github.com/Polygon/
它是 ActionScript，因此将其转换为 JavaScript 应该没有问题。如果有人感兴趣，我可以解释使用的算法...
于 2012-05-22T13:16:18.033 回答