在笛卡尔坐标系2D中计算不规则形状的边界

Question

我是一名有用的助手，可以进行文本翻译。

我正在寻找一个解决方案来计算不规则形状的边界。

让我们以正方形为例:

如果我有x和y的最小值和x和y的最大值，如下:

MaxX = 5
MinX = 1
MaxY = 5
MinY = 1

在Python语言中：

#Python Code
X = {"Min":1, "Max":5} # is Dictionary of x Axis
Y = {"Min":1, "Max":5} # is Dictionary of y Axis

我可以通过比较轴与正方形边界的最小值和最大值来检查任何坐标是否在正方形边界内。现在让我们看看这两个不规则的例子： 现在我该如何计算形状的边界和坐标？我有点的坐标，但没有形状内部的坐标以及连接形状每个点的线条坐标。注意：你可能会建议使用点-多边形算法，但那就像每次针对特定坐标进行计算，如果形状巨大，它将需要很长时间。注意：即使你听说过任何书籍、演讲、视频、网站甚至是你的猜测中的解决方案，请在评论中让我知道，这可能会帮助我。

- Bear

---

你尝试过检测角落吗？如果是在图像上，我建议你使用一些专门用于此的库（如OpenCV）。分两步进行：检测和解释比例尺，然后检测形状的角落并解释它们的点。 - sop

你想要确定的是形状的“凹壳”，而不是凸壳。你的第一个图显示了最小区域边界矩形，第二个是凸壳，最后一个图是凹壳（也可以看看alpha shapes）。 - user1121588

@sop OpenCV，从未听说过，我会去了解一下，非常感谢。 - Bear

@DanPatterson 我明白了...我不熟悉那些术语，谢谢你指出来。 - Bear

Answer 1

如果您想获取形状内所有整数坐标的完整列表，请考虑使用泛洪算法。

- MBo

---

你如何知道从哪里开始？ - sop

@sop 当我创建一个形状时，它的每个点都有一个编号，只需要找到顺时针和逆时针方向，这很简单。但是如果线条像AutoCAD/Rhino一样被分开处理，那么找到点就是另一个问题了。 - Bear