Mathefreaks

[Hagen Reddmann]

Hi

Ich such gute URL's, Bücher, Info, Source zu folgendem Problem:

Gegeben sind mehrere Rechtecke und deren Eckpunkte. Alle Rechtecke passen in ein gleichmässiges Raster, d.h. die Rechtecke können sich berühren aber nicht überschneiden. Die Berührungskante ist dann bei beiden Rechtecken gleichlang. Nun, ich suche den Algorithmus der mir aus einer Anzahl solcher Rechtecke alle Berührungskanten elimiert, mir aus allen zusammenliegenden Rechtecken ein Polygon bildet, aber nichtzusammengehöhrige Polygone als eigenständige Objekte belässt.

Sehr hilfreich wäre auch der math. NAME für solch ein Algo. Damit könnte ich dann auf Suche gehen

Gruß Hagen

[Nico Bendlin]

Eine spontane Idee wäre CombineRgn zu benutzen je nach Ergebnis SIMPLEREGION / COMPLEXREGION / Fehler wäre das Gebilde noch zusammnehängend oder eben mehrteilig.<p>

Ansonsten ließe sich Deine Beschreibung gut mit einer zweidimensionalen Matrix abbilden (da es sich um ein gleimäßiges Raster handlet, kann man die Kanten vernachlässigen und die Frage eher in Richtung benachbarte Punkte formulieren).<p>

In diesem Zusammenhang solltest Du Dir Algos zum Füllen von Flächen ansehen, das entspricht ziemlich genau der Anforderung alle Punkte (oder eben Matrizen-Felder, wie mann es nennt ist ja egal) einer zusammenhängenden Fläche zu bestimmen.<br>
Die Kanten sind ja leicht aus den Marix-Positionen zu berechnen...<p>

...Gruß Nico

postum scriptum: nur mal so als Gedankenanstoß :

[Hagen Reddmann]

Hi Nico

Jo, die Idee mit den Regions ist mir auch gekommen, der Hacken: Regions werden intern als Rechtecke verwaltet --> Folge davon "vom Regen in die Traufe ". Zudem sind Regions sehr langsam.

Ich zeichne mit PolyPolyLine() etc. (am schnellsten), habe aber Rechtecke als Input.

Die Idee mit der Matrix ist nicht schlecht, aber ich benötige einen Algo. der die Punkte zusammenhängend UND in der richtigen Reihenfolge beibehält, und natürlich sehr schnell muss er sein.
Meine momentane Lösung kennt nur vertikale & horizintale Strecken, und verbindet diese. Danach werden die doppelten Streckenpunkte entfernt.

Ich will aber in Zukunft auch überlappende Bereiche, polygone bereiche und elliptische Bereiche so erzeugen können. Deshalb die Frage nach dem ORT DES WISSENS

Gruß Hage

[Nico Bendlin]

Kennst Du nicht jemanden, der Mathematica 4 hat ?
Ich frage mal einen "Geistes-Bruder", der hat öfter mit solchen Problemen zu tun - Antwort, denke ich so heute abend.

Gruß Nic

[Nico Bendlin]

Das Wort nach dem Du suchst ist: Hüllkurven-Berechnung (envelope, surface).

Gruß Nic

[Hagen Reddmann]

Thanks, das ist schon ein SPRUNG in die richtige Richtung.
Heut abend ist dann wohl Dauer-Surfing angesagt :

[Nico Bendlin]

Du kennst ja sicher C++

Hab' gerade den Tip bekommen, das es einen Header mit einem Template dafür gibt...<p>
In der <b>STL</b>-Klassenbibliothek gibts in <b>Map.h</b> (ursprünglich von Hewlett-Packard) eine Klasse Map.<br>
Mit deren Hilfe kann man (über eine Baum-Struktur) die doppelten Kanten finden und dann entfernen.

Gruß Nic

[Hagen Reddmann]

Hi Nico

Unter "Hüllkurven, etc." hab ich nur Schei. gefunden, nichts von Bedeutung. Ich habe mir auch nochmal die Regions/GetRegionData angeschaut -> wie gesagt, vom Regen in die Traufe. ABER, gestern Nacht hab ich dann selber nachgedacht, und es ist für den ersten Schritt rel. einfach.
Angenommenen es dürfen nur Rechtecke die aus den Zellen eines Gitters bestehen benutzt werden. D.h. zwei Rechtecke können identisch, völlig getrennt oder an EINER Kante zusammenstoßen. Als erstes werden die Rechtecke in 4 Strecken zerlegt und diese in eine Punktliste eingefügt. Dabei wird linksherum das Rechteck zerlegt. Doppelte Strecken werden nicht hinzugefügt, antiparallele Strecken werden nicht hinzugefügt und die antiparellele Strecke wird aus der Liste entfernt. Zum Schluß bleiben also Linien übrig die nicht überlappen, allerdings noch nicht verbunden sind. Das macht der zweite Schritt. Für jeden Endpunkt einer Linie wird ein passendes Gegenstück gesucht und nur dessen Endpunkt angehängt. Irgendwann muß ich wieder im Ausgangspunkt einer Figur landen, geht ja garnicht anders. Ein Viereck besteht also aus 5 Punktkoordinaten , wobei die Letzte mit der Ersten identisch ist.

Fazit: 1 Stunde mal selber nachgedacht, 1 Stunde gecodet fertig war mein Code

Gruß Hagen

PS: das löst aber nur ein spezielles Problem. An einer ganz allgemeinen Lösung für verschiedene Ausgangsfiguren bin ich denoch interessiert

[Fritz Schulze]

Hallo Hagen <br><br>
Folgende Idee<br>
1. Memory-DC über die Win-API erstellen mit zugehörigen Bitmap<br>
2. alle Figuren (Rechtecke, Ellipsen, Polygone et c. ) einfarbig<br>
- auf das Bitmap zeichnen<br>
3. das Bitmap waagerecht und senkrecht nach Farbübergängen durchforsten<br>
- und Randpixel setzen.<br>
4. das ganze irgendwie speichern<br><br>
Das ist zwar keine mathematische Lösung aber wenn man an Flächen <br>
unter Parabeln, Sinusfunktionen, Hyperbeln et c. denkt ...<br&gt