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!

Kreise/Kugeln, Duplikate entfernen

Werbeanzeige

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

1

18.09.2017, 23:08

Kreise/Kugeln, Duplikate entfernen

Hi,

folgendes Problem:

Ich habe eine Menge von 2D-Kreisen oder 3D-Kugeln und möchte möglichst effizient Duplikate aus der Menge entfernen (bzw. eine neue Menge ohne Duplikate erzeugen). Ein Duplikat liegt dann vor, wenn sich jeweils zwei der Kreise/Kugeln schneiden. Hat jemand eine Idee, wie ich so was umsetzen kann? Ich müsste ja so was Ähnliches wie einen Hash bauen. Ich könnte im vorliegenden Fall zwar notfalls auch den navien O(n²)-Algorithmus umsetzen, aber vielleicht geht es ja mit wenig Aufwand noch effizienter?!

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

2

18.09.2017, 23:14

Du kannst deine Welt vorher partitionieren. Jeder Kreis wird einer Partition zugewiesen. Danach prüfst du Kollisionen nur noch von Kreisen innerhalb einer Partition bzw mit den Kreisen der anliegenden Partitionen. Die Größe kannst du in Abhängigkeit vom größten Kreis wählen. Machst du die Partitionen kleiner musst du gegebenenfalls nicht nur mit direkten Nachbaren prüfen, sondern auch die darauf folgenden mit einberechnen.

edit: Anstatt einer Rasterpartitionierung kannst du auch einen Quadtree/Octree benutzen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

19.09.2017, 07:17

Zitat von »Sk!p«

Ich habe eine Menge von 2D-Kreisen oder 3D-Kugeln und möchte möglichst effizient Duplikate aus der Menge entfernen (bzw. eine neue Menge ohne Duplikate erzeugen). Ein Duplikat liegt dann vor, wenn sich jeweils zwei der Kreise/Kugeln schneiden. Hat jemand eine Idee, wie ich so was umsetzen kann? Ich müsste ja so was Ähnliches wie einen Hash bauen. Ich könnte im vorliegenden Fall zwar notfalls auch den navien O(n²)-Algorithmus umsetzen, aber vielleicht geht es ja mit wenig Aufwand noch effizienter?!

Stell dir mal 3 Kreise vor, die sich allesamt schneiden (so wie hier: https://rechneronline.de/pi/img/three-circles.png). Welche zwei davon sollen rausfliegen, welcher soll bleiben? Ist es egal?
David Scherfgens Website | Konzentrationstest Polizei

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

4

19.09.2017, 11:22

Richtig, Quad/Octrees kamen mir auch schon in den Sinn, aber das wäre dann doch etwas mit Kanonen auf Spatzen geschossen. In der Praxis wird meine Kugel-Menge ohnehin immer weniger als 100 Elemente enthalten. Im Beispiel von David wäre es übrigens egal, welche Kugeln rausfliegen bzw. ich führe dann noch eine Wertigkeit pro Kugel mit und es soll bei übereinanderfallenden Kugeln die "beste" übernommen werden.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

5

19.09.2017, 11:40

Zitat von »Sk!p«

Quad/Octrees kamen mir auch schon in den Sinn, aber das wäre dann doch etwas mit Kanonen auf Spatzen geschossen. In der Praxis wird meine Kugel-Menge ohnehin immer weniger als 100 Elemente enthalten.

Ohne irgendwie vorher zu filtern wirst du vermutlich keine bessere Laufzeit bekommen können. Bei weniger als 100 Elementen ist es aber auch völlig egal. Ein Kollisionscheck von Kugeln ist ja nicht besonders teuer.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Chaia*

Treue Seele

Beiträge: 170

  • Private Nachricht senden

6

19.09.2017, 11:43

Bei maximal 100 Kugeln vergleiche doch einfach Brute Force. Wenns nicht auf nem Taschenrechner laufen soll, solltest du davon nicht allzu viel merken (bzgl. Performance).

Tobiking

1x Rätselkönig

Beiträge: 1 231

  • Private Nachricht senden

7

19.09.2017, 12:46

Zitat von »Sk!p«

Im Beispiel von David wäre es übrigens egal, welche Kugeln rausfliegen bzw. ich führe dann noch eine Wertigkeit pro Kugel mit und es soll bei übereinanderfallenden Kugeln die "beste" übernommen werden.

Falls du während des Prüfdurchlaufs die Kugeln schon entfernst, hast du noch eine Abhängigkeit der Prüfreihenfolge

Situation:
Wert A > B > C
A schneidet B
B schneidet C

1. Fall (B-C vor A-B)
B-C: C entfernen
A-B: B entfernen
=> Ergebnis A

1. Fall (A-B vor B-C)
A-B: B entfernen
B-C entfällt
=> Ergebnis A, C

Das könntest du auflösen wenn du die Kugeln nach Wertigkeit absteigend sortierst und dann der Reihe nach die "kleineren" eliminierst.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

8

19.09.2017, 13:06

Zitat von »Tobiking«

Falls du während des Prüfdurchlaufs die Kugeln schon entfernst, hast du noch eine Abhängigkeit der Prüfreihenfolge

Falls die überhaupt eine Rolle spielt. Er schrieb ja dass es an sich egal ist welche Kugeln bei einer Kollision gelöscht werden.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Werbeanzeige

Ähnliche Themen