Flächenumring prüfen auf Überlappungen

  • VB.NET

Es gibt 8 Antworten in diesem Thema. Der letzte Beitrag () ist von Morrison.

    @jan99 Kannst Du dazu mal eine Skizze posten?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @VB1963 Das muss der Fall sein. Denn wenn nicht lässt sich immer eine Reihenfolge finden, die keine Überlappung hat.

    @jan99 Du musst alle nichtbenachbarten Kantenpaare auf Schneidung prüfen.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Haudruferzappeltnoch“ ()

    Neu

    @jan99 Sieh Dir mal an, was Wiki zu Polygon schreibt:
    de.wikipedia.org/wiki/Polygon#Regelm%C3%A4%C3%9Figes_Polygon
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Neu

    Nimm eine Physik Engine und prüf auf Kollision. Glaube das ist der einfachste weg. Da gibt es bestimmt irgend etwas fertiges um zu sehen ob sich etwas überlappt. Alternativ könntest du dein polygon in linien aufteilen also Punkt A zu B ist eine Line und Punkt B zu C und so weiter. Dann kannst du einfach prüfen ob sich diese linen miteinander überlappen.

    Edit habe hier etwas gefunden: gist.github.com/unitycoder/10241239e080720376830f84511ccd3c
    Meine Projekte Genesis Game Engine | GFX | smartli.me - Der smarte URL shortener

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Andy“ ()

    Neu

    ChatGPT sagt:

    Install-Package NetTopologySuite


    Spoiler anzeigen

    VB.NET-Quellcode

    1. Imports NetTopologySuite.Geometries
    2. Imports NetTopologySuite.Operation.Overlay
    4. Module Module1
    5. Sub Main()
    6. ' Beispiel: Umring erstellen
    7. Dim factory As New GeometryFactory()
    8. Dim polygonCoords As Coordinate() = {
    9. New Coordinate(0, 0),
    10. New Coordinate(10, 0),
    11. New Coordinate(10, 10),
    12. New Coordinate(0, 10),
    13. New Coordinate(0, 0) ' Schließt den Umring
    14. }
    15. Dim polygon As Polygon = factory.CreatePolygon(polygonCoords)
    17. ' Beispiel: Punkte innerhalb der Fläche
    18. Dim pointCoords As Coordinate() = {
    19. New Coordinate(5, 5),
    20. New Coordinate(15, 15) ' Dieser Punkt liegt außerhalb
    21. }
    22. Dim points As MultiPoint = factory.CreateMultiPoint(pointCoords)
    24. ' Überprüfung, ob Punkte im Umring liegen
    25. For Each point In points.Geometries
    26. If polygon.Contains(point) Then
    27. Console.WriteLine($"Punkt {point} liegt im Umring.")
    28. Else
    29. Console.WriteLine($"Punkt {point} liegt außerhalb des Umrings.")
    30. End If
    31. Next
    33. ' Beispiel: Zwei Flächen prüfen, ob sie sich überschneiden
    34. Dim anotherPolygonCoords As Coordinate() = {
    35. New Coordinate(5, 5),
    36. New Coordinate(15, 5),
    37. New Coordinate(15, 15),
    38. New Coordinate(5, 15),
    39. New Coordinate(5, 5)
    40. }
    41. Dim anotherPolygon As Polygon = factory.CreatePolygon(anotherPolygonCoords)
    43. If polygon.Intersects(anotherPolygon) Then
    44. Console.WriteLine("Die Flächen überschneiden sich.")
    45. Else
    46. Console.WriteLine("Die Flächen überschneiden sich nicht.")
    47. End If
    48. End Sub
    49. End Module



    Oder ohne externe Bibliothek:


    Spoiler anzeigen

    VB.NET-Quellcode

    1. Function IsPointInPolygon(polygon As List(Of PointF), point As PointF) As Boolean
    2. Dim intersects As Integer = 0
    3. Dim n As Integer = polygon.Count
    5. For i As Integer = 0 To n - 1
    6. Dim p1 As PointF = polygon(i)
    7. Dim p2 As PointF = polygon((i + 1) Mod n)
    9. ' Prüfe, ob die Linie [p1, p2] eine horizontale Linie nach rechts schneidet
    10. If (point.Y > Math.Min(p1.Y, p2.Y)) AndAlso (point.Y <= Math.Max(p1.Y, p2.Y)) AndAlso
    11. (point.X <= Math.Max(p1.X, p2.X)) Then
    13. Dim xinters As Double = (point.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X
    14. If p1.Y <> p2.Y AndAlso point.X <= xinters Then
    15. intersects += 1
    16. End If
    17. End If
    18. Next
    20. ' Ist die Anzahl der Schnitte ungerade, liegt der Punkt im Polygon
    21. Return (intersects Mod 2) <> 0
    22. End Function
    25. Function DoLinesIntersect(p1 As PointF, p2 As PointF, q1 As PointF, q2 As PointF) As Boolean
    26. ' Berechnung der Orientierung
    27. Dim o1 As Integer = Orientation(p1, p2, q1)
    28. Dim o2 As Integer = Orientation(p1, p2, q2)
    29. Dim o3 As Integer = Orientation(q1, q2, p1)
    30. Dim o4 As Integer = Orientation(q1, q2, p2)
    32. ' Allgemeine Überschneidung
    33. If (o1 <> o2) AndAlso (o3 <> o4) Then Return True
    35. ' Spezialfälle: Endpunkte liegen auf einer Linie
    36. If (o1 = 0 AndAlso IsOnSegment(p1, q1, p2)) Then Return True
    37. If (o2 = 0 AndAlso IsOnSegment(p1, q2, p2)) Then Return True
    38. If (o3 = 0 AndAlso IsOnSegment(q1, p1, q2)) Then Return True
    39. If (o4 = 0 AndAlso IsOnSegment(q1, p2, q2)) Then Return True
    41. Return False
    42. End Function
    44. Function Orientation(p As PointF, q As PointF, r As PointF) As Integer
    45. ' Berechnet die Orientierung von drei Punkten
    46. Dim val As Double = (q.Y - p.Y) * (r.X - q.X) - (q.X - p.X) * (r.Y - q.Y)
    47. If val = 0 Then Return 0 ' Kollinear
    48. Return If(val > 0, 1, 2) ' Uhrzeigersinn oder gegen Uhrzeigersinn
    49. End Function
    51. Function IsOnSegment(p As PointF, q As PointF, r As PointF) As Boolean
    52. Return (q.X <= Math.Max(p.X, r.X) AndAlso q.X >= Math.Min(p.X, r.X) AndAlso
    53. q.Y <= Math.Max(p.Y, r.Y) AndAlso q.Y >= Math.Min(p.Y, r.Y))
    54. End Function
    57. Function DoPolygonsIntersect(polygon1 As List(Of PointF), polygon2 As List(Of PointF)) As Boolean
    58. For i As Integer = 0 To polygon1.Count - 1
    59. Dim p1 As PointF = polygon1(i)
    60. Dim p2 As PointF = polygon1((i + 1) Mod polygon1.Count)
    62. For j As Integer = 0 To polygon2.Count - 1
    63. Dim q1 As PointF = polygon2(j)
    64. Dim q2 As PointF = polygon2((j + 1) Mod polygon2.Count)
    66. If DoLinesIntersect(p1, p2, q1, q2) Then
    67. Return True
    68. End If
    69. Next
    70. Next
    71. Return False
    72. End Function
    75. Sub Main()
    76. Dim polygon1 As New List(Of PointF) From {
    77. New PointF(0, 0),
    78. New PointF(10, 0),
    79. New PointF(10, 10),
    80. New PointF(0, 10)
    81. }
    83. Dim polygon2 As New List(Of PointF) From {
    84. New PointF(5, 5),
    85. New PointF(15, 5),
    86. New PointF(15, 15),
    87. New PointF(5, 15)
    88. }
    90. ' Prüfe Überschneidung
    91. If DoPolygonsIntersect(polygon1, polygon2) Then
    92. Console.WriteLine("Die Polygone überschneiden sich.")
    93. Else
    94. Console.WriteLine("Die Polygone überschneiden sich nicht.")
    95. End If
    97. ' Prüfe Punkt in Polygon
    98. Dim testPoint As New PointF(5, 5)
    99. If IsPointInPolygon(polygon1, testPoint) Then
    100. Console.WriteLine("Der Punkt liegt im Polygon.")
    101. Else
    102. Console.WriteLine("Der Punkt liegt außerhalb des Polygons.")
    103. End If
    104. End Sub
    107. Function HasSelfIntersections(polygon As List(Of PointF)) As Boolean
    108. Dim n As Integer = polygon.Count
    110. For i As Integer = 0 To n - 1
    111. Dim p1 As PointF = polygon(i)
    112. Dim p2 As PointF = polygon((i + 1) Mod n)
    114. For j As Integer = 0 To n - 1
    115. ' Überspringe benachbarte Kanten und dieselbe Kante
    116. If j = i OrElse j = (i + 1) Mod n OrElse (j + 1) Mod n = i Then
    117. Continue For
    118. End If
    120. Dim q1 As PointF = polygon(j)
    121. Dim q2 As PointF = polygon((j + 1) Mod n)
    123. If DoLinesIntersect(p1, p2, q1, q2) Then
    124. Return True ' Überschneidung gefunden
    125. End If
    126. Next
    127. Next
    129. Return False ' Keine Überschneidungen
    130. End Function
    133. Sub Main()
    134. Dim polygonOk As New List(Of PointF) From {
    135. New PointF(0, 0),
    136. New PointF(10, 0),
    137. New PointF(10, 10),
    138. New PointF(0, 10)
    139. }
    141. Dim polygonWrong As New List(Of PointF) From {
    142. New PointF(0, 0),
    143. New PointF(10, 0),
    144. New PointF(5, 5),
    145. New PointF(10, 10),
    146. New PointF(0, 10)
    147. }
    149. If HasSelfIntersections(polygonOk) Then
    150. Console.WriteLine("Polygon OK: Hat Selbstüberschneidungen")
    151. Else
    152. Console.WriteLine("Polygon OK: Keine Selbstüberschneidungen")
    153. End If
    155. If HasSelfIntersections(polygonWrong) Then
    156. Console.WriteLine("Polygon Falsch: Hat Selbstüberschneidungen")
    157. Else
    158. Console.WriteLine("Polygon Falsch: Keine Selbstüberschneidungen")
    159. End If
    160. End Sub





    Die hochgeladene Datei zeigt zwei Beispiele:

    Links (OK): Ein Polygon, dessen Linien sich nicht überschneiden.
    Rechts (Falsch): Ein Polygon, dessen Linien sich gegenseitig überschneiden.
    Das Problem hier ist, Selbstüberschneidungen innerhalb eines Polygons zu erkennen. Das bedeutet, dass überprüft werden muss, ob eine Linie des Polygons eine andere Linie desselben Polygons schneidet.

    Lösung ohne zusätzliche Bibliotheken
    Du kannst die Funktion DoLinesIntersect aus meinem vorherigen Vorschlag verwenden, um die Kanten des Polygons miteinander zu vergleichen.

    Algorithmus:Iteriere über jede Kante des Polygons.
    Vergleiche jede Kante mit allen anderen Kanten des Polygons.
    Überspringe benachbarte Kanten, da diese sich teilen dürfen (gemeinsamer Punkt).
    Überprüfe mit DoLinesIntersect, ob sich zwei Kanten schneiden.



    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Morrison“ ()