如何找到一组任意放置的非重叠矩形的自然边界多边形?

给出一组任意放置的,不重叠的矩形;我如何找到代表组成矩形的点周围的自然边界的多边形?举例说明:

如何找到一组任意放置的非重叠矩形的自然边界多边形?

如何找到绿线或蓝线?我已经尝试过但没有成功:

  • 使用寻路行走。我努力寻找一种有意义的启发式方法。
  • 使用距离阈值步行,然后根据前两个点的矢量的角度选择下一个(例如,始终向右转)。这种方法行得通,但有很多奇怪的情况却没有。
  • 从最左侧,最顶部,最右侧和最底部的初始菱形开始,按照程序构建多边形。这个想法是要检测一个点是否已经在polgyon中,在这种情况下可以忽略它,但是当我需要插入时,我不知道如何确定插入位置。

我不确定是否遗漏了明显的东西,或者这实际上是否比我最初预期的要难。

zhangxiaoqi525 回答:如何找到一组任意放置的非重叠矩形的自然边界多边形?

这是一种启发式方法。计算船体的 H 1 矩形。现在计算船体 H 2 不在 H 1 上的矩形角。 因此,现在您有两个嵌套的凸包。 考虑将 H 1 的边 e 移动到 H 2 的顶点 v 。 可以排除某些此类动作,因为这两个新动作 边缘穿过矩形。选择接受最小的 由 e v 形成的三角形的高度, 如下图所示。


HullOnion


本文链接:https://www.f2er.com/3115841.html

大家都在问