我想构建一个动态数据结构，可以保存多边形列表并返回与指定矩形重叠的多边形列表。
我研究了 bst 树(和四叉树)，但当多边形严重重叠时，这些树似乎效果不佳。
在我胡说八道之前，我应该检查一下有什么好的想法吗？
编辑
让我们假设所有多边形都是正常的非旋转矩形。我愿意在点测试期间接受命中(多边形测试中的点)(无论如何我可能会这样做)，并且在区域测试期间获得他们的边界框同样好。只有一小部分实际上不会与相关区域重叠。
最佳答案
我会看看 2-d segment delaunay graphs .另请参阅 Nef polygons . CGAL对polygons有很多集合操作. question 的答案也可能有值(value)
编辑 如果您的多边形是非旋转矩形，请参阅 R-Trees
关于java - 二维平面上的重叠多边形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3448399/