Seite 1 von 2
Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 16:26
von Agent
Hi Boarder
Die Suche brachte leider kein brauchbares Ergebnis.
Ich möchte eine Fläche (z.b. den ganzen Bildschirm) mit bliebigen Dreiecken füllen. Aneinandergereiht. Jedoch nicht alle gleichgroß sondern variierend sodass der Eindruck entsteht alle wären unterschiedlich groß. Wobei die Größenvariationen schon in einem gewissen Maße sein sollen. Leider fand ich nicht mal ein passendes Bild um dies zu veranschaulichen.
Ich hoffe das war trotzdem verständlich.
Ich weiß nicht ob ich zufällige Punkte zeichnen soll und diese verbinden (wüsste auch nicht das umzusetzen) oder Dreiecke. So oder so bekomme ich da keinen Ansatz hin. Ideen?
Vielen Dank im voraus!
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 16:36
von STARGÅTE
Agent hat geschrieben:Leider fand ich nicht mal ein passendes Bild um dies zu veranschaulichen.
Wäre aber schön, wenn du noch eins finden würdest, oder schnell mit Paint erstellst, denn zumindest ich, kann mir gerade nichts unter "aneinandergereihte" aber "beliebige angeordnet" vorstellen.
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 17:22
von Agent
Bei meinen prima Zeichenkünsten... Naja. So in der Art:
Ich möchte so den ganzen Hintergrund füllen. Die Dreiecke möchte ich dann füllen und ggf die Ankerpunkte bewegen, aber das erstmal im nächsten Step.
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 18:37
von STARGÅTE
Das hier hat leider nicht ganz das Resultat was ich gehofft hatte:
Code: Alles auswählen
Enumeration
#Window
#Gadget
EndEnumeration
Structure Node
X.i
Y.i
EndStructure
Global NewList Node.Node()
Structure Route
*Node1.Node
*Node2.Node
Length.f
EndStructure
Global NewList Route.Route()
Procedure RouteCollision(*Route.Route)
Protected Cross.f, Difference.Node, Distance.f, Length.f
ForEach Route()
If Route() = *Route
Continue
EndIf
Cross = (Route()\Node2\X-Route()\Node1\X) * (*Route\Node2\Y-*Route\Node1\Y) - (Route()\Node2\Y-Route()\Node1\Y) * (*Route\Node2\X-*Route\Node1\X)
If Cross
Difference\X = *Route\Node1\X - Route()\Node1\X
Difference\Y = *Route\Node1\Y - Route()\Node1\Y
Distance = Difference\X * (*Route\Node2\Y-*Route\Node1\Y) - Difference\Y * (*Route\Node2\X-*Route\Node1\X)
Length = Distance / Cross
If Length > 0.00 And Length < 1.00
Distance = Difference\X * (Route()\Node2\Y-Route()\Node1\Y) - Difference\Y * (Route()\Node2\X-Route()\Node1\X)
Length = Distance / Cross
If Length > 0.00 And Length < 1.00
ProcedureReturn #True
EndIf
EndIf
EndIf
Next
EndProcedure
For N = 1 To 100
AddElement(Node())
Node()\X = Random(799)
Node()\Y = Random(599)
Next
ForEach Node()
*Node.Node = Node()
While NextElement(Node())
AddElement(Route())
Route()\Node1 = *Node
Route()\Node2 = Node()
Route()\Length = Sqr(Pow(*Node\X-Node()\X, 2)+Pow(*Node\Y-Node()\Y, 2))
Wend
ChangeCurrentElement(Node(), *Node)
Next
SortStructuredList(Route(), #PB_Sort_Descending, OffsetOf(Route\Length), #PB_Sort_Float)
ForEach Route()
PushListPosition(Route())
If RouteCollision(Route())
PopListPosition(Route())
DeleteElement(Route())
Else
PopListPosition(Route())
EndIf
Next
OpenWindow(#Window, 0, 0, 800, 600, "WindowTitle", #PB_Window_MinimizeGadget|#PB_Window_ScreenCentered)
CanvasGadget(#Gadget, 0, 0, WindowWidth(#Window), WindowHeight(#Window))
If StartDrawing(CanvasOutput(#Gadget))
ForEach Route()
LineXY(Route()\Node1\X, Route()\Node1\Y, Route()\Node2\X, Route()\Node2\Y, $000000)
Next
StopDrawing()
EndIf
Repeat
Select WaitWindowEvent()
Case #PB_Event_CloseWindow
End
Case #PB_Event_Gadget
Select EventGadget()
EndSelect
EndSelect
ForEver
Ich verbinde hier erst jeden Punkt mit jedem anderen und lösche danach Linien die sich überschneiden und fange dabei bei der längsten an. Leider wird an einigen Stellen zu viel gelöscht, sodass auch Polygone entstehen.
Vermutlich ist das der falsche Anzsatz.
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 19:18
von DarkDragon
Delaunay Triangulation/Voronoi Maps wär vllt etwas. Da lässt sich die Flächengleichheit variieren.
http://de.wikipedia.org/wiki/Delaunay-Triangulation
Was man machen könnte wäre auch eine Subdivision, man fängt mit einem Dreieck an und unterteilt es in mehrere Dreiecke. Danach variiert man die Positionen der Punkte, damit es ungleichmäßig aussieht.
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 22:58
von Agent
@Stargate
Danke für die Mühe!
Schade, kapiert hab ich es beim überfliegen nicht, schaue es mir aber nochmal an
@Darkdragon:
Das sieht ziemlich danach aus (nach den Bildern). Kapiert habe ich da aber nix.
Prinzipiell nach meinem Verständnis brauche ich nur eine Routine die beliebige Punkte (z.B. aus einem Array) alle miteinander verbindet, oder?
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 27.09.2012 23:32
von STARGÅTE
Jo so in etwa. Problem ist halt (wie bei mir) zu "wählen" welche Punkte es sein sollen, damit alle deine "optischen" Kriterien erfüllt werden.
Der Link von DarkDragon ist sehr Hilfreich (zumindest für mich^^), werde dazu mal zu morgen n Demo schreiben, dann auch mit Kommentaren
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 28.09.2012 18:20
von Agent
@stargate
Das wäre ja überragend!
Es sieht so aus, als wäre das VOronoi-Diagramm einfacher. Dies würde mir auch genügen, es müssten nicht zwangsläufig Dreiecke sein. Leider ist mein Mathe zu lang her um dass ich das umgesetzt bekomme. Ich habe schon mal im Netz nach anderen Sourcecodes gesucht und Umsetzungen in JAVA gesehen. Nicht zu erwähnen das es doch etwas zu hoch war. Ich hätte es portieren können, aber nicht verstehen
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 28.09.2012 19:15
von STARGÅTE
So, hier nun der Code, der mit der Umkreismethode arbeitet:
Damit die Dreiecke noch etwas schöner aussehen, werden die Punkte am anfang nicht komplett zufällig verteilt, sonden auf einem Raster nur verschoben.
Code: Alles auswählen
; Knotenpunkte
Structure Node
X.i
Y.i
EndStructure
; Verbindungslinie zwischen Knoten
Structure Route
*Node1.Node
*Node2.Node
EndStructure
; Prüft, ob ein anderer Knoten innerhalb des Umkreises des Dreiecks (aus den Knoten 1, 2, 3) liegt
Procedure InTriangleCircle(List Node.Node(), *Node1.Node, *Node2.Node, *Node3.Node)
Protected x1.f = *Node1\X
Protected x2.f = *Node2\X
Protected x3.f = *Node3\X
Protected y1.f = *Node1\Y
Protected y2.f = *Node2\Y
Protected y3.f = *Node3\Y
; Bestimmung des Umkreises
Protected CircleX.f, CircleY.f, CircleRadius.f
Protected Z = (x3*(y1-y2)+x1*(y2-y3)+x2*(y3-y1))
CircleX = (x3*x3*(y1-y2)+(x1*x1+(y1-y2)*(y1-y3))*(y2-y3)+x2*x2*(y3-y1)) / Z / 2
CircleY = (-x2*x2*x3 + x1*x1*(x3-x2) + x3*(y1*y1 - y2*y2) + x1*(x2*x2-x3*x3+y2*y2-y3*y3)+x2*(x3*x3-y1*y1+y3*y3)) / Z / 2
CircleRadius = 0.5 * Sqr((x1*x1-2*x1*x2+x2*x2+(y1-y2)*(y1-y2))*(x1*x1-2*x1*x3+x3*x3+(y1-y3)*(y1-y3))*(x2*x2-2*x2*x3+x3*x3+(y2-y3)*(y2-y3))/(Z*Z))
; Abfrage ob Knoten drin liegt
ForEach Node()
If Node() <> *Node1 And Node() <> *Node2 And Node() <> *Node3
If (Node()\X-CircleX)*(Node()\X-CircleX) + (Node()\Y-CircleY)*(Node()\Y-CircleY) < CircleRadius*CircleRadius
ProcedureReturn #True
EndIf
EndIf
Next
EndProcedure
; Fügt die Verbindungslinie hinzu, falls sie noch nicht existiert
Procedure AddRouteIfNotExist(List Route.Route(), *Node1.Node, *Node2.Node)
ForEach Route()
If (Route()\Node1 = *Node1 And Route()\Node2 = *Node2) Or (Route()\Node1 = *Node2 And Route()\Node2 = *Node1)
ProcedureReturn #False
EndIf
Next
AddElement(Route())
Route()\Node1 = *Node1
Route()\Node2 = *Node2
EndProcedure
; Führt eine Triangulation aus, dabei werden Knoten übergeben und die Verbindungslinien zurückgegeben
Procedure DelaunayTriangulation(List Node.Node(), List Route.Route())
Protected *Node1.Node, *Node2.Node, *Node3.Node
; Alle 3-Punkt-Kombinationen durchlaufen
ForEach Node()
*Node1 = Node()
While NextElement(Node())
*Node2 = Node()
While NextElement(Node())
*Node3 = Node()
PushListPosition(Node())
; Verbindungslinie erstellen, falls nötig
If Not InTriangleCircle(Node(), *Node1, *Node2, *Node3)
AddRouteIfNotExist(Route(), *Node1, *Node2)
AddRouteIfNotExist(Route(), *Node2, *Node3)
AddRouteIfNotExist(Route(), *Node3, *Node1)
EndIf
PopListPosition(Node())
Wend
ChangeCurrentElement(Node(), *Node2)
Wend
ChangeCurrentElement(Node(), *Node1)
Next
EndProcedure
;- Beispiel
NewList Node.Node()
NewList Route.Route()
Define X, Y
For Y = 0 To 5
For X = 0 To 7
AddElement(Node())
Node()\X = X*100+Random(50)+25
Node()\Y = Y*100+Random(50)+25
Next
Next
DelaunayTriangulation(Node(), Route())
Enumeration
#Window
#Gadget
EndEnumeration
OpenWindow(#Window, 0, 0, 800, 600, "WindowTitle", #PB_Window_MinimizeGadget|#PB_Window_ScreenCentered)
CanvasGadget(#Gadget, 0, 0, WindowWidth(#Window), WindowHeight(#Window))
If StartDrawing(CanvasOutput(#Gadget))
ForEach Route()
LineXY(Route()\Node1\X, Route()\Node1\Y, Route()\Node2\X, Route()\Node2\Y, $000000)
Next
StopDrawing()
EndIf
Repeat
Select WaitWindowEvent()
Case #PB_Event_CloseWindow
End
Case #PB_Event_Gadget
Select EventGadget()
EndSelect
EndSelect
ForEver
Bitte nicht über die Berechung des Umkreises wundern, habe dort nicht optimiert, sondern einfach die Lösung des Gleichungssystem übernommen.
Re: Beliebige Fläche (Screen) mit Dreiecken füllen
Verfasst: 28.09.2012 21:04
von DarkDragon
Wenn dir auch nur die gerasterten Flächen von gewichteten Voronoi Diagrammen genügen kann ich dir morgen schnell mal einen Code von mir aufräumen. Wenn man deren Zentren als Punkte darstellt kommt sowas dabei raus:
http://www.saliences.com/projects/npr/s ... index.html Das war auch Teil meiner Abschlussarbeit.