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

本文关键字：最佳 方法 数据结构 多边形 查找 包含 坐标 | 更新日期: 2023-09-27 18:34:43

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

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

如何

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

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

首先，如果尚未执行此操作，则应为每个多边形提供一个边界框。 这是完全包含多边形的最小矩形。 您可以在创建多边形时指定边界框，如果调整多边形的大小，则调整 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边界框。MinX(，然后你可以跳过SkipWhile pointOfInterest.Longitude.AsX

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

相关文章：