使用光线投射算法进行纬度/经度坐标的多边形点测试

Question

我已经成功使用了DotSpace。包含用于测试我的每个点（180万）是否位于我的shapefile中的函数。然而，该算法非常缓慢，因为我正在针对大量点和非常复杂的多边形进行测试。以下是一个示例：http://picload.org/image/igararl/pointshapesel.png

图像中德国的边界是我的shapefile，它用于选择点（简化了，但仍然有140000个顶点），红色矩形是我180万个点所在的区域。

为了在空间经纬度坐标的多边形测试中寻找更快的点，我遇到了光线投射算法：http://alienryderflex.com/polygon/

我把代码翻译成VB.Net，它运行时没有错误，但没有找到任何点/shapefile的交集。我知道纬度/经度坐标的困难，但在德国地区，纬度/经度的坐标与标准笛卡尔坐标系相匹配。

这是我的密码。出于速度优先的原因，我声明全局变量：

Public polyCorners As Integer
Public polyX() As Double
Public polyY() As Double
Public xP, yP As Double
Public constant() As Double
Public multiple() As Double

然后我将我的Shapefile顶点添加到polyCorners列表中（这很有效）：

  Dim ShapefilePoly As Shapefile = Shapefile.OpenFile(TextBox4.Text)
    Dim x As Long = 1
    For Each MyShapeRange As ShapeRange In ShapefilePoly.ShapeIndices
        For Each MyPartRange As PartRange In MyShapeRange.Parts
            For Each MyVertex As Vertex In MyPartRange
                If MyVertex.X > 0 AndAlso MyVertex.Y > 0 Then
                    pointsShape.Add(New PointLatLng(MyVertex.Y, MyVertex.X))
                    ReDim Preserve polyY(x)
                    ReDim Preserve polyX(x)
                    polyY(x) = MyVertex.Y
                    polyX(x) = MyVertex.X
                    x = x + 1
                End If
            Next
        Next
    Next
    ReDim constant(x)
    ReDim multiple(x)

在实际搜索之前，我调用了作者建议的prelc_values（）：

    Private Sub precalc_values()
    Dim i As Integer, j As Integer = polyCorners - 1
    For i = 0 To polyCorners - 1
        If polyY(j) = polyY(i) Then
            constant(i) = polyX(i)
            multiple(i) = 0
        Else
            constant(i) = polyX(i) - (polyY(i) * polyX(j)) / (polyY(j) - polyY(i)) + (polyY(i) * polyX(i)) / (polyY(j) - polyY(i))
            multiple(i) = (polyX(j) - polyX(i)) / (polyY(j) - polyY(i))
        End If
        j = i
    Next
End Sub

最后，我为我的每个lat/lng点调用pointInPolygon（）：

Function LiesWithin(latP As Double, lngP As Double) As Boolean
    LiesWithin = False
    xP = lngP
    yP = latP
    If pointInPolygon() = True Then LiesWithin = True
End Function
Private Function pointInPolygon() As Boolean
    Dim i As Integer, j As Integer = polyCorners - 1
    Dim oddNodes As Boolean = False
    For i = 0 To polyCorners - 1
        If (polyY(i) < yP AndAlso polyY(j) >= yP OrElse polyY(j) < yP AndAlso polyY(i) >= yP) Then
            oddNodes = oddNodes Xor (yP * multiple(i) + constant(i) < xP)
        End If
        j = i
    Next
    Return oddNodes
End Function

所有变量似乎都得到了正确的填充，数组包含我的多边形角，点列表从第一个点到最后一个点都得到了准确的检查。它在不到20秒内完成了180万点的完整列表（相比之下，使用DotSpatial.Contains函数需要1小时30分钟）。有人知道为什么它没有找到任何相交点吗？

Answer 1

好吧，我发现问题的速度比预期的要快：我忘记将Shapefile顶点的数量指定给polyCorners。在我上面的代码中，只需在后添加polyCorners=x

   ReDim constant(x)
   ReDim multiple(x)
   polyCorners = x

也许有人觉得这个代码很有用。我真的很惊讶它有这么快！