问题：在正交多边形（Java）中查找重叠的矩形

Question

目标是找到当您来自正交多边形的所有面（北，西，东，南）时得到的所有矩形。但是，我无法进一步了解具体实现。

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

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

public static Polygon getPolygonFromFile(String filePath)
File fXmlFile = null;
Polygon resultPolygon = null; 
try {
// check here whether file exists
fXmlFile = new File(filePath);
} catch (Exception e) {
// what to do if the file doesn't exist
}
// creating Polygon

return resultPolygon;
 }

然后，我想对边缘进行分类，然后将其分类（北或顶，东或右，西或左，南或底），并将其保存在容器中。如果多边形点是逆时针排序的，我将使用以下代码：

enum EdgeType {TOP, BOTTOM, LEFT, RIGHT, EMPTY}

public EdgeType orthoEdgeTypeCCW(double x0, double y0, double x1, double y1)
{
    if(x0 == x1) // vertical
    {           
        return (y0 < y1) ? EdgeType.RIGHT : 
               (y0 > y1) ? EdgeType.LEFT : 
                           EdgeType.EMPTY;
    }
    else if(y0 == y1) // horizontal
    {
        return (x0 < x1) ? EdgeType.BOTTOM : 
               (x0 > x1) ? EdgeType.TOP : 
                           EdgeType.EMPTY;
    }
    else
    {
        throw new IllegalArgumentException("Edge not orthogonal");
    }
}

知道如何将其保存在容器中吗？

所以现在是我的主要问题。我想找到该多边形内的所有矩形，从各个方向（北，东，南，西）开始。我对此步骤有疑问。我想到使用SweepLine算法，但是我不确定如何实现它来获得所需的结果（四面八方的重叠矩形）。为此，我画了那些照片以阐明我的意思。如果您来自多边形的北边缘，则会找到绿色矩形。如果您来自多边形的西边缘，则会发现红色矩形。以及重叠的矩形但是，我不确定如何最简单地执行此操作。我研究了很多扫掠线算法，但是我不确定如何实现它以及这是否是一种有效的方法。我的目标是找到这些矩形并以适当的方式保存它们，以便我可以将其用于其他步骤（例如，在多边形中找到许多矩形重叠的位置）

也许有人可以帮助我。非常感谢！

Answer 1

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

• 遍历边缘。
  • 假设我们在（n.x1，n.y）和（n.x2，n.y）之间有一个朝北的边缘。相应的矩形必须具有其朝北的边缘，即我们刚刚看过的矩形，并且其朝南的边缘必须至少部分地由一个或多个朝南的边缘组成。
  • 我们遍历所有朝南的边缘并找到边缘，使得边缘上的至少一个点的X坐标在（n.x1，n.x2）范围内。
    • 另外，它们实际上必须在朝北的边缘以南，所以将其保留在s.y > n.y处。
  • 现在，剩下的是所有可能会限制矩形高度的所有朝南边缘的列表。但是，矩形受最接近的矩形的限制，因此我们只选择y坐标最低的剩余朝南边缘s。
  • 我们现在在（n.x1，n.y）和（n.x2，s.y）之间有一个矩形。

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