如何找到可用区域矩形？
谁能帮助我如何在具有 n 个矩形障碍物的边界框区域中绘制空间矩形？ 可能存在任意数量的轴平行矩形障碍物，这不是唯一的情况，因此需要考虑不同的角落情况。 最好使用最大水平条算法吗？ 如何？
问题描述：
1.SUB1和SUB2是障碍物，你不会触及SUB1和SUB2的内部，你需要找到所有SUB外部的所有空闲区域，并用它们创建矩形。
2.您需要在空闲区域矩形上找到所有可能的矩形，相应地从左到右扫描而不与SUB相交；
在这种情况下，最大水平空间矩形的总数应为 7，或者一般为 3n+2（其中 n 是障碍物的数量）： 替代文本 http://img25.imageshack.us/img25/452/pic1gts.png< /a>
替代文本 http://img22.imageshack.us/img22/3417/pic2h .png
替代文本 http://img16.imageshack.us/img16/ 5818/pic3h.png
替代文本 http://img13.imageshack.us /img13/2151/pic4.png
点击查看图片： http://img25.imageshack.us/img25/452/pic1gts.png http://img22.imageshack.us/img22/3417/pic2h.png http://img16.imageshack.us/img16/5818/pic3h.png http://img13.imageshack.us/img13/2151/pic4.png
Can anyone help me on how to draw rectangles for space in a bounding box region with n rectangular obstacles? There could be any number of axis parallel rectangular obstacles, this is not a unique case, thus different corner cases needs to be taken into consideration. Is it best to use maximal horizontal strip algorithm? And how?
Problem Description:
1.SUB1 and SUB2 are the obstacles and you will not touch the internal of SUB1 and SUB2, you need to find all the free areas externally to all SUBs and create rectangles out of them.
2.You will need to find all the possible rectangles on the free areas rectangles accordingly with its sweep through from left to right without intersecting the SUBs;
The total number of maximal horizontal space rectangles in this case should be 7 or in general, 3n+2 (where n being the number of obstacles):
alt text http://img25.imageshack.us/img25/452/pic1gts.png
alt text http://img22.imageshack.us/img22/3417/pic2h.png
alt text http://img16.imageshack.us/img16/5818/pic3h.png
alt text http://img13.imageshack.us/img13/2151/pic4.png
Click to view images:
http://img25.imageshack.us/img25/452/pic1gts.png
http://img22.imageshack.us/img22/3417/pic2h.png
http://img16.imageshack.us/img16/5818/pic3h.png
http://img13.imageshack.us/img13/2151/pic4.png
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您是在寻找最简单的算法，还是寻找最少分割矩形的最佳算法？
从最容易编码的算法作为基线开始，这本身对于许多应用程序来说可能已经足够好了。 这很容易编写和理解。
初始化矩形列表以仅包含一个，即屏幕矩形。
现在，对于每个障碍物，迭代矩形列表。 如果矩形与障碍物相交，则从列表中删除该矩形并插入新的、较小的矩形来避开障碍物。 这是一个小子问题，只需查看障碍物的哪一部分与矩形相交即可轻松解决。 您最终可能会得到 0、1、2、3 或 4 个新的子矩形。 （考虑障碍物与一个角、两个角、所有角、无角且无边、无角与 1 个边、无角与 2 个边相交的六种情况。）
对所有障碍物重复上述操作，您将得到一个列表分割的矩形可以覆盖您的区域而不会碰到障碍物。 虽然数量不算少，但它是一个很好的起点，只需 10 分钟即可编写代码。
Are you looking for the simplest algorithm, or the one that finds the optimally fewest split rectangles?
Start with the easiest-to-code algorithm as a baseline, which is likely good enough for many applications by itself. This is easy to write and understand.
Initialize your list of rectangles to include just one, the screen rectangle.
Now, for each obstacle, iterate through the rectangle list. If the rectangle intersects with the obstacle, remove the rectangle from the list and insert new, smaller rectangles that avoid the obstacle. This is a small subproblem, easy to solve by just looking at what part of the obstacle intersects the rectangle. You may end up with 0, 1, 2, 3, or 4 new subrectangles. (consider the six cases where the obstacle intersects one corner, two corners, all corners, no corners and no edge, no corners and 1 edge, no corners and 2 edges.)
Repeat for all obstacles, and you're left with a list of split rectangles that cover your area without hitting the obstacles. It's not optimally few, but it's a good place to start and 10 minutes to code.
是的，我正在寻找最少的最佳分割矩形。
我想对您的建议进行一些澄清。
“初始化矩形列表以仅包含一个，即屏幕矩形”。
屏幕矩形是指外部边界画布吗？ 然后，矩形列表中只有一个矩形。
“现在，对于每个障碍物，迭代矩形列表。如果矩形与障碍物相交，则从列表中删除该矩形并插入新的、较小的矩形来避开障碍物。”
要继续上述操作，我是否应该根据障碍物的每个共线边缘（4 个边缘 - 左、右、上、下）进行比较？ 这意味着检查 4 个角点处的每个 SUB1 和 SUB2 边是否彼此相交或与画布边界框相交。 这是正确的吗？
Yes, I am looking to find the optimally fewest split rectangles.
I would like to get a little bit of clarification on your suggestion.
"Initialize your list of rectangles to include just one, the screen rectangle".
By screen rectangle, do you mean the outer bounding canvas? Then, I would only have a single rectangle in the Rectangle List.
"Now, for each obstacle, iterate through the rectangle list. If the rectangle intersects with the obstacle, remove the rectangle from the list and insert new, smaller rectangles that avoid the obstacle."
To proceed with above, should I make comparison based on each collinear edges of the obstacles (4 edges - left, right, top, bottom)? Meaning each SUB1 and SUB2 edges at 4 corner points are examine to see whether it intersects with each other or the canvas bounding box. Is this right?
角缝合数据结构可以为您做到这一点。 但我不知道有任何开源实现。 原始的（或者至少是规范的）论文是 Ousterhout（Tcl 出名）：http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html
The corner-stitching data structure can do this for you. I don't know of any open-source implementations though. The original, or at least canonical, paper for this is Ousterhout (of Tcl fame): http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html