2

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

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

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

4

1 回答 1

2

首先，如果你还没有这样做，你应该给每个多边形一个边界框。这是完全包含多边形的最小矩形。创建多边形时分配边界框，如果调整多边形大小，则调整 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以及AsParallel 究竟是如何工作的？

根据 Sinatr 的评论，如果您选择一个轴（可能是 x 轴）来对多边形集合进行排序（例如 orderby boundingbox.MinX），那么您可以 SkipWhile pointOfInterest.Longitude.AsX < poly.boudingBox.MinX。这应该会根据 pointOfInterest 在数据集足迹中的位置为您提供性能提升。

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

于 2013-10-10T15:48:15.693 回答