5

如何查找一个点是否存在于给定的一组多边形中？我有坐标

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" : { } } }) S​​QL 检查了 postgre 和 openGIS 以获得一些帮助。但是colud没有弄清楚它是否可能。

如果有人可以帮助我...在此先感谢。

4

2 回答 2

3

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

另一方面，如果你有大量的多边形，我会推荐使用标准库中没有的 R-tree 数据结构。如果你想使用 R-tree 选项，你应该检查这个项目：http: //sourceforge.net/projects/jsi/。

R-tree 允许您索引矩形（在这种情况下为多边形的边界框）。因此，您可以使用 R-tree 非常快速地找到少量候选多边形。然后您可以遍历候选列表以获得最终结果。

于 2012-05-27T13:53:00.710 回答
1

您可以使用 GeneralPath 类来帮助您确定点是否与多边形相交。首先，创建一个添加了坐标的 GeneralPath：

    GeneralPath gp = new GeneralPath();
    double[] x = ...
    double[] y = ...
    gp.moveTo(x[0], y[0]);
    for (int i =1; i < x.length; i++) {
        gp.lineTo(x[i], y[i]);
    }
    gp.closePath();

    if (gp.contains(pointX, pointY)) {
        ...
    }

对于一个点更接近哪个多边形的问题，这在一定程度上取决于您需要解决方案的准确程度。

为了获得准确的解决方案，这相当于（未经优化）：

  • 取点和连接每个多边形顶点的每条线（段）之间的最短距离（Java2D 显然没有为此提供方法，但是从点到线的最短距离是一个相当简单的计算)
  • 哪个多边形的直线到该点的距离最短？

在实践中，您可以为某些应用程序近似此过程。例如，您可以更有效地执行此操作：

  • 取每个多边形的边界矩形的中心点（GeneralPath.getBounds() 会给你这个）
  • 取查询点和每个中心点之间的距离，看看哪个最近。

如果您确实需要一个准确的答案，那么您可以结合这些技术来优化您在所有顶点之间的搜索。例如，您可以按到“中心点”（如上定义）的距离对多边形进行排序。从最小到最大距离搜索。如果到目前为止您找到的线段的最小距离是 d，那么您可以自动排除从查询点到其“中心点”的距离为 d + r 的任何多边形 P，其中 r 是长度的一半P 的边界矩形的对角线（换句话说，为简单起见，您可以想象围绕该边界框的边界圆，并检查到该边界圆的距离是否比迄今为止在其他多边形上找到的最近点更远）。

我不太了解数据库。您的多边形只是定义为一系列点。您如何决定将这些存储在内存/文件中并不会对算法产生任何影响。

于 2012-05-27T15:21:36.253 回答