给定一组坐标点,删除内点(或找到点的外环)以形成多边形

Question

对于我的d3项目,我有一系列相邻的多边形,我想计算一个新的多边形,它是放在一起的所有较小多边形的外边框.

我已将几个连接多边形的所有点合并为一个数组以创建一个大多边形.但这包括所有内部边缘以及外部边缘.我想删除这个合并多边形的内边缘,这样我只有一个表示该区域外边框的形状,但我找不到合适的算法来做到这一点.

我找到了这个,但它要求已经明确知道多边形的顶点; 我只有一组点,外部和内部没有区别.

一旦我删除了生成的多边形的内部点,我想在外部点周围绘制一条"基数"插值线.这就是为什么我必须保持点的完整性而不是将多边形转换为弧并使用像topojson.mesh这样的东西!

这是一个截图,可以更清楚地解释:

绿色多边形的所有顶点(红线的角)被连接成一个点阵列.我想弄清楚如何移除内部点,以便我可以在剩余的外部点周围应用"基数"插值线.

Answer 1

数学家会说你需要计算凸包:

D3为这种算法提供接口.

文档在这里.你必须仔细阅读.

有使用的例子在这里.它与您想要的不一样,但您可以通过研究它来熟悉界面.

您可以在网上找到使用D3凸包算法的其他示例.

一旦理解了文档和示例,就应该将所有新知识应用到您的问题中.

如果您在代码集成方面遇到其他问题,可以打开另一个问题.

希望这可以帮助.