给定一组多边形和一系列点，找出哪些多边形是所定位的点

本文介绍了给定一组多边形和一系列点，找出哪些多边形是所定位的点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是一个类似于这里的问题，但我认为如果我可以用更一般的术语重新定义它会有所帮助.

This is a question similar to the one here, but I figure that it would be helpful if I can recast it in a more general terms.

我有一组多边形，这些多边形可以相互接触、重叠并且可以呈现任何形状.我的问题是，给定一个点列表，如何设计一种有效的算法来找到这些点所在的多边形?

I have a set of polygons, these polygons can touch one another, overlap and can take on any shape. My question is, given a list of points, how to devise an efficient algorithm that find which polygons are the points located?

点位置的有趣限制之一是，如果有帮助的话，所有点都位于多边形的边缘.

One of the interesting restriction of the location of the points is that, all the points are located at the edges of the polygons, if this helps.

我知道 r-trees 可以提供帮助，但是考虑到我在做一系列的点，有没有更高效的算法，而不是一个一个地计算每个点?

I understand that r-trees can help, but given that I am doing a series of points, is there a more efficient algorithm instead of computing for each point one by one?

推荐答案

此处的关键搜索词是点位置.在这个名称下，计算几何文献中有许多算法用于各种情况，从特殊到一般.例如，这个链接 列出了各种软件包，包括我自己的.(现在有点过时的列表.)

The key search term here is point location. Under that name, there are many algorithms in the computational geometry literature for various cases, from special to general. For example, this link lists various software packages, including my own. (A somewhat out-of-date list now.)

速度和程序复杂性(以及实现工作量)之间存在显着的权衡.最容易编程的方法是使用标准的点中多边形代码，根据每个多边形检查每个点.但这可能会很慢，具体取决于您拥有的多边形数量.更难的是通过扫描平面构建点-位置数据结构并找到所有的边-边交点.请参阅这篇维基百科文章，了解您的一些选择.

There is a significant tradeoff between speed and program complexity (and therefore implementation effort). The easiest-to-program method is to check each point against each polygon, using standard point-in-polygon code. But this could be slow depending on how many polygons you have. More difficult is to build a point-location data structure by sweeping the plane and finding all the edge-edge intersection points. See the this Wikipedia article to see some of your options.