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 轴)来对多边形集合进行排序(例如 orderbyboundingbox.MinX)，那么您可以 SkipWhile pointOfInterest.Longitude.AsX < poly.boudingBox。敏X。这应该会给您带来性能提升，具体取决于兴趣点在数据集足迹中的位置。

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