如何查找哪个点存在于哪个多边形中

Question

如何找到一个给定的多边形集合中是否存在一个点？我有坐标像

polygonA = 1(0,0),2(0,5),3(3,4),4(3,5),5( 2,2)
polygonB = 1(10,10),2(10,15),3(13,14),4(13,15),5(12,12)

我有一个点,因为(6,4)现在想要搜索这个点是否在这个多边形中的任何一个或两者中或最接近哪个多边形.

如何存储这样的数据(多边形)？有没有系统/数据库/算法来进行此搜索？

更新:感谢所有人的快速反应......我想我需要更加具体......

如何搜索=是...获得相同的算法和库列表.

如何存储=基于我的研究SQL和NoSQL db有他们的解决方案.NoSQL = MongoDb似乎最接近我需要的东西.但问题是我可以查询"db.places.find({"loc":{"$ within":{"$ polygon":polygonB}}})"但是不能像db.places.find那样进行查询({" loc":{"$ in":{}}}} SQL检查postgre和openGIS以获得一些帮助.但是如果可能的话,colud就不会想出来.

如果有人可以帮助我...提前谢谢.

Answer 1

基本方法（如果多边形数量较少）是将所有多边形存储在集合中，并循环遍历元素以检查点是否位于多边形内部。

另一方面，如果您有相当数量的多边形，我建议使用 R 树数据结构，该结构在标准库中不可用。如果你想使用 R-tree 选项，你应该检查这个项目： http://sourceforge.net/projects/jsi/。

R 树允许您索引矩形（在本例中为多边形的边界框）。因此，您可以使用 R 树非常快速地找到少量候选多边形。然后你可以循环候选列表以获得最终结果。