Aktuelle Zeit: 22.09.2018 09:50

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 5 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Polygon Include - Vereinigung,Schnitt,Differenz - Testphase
BeitragVerfasst: 08.07.2018 22:34 
Offline
Kommando SG1
Benutzeravatar

Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Hallo Leute,

nachdem ich letzten Monat die Snapsidee hatte n kleines Drawing-Only Game zu schreiben (ja werde ich später auch noch vorstellen), bei dem man Polygone zerschießen kann, brauchte ich zwangsweise ein gutes Include für Polygon-Operationen (Vereinigung, Schnitt, Differenz).

Im Internet bin ich dann auf ein sehr gutes Paper von
A. Margalit und G. D. Knott, "An algorithm for computing the union, intersection or difference of two polygons", Comput & Graphics 13, No 2, pp 167-183, (1989)
gestoßen. Dort wird ein Verfahren für Set-Operationen vorgestellt, welches für so genannte "vertex-complete polygons" geeignet ist, also für Polygone eine Orientierung haben und sich außer an ihren Vertizes keine weiteren Überschneidungen mit sich selbst haben, aber auch verschachtelt sein können.

Lange Rede kurzer Sinn, hier mal eine Vorabversion des Includes mit Demo.
Es ist noch lange nicht Fertig, aber das Wochenende ist zuende, und Feedback kann nicht schaden.
Ziel ist (später) weniger die Anzeige solcher Polygone (das können andere besser und schneller). Vielmehr sollen diese Polygone (und die Resultate) dann für Spiele und 2D-Physik zu nutzen sein, daher sind auch sachen wie MomentOfInertia enthalten.

Bild
______________________________________________

Hier der Code, wie gesagt, sich überschneidene Seiten ohne Vertex sind nicht erlaubt.
Der Algorythmus ist dann nicht nutzbar. Ansonsten könnte ihr Vertizes verschieben wie ihr wollt:
Code:
EnumerationBinary
   #Polygon_Border
   #Polygon_Inside
   #Polygon_Outside
EndEnumeration

Enumeration 1
   #Polygon_Union
   #Polygon_Intersection
   #Polygon_Difference
EndEnumeration

EnumerationBinary
   #Polygon_Filled
   #Polygon_Vertices
   #Polygon_Orientation
EndEnumeration

#Polygon_Epsilon = 1e-7



Structure PolygonVertex
   X.d
   Y.d
EndStructure

Structure PolygonPath
   Array Vertex.PolygonVertex(0)
EndStructure

Structure Polygon
   List Path.PolygonPath()
   BoundaryRadius.d
   MomentOfInertia.d
   Area.d
   Center.PolygonVertex
EndStructure

Structure PolygonCollision
   Position.PolygonVertex
   *Path1.PolygonPath
   PathIndex1.i
   *Path2.PolygonPath
   PathIndex2.i
   Edge1.i
   Edge2.i
   Factor1.d
   Factor2.d
EndStructure

Structure PolygonCollisionList
   List Collision.PolygonCollision()
EndStructure

Structure Polygon_VertexRing_Vertex
   X.d
   Y.d
   Type.i
   Path.i
   Index.i
   Factor.d
   Count.i
EndStructure

Structure Polygon_EdgeFragments_Edge
   *Vertex1.Polygon_VertexRing_Vertex
   *Vertex2.Polygon_VertexRing_Vertex
   Type.i
   *Polygon.Polygon
   Picked.i
EndStructure

Global NewList Polygon.Polygon()


Declare AddPolygonPath(*Polygon.Polygon, *Buffer.PolygonVertex=#Null, Vertices.i=0)
Declare AddPolygonPoint(*Polygon.Polygon, X.d, Y.d, PathIndex.i=-1, VertexIndex.i=-1)
Declare CreatePolygon()
Declare CopyPolygon(*Polygon.Polygon)
Declare FreePolygon(*Polygon.Polygon)
Declare.i CountPolygonPaths(*Polygon.Polygon)
Declare.d PolygonArea(*Polygon.Polygon)
Declare.d PolygonCenterX(*Polygon.Polygon)
Declare.d PolygonCenterY(*Polygon.Polygon)
Declare.i UpdatePolygonAttributes(*Polygon.Polygon)
Declare PolygonVertexTest(*Polygon.Polygon, X.d, Y.d, Radius.d)
Declare PolygonPointTest(*Polygon.Polygon, X.d, Y.d)
Declare DrawPolygon(*Polygon.Polygon, Color.i, Flags.i=#Polygon_Filled|#Polygon_Vertices|#Polygon_Orientation)
Declare PolygonCollision(*Polygon1.Polygon, *Polygon2.Polygon, *PolygonCollisionList.PolygonCollisionList=#Null)
Declare PolygonUnion(*Polygon1.Polygon, *Polygon2.Polygon)
Declare PolygonIntersection(*Polygon1.Polygon, *Polygon2.Polygon)
Declare PolygonDifference(*Polygon1.Polygon, *Polygon2.Polygon)
Declare PolygonSymmetricDifference(*Polygon1.Polygon, *Polygon2.Polygon)
Declare AlignPolygon(*Polygon.Polygon)
Declare TranslatePolygon(*Polygon.Polygon, X.d, Y.d)
Declare RotatePolygon(*Polygon.Polygon, Angle.d, CenterX.d=0.0, CenterY.d=0.0)
Declare ScalePolygon(*Polygon.Polygon, Factor.d, CenterX.d=0.0, CenterY.d=0.0)



;- Private



Procedure Polygon_VertexRing_InsertVertex(List Vertex.Polygon_VertexRing_Vertex(), *Vertex.PolygonVertex, Type.i, Path.i, Index.i, Factor.d=0.0)
   
   Protected Count.i = 0
   
   Repeat
      
      If LastElement(Vertex())
         Repeat
            If Vertex()\Path < Path
               Break
            ElseIf Vertex()\Path = Path
               If Vertex()\Index < Index
                  Break
               ElseIf Vertex()\Index = Index
                  If Vertex()\Factor < Factor - #Polygon_Epsilon
                     Break
                  ElseIf Abs(Vertex()\Factor-Factor) <= #Polygon_Epsilon
                     If Vertex()\Count < 0
                        Count = 1
                        Break
                     Else
                        Break 2
                     EndIf
                  EndIf
               EndIf
            EndIf
         Until Not PreviousElement(Vertex())
      EndIf
      
      AddElement(Vertex())
      Vertex()\X      = *Vertex\X
      Vertex()\Y      = *Vertex\Y
      Vertex()\Type   = Type
      Vertex()\Path   = Path
      Vertex()\Index  = Index
      Vertex()\Factor = Factor
      Vertex()\Count  = Count
      
      ProcedureReturn Vertex()
      
   Until #True
   
EndProcedure


Procedure Polygon_VertexRing_Reverse(List Vertex.Polygon_VertexRing_Vertex())
   
   Protected *Vertex.Polygon_VertexRing_Vertex
   Protected *FirstVertex.Polygon_VertexRing_Vertex
   
   *FirstVertex = FirstElement(Vertex())
   If *FirstVertex
      While NextElement(Vertex())
         MoveElement(Vertex(), #PB_List_First)
         ChangeCurrentElement(Vertex(), *FirstVertex)
      Wend
   EndIf
   
EndProcedure



Procedure Polygon_EdgeFragments_AddEdge(List Edge.Polygon_EdgeFragments_Edge(), *Vertex1.Polygon_VertexRing_Vertex, *Vertex2.Polygon_VertexRing_Vertex, *Polygon.Polygon, *OtherPolygon.Polygon)
   
   Protected Vertex.PolygonVertex
   Protected EdgeType.i
   
   If *Vertex1\Type = #Polygon_Inside Or *Vertex2\Type = #Polygon_Inside
      EdgeType = #Polygon_Inside
   ElseIf *Vertex1\Type = #Polygon_Outside Or *Vertex2\Type = #Polygon_Outside
      EdgeType = #Polygon_Outside
   Else ; Beides #Polygon_Border
      Vertex\X = (*Vertex1\X+*Vertex2\X)*0.5
      Vertex\Y = (*Vertex1\Y+*Vertex2\Y)*0.5
      EdgeType = PolygonPointTest(*OtherPolygon, Vertex\X, Vertex\Y)
   EndIf
   
   AddElement(Edge())
   Edge()\Vertex1 = *Vertex1
   Edge()\Vertex2 = *Vertex2
   Edge()\Type    = EdgeType
   Edge()\Polygon = *Polygon
   
EndProcedure


Procedure Polygon_EdgeFragments_InsertAllEdges(List Edge.Polygon_EdgeFragments_Edge(), List Vertex.Polygon_VertexRing_Vertex(), *Polygon.Polygon, *OtherPolygon.Polygon)
   
   Protected *PreviousVertex.Polygon_VertexRing_Vertex
   Protected *FirstVertex.Polygon_VertexRing_Vertex
   
   *FirstVertex = FirstElement(Vertex())
   If *FirstVertex
      *PreviousVertex = *FirstVertex
      While NextElement(Vertex())
         If Vertex()\Path = *PreviousVertex\Path
            Polygon_EdgeFragments_AddEdge(Edge(), *PreviousVertex, Vertex(), *Polygon, *OtherPolygon)
         Else
            Polygon_EdgeFragments_AddEdge(Edge(), *PreviousVertex, *FirstVertex, *Polygon, *OtherPolygon)
            *FirstVertex = Vertex()
         EndIf
         *PreviousVertex = Vertex()
      Wend
      Polygon_EdgeFragments_AddEdge(Edge(), *PreviousVertex, *FirstVertex, *Polygon, *OtherPolygon)
   EndIf
   
EndProcedure



Procedure Polygon_Operation(Operation.i, *Polygon1.Polygon, *Polygon2.Polygon)
   
   ; Reference: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.6264&rep=rep1&type=pdf
   
   Protected *ResultPolygon.Polygon = CreatePolygon()
   Protected PolygonCollisionList.PolygonCollisionList
   Protected I.i, MaxI.i, Path.i, NotFound.i
   
   Protected NewList Vertex1.Polygon_VertexRing_Vertex()
   Protected NewList Vertex2.Polygon_VertexRing_Vertex()
   Protected NewList Edge.Polygon_EdgeFragments_Edge()
   Protected NewList *SelectedEdge.Polygon_EdgeFragments_Edge()
   Protected *Edge.Polygon_EdgeFragments_Edge, *PreviousEdge.Polygon_EdgeFragments_Edge, *FirstEdge.Polygon_EdgeFragments_Edge
   
   ; Classify and insert vertices into the vertex rings
   ForEach *Polygon1\Path()
      MaxI = ArraySize(*Polygon1\Path()\Vertex())
      For I = 0 To MaxI
         Polygon_VertexRing_InsertVertex(Vertex1(), *Polygon1\Path()\Vertex(I), PolygonPointTest(*Polygon2, *Polygon1\Path()\Vertex(I)\X, *Polygon1\Path()\Vertex(I)\Y), ListIndex(*Polygon1\Path()), I)
      Next
   Next
   ForEach *Polygon2\Path()
      MaxI = ArraySize(*Polygon2\Path()\Vertex())
      For I = 0 To MaxI
         Polygon_VertexRing_InsertVertex(Vertex2(), *Polygon2\Path()\Vertex(I), PolygonPointTest(*Polygon1, *Polygon2\Path()\Vertex(I)\X, *Polygon2\Path()\Vertex(I)\Y), ListIndex(*Polygon2\Path()), I)
      Next
   Next
   
   ; Find and insert the intersections points into both vertex rings
   PolygonCollision(*Polygon1, *Polygon2, @PolygonCollisionList)
   ForEach PolygonCollisionList\Collision()
      With PolygonCollisionList\Collision()
         If Abs(\Factor1-1.0) <= #Polygon_Epsilon
            If \Edge1 < ArraySize(\Path1\Vertex())
               \Edge1 + 1 : \Factor1 = 0.0
            Else
               \Edge1 = 0 : \Factor1 = 0.0
            EndIf
         EndIf
         If Abs(\Factor2-1.0) <= #Polygon_Epsilon
            If \Edge2 < ArraySize(\Path2\Vertex())
               \Edge2 + 1 : \Factor2 = 0.0
            Else
               \Edge2 = 0 : \Factor2 = 0.0
            EndIf
         EndIf
         Polygon_VertexRing_InsertVertex(Vertex1(), \Position, #Polygon_Border, \PathIndex1, \Edge1, \Factor1)
         Polygon_VertexRing_InsertVertex(Vertex2(), \Position, #Polygon_Border, \PathIndex2, \Edge2, \Factor2)
      EndWith
   Next
   
   ; Optionally: Reverse the orientation of the vertex ring
   Select Operation
      Case #Polygon_Union, #Polygon_Intersection
         If Sign(*Polygon1\Area) <> Sign(*Polygon2\Area)
            Polygon_VertexRing_Reverse(Vertex2())
         EndIf
      Case #Polygon_Difference
         If Sign(*Polygon1\Area) = Sign(*Polygon2\Area)
            Polygon_VertexRing_Reverse(Vertex2())
         EndIf
   EndSelect
   
   ; Classify and insert edge fragments into the edge fragment list
   Polygon_EdgeFragments_InsertAllEdges(Edge(), Vertex1(), *Polygon1, *Polygon2)
   Polygon_EdgeFragments_InsertAllEdges(Edge(), Vertex2(), *Polygon2, *Polygon1)
   
   ; Select the edge fragments
   Select Operation
      Case #Polygon_Union
         ForEach Edge()
            If Edge()\Type = #Polygon_Outside
               AddElement(*SelectedEdge()) : *SelectedEdge() = Edge()
            EndIf
         Next
      Case #Polygon_Intersection
         ForEach Edge()
            If Edge()\Type = #Polygon_Inside
               AddElement(*SelectedEdge()) : *SelectedEdge() = Edge()
            EndIf
         Next
      Case #Polygon_Difference
         ForEach Edge()
            If (Edge()\Type = #Polygon_Outside And Edge()\Polygon = *Polygon1) Or (Edge()\Type = #Polygon_Inside And Edge()\Polygon = *Polygon2)
               AddElement(*SelectedEdge()) : *SelectedEdge() = Edge()
            EndIf
         Next
   EndSelect
   ForEach Edge()
      *Edge = Edge()
      If *Edge\Type = #Polygon_Border And *Edge\Polygon = *Polygon1
         ForEach Edge()
            If Edge()\Type = #Polygon_Border And Edge()\Polygon = *Polygon2
               If Abs(*Edge\Vertex1\X-Edge()\Vertex1\X) < #Polygon_Epsilon And Abs(*Edge\Vertex1\Y-Edge()\Vertex1\Y) < #Polygon_Epsilon And
                  Abs(*Edge\Vertex2\X-Edge()\Vertex2\X) < #Polygon_Epsilon And Abs(*Edge\Vertex2\Y-Edge()\Vertex2\Y) < #Polygon_Epsilon
                  AddElement(*SelectedEdge()) : *SelectedEdge() = *Edge
               ElseIf Abs(*Edge\Vertex1\X-Edge()\Vertex2\X) < #Polygon_Epsilon And Abs(*Edge\Vertex1\Y-Edge()\Vertex2\Y) < #Polygon_Epsilon And
                      Abs(*Edge\Vertex2\X-Edge()\Vertex1\X) < #Polygon_Epsilon And Abs(*Edge\Vertex2\Y-Edge()\Vertex1\Y) < #Polygon_Epsilon
                  AddElement(*SelectedEdge()) : *SelectedEdge() = *Edge
                  AddElement(*SelectedEdge()) : *SelectedEdge() = Edge()
               EndIf
            EndIf
         Next
         ChangeCurrentElement(Edge(), *Edge)
      EndIf
   Next
   ForEach *SelectedEdge()
      *Edge = *SelectedEdge()
      PushListPosition(*SelectedEdge())
      ForEach *SelectedEdge()
         If *SelectedEdge() = *Edge
            Continue
         EndIf
         If Abs(*Edge\Vertex1\X-*SelectedEdge()\Vertex2\X) < #Polygon_Epsilon And Abs(*Edge\Vertex1\Y-*SelectedEdge()\Vertex2\Y) < #Polygon_Epsilon And
            Abs(*Edge\Vertex2\X-*SelectedEdge()\Vertex1\X) < #Polygon_Epsilon And Abs(*Edge\Vertex2\Y-*SelectedEdge()\Vertex1\Y) < #Polygon_Epsilon
            *Edge\Picked = #True
            DeleteElement(*SelectedEdge())
            Break
         EndIf
      Next
      PopListPosition(*SelectedEdge())
      If *Edge\Picked
         DeleteElement(*SelectedEdge())
      EndIf
   Next
;    ForEach *SelectedEdge()
;       *Edge = *SelectedEdge()
;       If Abs(*Edge\Vertex1\X-*Edge\Vertex2\X) <= #Polygon_Epsilon And Abs(*Edge\Vertex1\Y-*Edge\Vertex2\Y) <= #Polygon_Epsilon
;          *Edge\Picked = #True
;          PushListPosition(*SelectedEdge())
;          ForEach *SelectedEdge()
;             If *SelectedEdge() = *Edge
;                Continue
;             EndIf
;             If Abs(*Edge\Vertex1\X-*SelectedEdge()\Vertex1\X) < #Polygon_Epsilon And Abs(*Edge\Vertex1\Y-*SelectedEdge()\Vertex1\Y) < #Polygon_Epsilon
;                *Edge\Picked = #True
;                Break
;             EndIf
;             If Abs(*Edge\Vertex1\X-*SelectedEdge()\Vertex2\X) < #Polygon_Epsilon And Abs(*Edge\Vertex1\Y-*SelectedEdge()\Vertex2\Y) < #Polygon_Epsilon
;                *Edge\Picked = #True
;                Break
;             EndIf
;          Next
;          PopListPosition(*SelectedEdge())
;          If *Edge\Picked
;             DeleteElement(*SelectedEdge())
;          EndIf
;       EndIf
;    Next
   
   ; Debugging
   CompilerIf #False
      Debug "  Vertex rings:"
      Debug "    Polygon1:"
      Path = -1
      ForEach Vertex1()
         If Vertex1()\Path > Path : Debug "      Path "+Vertex1()\Path : Path = Vertex1()\Path : EndIf
         Select Vertex1()\Type
            Case #Polygon_Outside : Debug "        Outside: "+StrD(Vertex1()\X,15)+" , "+StrD(Vertex1()\Y,15) + " f="+StrD(Vertex1()\Factor,15) + " i="+Str(Vertex1()\Index)
            Case #Polygon_Border  : Debug "        Border:  "+StrD(Vertex1()\X,15)+" , "+StrD(Vertex1()\Y,15) + " f="+StrD(Vertex1()\Factor,15) + " i="+Str(Vertex1()\Index)
            Case #Polygon_Inside  : Debug "        Inside:  "+StrD(Vertex1()\X,15)+" , "+StrD(Vertex1()\Y,15) + " f="+StrD(Vertex1()\Factor,15) + " i="+Str(Vertex1()\Index)
         EndSelect
      Next
      Debug "    Polygon2:"
      Path = -1
      ForEach Vertex2()
         If Vertex2()\Path > Path : Debug "      Path "+Vertex2()\Path : Path = Vertex2()\Path : EndIf
         Select Vertex2()\Type
            Case #Polygon_Outside : Debug "        Outside: "+StrD(Vertex2()\X,15)+" , "+StrD(Vertex2()\Y,15) + " f="+StrD(Vertex2()\Factor,15) + " i="+Str(Vertex2()\Index)
            Case #Polygon_Border  : Debug "        Border:  "+StrD(Vertex2()\X,15)+" , "+StrD(Vertex2()\Y,15) + " f="+StrD(Vertex2()\Factor,15) + " i="+Str(Vertex2()\Index)
            Case #Polygon_Inside  : Debug "        Inside:  "+StrD(Vertex2()\X,15)+" , "+StrD(Vertex2()\Y,15) + " f="+StrD(Vertex2()\Factor,15) + " i="+Str(Vertex2()\Index)
         EndSelect
      Next
      Debug "  Edge fragments:"
      ForEach Edge()
         If Edge()\Polygon = *Polygon1
            Select Edge()\Type
               Case #Polygon_Outside : Debug "    Outside[1]: "+StrD(Edge()\Vertex1\X,15)+" , "+StrD(Edge()\Vertex1\Y,15)+" -> "+StrD(Edge()\Vertex2\X,15)+" , "+StrD(Edge()\Vertex2\Y,15)
               Case #Polygon_Border  : Debug "    Border[1]:  "+StrD(Edge()\Vertex1\X,15)+" , "+StrD(Edge()\Vertex1\Y,15)+" -> "+StrD(Edge()\Vertex2\X,15)+" , "+StrD(Edge()\Vertex2\Y,15)
               Case #Polygon_Inside  : Debug "    Inside[1]:  "+StrD(Edge()\Vertex1\X,15)+" , "+StrD(Edge()\Vertex1\Y,15)+" -> "+StrD(Edge()\Vertex2\X,15)+" , "+StrD(Edge()\Vertex2\Y,15)
            EndSelect
         ElseIf Edge()\Polygon = *Polygon2
            Select Edge()\Type
               Case #Polygon_Outside : Debug "    Outside[2]: "+StrD(Edge()\Vertex1\X,15)+" , "+StrD(Edge()\Vertex1\Y,15)+" -> "+StrD(Edge()\Vertex2\X,15)+" , "+StrD(Edge()\Vertex2\Y,15)
               Case #Polygon_Border  : Debug "    Border[2]:  "+StrD(Edge()\Vertex1\X,15)+" , "+StrD(Edge()\Vertex1\Y,15)+" -> "+StrD(Edge()\Vertex2\X,15)+" , "+StrD(Edge()\Vertex2\Y,15)
               Case #Polygon_Inside  : Debug "    Inside[2]:  "+StrD(Edge()\Vertex1\X,15)+" , "+StrD(Edge()\Vertex1\Y,15)+" -> "+StrD(Edge()\Vertex2\X,15)+" , "+StrD(Edge()\Vertex2\Y,15)
            EndSelect
         EndIf
      Next
      Debug "  Selected edge fragments:"
      ForEach *SelectedEdge()
         Select *SelectedEdge()\Type
            Case #Polygon_Outside : Debug "    Outside: "+StrD(*SelectedEdge()\Vertex1\X)+" , "+StrD(*SelectedEdge()\Vertex1\Y)+" -> "+StrD(*SelectedEdge()\Vertex2\X)+" , "+StrD(*SelectedEdge()\Vertex2\Y)
            Case #Polygon_Border  : Debug "    Border:  "+StrD(*SelectedEdge()\Vertex1\X)+" , "+StrD(*SelectedEdge()\Vertex1\Y)+" -> "+StrD(*SelectedEdge()\Vertex2\X)+" , "+StrD(*SelectedEdge()\Vertex2\Y)
            Case #Polygon_Inside  : Debug "    Inside:  "+StrD(*SelectedEdge()\Vertex1\X)+" , "+StrD(*SelectedEdge()\Vertex1\Y)+" -> "+StrD(*SelectedEdge()\Vertex2\X)+" , "+StrD(*SelectedEdge()\Vertex2\Y)
         EndSelect
      Next
   CompilerEndIf
   
   ; Construct the result polygons
   While ListSize(*SelectedEdge()) > 0
      FirstElement(*SelectedEdge())
      *FirstEdge = *SelectedEdge()
      *PreviousEdge = *FirstEdge
      AddPolygonPath(*ResultPolygon)
      Repeat
         *PreviousEdge\Picked = #True
         AddPolygonPoint(*ResultPolygon, *PreviousEdge\Vertex1\X, *PreviousEdge\Vertex1\Y)
         ;Debug "AddPolygonPoint "+StrF(*PreviousEdge\Vertex1\X)+" , "+StrF(*PreviousEdge\Vertex1\Y)
         NotFound = #False
         Repeat
            ForEach *SelectedEdge()
               If Abs(*SelectedEdge()\Vertex1\X-*PreviousEdge\Vertex2\X) <= #Polygon_Epsilon And Abs(*SelectedEdge()\Vertex1\Y-*PreviousEdge\Vertex2\Y) <= #Polygon_Epsilon And *SelectedEdge()\Picked = #False
                  *PreviousEdge = *SelectedEdge()
                  Break 2
               EndIf
            Next
            NotFound = #True
         Until #True
      Until NotFound Or (Abs(*FirstEdge\Vertex1\X-*PreviousEdge\Vertex1\X) <= #Polygon_Epsilon And Abs(*FirstEdge\Vertex1\Y-*PreviousEdge\Vertex1\Y) <= #Polygon_Epsilon)
      ForEach *SelectedEdge()
         If *SelectedEdge()\Picked
            DeleteElement(*SelectedEdge())
         EndIf
      Next
   Wend
   
   ProcedureReturn *ResultPolygon
   
EndProcedure



;- Public



;+ Adds an empty path into a valid polygon.
;  Optionally a buffer with vertices and the count of vertices can be passed, which inserted into the path.
Procedure AddPolygonPath(*Polygon.Polygon, *Buffer.PolygonVertex=#Null, Vertices.i=0)
   
   With *Polygon
      
      LastElement(\Path())
      AddElement(\Path())
      If *Buffer And Vertices > 0
         Dim \Path()\Vertex(Vertices-1)
         CopyMemory(*Buffer, @\Path()\Vertex(0), SizeOf(PolygonVertex)*Vertices)
      Else
         FreeArray(\Path()\Vertex())
      EndIf
      
   EndWith
   
   ProcedureReturn *Polygon\Path()
   
EndProcedure


;+ Adds a vertex into a valid polygon at the end of the last added path.
;  Optionally the index of the path to be used can be specified.
;  Optionally the position of the insertion can be passed.
Procedure AddPolygonPoint(*Polygon.Polygon, X.d, Y.d, PathIndex.i=-1, VertexIndex.i=-1)
   
   Protected Vertices.i
   Protected Paths.i
   
   With *Polygon
      
      Paths = ListSize(\Path())
      If Paths = 0
         ProcedureReturn #False
      EndIf
      
      If PathIndex >= Paths-1
         LastElement(\Path())
      ElseIf -PathIndex >= Paths
         FirstElement(\Path())
      ElseIf PathIndex < 0
         SelectElement(\Path(), Paths+PathIndex)
      Else
         SelectElement(\Path(), PathIndex)
      EndIf
      
      If ArraySize(\Path()\Vertex()) = -1
         Vertices = 1
         Dim \Path()\Vertex(0)
      Else
         Vertices = ArraySize(\Path()\Vertex())+2
         ReDim \Path()\Vertex(Vertices-1)
      EndIf
      
      If VertexIndex >= Vertices-1
         VertexIndex = Vertices-1
      ElseIf -VertexIndex >= Vertices
         VertexIndex = 0
      ElseIf VertexIndex < 0
         VertexIndex = Vertices + VertexIndex
      EndIf
      If VertexIndex < Vertices-1
         MoveMemory(@\Path()\Vertex(VertexIndex), @\Path()\Vertex(VertexIndex+1), (Vertices-VertexIndex-1)*SizeOf(PolygonVertex))
      EndIf
      \Path()\Vertex(VertexIndex)\X = X
      \Path()\Vertex(VertexIndex)\Y = Y
      
   EndWith
   
   ProcedureReturn #True
   
EndProcedure


;+ Creates an empty polygon.
Procedure CreatePolygon()
   
   AddElement(Polygon())
   
   ProcedureReturn Polygon()
   
EndProcedure


;+ Copies a valid polygon.
Procedure CopyPolygon(*Polygon.Polygon)
   
   AddElement(Polygon())
   CopyStructure(*Polygon, Polygon(), Polygon)
   
   ProcedureReturn Polygon()
   
EndProcedure


;+ Deletes a valid polygon.
Procedure FreePolygon(*Polygon.Polygon)
   
   ChangeCurrentElement(Polygon(), *Polygon)
   DeleteElement(Polygon())
   
   ProcedureReturn #Null
   
EndProcedure


;+ Counts the number of paths in a valid polygon.
Procedure.i CountPolygonPaths(*Polygon.Polygon)
   
   ProcedureReturn ListSize(*Polygon\Path())
   
EndProcedure


;+ Gets the area of a valid polygon.
Procedure.d PolygonArea(*Polygon.Polygon)
   
   ProcedureReturn *Polygon\Area
   
EndProcedure


;+ Gets the X-coordinate of the center of area of a valid polygon.
Procedure.d PolygonCenterX(*Polygon.Polygon)
   
   ProcedureReturn *Polygon\Center\X
   
EndProcedure


;+ Gets the Y-coordinate of the center of area of a valid polygon.
Procedure.d PolygonCenterY(*Polygon.Polygon)
   
   ProcedureReturn *Polygon\Center\Y
   
EndProcedure


;+ Updates the attributes like area of a valid polygon.
Procedure.i UpdatePolygonAttributes(*Polygon.Polygon)
   
   Protected I.i, MaxI.i
   Protected Area.d, Radius.d
   Protected *P0.PolygonVertex, *P1.PolygonVertex
   
   With *Polygon
      
      \Area            = 0.0
      \MomentOfInertia = 0.0
      \BoundaryRadius  = 0.0
      \Center\X        = 0.0
      \Center\Y        = 0.0
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            *P0 = \Path()\Vertex(I)
            If I = MaxI
               *P1 = \Path()\Vertex(0)
            Else
               *P1 = \Path()\Vertex(I+1)
            EndIf
            Radius = *P0\X**P0\X+*P0\Y**P0\Y
            If Radius > \BoundaryRadius
               \BoundaryRadius = Radius
            EndIf
            Area = 0.5 * (*P0\X**P1\Y - *P1\X**P0\Y)
            \Center\X + Area*(*P0\X+*P1\X)/3
            \Center\Y + Area*(*P0\Y+*P1\Y)/3
            \MomentOfInertia + Area * ( *P0\X**P0\X+*P0\Y**P0\Y + *P1\X**P1\X+*P1\Y**P1\Y + *P0\X**P1\X+*P0\Y**P1\Y )
            \Area + Area
         Next
      Next
      \BoundaryRadius = Sqr(\BoundaryRadius)
      \MomentOfInertia / (12*\Area)
      \Center\X / \Area
      \Center\Y / \Area
      
   EndWith
   
   ProcedureReturn *Polygon
   
EndProcedure


;+ Tests the X- and Y-coordinates whether there is a vertex in the valid polygon.
Procedure PolygonVertexTest(*Polygon.Polygon, X.d, Y.d, Radius.d)
   
   Protected I.i, MaxI.i
   
   With *Polygon
      
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            If (\Path()\Vertex(I)\X-X)*(\Path()\Vertex(I)\X-X) + (\Path()\Vertex(I)\Y-Y)*(\Path()\Vertex(I)\Y-Y) < Radius*Radius
               ProcedureReturn @\Path()\Vertex(I)
            EndIf
         Next
      Next
      
   EndWith
   
EndProcedure


;+ Tests the X- and Y-coordinates whether its inside, outside or on the border of a valid polygon.
Procedure PolygonPointTest(*Polygon.Polygon, X.d, Y.d)
   
   ; Quelle: https://de.wikipedia.org/wiki/Punkt-in-Polygon-Test_nach_Jordan
   
   Protected I.i, MaxI.i
   Protected Sign.d, Cross.d
   Protected *R.PolygonVertex, *S.PolygonVertex
   
   With *Polygon
      
      Sign.d = -1
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            *R = \Path()\Vertex(I)
            If I = MaxI
               *S = \Path()\Vertex(0)
            Else
               *S = \Path()\Vertex(I+1)
            EndIf
            If Abs(Y-*R\Y) <= #Polygon_Epsilon And Abs(Y-*S\Y) <= #Polygon_Epsilon
               If (*R\X <= X And X <= *S\X) Or (*S\X <= X And X <= *R\X)
                  ProcedureReturn #Polygon_Border
               EndIf
            ElseIf Abs(Y-*R\Y) <= #Polygon_Epsilon And Abs(X-*R\X) <= #Polygon_Epsilon
               ProcedureReturn #Polygon_Border
            Else
               If *R\Y > *S\Y
                  Swap *R, *S
               EndIf
               If Not (Y <= *R\Y Or Y > *S\Y)
                  Cross = (*R\X-X)*(*S\Y-Y) - (*R\Y-Y)*(*S\X-X)
                  If Cross > #Polygon_Epsilon
                     Sign = -Sign
                  ElseIf Cross < -#Polygon_Epsilon
                  Else
                     Sign = 0
                  EndIf
               EndIf
            EndIf
         Next
      Next
      If Sign = 1
         ProcedureReturn #Polygon_Inside
      ElseIf Sign = 0
         ProcedureReturn #Polygon_Border
      EndIf
      
      ProcedureReturn #Polygon_Outside
      
   EndWith
   
EndProcedure


;+ Draws a valid polygon with the specified color and flags.
Procedure DrawPolygon(*Polygon.Polygon, Color.i, Flags.i=#Polygon_Filled|#Polygon_Vertices|#Polygon_Orientation)
   
   Protected I.i, MaxI.i
   Protected Direction.f, X.f, Y.f
   Protected MinX.i = OutputWidth()-1
   Protected MaxX.i = 0
   Protected MinY.i = OutputHeight()-1
   Protected MaxY.i = 0
   Protected XI.i, YI.i
   
   With *Polygon
      
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         If MaxI = 0
            If Flags & #Polygon_Vertices
               Circle(\Path()\Vertex(0)\X, \Path()\Vertex(0)\Y, 3, Color)
            Else
               Circle(\Path()\Vertex(0)\X, \Path()\Vertex(0)\Y, 2, Color)
            EndIf
         Else
            For I = 0 To MaxI
               If I = MaxI
                  LineXY(\Path()\Vertex(I)\X, \Path()\Vertex(I)\Y, \Path()\Vertex(0)\X, \Path()\Vertex(0)\Y, Color)
                  Direction = ATan2(\Path()\Vertex(0)\X-\Path()\Vertex(I)\X, \Path()\Vertex(0)\Y-\Path()\Vertex(I)\Y)
                  X = 0.5*\Path()\Vertex(I)\X+0.5*\Path()\Vertex(0)\X
                  Y = 0.5*\Path()\Vertex(I)\Y+0.5*\Path()\Vertex(0)\Y
               Else
                  LineXY(\Path()\Vertex(I)\X, \Path()\Vertex(I)\Y, \Path()\Vertex(I+1)\X, \Path()\Vertex(I+1)\Y, Color)
                  Direction = ATan2(\Path()\Vertex(I+1)\X-\Path()\Vertex(I)\X, \Path()\Vertex(I+1)\Y-\Path()\Vertex(I)\Y)
                  X = 0.5*\Path()\Vertex(I)\X+0.5*\Path()\Vertex(I+1)\X
                  Y = 0.5*\Path()\Vertex(I)\Y+0.5*\Path()\Vertex(I+1)\Y
               EndIf
               If Flags & #Polygon_Orientation
                  LineXY(X, Y, X+Cos(Direction+Radian(160))*11, Y+Sin(Direction+Radian(160))*11, Color)
                  LineXY(X, Y, X+Cos(Direction-Radian(160))*11, Y+Sin(Direction-Radian(160))*11, Color)
               EndIf
               If Flags & #Polygon_Vertices
                  Circle(\Path()\Vertex(I)\X, \Path()\Vertex(I)\Y, 3, Color)
               EndIf
               If Flags & #Polygon_Filled
                  If \Path()\Vertex(I)\X < MinX : MinX = \Path()\Vertex(I)\X : EndIf
                  If \Path()\Vertex(I)\X > MaxX : MaxX = \Path()\Vertex(I)\X : EndIf
                  If \Path()\Vertex(I)\Y < MinY : MinY = \Path()\Vertex(I)\Y : EndIf
                  If \Path()\Vertex(I)\Y > MaxY : MaxY = \Path()\Vertex(I)\Y : EndIf
               EndIf
            Next
         EndIf
      Next
      
      If Flags & #Polygon_Filled
         If MinX < 0 : MinX = 0 : EndIf
         If MaxX > OutputWidth()-1 : MaxX = OutputWidth()-1 : EndIf
         If MinY < 0 : MinY = 0 : EndIf
         If MaxY > OutputHeight()-1 : MaxY = OutputHeight()-1 : EndIf
         MinX = MinX & ~1
         MinY = MinY & ~1
         For XI = MinX To MaxX Step 2
            For YI = MinY To MaxY Step 2
               If PolygonPointTest(*Polygon, XI, YI) = #Polygon_Inside
                  Line(XI, YI, 1, 1, Color)
               EndIf
            Next
         Next
      EndIf
      
      Line(PolygonCenterX(*Polygon)-5, PolygonCenterY(*Polygon), 11, 1, Color)
      Line(PolygonCenterX(*Polygon), PolygonCenterY(*Polygon)-5, 1, 11, Color)
      
   EndWith
   
EndProcedure


;+ Performs a collision test and fills the *PolygonCollisionList with all collision points and their informations.
Procedure PolygonCollision(*Polygon1.Polygon, *Polygon2.Polygon, *PolygonCollisionList.PolygonCollisionList=#Null)
   
   Protected I.i, MaxI.i
   Protected J.i, MaxJ.i
   Protected.PolygonVertex *P0, *P1, *Q0, *Q1
   Protected Det.d, U.d, V.d
   
   With *PolygonCollisionList
      
      ForEach *Polygon1\Path()
         MaxI = ArraySize(*Polygon1\Path()\Vertex())
         ForEach *Polygon2\Path()
            MaxJ = ArraySize(*Polygon2\Path()\Vertex())
            For I = 0 To MaxI
               *P0 = *Polygon1\Path()\Vertex(I)
               If I < MaxI
                  *P1 = *Polygon1\Path()\Vertex(I+1)
               Else
                  *P1 = *Polygon1\Path()\Vertex(0)
               EndIf
               For J = 0 To MaxJ
                  *Q0 = *Polygon2\Path()\Vertex(J)
                  If J < MaxJ
                     *Q1 = *Polygon2\Path()\Vertex(J+1)
                  Else
                     *Q1 = *Polygon2\Path()\Vertex(0)
                  EndIf
                  Det = (*Q1\X-*Q0\X)*(*P1\Y-*P0\Y) - (*Q1\Y-*Q0\Y)*(*P1\X-*P0\X)
                  If Abs(Det) <= #Polygon_Epsilon
                     ; Identisch?
                     If Abs( (*P0\X-*Q0\X)*(*Q0\Y-*P1\Y) - (*P0\Y-*Q0\Y)*(*Q0\X-*P1\X) ) <= #Polygon_Epsilon
                        If *P1\Y-*P0\Y
                           U = (*Q0\Y-*P0\Y)/(*P1\Y-*P0\Y)
                        ElseIf *P1\X-*P0\X
                           U = (*Q0\X-*P0\X)/(*P1\X-*P0\X)
                        Else
                           U = -1
                        EndIf
                        If U >= 0 And U <= 1
                           AddElement(\Collision())
                           \Collision()\Position\X = *Q0\X
                           \Collision()\Position\Y = *Q0\Y
                           \Collision()\Path1 = *Polygon1\Path()
                           \Collision()\Path2 = *Polygon2\Path()
                           \Collision()\PathIndex1 = ListIndex(*Polygon1\Path())
                           \Collision()\PathIndex2 = ListIndex(*Polygon2\Path())
                           \Collision()\Edge1 = I
                           \Collision()\Edge2 = J
                           \Collision()\Factor1 = U
                           \Collision()\Factor2 = 0
                        EndIf
                        If *P1\Y-*P0\Y
                           U = (*Q1\Y-*P0\Y)/(*P1\Y-*P0\Y)
                        ElseIf *P1\X-*P0\X
                           U = (*Q1\X-*P0\X)/(*P1\X-*P0\X)
                        Else
                           U = -1
                        EndIf
                        If U >= 0 And U <= 1
                           AddElement(\Collision())
                           \Collision()\Position\X = *Q1\X
                           \Collision()\Position\Y = *Q1\Y
                           \Collision()\Path1 = *Polygon1\Path()
                           \Collision()\Path2 = *Polygon2\Path()
                           \Collision()\PathIndex1 = ListIndex(*Polygon1\Path())
                           \Collision()\PathIndex2 = ListIndex(*Polygon2\Path())
                           \Collision()\Edge1 = I
                           \Collision()\Edge2 = J
                           \Collision()\Factor1 = U
                           \Collision()\Factor2 = 1
                        EndIf
                        If *Q1\Y-*Q0\Y
                           V = (*P0\Y-*Q0\Y)/(*Q1\Y-*Q0\Y)
                        ElseIf *Q1\X-*Q0\X
                           V = (*P0\X-*Q0\X)/(*Q1\X-*Q0\X)
                        Else
                           V = -1
                        EndIf
                        If V >= 0 And V <= 1
                           AddElement(\Collision())
                           \Collision()\Position\X = *P0\X
                           \Collision()\Position\Y = *P0\Y
                           \Collision()\Path1 = *Polygon1\Path()
                           \Collision()\Path2 = *Polygon2\Path()
                           \Collision()\PathIndex1 = ListIndex(*Polygon1\Path())
                           \Collision()\PathIndex2 = ListIndex(*Polygon2\Path())
                           \Collision()\Edge1 = I
                           \Collision()\Edge2 = J
                           \Collision()\Factor1 = 0
                           \Collision()\Factor2 = V
                        EndIf
                        If *Q1\Y-*Q0\Y
                           V = (*P1\Y-*Q0\Y)/(*Q1\Y-*Q0\Y)
                        ElseIf *Q1\X-*Q0\X
                           V = (*P1\X-*Q0\X)/(*Q1\X-*Q0\X)
                        Else
                           V = -1
                        EndIf
                        If V >= 0 And V <= 1
                           AddElement(\Collision())
                           \Collision()\Position\X = *P1\X
                           \Collision()\Position\Y = *P1\Y
                           \Collision()\Path1 = *Polygon1\Path()
                           \Collision()\Path2 = *Polygon2\Path()
                           \Collision()\PathIndex1 = ListIndex(*Polygon1\Path())
                           \Collision()\PathIndex2 = ListIndex(*Polygon2\Path())
                           \Collision()\Edge1 = I
                           \Collision()\Edge2 = J
                           \Collision()\Factor1 = 1
                           \Collision()\Factor2 = V
                        EndIf
                     EndIf
                  Else
                     U = ( *Q0\X**P0\Y-*Q0\Y**P0\X + *Q1\X**Q0\Y-*Q1\Y**Q0\X + *P0\X**Q1\Y-*P0\Y**Q1\X ) / Det
                     V = ( *Q0\X**P0\Y-*Q0\Y**P0\X + *P0\X**P1\Y-*P0\Y**P1\X + *P1\X**Q0\Y-*P1\Y**Q0\X ) / Det
                     If U >= 0.0 And U <= 1.0 And V >= 0.0 And V <= 1.0
                        AddElement(\Collision())
                        \Collision()\Position\X = *P0\X + U*(*P1\X-*P0\X)
                        \Collision()\Position\Y = *P0\Y + U*(*P1\Y-*P0\Y)
                        \Collision()\Path1 = *Polygon1\Path()
                        \Collision()\Path2 = *Polygon2\Path()
                        \Collision()\PathIndex1 = ListIndex(*Polygon1\Path())
                        \Collision()\PathIndex2 = ListIndex(*Polygon2\Path())
                        \Collision()\Edge1 = I
                        \Collision()\Edge2 = J
                        \Collision()\Factor1 = U
                        \Collision()\Factor2 = V
                     EndIf
                  EndIf
               Next
            Next
         Next
      Next
      
   EndWith
   
EndProcedure



;- Set operations of two polygons

;+ Creates the union of two valid polygons.
Procedure PolygonUnion(*Polygon1.Polygon, *Polygon2.Polygon)
   
   ProcedureReturn UpdatePolygonAttributes(Polygon_Operation(#Polygon_Union, *Polygon1, *Polygon2))
   
EndProcedure


;+ Creates the intersection of two valid polygons.
Procedure PolygonIntersection(*Polygon1.Polygon, *Polygon2.Polygon)
   
   ProcedureReturn UpdatePolygonAttributes(Polygon_Operation(#Polygon_Intersection, *Polygon1, *Polygon2))
   
EndProcedure


;+ Creates the difference of two valid polygons.
Procedure PolygonDifference(*Polygon1.Polygon, *Polygon2.Polygon)
   
   ProcedureReturn UpdatePolygonAttributes(Polygon_Operation(#Polygon_Difference, *Polygon1, *Polygon2))
   
EndProcedure


;+ Creates the difference of two valid polygons.
Procedure PolygonSymmetricDifference(*Polygon1.Polygon, *Polygon2.Polygon)
   
   Protected *Difference1 = Polygon_Operation(#Polygon_Difference, *Polygon1, *Polygon2)
   Protected *Difference2 = Polygon_Operation(#Polygon_Difference, *Polygon2, *Polygon1)
   Protected *SymmetricDifference = Polygon_Operation(#Polygon_Union, *Difference1, *Difference2)
   
   FreePolygon(*Difference1)
   FreePolygon(*Difference2)
   
   ProcedureReturn UpdatePolygonAttributes(*SymmetricDifference)
   
EndProcedure



;- Transformation of a polygon


;+ Alligns a valid polygon to the center of it.
Procedure AlignPolygon(*Polygon.Polygon)
   
   Protected I.i, MaxI.i
   
   With *Polygon
      
      UpdatePolygonAttributes(*Polygon)
      
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            \Path()\Vertex(I)\X - \Center\X
            \Path()\Vertex(I)\Y - \Center\Y
         Next
      Next
      
   EndWith
   
   ProcedureReturn UpdatePolygonAttributes(*Polygon)
   
EndProcedure


;+ Translates a valid polygon along the specified X- and Y-Axes.
Procedure TranslatePolygon(*Polygon.Polygon, X.d, Y.d)
   
   Protected I.i, MaxI.i
   
   With *Polygon
      
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            \Path()\Vertex(I)\X + X
            \Path()\Vertex(I)\Y + Y
         Next
      Next
      
   EndWith
   
   ProcedureReturn UpdatePolygonAttributes(*Polygon)
   
EndProcedure


;+ Rotates a valid polygon with the specified angle (in degree).
;  Optionally a rotation center can be passed.
Procedure RotatePolygon(*Polygon.Polygon, Angle.d, CenterX.d=0.0, CenterY.d=0.0)
   
   Protected I.i, MaxI.i
   Protected Cos.d = Cos(Radian(Angle))
   Protected Sin.d = Sin(Radian(Angle))
   Protected X.d, Y.d
   
   With *Polygon
      
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            X = \Path()\Vertex(I)\X-CenterX
            Y = \Path()\Vertex(I)\Y-CenterY
            \Path()\Vertex(I)\X = X*Cos - Y*Sin + CenterX
            \Path()\Vertex(I)\Y = X*Sin + Y*Cos + CenterY
         Next
      Next
      
   EndWith
   
   ProcedureReturn UpdatePolygonAttributes(*Polygon)
   
EndProcedure


;+ Scales a valid polygon with the specified factor.
;  Optionally a scaling center can be passed.
Procedure ScalePolygon(*Polygon.Polygon, Factor.d, CenterX.d=0.0, CenterY.d=0.0)
   
   Protected I.i, MaxI.i
   Protected X.d, Y.d
   
   With *Polygon
      
      ForEach \Path()
         MaxI = ArraySize(\Path()\Vertex())
         For I = 0 To MaxI
            X = \Path()\Vertex(I)\X-CenterX
            Y = \Path()\Vertex(I)\Y-CenterY
            \Path()\Vertex(I)\X = X*Factor + CenterX
            \Path()\Vertex(I)\Y = Y*Factor + CenterY
         Next
      Next
      
   EndWith
   
   ProcedureReturn UpdatePolygonAttributes(*Polygon)
   
EndProcedure




;- ########### Demo ############

CompilerIf #PB_Compiler_Debugger
   MessageRequester("Info", "Performance limited with enabled debugger!")
CompilerEndIf

Enumeration
   #Window
   #Gadget
   #FontLarge
   #Font
   #Image
EndEnumeration


#Size = 400

OpenWindow(#Window, 0, 0, #Size*3, #Size*2+30, "Polygon Operations", #PB_Window_ScreenCentered|#PB_Window_SystemMenu)
CanvasGadget(#Gadget, 0, 0, WindowWidth(#Window), WindowHeight(#Window))
LoadFont(#FontLarge, "Arial", 20, #PB_Font_Bold)
LoadFont(#Font, "Arial", 10)
AddKeyboardShortcut(#Window, #PB_Shortcut_F12, #PB_Shortcut_F12)



Global *A.Polygon = CreatePolygon()
AddPolygonPath(*A)
AddPolygonPoint(*A, 0.50, 0.10)
AddPolygonPoint(*A, 0.75, 0.35)
AddPolygonPoint(*A, 0.60, 0.35)
AddPolygonPoint(*A, 0.60, 0.80)
AddPolygonPoint(*A, 0.40, 0.80)
AddPolygonPoint(*A, 0.40, 0.35)
AddPolygonPoint(*A, 0.25, 0.35)
RotatePolygon(ScalePolygon(*A, #Size), 30, #Size/2, #Size/2)

Global *B.Polygon = CreatePolygon()
AddPolygonPath(*B)
AddPolygonPoint(*B, 0.50, 0.20)
AddPolygonPoint(*B, 0.75, 0.70)
AddPolygonPoint(*B, 0.25, 0.70)
AddPolygonPath(*B)
AddPolygonPoint(*B, 0.50, 0.34)
AddPolygonPoint(*B, 0.35, 0.64)
AddPolygonPoint(*B, 0.65, 0.64)
ScalePolygon(*B, #Size)
RotatePolygon(*B, -80, PolygonCenterX(*B), PolygonCenterY(*B))




Global *C.Polygon


#ColorA = $00C040
#ColorB = $4000C0
#ColorAB = $FF8000
#ColorGray = $E0E0E0

Procedure OperationText(X.i, Y.i, Operation.s, A.s, B.s)
   
   DrawText(X-TextWidth(Operation)/2, Y, Operation, $000000)
   DrawText(X-TextWidth(Operation)/2-TextWidth(A+" "), Y, A+" ", #ColorA)
   DrawText(X+TextWidth(Operation)/2, Y, " "+B, #ColorB)
   
EndProcedure

Global Filling.i = #True

Procedure Update(MouseX.i=0, MouseY.i=0)
   
   Protected Flags.i, Text.s
   Protected PolygonCollisionList.PolygonCollisionList
   
   If StartDrawing(CanvasOutput(#Gadget))
      Box(0, 0, OutputWidth(), OutputHeight(), $FFFFFF)
      
      DrawingMode(#PB_2DDrawing_Outlined|#PB_2DDrawing_Transparent)
      DrawingFont(FontID(#FontLarge))
      Box(0, 0, #Size, #Size, $C0C0C0)
         DrawText(#Size/2-TextWidth("A")/2, 0, "A", #ColorA)
      Box(#Size, 0, #Size, #Size, $C0C0C0)
         OperationText(#Size+#Size/2, 0, "∪", "A", "B")
      Box(#Size*2, 0, #Size, #Size, $C0C0C0)
         OperationText(#Size*2+#Size/2, 0, "∩", "A", "B")
      Box(0, #Size, #Size, #Size, $C0C0C0)
         DrawText(#Size/2-TextWidth("B")/2, #Size, "B", #ColorB)
      Box(#Size, #Size, #Size, #Size, $C0C0C0)
         OperationText(#Size+#Size/2, #Size, "−", "A", "B")
      Box(#Size*2, #Size, #Size, #Size, $C0C0C0)
         OperationText(#Size*2+#Size/2, #Size, "−", "B", "A")
      
      DrawingFont(FontID(#Font))
      DrawingMode(#PB_2DDrawing_Transparent)
      
      
      If Filling
         DrawText(5, #Size*2+5, "Drawing mode (middle mouse button): Filled", $000000)
         If GetGadgetAttribute(#Gadget, #PB_Canvas_Buttons) & #PB_Canvas_LeftButton
            Flags = #Null
         Else
            Flags = #Polygon_Filled
         EndIf
      Else
         DrawText(5, #Size*2+5, "Drawing mode (middle mouse button): Path & Vertices", $000000)
         Flags = #Polygon_Vertices|#Polygon_Orientation
      EndIf
      Text = "Moving polygon & vertices (left mouse button), rotate (left mouse button + Strg)"
      DrawText(#Size*3-TextWidth(Text)-5, #Size*2+5, Text, $000000)
      
      
      ; A
      ClipOutput(0, 0, #Size, #Size)
      SetOrigin(0, 0)
      DrawPolygon(*A, #ColorA, Flags)
      DrawText(10, 10, "Paths: "+Str(CountPolygonPaths(*A)), $000000)
      DrawText(10, 25, "Area:  "+StrD(PolygonArea(*A), 2), #ColorA)
      
      ; B
      ClipOutput(0, #Size, #Size, #Size)
      SetOrigin(0, #Size)
      DrawPolygon(*B, #ColorB, Flags)
      DrawText(10, 10, "Paths: "+Str(CountPolygonPaths(*B)), $000000)
      DrawText(10, 25, "Area:  "+StrD(PolygonArea(*B), 2), #ColorB)
      
      ;ClearDebugOutput()
      
      ; A ∪ B
      ;Debug "PolygonUnion(*A, *B)"
      *C = PolygonUnion(*A, *B)
      ClipOutput(#Size, 0, #Size, #Size)
      SetOrigin(#Size, 0)
      DrawPolygon(*A, #ColorGray, #Null)
      DrawPolygon(*B, #ColorGray, #Null)
      DrawPolygon(*C, #ColorAB, Flags)
      DrawText(10, 10, "Paths: "+Str(CountPolygonPaths(*C)), $000000)
      DrawText(10, 25, "Area:  "+StrD(PolygonArea(*C), 2), #ColorAB)
      FreePolygon(*C)
      
      ; A ∩ B
      ;Debug "PolygonIntersection(*A, *B)"
      *C = PolygonIntersection(*A, *B)
      ClipOutput(#Size*2, 0, #Size, #Size)
      SetOrigin(#Size*2, 0)
      DrawPolygon(*A, #ColorGray, #Null)
      DrawPolygon(*B, #ColorGray, #Null)
      DrawPolygon(*C, #ColorAB, Flags)
      DrawText(10, 10, "Paths: "+Str(CountPolygonPaths(*C)), $000000)
      DrawText(10, 25, "Area:  "+StrD(PolygonArea(*C), 2), #ColorAB)
      FreePolygon(*C)
      
      ; A - B
      ;Debug "PolygonDifference(*A, *B)"
      *C = PolygonDifference(*A, *B)
      ClipOutput(#Size, #Size, #Size, #Size)
      SetOrigin(#Size, #Size)
      DrawPolygon(*A, #ColorGray, #Null)
      DrawPolygon(*B, #ColorGray, #Null)
      DrawPolygon(*C, #ColorAB, Flags)
      DrawText(10, 10, "Paths: "+Str(CountPolygonPaths(*C)), $000000)
      DrawText(10, 25, "Area:  "+StrD(PolygonArea(*C), 2), #ColorAB)
      FreePolygon(*C)
      
      ; B - A
      ;Debug "PolygonDifference(*B, *A)"
      *C = PolygonDifference(*B, *A)
      ClipOutput(#Size*2, #Size, #Size, #Size)
      SetOrigin(#Size*2, #Size)
      DrawPolygon(*A, #ColorGray, #Null)
      DrawPolygon(*B, #ColorGray, #Null)
      DrawPolygon(*C, #ColorAB, Flags)
      DrawText(10, 10, "Paths: "+Str(CountPolygonPaths(*C)), $000000)
      DrawText(10, 25, "Area:  "+StrD(PolygonArea(*C), 2), #ColorAB)
      FreePolygon(*C)
      
;       DrawingMode(#PB_2DDrawing_Outlined|#PB_2DDrawing_Transparent)
;       PolygonCollision(*A, *B, @PolygonCollisionList)
;       ForEach PolygonCollisionList\Collision()
;          Circle(PolygonCollisionList\Collision()\Position\X, PolygonCollisionList\Collision()\Position\Y, 10, $000000)
;       Next
; ;       
      StopDrawing()
   EndIf
EndProcedure

Update()

Define *SelectedPolygon.Polygon, OldX, OldY
Define *SelectedVertex.PolygonVertex, *Vertex.PolygonVertex
Define MouseX.i, MouseY.i

Repeat
   
   Select WaitWindowEvent()
      Case #PB_Event_CloseWindow
         End
      Case #PB_Event_Menu
         Select EventMenu()
            Case #PB_Shortcut_F12
               If StartDrawing(CanvasOutput(#Gadget))
                  GrabDrawingImage(#Image, 0, 0, OutputWidth(), OutputHeight())
                  SetClipboardImage(#Image)
                  StopDrawing()
               EndIf
         EndSelect
      Case #PB_Event_Gadget
         Select EventGadget()
            Case #Gadget
               MouseX = GetGadgetAttribute(#Gadget, #PB_Canvas_MouseX)
               MouseY = GetGadgetAttribute(#Gadget, #PB_Canvas_MouseY)
               Select EventType()
                  Case #PB_EventType_MiddleButtonUp
                     Filling = 1-Filling
                     Update(MouseX, MouseY)
                  Case #PB_EventType_LeftButtonDown
                     *Vertex = PolygonVertexTest(*A, MouseX, MouseY, 10)
                     If *Vertex
                        *SelectedVertex = *Vertex
                        *SelectedPolygon = *A
                     ElseIf PolygonPointTest(*A, MouseX, MouseY) = #Polygon_Inside
                        *SelectedPolygon = *A
                     EndIf
                     *Vertex = PolygonVertexTest(*B, MouseX, MouseY-#Size, 10)
                     If *Vertex
                        *SelectedVertex = *Vertex
                        *SelectedPolygon = *B
                     ElseIf PolygonPointTest(*B, MouseX, MouseY-#Size) = #Polygon_Inside
                        *SelectedPolygon = *B
                     EndIf
                  Case #PB_EventType_LeftButtonUp, #PB_EventType_MouseMove
                     If *SelectedVertex
                        *SelectedVertex\X + (MouseX-OldX)
                        *SelectedVertex\Y + (MouseY-OldY)
                        UpdatePolygonAttributes(*SelectedPolygon)
                        Update(MouseX, MouseY)
                     ElseIf *SelectedPolygon
                        If GetGadgetAttribute(#Gadget, #PB_Canvas_Buttons) & #PB_Canvas_LeftButton
                           If GetGadgetAttribute(#Gadget, #PB_Canvas_Modifiers) & #PB_Canvas_Control
                              If *SelectedPolygon = *B
                                 RotatePolygon(*SelectedPolygon, Degree(ATan2(MouseX-PolygonCenterX(*SelectedPolygon), MouseY-#Size-PolygonCenterY(*SelectedPolygon))-ATan2(OldX-PolygonCenterX(*SelectedPolygon), OldY-#Size-PolygonCenterY(*SelectedPolygon))), PolygonCenterX(*SelectedPolygon), PolygonCenterY(*SelectedPolygon))
                              Else
                                 RotatePolygon(*SelectedPolygon, Degree(ATan2(MouseX-PolygonCenterX(*SelectedPolygon), MouseY-PolygonCenterY(*SelectedPolygon))-ATan2(OldX-PolygonCenterX(*SelectedPolygon), OldY-PolygonCenterY(*SelectedPolygon))), PolygonCenterX(*SelectedPolygon), PolygonCenterY(*SelectedPolygon))
                              EndIf
                           Else
                              TranslatePolygon(*SelectedPolygon, MouseX-OldX, MouseY-OldY)
                           EndIf
                        EndIf
                        Update(MouseX, MouseY)
                     EndIf
               EndSelect
               Select EventType()
                  Case #PB_EventType_LeftButtonUp
                     *SelectedPolygon = #Null
                     *SelectedVertex = #Null
               EndSelect
               OldX = MouseX
               OldY = MouseY
         EndSelect
   EndSelect
   
ForEver

_________________
Bild
 
BildBildBild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph
BeitragVerfasst: 09.07.2018 01:30 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
Cool. Genau an sowas hab ich heute auch gedacht, nachdem Blender wieder gesponnen hat bei den Boolschen Operationen. Aber für 3D ist das Ganze sowieso noch mal eine ganze Ecke komplizierter.

_________________
Freakscorner.de - Der Bastelkeller | Neustes Video: Neje DK - 1 Watt Laser Engraver
Ubuntu Gnome 16.04.3 LTS x64, PureBasic 5.60 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph
BeitragVerfasst: 09.07.2018 12:46 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
So, habe es jetzt mal kopiert und wollte es testen. Natürlich erst mal mit Debugger. Ist es normal, dass da dieser Fehler kommt?
Code:
[12:43:36] [ERROR] Zeile: 1099
[12:43:36] [ERROR] AddKeyboardShortcut(): Der 'Event' Wert von AddKeyboardShortcut() muss zwischen 0 und 64000 liegen.

Ansonsten funktioniert es aber super. Und der Debugger stört kein bisschen die Geschwindigkeit. :allright:

_________________
Freakscorner.de - Der Bastelkeller | Neustes Video: Neje DK - 1 Watt Laser Engraver
Ubuntu Gnome 16.04.3 LTS x64, PureBasic 5.60 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph
BeitragVerfasst: 09.07.2018 20:04 
Offline
Kommando SG1
Benutzeravatar

Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Ich hatte die #PB_Shortcut_F12 Konstante auch einfach als Event-Nummer genutzt, scheinbar ist die Konstante in Linux deutlich höher ^^.

_________________
Bild
 
BildBildBild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph
BeitragVerfasst: 09.07.2018 20:51 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
Sie ist 65481. :lol:

_________________
Freakscorner.de - Der Bastelkeller | Neustes Video: Neje DK - 1 Watt Laser Engraver
Ubuntu Gnome 16.04.3 LTS x64, PureBasic 5.60 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 5 Beiträge ] 

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye