合并和分割重叠的矩形以产生不重叠的矩形 [英] Merging and splitting overlapping rectangles to produce non-overlapping ones

问题描述

给定一组可能重叠的矩形（所有这些都是不旋转的），可以统一表示为（左，上，右，下）连音符等等），它会返回一组最小的（非旋转的）不重叠的矩形，占据相同的区域。

有没有一些已知的方法可以用于这个/ ideas /指针？

方法不一定最小，但启发式小，set也很有趣，所以方法可以产生任何有效的输出集合。

解决方案

基于行扫描算法的东西可以工作，我认为：

• 将所有矩形的最小值和最大值 x 坐标排序为数组，作为start-rectangle和end-rectangle li>
  
• 遍历数组，添加每个ne w矩形遇到（启动事件）到当前集合中
  
• 同时，维护一组将作为输出集合的非重叠矩形
  
• 任何时候当你遇到一个新的矩形时，你都可以检查它是否已经完全包含在当前/输出集合中（简单比较 y -coordinates就足够了）


• 如果不是，则将一个新的矩形添加到您的输出集中，其中 y -coordinates设置为新矩形的一部分，已经覆盖。


• 任何时候您点击矩形结束事件时，都会停止输出集中任何不再覆盖任何东西的矩形。

我不完全确定这是否涵盖了所有内容，但我认为通过调整它可以完成工作。或者至少给你一些想法......）

I am looking for an algorithm as follows:

Given a set of possibly overlapping rectangles (All of which are "not rotated", can be uniformly represented as (left,top,right,bottom) tuplets, etc...), it returns a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

It seems simple enough at first glance, but prooves to be tricky (at least to be done efficiently).

Are there some known methods for this/ideas/pointers?

Methods for not necessarily minimal, but heuristicly small, sets, are interesting as well, so are methods that produce any valid output set at all.

解决方案

Something based on a line-sweep algorithm would work, I think:

• Sort all of your rectangles' min and max x coordinates into an array, as "start-rectangle" and "end-rectangle" events
• Step through the array, adding each new rectangle encountered (start-event) into a current set
• Simultaneously, maintain a set of "non-overlapping rectangles" that will be your output set
• Any time you encounter a new rectangle you can check whether it's completely contained already in the current / output set (simple comparisons of y-coordinates will suffice)
• If it isn't, add a new rectangle to your output set, with y-coordinates set to the part of the new rectangle that isn't already covered.
• Any time you hit a rectangle end-event, stop any rectangles in your output set that aren't covering anything anymore.

I'm not completely sure this covers everything, but I think with some tweaking it should get the job done. Or at least give you some ideas... :)

这篇关于合并和分割重叠的矩形以产生不重叠的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！