Polygon Include - Vereinigung,Schnitt,Differenz - Testphase

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Polygon Include - Vereinigung,Schnitt,Differenz - Testphase

Beitrag von STARGÅTE »

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: Alles auswählen

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
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph

Beitrag von NicTheQuick »

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.
Bild
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph

Beitrag von NicTheQuick »

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: Alles auswählen

[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:
Bild
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph

Beitrag von STARGÅTE »

Ich hatte die #PB_Shortcut_F12 Konstante auch einfach als Event-Nummer genutzt, scheinbar ist die Konstante in Linux deutlich höher ^^.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Polygon Include - Vereinigung,Schnitt,Differenz - Testph

Beitrag von NicTheQuick »

Sie ist 65481. :lol:
Bild
Antworten