Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Nachbarschaftsrelation von Polygonen

  • 1
  • 2

Werbeanzeige

Black-Panther

Alter Hase

Beiträge: 1 443

Wohnort: Innsbruck

  • Private Nachricht senden

11

16.01.2009, 18:54

Zur Optimierung könntest du einen modifizierten (auf 2D getrimmten) Hillclimbing-Algorithmus verwenden, und für die erste Ausschlussphase AABB und Sweep and Prune... Wenn das allerdings nicht zur "Laufzeit", also während des Spielens, passieren soll, vergiss diese Optimierungen und mach einen Bruteforce... Je mehr du dran feilst, umso mehr kann dann schief gehen... glaub mir, ich sprech aus Erfahrung ;)
stillalive studios
Drone Swarm (32.000 Dronen gleichzeitig steuern!)
facebook, twitter

AlGaN

Frischling

  • »AlGaN« ist der Autor dieses Themas

Beiträge: 8

  • Private Nachricht senden

12

17.01.2009, 20:01

@nox:

Ja, diese Überlegung hab ich auch gemacht, dazu kommt noch, dass ich nicht mit Sicherheit garantieren kann, dass alle Polygone konvex sind, was die Berechnung eines Schwerpunkts meinen Recherchen nach ziemlich verkompliziert.

@Black-Panther: Ich weiß jetzt nicht so genau, auf was Du hinaus willst, Hill-Climbing Algorithmus ist m.W. doch eine Methode, um Optimierungsprobleme zu lösen, oder ? Hab da bis jetzt noch nicht soviel Ahnung von, inwiefern das auf geometrische Probleme angwendet werden kann.

Mir ist gestern noch eine Idee gekommen, wie das Problem evt. lösbar ist: Ich baue einen BSP- bzw. KD-Tree auf, indem ich solange den 2D-Raum aufteile (x-, y-, x-, y-Richtungen...), bis in einem Knoten (Quadranten) <= 2 Polygone drin sind - dann weiß ich doch, dass diese beiden Polygone eine gemeinsame Kante haben. Das wäre auch einfach zu implementieren, da ich schonmal einen Quadtree eingebaut hatte...
Bin für alle Kommentare zu o.g. Idee dankbar... (hab jetzt noch nicht angefangen, das zu implementieren/testen)

Black-Panther

Alter Hase

Beiträge: 1 443

Wohnort: Innsbruck

  • Private Nachricht senden

13

18.01.2009, 21:52

BSP-Algo ist nicht performant...
Hillclimbing war in diesem Fall so gemeint, dass du ala V-Clip Algorithmus VernoiRegionen aufbaust und Nachbarschaftsrelationen über die Randvertizes eines Polygons erstellst, und so dann nach dem mit dem minimalen Abstand suchst... und wenns eben dann mehrmals passieren soll, dann kannst du die temporale und räumliche Koherenz mit eben diesem Algorithmus voll ausnutzen (Speichern des Startvertex mit dem die Suche nach dem nähesten begonnen wird.).
stillalive studios
Drone Swarm (32.000 Dronen gleichzeitig steuern!)
facebook, twitter

Werbeanzeige

  • 1
  • 2