c# 查找包含坐标的所有多边形的最佳方法/数据结构？

Question

我有大约 10,000 个由纬度/经度点组成的多边形。每个多边形都有关于它是什么以及它包含什么的元数据。所有多边形都可以相互相交。

我现在想做的是获取所有包含特定纬度/经度点的多边形。

这样做的有效方法是什么？有没有比遍历所有多边形并分别检查它们更快的方法？是否有某种智能索引数据结构，我可以在其中存储多边形以便我可以在 C# 中执行此类查询？

Answer 1

首先，如果您还没有这样做，您应该给每个多边形一个边界框。这是完全包含多边形的最小矩形。您在创建多边形时分配边界框，并在调整多边形大小时调整 BB 的大小。

可以快速检查每个多边形是否可能包含该点:

// untested code
// in scope is pointOfInterest
var candidatePolygons = from poly in allPolygons
                           where poly.BoundingBox.contains(pointOfInterest)
                           select poly;

. . .

// method of BoundingBox class
public Boolean contains(LatLongClass pointOfInterest)
{
   return pointOfInterest.Longitude.AsX >= this.minX &&
          pointOfInterest.Longitude.AsX <= this.maxX &&
          pointOfInterest.Latitude.AsY >= this.minY &&
          pointOfInterest.Latitude.AsY <= this.maxY;
}

对于每个多边形，这证明该多边形肯定不包含该点，并且它应该很快消除大部分多边形。

会有一些多边形的边界框包含点但多边形不包含。这些必须使用较慢的方法进行检查，但至少您没有对所有这些都使用较慢的方法。

此外，如果您还没有使用 PLinq(来自 allPolygons.AsParallel() 中的 poly )用于两个过滤器(边界框和较慢的测试)。

参见 http://msdn.microsoft.com/en-us/library/dd997425.aspx和 How exactly does AsParallel work?

按照 Sinatr 的评论，如果您选择一个轴(可能是 x 轴)来对多边形集合进行排序(比如 orderby boundingbox.MinX)，那么您可以 SkipWhile pointOfInterest.Longitude.AsX < poly.boudingBox。 MinX。这应该会提升性能，具体取决于 pointOfInterest 在数据集足迹中的位置。

最后一件事:您不仅应该为每个多边形设置一个边界框，还应该考虑为您的整个数据集设置一个边界框。这样，如果调用者向您发送了一个超出您足迹的点，您可以通过非常快速地检查大型“全局”边界框来消除所有多边形，并且处理时间不会明显增加 -足迹点。