相关疑难解决方法(0)

我有很多多边形,在我做了所有这些多边形的联合之后,我得到了一个新的大多边形.联合算法是一个黑盒子,使用我无法控制的第三方库过程,我也不希望从任何进展中提取任何信息.

对于那个巨大的巨大联合多边形的每个边缘,它是否有效的方法让我知道哪个属于较小多边形的哪个边缘？

解决这个问题的一种强力方法是将工会化多边形的每个边缘与每个较小的多边形进行比较,但这将是非常低效的.还有其他更有效的技术吗？

我的预感告诉我,扫描线算法可能会有所帮助,虽然我完全不知道如何做到这一点.

编辑:小的npolygons可以重叠,因此union多边形可以包含位于小多边形边缘的点,但这些点可能不是原始多边形的顶点.

截图如下所示:

我有一组多边形区域(地理围栏).这组数据是固定的; 所以不需要插入和删除数据.哪个数据结构可用于搜索查询点(经度,纬度)所在的区域？

注意:我已经成功地为一组点实现了KD-Tree(实际上是一个2D树).但它不适用于这个问题.我已经实现了一个R-Tree; 它解决了问题,但它很慢(或我的实施很糟糕).

谢谢

注意:我从事过R-Tree实现,现在工作正常.

我的问题几乎与此类似.但就我而言,多边形不一定相互接触/重叠.它们遍布整个空间.

我有一大堆这样的多边形.同样,我有很多积分.我目前正在运行一个RoR模块,一次取1个点并一次检查相对于1个多边形的交点.数据库是PostGIS.表现很慢.

有没有更快或最佳的方式这样做？

我无法弄清楚如何以表演方式实现这一点,所以我决定问你们.

我有一个矩形列表 - 实际上atm只有正方形,但我可能不得不稍后迁移到矩形,所以让我们坚持它们并保持它更一般 - 在二维空间中.每个矩形由两个点指定,矩形可以重叠,我不太关心设置时间,因为矩形基本上是静态的,并且有一些预先计算任何设置内容的空间(如构建树,排序,预先计算其他向量,等等).哦,如果有任何问题,我正在开发JavaScript.

对于我的实际问题:给出一个观点,我如何得到一组包含该点的所有矩形？

线性方法表现不佳.所以我寻找比O(n)更好的东西.我读了一些东西,比如在Bounding Volume Hierarchies和类似的东西上,但无论我尝试了矩形可以重叠的事实(我实际上想要得到所有这些,如果点在多个矩形内)似乎总是进入我的方式.

有什么建议吗？我错过了一些明显的事吗？BVH是否适用于可能重叠的边界？如果是这样,我如何构建这样一个可能重叠的树？如果没有,我还能用什么？如果边界在内部,外部或未确定,我不关心.

如果有人能想出任何有用的东西,比如链接或咆哮我是多么愚蠢的使用BVH而不是Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem我真的很感激!

编辑:好的,我和R-Trees玩了一下,这正是我想要的.事实上,我正在使用endy_c 建议的RTree实现http://stackulator.com/rtree/.它表现得非常好,完全满足了我的要求.非常感谢您的支持!