一條線是否與多邊形相交？

-1

我重新使用sijipie的代碼在這裏：https://www.mrexcel.com/forum/excel-questions/713005-does-point-fall-within-polygon-visual-basic-applications-function.html 一條線是否與多邊形相交？

我需要做的是決定一條線是否在一個多邊形內。

不可否認，這有點懶，因爲我不會測試每條線與每條邊的交點，因爲我重複了線的中點並測試它們是否爲內點。

我想知道是否有更快的方法來做到這一點。

VBA以下代碼：

Function PolyLineIntersect(lXY As Range, polyXY As Range) As Boolean 
    Dim i As Integer, j As Integer, a As Integer, polySides As Integer 
    Dim Result As Boolean 
    Dim x As Double, y As Double 
    Dim aXY As Variant 
    Dim mXY(1 To 5, 1 To 2) As Integer 
    Dim tXY(1 To 5) As Boolean 

    x = lXY.Cells.value2(1, 1) 
    y = lXY.Cells.value2(1, 2) 
    xb = lXY.Cells.value2(1, 3) 
    yb = lXY.Cells.value2(1, 4) 

    mXY(1, 1) = x 
    mXY(1, 2) = y 
    mXY(2, 1) = xb 
    mXY(2, 2) = yb 
    mXY(3, 1) = (xb + x)/2 
    mXY(3, 2) = (yb + y)/2 
    mXY(4, 1) = (xb + mx1)/2 
    mXY(4, 2) = (yb + my1)/2 
    mXY(5, 1) = (xb + mx1)/2 
    mXY(5, 2) = (yb + my1)/2 

    Result = False 

    aXY = polyXY.Value 

    polySides = polyXY.Rows.Count 
    j = polySides - 1 
    For a = 1 To 5     
     x = mXY(a, 1) 
     y = mXY(a, 2)     
     For i = 1 To polySides      
     If (((aXY(i, 2) < y And aXY(j, 2) >= y) _ 
     Or (aXY(j, 2) < y And aXY(i, 2) >= y)) _ 
     And (aXY(i, 1) <= x Or aXY(j, 1) <= x)) Then     
      Result = Result Xor (aXY(i, 1) + (y - aXY(i, 2))/(aXY(j, 2) - aXY(i, 2)) * (aXY(j, 1) - aXY(i, 1)) < x)        
     End If 
     j = i   
     Next i 
    Next a 
    PolyLineIntersect = Result 

End Function

來源

2017-04-26 EmilyQ

刪除了mathematica標記。如果你認爲它屬於你應該說爲什麼。 – agentp

似乎比CodeOview更適合於StackOverflow。 – xidgel

正式注意。沒有意識到這一點。謝謝你xidgel！ – EmilyQ

檢查所有多邊形頂點是否位於相同的半平面（左或右）相對於使用cross product給定行。如果是，線不會與多邊形相交。

Side = Sign(CrossProduct(L2-L1, P[i] - L1)) 
where L1, L2 are points defining the line, P[i] is i-th polygon vertex

算法在線性時間O（N）中工作，其中N是多邊形頂點數。請注意，對於凸多邊形，結果可能使用二分搜索在O（logN）時間中推導出來。

來源

2017-04-27 06:25:11 MBo

一條線是否與多邊形相交？

回答

相關問題