java - 如何找到重叠区域？

Question

目标是在正交多边形中找到从四面八方（北、西、东、南）获得的所有矩形。但是，我无法进一步了解具体实施。

所以这是我到目前为止所做的。

首先：我有一个坐标列表（在 XML 文件中），我想将它们读入 Java 以确定多边形的点和边缘。

所以现在来解决我的主要问题。我想找到位于这个多边形内的所有矩形，[！[多边形]从所有边（北，东，南，西）开始。这一步我有问题。我突然想到使用 SweepLine 算法，但我不确定如何实现它以获得所需的结果（来自各个方面的重叠矩形）。为此，我画了这些照片以澄清我的意思。如果您来自多边形的北边，您会发现绿色矩形。[![多边形中来自北边的矩形] 如果你来自多边形的西边，你会发现红色矩形。[来自西边缘的多边形中的矩形] 以及重叠的矩形.. [绿色和红色矩形的重叠] 但是，我不确定如何以最简单的方式做到这一点。我研究了很多扫线算法，但我不确定如何实现它以及这是否是一种有效的方法。我的目标是找到这些矩形并以适当的方式保存它们，以便我可以将它们用于进一步的步骤（例如在多边形中找到许多矩形重叠的位置）

也许有人可以帮助我。将不胜感激！

标签： java

Answer 1

如果您已经知道所有的边并且已经确定它们是面向北、南、东还是西，那么可以像这样确定矩形：

• 遍历边缘。
  • 假设我们在 (n.x1, ny) 和 (n.x2, ny) 之间有一个朝北的边缘。对应的矩形的北边必须是我们刚刚看到的那个，并且它的南边必须至少部分地由一个或多个朝南的边组成。
  • 我们遍历所有朝南的边缘，并找到边缘上的至少一个点的 X 坐标在 (n.x1, n.x2) 范围内的那些。
    • 此外，它们实际上需要位于朝北边缘的南部，因此请保留s.y > n.y.
  • 现在，我们剩下的是所有可能限制矩形高度的朝南边缘的列表。但是，矩形受最接近的那个限制，因此我们只需选择剩余的朝南边 s，其 y 坐标最低。
  • 我们现在在 (n.x1, ny) 和 (n.x2, sy) 之间有一个矩形。

为每个基本方向实现相应的逻辑。