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!

Suche geometrischen Algorithmus

Werbeanzeige

TypeOverride

Treue Seele

  • »TypeOverride« ist der Autor dieses Themas

Beiträge: 268

  • Private Nachricht senden

1

19.06.2017, 13:11

Suche geometrischen Algorithmus

Hey,

Suche einen Algo der das hier für mich macht:


(Link)


So sieht der Prototyp vereinfacht aus:
List<Rectangle> methode(List<Rectangle>);

Der Input sind "die Roten" Rechtecke auf dem Bild und der Output "die Grünen" Rechtecke.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »TypeOverride« (19.06.2017, 13:36)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

2

19.06.2017, 13:17

Zitat von »TypeOverride«

Sollte ich vielleicht einfach einen NavMesh-Generator, auf Rectangle Basis verwenden? Oder kennt jemand direkt den Namen des Algorithmuses?

Das ist ja nicht ein bestimmter Algorithmus. Es gibt verschiedene Möglichkeiten zur Unterteilung. Was ist denn dein Ziel? Geht es am Ende um NavMeshs?
„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.“

TypeOverride

Treue Seele

  • »TypeOverride« ist der Autor dieses Themas

Beiträge: 268

  • Private Nachricht senden

3

19.06.2017, 13:37

Zitat von »Schorsch«

Zitat von »TypeOverride«

Sollte ich vielleicht einfach einen NavMesh-Generator, auf Rectangle Basis verwenden? Oder kennt jemand direkt den Namen des Algorithmuses?

Das ist ja nicht ein bestimmter Algorithmus. Es gibt verschiedene Möglichkeiten zur Unterteilung. Was ist denn dein Ziel? Geht es am Ende um NavMeshs?


War ne dumme Idee einen Nav-Mesh Algo hier reinzubringen. Da kommt nur Verwirrung auf.
Habe den Thread korrigiert, sprich das mit dem Nav-Mesh entfernt und nun sollte es weniger verwirrend sein.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

4

19.06.2017, 13:42

Es gibt viele Lösungen. Suchst du einfach nur irgendeine, oder forderst du z. B., dass die Anzahl der grünen Rechtecke minimal ist?
David Scherfgens Website | Konzentrationstest Polizei

TypeOverride

Treue Seele

  • »TypeOverride« ist der Autor dieses Themas

Beiträge: 268

  • Private Nachricht senden

5

19.06.2017, 13:58

Zitat von »David Scherfgen«

Es gibt viele Lösungen. Suchst du einfach nur irgendeine, oder forderst du z. B., dass die Anzahl der grünen Rechtecke minimal ist?


Minimal ist natürlich immer schön. Aber das ist erstmal alles egal. Brauche einfach nur paar Stichwörter oder direkte Namen sowelcher Algorithmen um weiter gucken zu können.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

19.06.2017, 14:03

Wenn die Rechtecke alle ganzzahlige Positionen und Größen haben (Integer), dann kannst du einen einfachen "bildbasierten" Ansatz umsetzen. Zu Beginn markierst du alle "Pixel" innerhalb der roten Rechtecke als "abgedeckt". Jetzt iterierst du so lange es noch nicht abgedeckte "Pixel" gibt: Finde das erste "Pixel", das noch nicht abgedeckt ist, und lass dort ein neues grünes Rechteck starten. Lass es so weit wachsen wie möglich, solange es keine bereits abgedeckten "Pixel" überlappt. Du kannst z. B. abwechselnd in x- und y-Richtung vergrößern, bis keine Richtung mehr geht. Dann fügst du dieses Rechteck in die Ergebnisliste ein und markierst die darin liegenden "Pixel" als "abgedeckt".
Wenn die Rechtecke nicht ganzzahlig sind oder die Dimensionen zu groß sind, dann geht der Ansatz etwas abgewandelt trotzdem. Deine "Pixel" sind dann jedoch unregelmäßig. Dann unterteilst du dein "Koordinatengitter" an jeder x-Stelle bzw. y-Stelle, an der irgendein rotes Rechteck startet oder endet.
David Scherfgens Website | Konzentrationstest Polizei

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

7

19.06.2017, 14:20

Man kann einfach greedy gruene Rechtecke erstellen indem man irgendeine freie Stelle sucht und dann das Rechteck so gross werden laesst wie moeglich.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Wirago

Alter Hase

Beiträge: 1 193

Wohnort: Stockerau

Beruf: CRM Application Manager

  • Private Nachricht senden

8

19.06.2017, 14:26

Zitat von »TGGC«

Man kann einfach greedy gruene Rechtecke erstellen indem man irgendeine freie Stelle sucht und dann das Rechteck so gross werden laesst wie moeglich.


Ist die Wahrscheinlich dann nicht sehr hoch, dass sehr viele sehr kleine Rechtecke entstehen, wenn die Startposition "ungünstig" ausgewählt wird?

DucKster

Frischling

Beiträge: 19

Beruf: Student

  • Private Nachricht senden

9

19.06.2017, 14:40

Zitat

Ist die Wahrscheinlich dann nicht sehr hoch, dass sehr viele sehr kleine Rechtecke entstehen, wenn die Startposition "ungünstig" ausgewählt wird?


Ich kann zwar keinen Beweis liefern, aber ich finde auf die schnelle kein einziges Beispiel dafür, dass man mit greedy nicht die minimale Lösung finden würde 8|

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

10

19.06.2017, 14:54

Hier ist übrigens exakt dieses Problem gefragt (mit Google gefunden, gesucht nach "filling space with rectangles"!), und es werden auch Veröffentlichungen genannt, die sich mit der optimalen Lösung beschäftigen (also greedy ist nicht optimal): https://math.stackexchange.com/questions…r-of-rectangles
David Scherfgens Website | Konzentrationstest Polizei

Werbeanzeige

Ähnliche Themen