Befindet sich Punkt in Polygon?

  • Hallo liebe Com,

    muss euch heute leider wieder mit einer Frage quälen:
    Ich brauche eine Funktion, an die ich Punkte in einem Array übergebe.
    Nun möchte ich anhand dieser Punkte prüfen, ob sich ein anderer Punkt in diesem Polygon befindet - die Eckzahl muss jedoch variabel sein! Habe schon brav Tante Google und Onkel Forensuche verwendet, jedoch nichts gefunden.

    Mir fehlt einfach die zündende Idee, wie das umzusetzen ist. Im Prinzip muss ich ja erkennen, ob die Koordinaten des Punktes innerhalb eines bestimmten Rahmens sind, und diesen anpassen - für Dreiecke und Rechtecke dürfte das ja kein Problem sein, aber wie sieht es mit Vielecken (Polygonen) aus? Mir fehlt einfach die Idee, deshalb habe ich auch noch kein Script, dass ich vorzeigen könnte. Ich weiß, das ist hier nicht das Machmirmalforum, deswegen würde ich auch gerne einfach einen Lösungsvorschlag haben. (eine Funktion wäre natürlich trotzdem toll)

    Viele Grüße & Dank im Vorraus,
    stayawayknight

    Einmal editiert, zuletzt von stayawayknight (7. Februar 2011 um 15:36)

  • @Xeno:
    Ja, genau. Beispiel:

    Spoiler anzeigen
    [autoit]


    #include <Array.au3>
    Dim $aPoints[11][2]

    [/autoit] [autoit][/autoit] [autoit]

    $aPoints[0][0] = 10 ;Anzahl der Punkte

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 1 To UBound($aPoints, 1) - 1
    $aPoints[$i][0] = Random(0, 500, 1) ;X-Koordinate
    $aPoints[$i][1] = Random(0, 500, 1) ;Y-Koordinate
    Next

    [/autoit] [autoit][/autoit] [autoit]

    _ArrayDisplay($aPoints)

    [/autoit] [autoit][/autoit] [autoit]

    $PointSearchX = 180 ;X -Punkt, der gesucht werden soll (Variabel)! Liegt er in dem oben durch Punkte markiertem Polygon?
    $PointSearchY = 300 ;Y

    [/autoit]

    i2c: Sieht auf jeden Fall schonmal gut aus! Ich lese es mir mal durch, danke!
    @Prog@ndy: Vom Funktionsnamen spricht schonmal alles dafür! Danke schonmal, die Funktion sieht vielversprechend aus - nur was ist mit Handle zur Region gemeint?

    Danke euch allen schonmal für die Mühe!

    Einmal editiert, zuletzt von stayawayknight (7. Februar 2011 um 15:23)

  • Hi,
    damit hatte ich mich auch schon HIERrumgequält. Und da ging es nur um "billige" Vierecke...
    Es gibt zwar Funktionen für Rechtecke, aber die sind aufwendig!

    Schlussendlich habe ich das Problem einfach umgangen 8o. Ich habe es dann in etwa so gelöst:
    Sei n=Anzahl der Eckpunkte
    Geradengleichung aufstellen für alle Kanten zwischen P(0) und P(n). (Punkte rechtsrum bezeichnen) P(n+1)=P0
    PX ist der zu untersuchende Punkt

    Code
    setPX="INNERHALB"
    for i=0 to n+1
    wenn  PX sich LINKS von Gerade P(i)P(i+1) befindet, dann setPX="AUSSERHALB":exitloop
    next
  • Vielleicht hilft dir dies weiter:

    Spoiler anzeigen
    [autoit]


    ;http://www.autoitscript.com/forum/index.php?showtopic=89034
    #include <GuiConstantsEx.au3>
    #include <GDIPlus.au3>
    #include <WinAPI.au3>
    #include <WindowsConstants.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Opt('MustDeclareVars', 1)
    Opt("MouseCoordMode", 2);1=absolute, 0=relative, 2=client

    [/autoit] [autoit][/autoit] [autoit]

    Global $hGUI, $hBMPBuff, $hGraphicGUI, $hGraphic

    [/autoit] [autoit][/autoit] [autoit]

    _Main()

    [/autoit] [autoit][/autoit] [autoit]

    Func _Main()
    Local $msg, $aPos, $GuiSizeX = 400, $GuiSizeY = 300
    Local $aPoints[7][2], $aTriangle[5][2]
    Local $hButton
    ; Create GUI
    $hGUI = GUICreate("GDI+", $GuiSizeX, $GuiSizeY)

    [/autoit] [autoit][/autoit] [autoit]

    GUISetState()

    [/autoit] [autoit][/autoit] [autoit]

    _GDIPlus_Startup()
    ;Double Buffer
    $hGraphicGUI = _GDIPlus_GraphicsCreateFromHWND($hGUI)
    $hBMPBuff = _GDIPlus_BitmapCreateFromGraphics($GuiSizeX, $GuiSizeY - 65, $hGraphicGUI)
    $hGraphic = _GDIPlus_ImageGetGraphicsContext($hBMPBuff)
    ;End Double Buffer add-on 1 of 3

    [/autoit] [autoit][/autoit] [autoit]

    _GDIPlus_GraphicsClear($hGraphic, 0xFFE8FFEF)

    [/autoit] [autoit][/autoit] [autoit]

    $aPoints[0][0] = 5; Number of sides of Polygon
    $aPoints[1][0] = 100
    $aPoints[1][1] = 100
    $aPoints[2][0] = 200
    $aPoints[2][1] = 150
    $aPoints[3][0] = 200
    $aPoints[3][1] = 200
    $aPoints[4][0] = 150
    $aPoints[4][1] = 100
    $aPoints[5][0] = 70
    $aPoints[5][1] = 200
    $aPoints[6][0] = 100;Last point same as 1st point. Polygon is closed
    $aPoints[6][1] = 100
    _GDIPlus_GraphicsFillPolygon($hGraphic, $aPoints)

    [/autoit] [autoit][/autoit] [autoit]

    Local $iRectX = 220, $iRectY = 25, $iRectWidth = 100, $iRectHth = 50
    _GDIPlus_GraphicsDrawRect($hGraphic, $iRectX, $iRectY, $iRectWidth, $iRectHth)

    [/autoit] [autoit][/autoit] [autoit]

    Local $iElpsX = 220, $iElpsY = 180, $iElpsWidth = 130, $iElpsHth = 70
    _GDIPlus_GraphicsDrawEllipse($hGraphic, $iElpsX, $iElpsY, $iElpsWidth, $iElpsHth)

    [/autoit] [autoit][/autoit] [autoit]

    $aTriangle[0][0] = 3; Number of sides of Polygon
    $aTriangle[1][0] = 30
    $aTriangle[1][1] = 30
    $aTriangle[2][0] = 150
    $aTriangle[2][1] = 40
    $aTriangle[3][0] = 50
    $aTriangle[3][1] = 100
    $aTriangle[4][0] = 30;Last point same as 1st point. Polygon is closed
    $aTriangle[4][1] = 30
    _GDIPlus_GraphicsFillPolygon($hGraphic, $aTriangle)

    [/autoit] [autoit][/autoit] [autoit]

    $hButton = GUICtrlCreateButton("In Circle", 22, 240, 75, 20)

    [/autoit] [autoit][/autoit] [autoit]

    Local $iCircleX = 20, $iCircleY = 210, $iCircleWidth = 80, $iCircleHth = 80
    _GDIPlus_GraphicsFillEllipse($hGraphic, $iCircleX, $iCircleY, $iCircleWidth, $iCircleHth)

    [/autoit] [autoit][/autoit] [autoit]

    ConsoleWrite("Area of Polygon = " & _AreaPoly($aPoints) & @CRLF)
    Local $aCent = _CentroidPoly($aPoints)
    ConsoleWrite("Centroid of Polygon: cX = " & $aCent[0] & " cY = " & $aCent[1] & @CRLF)

    [/autoit] [autoit][/autoit] [autoit]

    ; Create Double Buffer, doesn't need to be repainted on PAINT-Event
    GUIRegisterMsg(0xF, "MY_PAINT"); Register PAINT-Event 0x000F = $WM_PAINT (WindowsConstants.au3)
    GUIRegisterMsg(0x85, "MY_PAINT"); $WM_NCPAINT = 0x0085 (WindowsConstants.au3)Restore after Minimize.
    _GDIPlus_GraphicsDrawImage($hGraphicGUI, $hBMPBuff, 0, 0)
    ;End Double Buffer add-on 2 of 3

    [/autoit] [autoit][/autoit] [autoit]

    While 1
    $msg = GUIGetMsg()
    Switch $msg
    Case $GUI_EVENT_CLOSE
    _GDIPlus_GraphicsDispose($hGraphic)
    _GDIPlus_GraphicsDispose($hGraphicGUI)
    _WinAPI_DeleteObject($hBMPBuff)
    _GDIPlus_Shutdown()
    Exit
    Case $hButton
    MsgBox(0, "", "Button Pressed. ")
    Case $GUI_EVENT_MOUSEMOVE
    $aPos = MouseGetPos()
    ToolTip("Mouse Position X: " & $aPos[0] & " Y: " & $aPos[1] & @CRLF & @CRLF & _
    "Cursor in Polygon: " & _PointInPoly($aPos[0], $aPos[1], $aPoints) & @CRLF & _
    "Cursor in Triangle: " & _PointInPoly($aPos[0], $aPos[1], $aTriangle) & @CRLF & _
    "Cursor in Ellipse: " & _PointInEllipse($aPos[0], $aPos[1], $iElpsX, $iElpsY, _
    $iElpsWidth, $iElpsHth) & @CRLF & _
    "Cursor in Circle: " & _PointInEllipse($aPos[0], $aPos[1], $iCircleX, $iCircleY, _
    $iCircleWidth, $iCircleHth) & @CRLF & _
    "Cursor in Rectangle: " & _WinAPI_PtInRectEx($aPos[0], $aPos[1], $iRectX, $iRectY, _
    $iRectX + $iRectWidth, $iRectY + $iRectHth) & @CRLF)
    Case $GUI_EVENT_PRIMARYUP
    $aPos = MouseGetPos()
    Select
    Case _PointInPoly($aPos[0], $aPos[1], $aPoints)
    ToolTip("")
    MsgBox(0, "", "Clicked in PolyGon")
    Case _WinAPI_PtInRectEx($aPos[0], $aPos[1], $iRectX, $iRectY, $iRectX + $iRectWidth, _
    $iRectY + $iRectHth)
    ToolTip("")
    MsgBox(0, "", "Clicked in Rectangle")
    Case _PointInEllipse($aPos[0], $aPos[1], $iElpsX, $iElpsY, $iElpsWidth, $iElpsHth)
    ToolTip("")
    MsgBox(0, "", "Clicked in Ellipse")
    Case _PointInPoly($aPos[0], $aPos[1], $aTriangle)
    ToolTip("")
    MsgBox(0, "", "Clicked in Triangle")
    Case _PointInEllipse($aPos[0], $aPos[1], $iCircleX, $iCircleY, $iCircleWidth, $iCircleHth)
    ToolTip("")
    MsgBox(0, "", "Clicked in Invisible Circle")

    [/autoit] [autoit][/autoit] [autoit]

    EndSelect
    EndSwitch
    WEnd
    EndFunc ;==>_Main

    [/autoit] [autoit][/autoit] [autoit]

    ; Returns the area of a polygon
    Func _AreaPoly($aPoints)
    Local $Med
    For $n = 1 To UBound($aPoints) - 2
    $Med += $aPoints[$n][0] * $aPoints[$n + 1][1] - $aPoints[$n + 1][0] * $aPoints[$n][1]
    Next
    Return $Med / 2
    EndFunc ;==>_AreaPoly

    [/autoit] [autoit][/autoit] [autoit]

    ; Returns an array containing the x, y position of the centroid of a polygon.
    Func _CentroidPoly($aPoints)
    Local $Med, $aRet[2], $MedX, $MedY, $Area
    For $n = 1 To UBound($aPoints) - 2
    $MedX += ($aPoints[$n][0] + $aPoints[$n + 1][0]) * ($aPoints[$n][0] * $aPoints[$n + 1][1] - _
    $aPoints[$n + 1][0] * $aPoints[$n][1])
    $MedY += ($aPoints[$n][1] + $aPoints[$n + 1][1]) * ($aPoints[$n][0] * $aPoints[$n + 1][1] - _
    $aPoints[$n + 1][0] * $aPoints[$n][1])
    Next
    $Area = _AreaPoly($aPoints)
    $aRet[0] = $MedX / ($Area * 6)
    $aRet[1] = $MedY / ($Area * 6)
    Return $aRet
    EndFunc ;==>_CentroidPoly

    [/autoit] [autoit][/autoit] [autoit]

    ; ($xPt, $yPt) - x, y position of the point to check
    ; $xTL, $yTL, Top left x Pos, top left Y position of the rectangle encompassing the ellipse.
    ; $w, $h - The width an height of ellipse
    ; Method: The distance from the 1st focal point to a point on the perimeter plus the distance from
    ; the second focal point to the same point on the perimeter is a constant and equals the width of
    ; the ellipse, the major axis. So, if the sum of the two distances form the point to check to the
    ; two foci is greater than the major axis, then the point is outside the ellipse.
    Func _PointInEllipse($xPt, $yPt, $xTL, $yTL, $w, $h)
    Local $bInside = False, $a = $w / 2, $b = $h / 2
    Local $c1X, $c2X, $dist, $xc = $xTL + $a, $yc = $yTL + $b
    $c1X = $xc - ($a ^ 2 - $b ^ 2) ^ 0.5; 1st focal point x position
    $c2X = $xc + ($a ^ 2 - $b ^ 2) ^ 0.5; 2nd focal point x position
    $dist = (($xPt - $c1X) ^ 2 + ($yPt - $yc) ^ 2) ^ 0.5 + (($xPt - $c2X) ^ 2 + ($yPt - $yc) ^ 2) ^ 0.5
    If $dist <= $w Then $bInside = Not $bInside
    Return $bInside
    EndFunc ;==>_PointInEllipse

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; ($iX, $iY) - x, y position of the point to check
    ; ($iLeft, $iTop) - x, y position of the top left corner of rectangle
    ; ($iRight, $iBottom) - x, y position of the bottom right corner of rectangle
    ;
    Func _WinAPI_PtInRectEx($iX, $iY, $iLeft, $iTop, $iRight, $iBottom)
    Local $aResult
    Local $tRect = DllStructCreate($tagRECT)
    DllStructSetData($tRect, "Left", $iLeft)
    DllStructSetData($tRect, "Top", $iTop)
    DllStructSetData($tRect, "Right", $iRight)
    DllStructSetData($tRect, "Bottom", $iBottom)
    $aResult = DllCall("User32.dll", "int", "PtInRect", "ptr", DllStructGetPtr($tRect), "int", $iX, "int", $iY)
    If @error Then Return SetError(@error, 0, False)
    Return $aResult[0] <> 0
    EndFunc ;==>_WinAPI_PtInRectEx

    [/autoit] [autoit][/autoit] [autoit]

    ; ($x, $y) - x, y position of the point to check
    ; $aPoints - An array of x,y values representing the nodes of a polygon.
    ; Finds the individual x values of the interestion of the individual sides of the polygon with the
    ; line y = $y (parallel with x-axis). If the number of x values found greater than $x is even, then
    ; the ($x, $y) point is outside the closed polygon. Plus, if $y is beyond the y values of the end
    ; points of individual sides of the polygon, the y = $y line will not interest with that side and will
    ; not be counted. Returns equivalent of, even number of intersections false, and, odd true(inside polygon).
    ; Requires Iif()function
    Func _PointInPoly($x, $y, $aPoints)
    Local $bEvenNum = False, $xOnLine, $yMin, $yMax
    For $i = 1 To $aPoints[0][0]
    $yMin = Iif($aPoints[$i + 1][1] < $aPoints[$i][1], $aPoints[$i + 1][1], $aPoints[$i][1])
    $yMax = Iif($aPoints[$i + 1][1] > $aPoints[$i][1], $aPoints[$i + 1][1], $aPoints[$i][1])
    $xOnLine = -($y * $aPoints[$i + 1][0] - $y * $aPoints[$i][0] - $aPoints[$i][1] * $aPoints[$i + 1][0] + _
    $aPoints[$i][0] * $aPoints[$i + 1][1]) / (-$aPoints[$i + 1][1] + $aPoints[$i][1])
    If ($x < $xOnLine) And ($y > $yMin) And ($y <= $yMax) Then $bEvenNum = Not $bEvenNum
    Next
    Return $bEvenNum
    EndFunc ;==>_PointInPoly

    [/autoit] [autoit][/autoit] [autoit]

    ; Same as _Iif() function from Misc.au3 include file
    Func Iif($fTest, $vTrueVal, $vFalseVal)
    If $fTest Then
    Return $vTrueVal
    Else
    Return $vFalseVal
    EndIf
    EndFunc ;==>Iif

    [/autoit] [autoit][/autoit] [autoit]

    ;Func to redraw on PAINT MSG
    Func MY_PAINT($hWnd, $msg, $wParam, $lParam)
    ; Check, if the GUI with the Graphic should be repainted
    _GDIPlus_GraphicsDrawImage($hGraphicGUI, $hBMPBuff, 0, 0)
    _WinAPI_RedrawWindow($hGUI, "", "", BitOR($RDW_INVALIDATE, $RDW_UPDATENOW, $RDW_FRAME));,$RDW_ALLCHILDREN
    Return $GUI_RUNDEFMSG
    EndFunc ;==>MY_PAINT

    [/autoit]

    Gruß,
    UEZ

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

  • Mit GDI geht das ungefähr so:

    [autoit]

    Local $aPoints[5][2] = [ _
    [ 0, 0], _
    [ 4, 7], _
    [ 2, 1], _
    [ 8, 11], _
    [ 1, 1] _
    ]
    $hRgn = _GDI_CreatePolygonRgn($aPoints)
    $ptInRgn = _GDI_PtInRegion($hRgn, 3, 4)
    _GDI_DeleteObject($hRgn)

    [/autoit]
  • Und wenn du es zur Übung mal selbst programmieren willst hier mal 2 mögliche Lösungen für das Problem:

    Für ein Konvexes Polynom:

    • Man geht das Polynom im Uhrzeigersinn ab.
    • Wenn der Punkt IMMER rechts jeder Verbindungslinie 2er aufeinanderfolgenden Polygonpunkte liegt, liegt er im Polygon.

    Für ein nicht-konvexes Polyonom:

    • Man sendet vom Punkt P aus einen Halbstrahl (Linie in nur eine Richtung von P aus) aus und schneidet ihn mit allen Randlinien des Polygons.
    • Ist die Anzahl der Schnittpunkte gerade liegt der Punkt außerhalb, ist sie ungerade liegt der Punkt im Polygon.

    Als kleine Hilfestellung mal noch eine kleine Funktion welche die Beziehung eines Punktes zu einer Linie deutet:

    Spoiler anzeigen
    [autoit]

    #include <Math.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Global $Punkt[2] = [2, 2]
    Global $LinienPunkt1[2] = [3, 2]
    Global $LinienPunkt2[2] = [7, 4]

    [/autoit] [autoit][/autoit] [autoit]

    $iRelationship = PointToLine2D($Punkt, $LinienPunkt1, $LinienPunkt2)
    If Not @error Then
    $bOnLine = @extended
    Switch $iRelationship
    Case 0
    MsgBox(0, "", "Punkt liegt auf Linie" & @CRLF & "Zwischen P1 und P2: " & $bOnLine)
    Case 1
    MsgBox(0, "", "Punkt liegt links der Geraden")
    Case -1
    MsgBox(0, "", "Punkt liegt rechts der Geraden")
    EndSwitch
    EndIf

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ; #FUNCTION# ======================================================================================
    ; Name ..........: PointToLine2D()
    ; Description ...: Gibt die Beziehung eines Punktes zu einer Geraden/Linie zurück
    ; Syntax ........: PointToLine2D(Const $aP, Const $aP1, Const $aP2)
    ; Parameters ....: Const $aP - Zu prüfender Punkt in der Form $Array = [x,y]
    ; Const $aP1 - Geradenpunkt 1 in der Form $Array = [x,y]
    ; Const $aP2 - Geradenpunkt 2 in der Form $Array = [x,y]
    ; Return values .: Success: Return=0: Punkt liegt auf Geraden; Return<0: Punkt liegt rechts der Geraden; Return >0: Punkt liegt links der Geraden
    ; Failure: @error=1: Falsche Dimensionen der Punktarrays
    ; Author ........: AspirinJunkie
    ; Related .......: Math.au3
    ; =================================================================================================
    Func PointToLine2D(Const $aP, Const $aP1, Const $aP2)
    If UBound($aP) < 2 Or UBound($aP2) < 2 Or UBound($aP2) < 2 Then Return SetError(1, 0, 0)

    [/autoit] [autoit][/autoit] [autoit]

    Local $d = $aP[0] * ($aP1[1] - $aP2[1]) - $aP1[0] * ($aP[1] - $aP2[1]) + $aP2[0] * ($aP[1] - $aP1[1])
    Local $bOnLine = $aP[0] <= _Max($aP1[0], $aP2[0]) And $aP[0] >= _Min($aP1[0], $aP2[0]) And $aP[1] <= _Max($aP1[1], $aP2[1]) And $aP[1] >= _Min($aP1[1], $aP2[1])
    If $d <> 0 Then $d /= Abs($d)

    [/autoit] [autoit][/autoit] [autoit]

    Return SetError(0, $bOnLine, $d)
    EndFunc ;==>PointToLine2D

    [/autoit]

    Einmal editiert, zuletzt von AspirinJunkie (7. Februar 2011 um 18:04)

  • Hi,

    Zitat von AspirinJunkie

    Für ein Konvexes Polynom:

    ................................

    Für ein nicht-konvexes Polyonom:


    wusst ichs doch, dass der das wieder auseinanderklabustert :thumbup: , aber genau so gehört sich das *verbeug*

    stayawayknight, sag mal kurz etwas zu deinem konkreten Problem!
    Wenn du die Fläche füllen möchtest, die innerhalb eines Polygons liegt und dabei jeden Punktl auf "drin/draussen" prüfst, dauern die o.g. Abfragen ewig....
    Auch bei "grossen" Polygonen, z.B. die Wände eines Labyrints in einem Spiel, ist die obige Methode suboptimal...

  • Um Rechenzeit einzusparen könnte man auch eine Schnellprüfung vor der exakten Bestimmung machen. Wenn der Punkt im Polygon liegt muss er sich in jedemfall innerhalb eines Rechteckes befinden welches sich aus den Punkten mit dem jeweils kleinsten und größten x/y Koordinaten zusammensetzt.

    Das bedeutet man bestimmt Xmin, Xmax, Ymin und Ymax aller Polygon Punkte. Nun muss man nur noch prüfen ob die x und y Werte des Punktes innerhalb dieser Grenzen liegen. Wenn nein ist das Ergebnis klar, er liegt ausserhalb des Polygons, wenn ja muss eines der genannten Verfahren angewendet werden.

    Einmal editiert, zuletzt von misterspeed (7. Februar 2011 um 19:06)

  • Auch dir nochmals vielen Dank, diese Methode scheint sehr einfach Anzuwenden zu sein - danke!
    Die Funktionen scheinen aber eher der GDIP.au3 anzugehören anstatt der GDIPlus.au3 - trotzdem nützlich!