algorithm - 检索二维图上最外层的点

Question

大家好，

我有一个二维图，上面绘制了一些点。我需要做的是只获得最外层的点，以便我可以将它们连接起来（并不真正相关）。

我似乎无法理解的是我需要使用的算法才能做到这一点？

我认为这可能会帮助您了解我想要实现的目标：

o o o
o x o
o o o

我想得到的所有 o 和我想忽略的 x。此外，这些点可以在任何位置和任何形状，但我仍然只想抓住最外面的点。

有任何想法吗？

另外，我不确定这是否是正确的网站，如果不是，请告诉我去哪里。

谢谢！

score 4 · Accepted Answer

您需要对您拥有的一组点进行凸包。我个人更喜欢为此使用格雷厄姆扫描，因为它相当容易实现并且具有良好的计算复杂性。

score 2 · Accepted Answer

如果您的 2d 图由一组 XY 坐标表示，您可以计算 Ivaylo 提到的凸包。

如果您的图表与帖子中的示例相似，由 2d 网格图表示，您可以使用洪水填充来获取边界。

score 0 · Accepted Answer

如果您尝试在 javascript 中实现这一点，请查看 d3.js geom.hull：https ://github.com/mbostock/d3/wiki/Hull-Geom

3 回答 3