<分区>
我有一组点 (x, y)，我想知道它们是否形成一个封闭区域(在矩形 2D 光栅内)。这似乎是一个简单的问题，但经过半小时的谷歌搜索，我无法找到解决这个问题的算法。这个问题有已知的算法吗？
用 C++ 或 C#(甚至伪代码)编写的例程是理想的。
编辑: 我在这里处理的具体问题是一个绘图程序，应用程序用户应该在其中绘制感兴趣区域周围的边界。如果用户绘制的边界未形成封闭区域，我想警告用户。
<分区>
我有一组点 (x, y)，我想知道它们是否形成一个封闭区域(在矩形 2D 光栅内)。这似乎是一个简单的问题，但经过半小时的谷歌搜索，我无法找到解决这个问题的算法。这个问题有已知的算法吗？
用 C++ 或 C#(甚至伪代码)编写的例程是理想的。
编辑: 我在这里处理的具体问题是一个绘图程序，应用程序用户应该在其中绘制感兴趣区域周围的边界。如果用户绘制的边界未形成封闭区域，我想警告用户。
最佳答案
您似乎想知道给定的点集是否包含一个封闭区域。幸运的是，对此有一个简单而灵活的答案:)
假设给定的点集是在白色背景上绘制的黑色像素集。 简单地从已知外部点(例如 (0, 0))开始执行黑色填充。现在查看图像中是否保留任何白色像素。如果是，则原始绘制的像素至少包含 1 个闭合区域。
如果您曾经在粗糙的位图绘制程序中用鼠标绘制过任何东西，您就会知道小缺陷很容易形成——例如如果您正在绘制一条自由曲线，急转弯并沿不同的方向继续这条线，则可能是您不小心创建了一个由 1 或 2 个白色像素组成的小气泡。幸运的是，这个算法可以很容易地考虑到这些:只计算填充后剩余的白色像素的数量，只有当这个计数超过某个选择的大于 1 的阈值时才返回"is"。(你可能想让阈值成比例到集合中的点数，以允许每个像素绘制给定数量的缺陷。)为了获得更多控制，在填充之后，您可以识别并删除所有低于某个固定“缺陷阈值”大小的白色像素岛。可以通过尝试从图像中的每个像素进行泛光填充并在超过阈值大小时停止(并撤消)来完成检测。
所有这些操作，包括检测和去除小缺陷，所花费的时间与图像中的像素数量成线性关系。洪水填充是一种简单而快速的算法，但如果您想要更快的速度，您可以只对给定像素集的边界框进行洪水填充，每边向外扩展 1 个像素。
关于c# - 是否有一种算法可以确定二维空间中的一组点是否形成一个封闭区域？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22697564/