ich hab da ein problem:

Das Programm soll in der Lage sein, aus einem .txt-File eine beliebige Fläche auszulesen. Aus den ausgelesenen Daten soll der angefertigte Algorithmus einen sinnvoll kurzen Weg berechnen und in der Konsole ausgeben. Dabei ist es wichtig, dass die ganze Fläche befahren werden soll.

die fläche wird mittels koordinaten aus einem txt.file eingelesen. die überlegung ist nun, um die gegebene fläche ein rechteck herumzubasteln und dieses in kästchen zu unterteilen. dann wird unterschieden, ob ein kästchen innerhalb oder außerhalb der zu befahrenden fläche liegt. zum schluss werden die kästchen nacheinander auf der konsole ausgegeben. eine idee ist, dafür den floodfill-algorithmus zu verwenden.

so weit, so gut, kann mir bitte jemand hinweise geben, ob der ansatz was taugt...

lg
don_dorner

Frage: Die Fläche ist wohl in Koordinaten (x,y) von Eckpunkten angegeben, oder? Zwischen zwei dieser Eckpunkte ist dann jeweils eine Linie, die die Begrenzungslinie der Fläche darstellt. Richtig? Falls die Fläche nicht allzu zerrupft aussieht - womit ich meine, dass sie eine relative glatte Begrenzung hat, brauchst Du ja eigentlich nur den Schwerpunkt der Fläche berechnen. Dieser sollte dann innerhalb der Fläche liegen. Mit Floodfill kannst Du dann ja die gezeichnete Fläche (aus den Linien zwischen den Eckpunkten) füllen.

Der Schwerpunkt ist in x :
xS = Summe(x)/n
in y:
yS = Summe(y)/n

n = Anzahl der Eckpunkte,
x, y Koordinaten der Eckpunkte.

Aber es kann auch sein - falls die Fläche eine sternförmige Struktur hat - dass der Schwerpunkt außerhalb der Fläche liegt.

richtig, (x,y)-koordinaten und damit dann die seitenvektoren. die flächen werden nicht allzu viele eckpunkte haben. was bringt mir der schwerpunkt dann, startet der floodfill-algorithmus vom dort weg?

ich brauche dann eine liste mit allen punkten innerhalb der fläche.
wenn ich diese punkte habe möchte ich einen algorithmus drüberlaufen lassen der mir der mir den kürzesten weg findet. zu beachten ist, dass die komplette fläche abefahren werden muss. das programm ist für einen rasenmäher gedacht.
und der startpunkt für den algorithmus muss in einer ecke der fläche sein, da der rasenmäher später nicht irgendwo im feld positioniert werden kann.

Ein anderer Ansatz wären Regionen. Dort unterteilt Windows eine beliebige Fläche in kleine Rechtecke und liefert dir deren Daten frei Haus.

Besonders schnell wird das nicht unbedingt sein, aber vielleicht hilft es ja.

Kann man denn nicht die Fläche in Dreiecke zerlegen?

Man nimmt den momentanen Punkt und die 2 nachfolgenden. Müsste man nur noch checken, ob das Dreieck dann positiv gerichtet ist oder negativ...damit man weiß, ob man Punkte hinzufügen oder entfernen muss.

Ich glaub ich erklär das so wirr, dass es niemand verstehen kann

Bin heute durch Zufall auf etwas gestoßen, wie man es machen könnte.

Annahme ist allerdings, dass du nur EINE Fläche hast (also nicht mehrere kleine).

Dann nimmst du dir 2 aufeinanderfolgende her. Du hast also eine Gerade. Jetzt nimmst du einen Punkt direkt neben der Geraden und machst den Punkt im Polgon Test. Ist der Punkt in deinem Polygon, dann wendest du floodfill auf den an. Ist er es nicht, dann prüfst du den Punkt auf der andren Seite der gerade. Ist dieser Punkt auch nicht im Polygon, dann hast du an der Stelle einen extrem spitzen Winkel. Dann würde ichs nochmal mit einer andren Gerade probieren.

(Auf einen Punkt neben der Gerade kannst du ja kommen, indem du z.B. halbe Strecke + kleines bisschen Normalenvektor der Gerade addierst).

Uh, was genau hast du vor ? Um herauszufinden, auf welcher Seite einer Polygonseite die Innenfläche ist, würde ich einfach die Innenwinkel addieren . Aber ich denke, dass es hier eher um pixel-/einheitenbasiertes Arbeiten geht, sonst wird das mit dem "Alle Punkte im Polygon aufzählen" langwierig . Auf jeden Fall bräuchten wir mehr Informationen.

Zitat:

ich brauche dann eine liste mit allen punkten innerhalb der fläche. wenn ich diese punkte habe möchte ich einen algorithmus drüberlaufen lassen der mir der mir den kürzesten weg findet. zu beachten ist, dass die komplette fläche abefahren werden muss. das programm ist für einen rasenmäher gedacht. und der startpunkt für den algorithmus muss in einer ecke der fläche sein, da der rasenmäher später nicht irgendwo im feld positioniert werden kann.

Der TE will denke ich einen Algorithmus haben mit dem man zu einer gegebenen Fläche einen möglichst kurzen Rasenmäherweg bekommt. Also einen Weg mit dem man jeden Punkt der Fläche mit dem Rasenmäher mindestens einmal besucht hat. Hierbei spielt natürlich die Größe des Rasenmähers eine Rolle.

Wenn die Flächen nicht allzu kompliziert sind, würde ich sie in Rechtecke (in denen dann das althergebrachte "rauf-runter"-Verfahren) und Dreiecke (hier dann vllt spiralförmig vom rand nach innen) aufteilen, dann müsste man nur noch einen guten Weg zwischen den Teilbereichen finden, wobei aber noch zu beachten ist, dass man bei "rauf-runter" und der Spiralmethode an unterschiedlichen Punkten anfangen kann und dann jeweils an unterschiedlichen Punkten endet (okay bei der Spiralmethode endet man immer in der Mitte des Dreiecks das vereinfacht das etwas).

...

Klingt eigentlich so, als suchst du das hier: SCANLINE-ALGORITHMUS

Hallo don

Suche auch mal nach Polygon offsetting.

Eine kurze Beschreibung hierzu findest du auch hier:

www.cgal.org/Manual/..._2/Chapter_main.html

Beste Grüsse

Geri

Hallo,

ich hätte da ein nettes Objekt, dass aus Vektoren die Fläche, Mittelpunkt, Schwerpunkt etc. eines Polygons berechnet.
Nur noch den TXT-Import implementieren und los geht's.

Die Unit mit Objekten im Anhang.



mit Gruß