如何确定点是否存在于多边形内部

Question

如何确定点是否存在于多边形内部

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数据库都有解决方案。NoSQL = MongoDb似乎最接近我所需的。但问题是我可以查询像“db.places.find（{“loc”：{“$within”：{“$polygon”：polygonB}}}}）”，但无法进行查询像db.places.find（{"loc" : { "$within" : { } } }）。SQL检查了postgre和openGIS以获得一些帮助。但是我无法确定是否可能。

如果有人能帮我解决这个问题...提前感谢。

- Jigar Shah

你的多边形是凸多边形、凹多边形还是自交多边形？ - nhahtdh

射线投射 - Jens

1

请参考此答案。 - trashgod

@nhahtdh，这有什么关系？ - Beta

@Beta - 一些算法对于某些类型的多边形来说效率低下或者不起作用，这就是为什么它很重要的原因。然而，有些算法涵盖了所有情况（如果我没记错的话），但是不如特殊情况算法快速。 - Zéychin

显示剩余2条评论

2个回答

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，则可以自动排除任何多边形P，其中从查询点到其“中心点”的距离为d + r，其中r是P的边界矩形对角线长度的一半（换句话说，为了简单起见，您可以想象一个围绕该边界框的边界圆，并检查到其他多边形迄今为止找到的最近点的距离是否比该边界圆更远）。

我不太理解关于数据库的部分。您的多边形只是由一系列点定义的。您决定如何将它们存储在内存/文件中并不会对算法产生任何实质性影响。

- Neil Coffey

准确的解决方案有点奇怪。我认为方法应该是：您必须计算到线段的最短距离，在其中对于多边形的每个线段，您必须计算一次到线的距离和两次到点的距离。对于自相交的多边形，这可能有点不明确。 - nhahtdh

忽略自相交多边形的情况。 - Neil Coffey

抱歉，我现在明白了——我们定义方式是一样的，但我混淆了术语。我所说的“顶点”实际上指的是“连接顶点的线/线段”（因此我提到了计算点到线距离的算法，例如）。对于混淆造成的困扰，我感到非常抱歉——我已经在上面进行了更正。 - Neil Coffey

抱歉，但我仍然不满意：到一条无界的直线的最短距离和到一条有界的线段的最短距离是不同的。对于到一条线段的最短距离，你需要比较3个距离：到相应的（无界的）直线的距离，以及到该线段的2个顶点的距离，并取最小值。 - nhahtdh

好的，我指的是定义多边形周长一部分的实际线条。也许有些秘密会议我错过了，在那里“line”这个词只能用英语表示无限制的线条。但希望我的表述足够清晰明了。 - Neil Coffey

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hakan Serce · Accepted Answer

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

另一方面，如果你有大量的多边形，我建议使用R-tree数据结构，这不是标准库中提供的。如果你想使用R-tree选项，请查看此项目：http://sourceforge.net/projects/jsi/。

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