Geometrische Monte Carlo Methode

Neue Frage »

Surveyor Auf diesen Beitrag antworten »
Geometrische Monte Carlo Methode
Meine Frage:
Hallo Leute,
ich sitze gerade an einem Problem und hoffe, dass ihr mir vielleicht ein paar Tipps geben könnt.

Ich habe ein Polygon mit n Ecken. Dieses Polygon kann konkave aber auch konvexe Ecken enthalten. Dieses Polygon ist immer anders und in dessen Lage und Orientierung fix. Es kann also nicht verdreht oder verschoben werden.
Jetzt möchte ich das Polygon in Rechtecke einteilen die eine bestimmte Fläche nicht überschreiten. Zudem sollen diese Rechtecke jedoch auch noch andere Kriterien erfüllen:

- maximale Fläche nicht übersteigen (kleiner können sie sein)
- Rechtecke können in beliebiger Lage und Orientierung sein
- Polygon kann ruhig zunächst geschnitten werden (überstehende Rechtecke werden dann nachträglich abgeschnitten)
- es soll die geringste Anzahl an Rechtecken gefunden werden
- Rechtecke müssen Rechtecke sein, keine Quadrate (nur wenn nicht anders möglich)

Meine Ideen:
Ich habe zu dem Thema bis jetzt nur den Algorithmus "Problem der Museumswächter" gefunden, indem das Polygon in Dreiecke aufgeteilt wird.

Meine Idee wäre, dass man es mit der Monte Carlo Methode versuchen könnte.
Also einfach so viele Möglichkeiten durchrechnen lassen bis die gewünschte Konstellation vorhanden ist.
Ich habe leider nur keine Erfahrung damit und wüsste nicht wie ich das umsetze.

Vielleicht ein Raster mit verschieden großen Rechtecken über das Polygon legen und dann das Raster so oft verändern bis beste Anpassung gefunden ist?

Programmieren ist nicht das Problem. Schön wäre eben eine analytische Methode dafür zu finden.

Vielen Dank im voraus!!

Surveyor
HAL 9000 Auf diesen Beitrag antworten »

Ich bin generell von deinem Anliegen irritiert: Ein allgemeines Polygon mit Ecken lässt sich i.a. gar nicht in endlich viele Rechtecke zerlegen, das geht z.B. schon bei einem Dreieck nicht. Oder sprichst du nur von Polygonen mit achsenparallelen Seiten, d.h., die nur Innenwinkel 90° sowie 270° haben? verwirrt

Zitat:
Original von Surveyor
- Rechtecke müssen Rechtecke sein, keine Quadrate (nur wenn nicht anders möglich)

Jedes Quadrat ist auch ein Rechteck, insofern ist dieser Satz Unsinn und bedarf einer Umformulierung.
Surveyor Auf diesen Beitrag antworten »

Hallo HAL 9000,

nee ich meine Polygone in jeglicher Form. Die Rechtecke (vielleicht auch wieder Polygon mit 4 Ecken genannt =)) müssen auch nicht exakt in das Polygon passen. Vielleicht sind die beiliegenden Bilder etwas besser für das Verstehen des Problems.
HAL 9000 Auf diesen Beitrag antworten »

An den Rändern hast du doch dann keine Rechtecke mehr. unglücklich

Es geht also anscheinend gar nicht um "Zerlegung" (bzw. bei dir "einteilen" genannt), sondern eher "Überdeckung" - ist das so? Falsch gewählte Begriffe und (zumindest erst) keine Skizze kann schon ziemlich verwirren. verwirrt
Surveyor Auf diesen Beitrag antworten »

Tut mir leid wenn es zu unklar ist.
Habe deswegen extra:

"- Polygon kann ruhig zunächst geschnitten werden (überstehende Rechtecke werden dann nachträglich abgeschnitten)"

geschrieben.

Dachte zur Berechnung ist es einfacher erst mit Rechtecken zu arbeiten und diese dann nur zu schneiden.
HAL 9000 Auf diesen Beitrag antworten »

Ok, für eine vorgegebene Polygonfläche (als Punktmenge) und eine maximale Flächengröße suchst du also ein minimales , so dass es abgeschlossene Rechtecke mit

sowie für

gibt.


Ohne die Beschränkung wäre die Antwort trivialerweise , so ist es natürlich erheblich komplizierter. Sofort klar sind lediglich die groben Schranken , wobei ein Rechteck mit ist, mit welcher Winkelneigung auch immer. Augenzwinkern
 
 
Surveyor Auf diesen Beitrag antworten »

Mir fällt gerade noch was zu "Random Sampling" ein. Gibt es da Möglichkeiten eine Geometrie zu definieren, die Lage und Orientierung "Random" zu setzen, mit der Bedingung dass diese Geometrien aneinander liegen müssen?
Surveyor Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Ok, für eine vorgegebene Polygonfläche (als Punktmenge) und eine maximale Flächengröße suchst du also ein minimales , so dass es abgeschlossene Rechtecke mit

sowie für

gibt.


Ohne die Beschränkung wäre die Antwort trivialerweise , so ist es natürlich erheblich komplizierter. Sofort klar sind lediglich die groben Schranken , wobei ein Rechteck mit ist, mit welcher Winkelneigung auch immer. Augenzwinkern


Genau, Neigung des "Schrankenrechtecks" ist erstmal egal. Wie würde man jetzt die n-Rechtecke generieren, sodass n minimal ist?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Surveyor
Wie würde man jetzt die n-Rechtecke generieren, sodass n minimal ist?

Ich hab nicht gesagt, dass ich das Patentrezept für die von dir gesuchte Gesamtlösung in der Tasche habe - leider nein. smile

Man könnte für eine (zunächst) vorgegebene Richtung dieses von mir genannte Umfassungsrechteck hernehmen. In einem ersten Ansatz könnte man es etwa gitterförmig in kongruente, genügend kleine Teilrechtecke zerlegen und dann schauen, welche dieser Teilrechtecke auch wirklich gebraucht werden, d.h. ein Teil liegt ja womöglich vollständig außerhalb . Das optimale wird man mit dieser Methode für beliebige Polygone A sicher nicht erzielen, aber es wäre zumindest ein Anfang für irgend eine "suboptimale" Lösung. Mehr kann ich bei oberflächlicher Betrachtung nicht bieten. Wie du von so einem einfachen Gitter zu komplizierteren Rechteck-Zerlegungen von kommst, bleibt deinem kreativen Geist überlassen. Augenzwinkern
Surveyor Auf diesen Beitrag antworten »

Ich denke, dass eine analytische Lösung nicht so schnell zu berechnen ist und denke, dass ich einfach das umfassende Rechteck nehme, die Linien, welche orthogonal zueinander stehen und somit das Raster bilden, lege ich variabel. Genauso wie die Richtung des umfassenden Rechtecks. Dann könnte ich per Monte Carlo ja eine Million Fälle berechnen und nach jedem Fall die Anzahl der entstandenen Rechtecke zählen. Dann wähle ich den Fall mit der geringsten Anzahl heraus und stutze überstehende Linien auf das Polygon.
Realistisch?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »