der*_*itz 5 java algorithm tree geometry treeset
我正在寻找一种方法来检查矩形的集合(Java TreeSet) - 由一个"可比较的"Java类实现,使用google guavas Range for x和y range - 用于交叉点和孔.我知道一个选项可能是使用kd树,但我不知道如何构建这样一个kd树(对于矩形它应该是4d,不应该吗？)以及如何解决问题(交集,孔).
排序优先考虑y轴上的x轴.
编辑:(尝试重述问题):用例是创建任意表(由2或3个矩形块"header","pre column","data"组成).我必须保证每个块中没有交叉点和孔(即由无效的html或其他表数据源提供)(除此之外,块必须组合在一起).目前(刚刚得到一个想法)我试图保存位置(x,y)被占用的二维数组.最后,所有位置必须恰好占用一次.
有很多方法可以解决这类问题,每种方法都有不同的优点和缺点.这里是其中的一些:
矩形对交点+面积和
查看每对矩形 - 如果两个矩形相交,则存在重叠.添加矩形区域并检查总和是否与画布区域匹配 - 如果区域不匹配,则存在间隙.
绘画
这是您提到的方法:创建具有画布尺寸的2D数组.然后,迭代矩形并将它们"绘制"到数组中.
这种方法的一个优化是坐标压缩.假设你有矩形[(10,20),(15,25)]和[(7,3),(15,25)].您可以查看不同的x坐标(7,10,15)并将它们重新映射到(0,1,2)和不同的y坐标(3,20,25)并将它们重新映射到(0,1, 2).然后,你留下矩形[(1,1),(2,2)]和[(0,0),(2,2)],所以你只需要一个3x3数组用于绘画,而不是26x26阵列.
扫描线算法
从左到右扫描一条线,停在"有趣"点,并跟踪哪些区域被占用.
2D范围树
一种可以在矩形范围内有效执行查询的数据结构.
选哪一个？
这取决于你拥有的矩形的数量,它们在该区域中的分布情况,算法的速度,你愿意承担的复杂程度等等.我提到的前两个算法比后者简单得多.二,所以我建议从那里开始.
更多信息
如果您想了解有关这些算法的更多信息,请尝试在线搜索"矩形联合".最有效的解决方案是扫描线算法.
以下是扫描线算法的几个参考:
参考文献3.通常作为矩形联合的线扫描算法的原始来源给出,但我不得不承认我实际上并没有在网上找到这篇论文,也许是因为它是"未发表"......