英文:
How to find overlapping areas?
问题
目标是在正交多边形的所有边（北、西、东、南）上进行遍历，找出所有从四个方向进入时所获得的矩形。然而，我在具体的实现上无法进一步。
以下是我目前所做的。
首先：我有一系列坐标（在一个XML文件中），我想将它们读入Java中以确定多边形的点和边。
现在来谈谈我的主要问题。我想在这个多边形内找到所有的矩形，从四个方向（北、东、南、西）开始。
如果从多边形的北侧边缘进入，您会找到绿色的矩形。
如果从多边形的西侧边缘进入，您会找到红色的矩形。
这样就得到了重叠的矩形。
然而，我不确定如何以最简单的方式做到这一点。我研究了很多扫描线算法，但我不确定如何实现它，以及这是否是一种高效的方法。我的目标是找到这些矩形并以适当的方式保存它们，以便在进一步的步骤中使用（例如，在多边形中找到许多矩形重叠的位置）。
也许有人可以帮助我。非常感谢！
英文:
the goal is to find all the rectangles you get when you come from all sides (north, west, east, south) in an orthogonal polygon. However, I can't get any further on concrete implementation.
So here is what I've done so far.
First: I have a list of coordinates (in a XML file), I want to read them into Java to determine the points and the edges of the polygon.
So now coming to my main problem. I want to find all rectangles that lie within this polygon,
[![the polygon]starting from all sides (north, east, south, west). I have a problem with this step. It occurred to me to use a SweepLine algorithm, but I am unsure how to implement it to get the desired result (overlapping rectangles coming from all sides). For that I have painted those pictures to clarify what I mean. If you come from the north edges of the polygon you would find the green rectangles. [![rectangles in the polygon coming from the north edges]
If you come from the west edges of the polygon you would find the red rectangles.
[rectangles in the polygon coming from the west edges]
and with that the overlapping rectangles..
[overlap of green and red rectangles]
However, I'm not sure how to do this the most easiest way. I researched a lot sweep line Algorithms, but I'm not sure how to implement it and whether this is an efficient way. My goal is to find those rectangles and save them in a proper way so that I can use them for further steps (e.g. finding positions in the polygon where many rectangles overlap)
Maybe someone could help me with that. Would appreciate this a lot!
答案1
得分: 1
如果您已经了解所有边缘并确定它们是面向北、南、东还是西，那么确定矩形可以按照以下方式进行：
- 遍历所有边缘。
- 假设我们有一个北向边缘位于 (n.x1, n.y) 和 (n.x2, n.y) 之间。相应的矩形必须具有以我们刚刚检查的边缘为北向边缘，并且其南向边缘必须至少部分地由一个或多个南向边缘组成。
- 我们遍历所有南向边缘，并找到其中至少有一个点的 X 坐标位于范围 (n.x1, n.x2) 内的边缘。
- 此外，它们实际上必须位于北向边缘的南侧，因此保留那些满足
s.y > n.y的边缘。
- 此外，它们实际上必须位于北向边缘的南侧，因此保留那些满足
- 现在，我们手头剩下的是一个列表，其中包含了所有可能限制我们矩形高度的南向边缘。然而，矩形受到最近边缘的限制，因此我们只选择剩余的南向边缘 s，其具有最低的 y 坐标。
- 现在，我们得到了一个位于 (n.x1, n.y) 和 (n.x2, s.y) 之间的矩形。
对于每个基本方向都实现了相应的逻辑。
英文:
If you already know all the edges and have determined whether they face North, South, East or West, determining the rectangles could be done like this:
- Iterate through the edges.
- Let's say we have a north-facing edge between (n.x1, n.y) and (n.x2, n.y). The corresponding rectangle must have its north-facing edge be the one we just looked at and its south-facing edge must, at least in part, consist of one or more south-facing edges.
- We iterate through all south-facing edges and find the ones such that at least one point on the edge has an X coordinate within the range (n.x1, n.x2).
- Additionally, they need to actually be south of the north-facing edge, so keep the ones where
s.y > n.y.
- Additionally, they need to actually be south of the north-facing edge, so keep the ones where
- Now, what we have left is a list of all south-facing edges that could possibly limit our rectangle's height. However, the rectangle is limited by whichever is the closest, so we simply pick the remaining south-facing edge, s, with the lowest y coordinate.
- We now have a rectangle between (n.x1, n.y) and (n.x2, s.y).
Corresponding logic is implemented for each cardinal direction.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论