algorithm - 如何有效地检测和去除形状中的非连接线

Question

我希望执行多边形点检查，但首先需要从多边形中删除冗余线，以便我可以执行光线投射算法。多边形以二维二进制数组表示（1 表示填充，0 表示空）。冗余线被认为在任一端有一个点，该点没有填充至少 2 个直接相邻的单元格（即北、东、南和/或西，但不是对角线）。

具有连接点的线示例（白色 = 空，蓝色 = 填充）：

以断开点结尾的线条示例（白色 = 空，蓝色 = 填充，绿色 = 填充但断开）：

多边形示例（白色 = 空，蓝色 = 填充，绿色 = 删除）：

删除冗余点后的多边形示例（白色 = 空，蓝色 = 填充）：

一个简单但效率极低的算法是检测具有少于 2 个相邻填充点的点，然后删除这些点并循环，直到没有进行任何更改。解决这个问题的更有效方法是什么？

旁注：我知道填充点的 2x2（或更大）区域将被视为相互连接，因此不会被删除 - 这是故意的。我也知道，当我到达光线投射算法时，光线投射测试需要考虑水平线和垂直线。

标签： algorithmpolygonpoint-in-polygon