如何找到一个点是否存在于多边形中 [英] How to find if a point exists in which polygon
问题描述
如何找到一个点是否存在于给定的多边形集合中?
我的坐标就像
$ b $ pre $ 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:{$ within:{}}})
SQL检查了postgre和openGIS的一些帮助。但如果有可能的话,colud并不知道。
如果有人可以帮我解决这个问题...提前致谢
另一方面,如果您有相当多的多边形,我会推荐使用R-tree数据结构,这在标准库中是不可用的。你应该检查这个项目,如果你想使用R-tree选项: http://sourceforge.net/projects / bsi / 。
R-tree允许您索引矩形(在这种情况下为多边形的边界框)。因此,您可以使用R-tree非常快速地找到少量候选多边形。然后,您可以遍历候选人列表以获得最终结果。
How to find if a point exists in which given set of polygons ? I have coordinates like
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)
I have a point as (6,4) now want to search if this point is in any of this polygon or in both or nearest to which polygon.
How to store such data (polygon) ? is there a system / database / algorithm to do this search ?
Update : Thanks all for such fast response...I think i need to be more specific...
How to search = Yes...got list of algorithms and library for the same.
How to store = based on my research SQL and NoSQL db have their solutions. NoSQL = MongoDb seems closest what i needed. But issue is I can query like "db.places.find({ "loc" : { "$within" : { "$polygon" : polygonB } } })" But cant make query like db.places.find({ "loc" : { "$within" : { } } }) SQL checked postgre and openGIS for some help. But colud not figureout if its possible.
If someone can help me with that...Thanks in advance.
The basic method (if you have a small number of polygons) is to store all polygons in a collection and loop over the elements to check if a point is inside a polygon.
On the other hand, if you have a considerable number of polygons, I would recommend using an R-tree data structure, which is not available in the standard library. You should check this project, if you want to go with R-tree option: http://sourceforge.net/projects/jsi/.
R-tree allows you to index rectangles (bounding boxes of the polygons in this case). So you can find a small number of candidate polygons very fast using R-tree. Then you can loop over the candidate list to get the final result.
这篇关于如何找到一个点是否存在于多边形中的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!