algorithm - 将n组顶点减少为矩形？

Question

我试图将一组n个顶点减少到m个矩形（点不在网格上，并且是用户定义的）。

最简单的情况是检查 4 个节点，并确认唯一距离少于 3 个，这将导致 1 个矩形形状。但是，考虑到每个顶点子集形成一个矩形，我希望将n个顶点减少为多个矩形。我很高兴矩形是对角的，并且不介意它是否只是一个矩形的近似值（例如，它悬挂在一个顶点上以形成一个矩形）。我也很高兴形状重叠。

当前输入是用户定义的：

• 用户单击以放置“节点”，可以连接节点以创建“边”（每条边最多 2 个节点，但每个节点有多个边）。
• 节点的每个“边”都有一个开始和结束位置（创建它的两个节点）
• 用户点击可以是非网格的，也可以是网格上的（网格大小是用户定义的，所以遗憾的是没有洪水填充算法）

我已经确定了一个合理的解决方案：

1. 在节点集中选择随机边
2. 在所有边上使用A Star算法，所选边是开始和结束位置，但不允许算法在第一个实例中遍历该边
3. 如果有返回边缘的路径，我们发现了一个封闭的形状
4. 字符串拉取结果路径（即简化路径，删除同一行上的节点/边以减少路径数）
5. 对矩形进行有效性检查，例如不超过 3 个唯一距离
6. 对未包含在该路径中的任何节点重复该过程

不幸的是，这对我的应用程序来说在计算上是相当昂贵的，我希望在运行时做到这一点。有没有人有任何改进上述方法的建议，或者知道另一种更好的方法？

标签： algorithmtopology