如何找到一组任意放置的非重叠矩形的自然边界多边形？
How can I find a natural border polygon of a set of arbitrarily placed non-overlapping rectangles?
给定一组任意放置的、不重叠的矩形；我怎样才能找到一个代表构成矩形的点周围的自然边界的多边形？举例说明：
如何找到绿线或蓝线？我已经尝试过，但没有成功：
- 使用寻路行走。我努力寻找一种有意义的启发式方法。
- 使用距离阈值行走并根据前两点矢量的角度选择下一个（例如始终右转）。这有点管用，但有很多奇怪的边缘情况没有。
- 从最左、最上、最右和最底部点的初始菱形开始，按程序构建多边形。想法是检测一个点是否已经在polgyon内部，如果是的话就忽略它，但是当我需要插入时我不知道如何确定插入位置。
我不确定我是否遗漏了一些明显的东西，或者这实际上是一个比我最初预期的更难的问题。
这是一个启发式的方法。计算船体 H1
矩形。现在计算船体 H2
不在 H1 上的矩形角。
所以现在你有两个嵌套的凸包。
考虑将 H1 的边 e 移动到
H2 的顶点 v。
一些这样的举动可以被排除在外，因为这两个新的
边穿过一个矩形。选择接受最小的
e 和 v 形成的三角形的高度，
如下图所示。
给定一组任意放置的、不重叠的矩形；我怎样才能找到一个代表构成矩形的点周围的自然边界的多边形？举例说明：
如何找到绿线或蓝线？我已经尝试过，但没有成功：
- 使用寻路行走。我努力寻找一种有意义的启发式方法。
- 使用距离阈值行走并根据前两点矢量的角度选择下一个（例如始终右转）。这有点管用，但有很多奇怪的边缘情况没有。
- 从最左、最上、最右和最底部点的初始菱形开始，按程序构建多边形。想法是检测一个点是否已经在polgyon内部，如果是的话就忽略它，但是当我需要插入时我不知道如何确定插入位置。
我不确定我是否遗漏了一些明显的东西，或者这实际上是一个比我最初预期的更难的问题。
这是一个启发式的方法。计算船体 H1 矩形。现在计算船体 H2 不在 H1 上的矩形角。 所以现在你有两个嵌套的凸包。 考虑将 H1 的边 e 移动到 H2 的顶点 v。 一些这样的举动可以被排除在外，因为这两个新的 边穿过一个矩形。选择接受最小的 e 和 v 形成的三角形的高度， 如下图所示。