8

最近一直在思考如何将复杂的多边形转化为非复杂的多边形。这是怎么做到的？

这是我想做的事情：

例子

完成后我将使用 JavaScript 结束，但任何形式的解决方案都可以（语言、算法或只是简单的英语）。

4

6 回答 6

6

我将使用与手动绘制多边形时相同的启发式方法（这可能不是计算该多边形的最数学有效的方法，但可能是最容易理解/实现的方法）。

  1. 从一点开始
  2. 找到我当前点和我要到达的点之间的所有交点
  3. 如果不存在，则绘制到下一点
  4. 如果有，则绘制到那里，然后将下一个点设置为从那里开始的下一个点
  5. 如果您没有回到起点，请转到 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 回答