Punkt finden der in einem Shape liegt..?

[sirbender]

Hallo,

ich habe einen Shape (genauer GeneralPath). Dieser hat eventuell auch Bereiche in seinem Inneren die nicht gerendert werden (flapsig ausgedrueckt: Loecher).

Nun suche ich eine Methode wie ich sicher einen Punkt finden kann, der in dem Shape liegt. Es ist egal welcher Punkt. Hauptsache er liegt im Shape. Nun koennte ich zum Beispiel zufaellig Punkte generieren die innerhalb des umschliessenden Rechtecks des Shape liegen und via Shape.contains(Point) tested ob die Punkte darin liegen. Wenn ein Punkt im Shape liegt breche ich ab da ich habe was ich will.

Ich frage mich aber ob es nicht einfacher und direkter geht ohne ausprobieren? Kenne ich direkt Punkte die sicher im Shape liegen?

 

[strußi]

wenn die löcher gleich Kreise sind und größer 3Pixel dann kannst du aus jeder ecke einen punkt nach innen gehen und hast damit sofort einen punkt

 

[sirbender]

wenn die löcher gleich Kreise sind und größer 3Pixel dann kannst du aus jeder ecke einen punkt nach innen gehen und hast damit sofort einen punkt

Solche Ueberlegungen sind sicher richtig und ich hab sie so aehnlich auch angestellt. Nur nimmst du halt viel an. Zum Beispiel, dass es Loecher gibt. Ich sagte oben "eventuell".
Desweiteren ist auch die Groesse der Loecher von dir eine Annahme. Auch bin ich mir jetzt nicht 100% sicher, was du mit "jeder Ecke" meinst. Ein Shape hat gewoehnlich keine "Ecke" sondern eine Umrandung.

 

[strußi]

ok, mein verständnisfehler. Kannst du über die Shapeform nicht ableiten ob ein Punkt innerhalb des Shapes liegt

Wenn du in einem x/y Koordinatensystem denkst und das Shape reinlegst?
z.b. Jedes Shape hat ymax, ymin, xmax und xmin, daraus kannst du dann den mittelpunkt errechnen, der sollte auf jeden fall im Shape liegen,

 

[Tobse]

Ich denke, dass es mathematisch unmglich ist, in einer Beliebigen form mit beliebig großen und beliebig-förmigen "Löchern" deterministisch und explizit einen solchen Punkt zu erreichen; demnach halte ich den probabilistischen Ansatz für am sinnvollsten.

Den kannst du aber optimieren. Anstadt einfach einen Punkt aus dem Umschließenden Rechteck zu wählen, kannst du z.B. n Punkte auf der "Umrandung" wählen, eine Gerade zwischen ihnen aufstellen und auf diesen Geraden 3-4 Punkte ausprobieren.

EDIT:

Wenn du in einem x/y Koordinatensystem denkst und das Shape reinlegst?
z.b. Jedes Shape hat ymax, ymin, xmax und xmin, daraus kannst du dann den mittelpunkt errechnen, der sollte auf jeden fall im Shape liegen,

Nein, das muss er nicht, ein solches "Loch" kann ja auch dort liegen. Aber auch der Mittelpunkt des umschließenden Rechtecks ist sehr wahrscheinlich drin, den also auch austesten.

 

[Dumdidum]

Eine andere Möglichkeit wäre z.B. auch:

1.) Berechne das Umschließende Rechteck
2.) Wähle hieraus 2 Punkte auf unterschiedlichen Seiten (also z.B. Mittelpunkt der oberen Rechtecklinie und Mittelpunkt der unteren Rechtecklinie, oder z.B. (0,0) und (1,1) also 2 Ecken)
3.) Es entsteht also eine Linie zwischen den 2 Punkten auf denen es Punkte geben MUSS (wenn es sich nicht auch um mehrere nicht miteinander verbundene Shapes handeln kann)
4.) Nun sollte man möglichst sinnvoll Punkte zum "testen" wählen.
5.) Mein Vorschlag immer letztendlich die Mittelpunkte auf der Linie testen, bei welcher dann bei den Teillinien wieder der Mittelpunkt getestet wird (und eben 1 Ebene nach der anderen).

Die Möglichkeit wäre auf jedenfall eine Verbesserung zum Test gegenüber beliebige Punkte innerhalb des Umschließenden Rechteckes.

 

[Tobse]

Eine andere Möglichkeit wäre z.B. auch:

1.) Berechne das Umschließende Rechteck
2.) Wähle hieraus 2 Punkte auf unterschiedlichen Seiten (also z.B. Mittelpunkt der oberen Rechtecklinie und Mittelpunkt der unteren Rechtecklinie, oder z.B. (0,0) und (1,1) also 2 Ecken)
3.) Es entsteht also eine Linie zwischen den 2 Punkten auf denen es Punkte geben MUSS (wenn es sich nicht auch um mehrere nicht miteinander verbundene Shapes handeln kann)
4.) Nun sollte man möglichst sinnvoll Punkte zum "testen" wählen.
5.) Mein Vorschlag immer letztendlich die Mittelpunkte auf der Linie testen, bei welcher dann bei den Teillinien wieder der Mittelpunkt getestet wird (und eben 1 Ebene nach der anderen).

Die Möglichkeit wäre auf jedenfall eine Verbesserung zum Test gegenüber beliebige Punkte innerhalb des Umschließenden Rechteckes.

Da Stimme ich zu. Solange nicht beide Punkte auf der selben Kante des umschließenden Rechtecks liegen sollte dieser Algorithmus in den Meissten Fällen nach spätestens 3-4 Ebenen ein Resultat haben (damit wären 9 bis 16 Punkte getestet, das ist im Rahmen).

 

[sirbender]

Ich habe ja auch den PathIterator. Also die Punkte die den Shape definieren. Wenn ich da einfach einen von denen nehme und anfange alle 8 direkt angrenzenden Pixel zu testen ob sie im Shape oder ausserhalb liegen.

Sollte das nicht effizienter sein?

 

[Dumdidum]

Ich habe ja auch den PathIterator. Also die Punkte die den Shape definieren. Wenn ich da einfach einen von denen nehme und anfange alle 8 direkt angrenzenden Pixel zu testen ob sie im Shape oder ausserhalb liegen.

Sollte das nicht effizienter sein?

Ja das hat zumindest ja einen garantierten worst case von 8 Was dann wirklich schneller ist hängt dann vom shape ab

Ich frage mich ja nur, dass wenn du wirklich auch einfach alle Punkte hast das nicht gleich dann so gemacht hast und zufällige Punkte testen wolltest?
Ich mein letztendlich ist es einfach komplett egal ob du 1 oder 100 punkt testen wirst. Den unterschied wirste ja ned merken.

Darf man fragen warum du überhaupt einen x-beliebigen Punkt innerhalb des shapes brauchst? Ich mein warum tut es dann nicht gleich ein eckpunkt? der liegt ja auch im shape...

 

[sirbender]

Ja das hat zumindest ja einen garantierten worst case von 8 Was dann wirklich schneller ist hängt dann vom shape ab

Ich frage mich ja nur, dass wenn du wirklich auch einfach alle Punkte hast das nicht gleich dann so gemacht hast und zufällige Punkte testen wolltest?
Ich mein letztendlich ist es einfach komplett egal ob du 1 oder 100 punkt testen wirst. Den unterschied wirste ja ned merken.

Darf man fragen warum du überhaupt einen x-beliebigen Punkt innerhalb des shapes brauchst? Ich mein warum tut es dann nicht gleich ein eckpunkt? der liegt ja auch im shape...

Was ist denn ein Eckpunkt?

Ich will den Shape fuellen. Der Startpunkt des FloodFill-Algos muss innerhalb des Shape liegen. Und ich will die Suche nach dem Punkt schon effizient machen. Ist ein Performance-Flaschenhals weil ich das sehr oft machen muss.

Muss mal schauen wie billig es ist die Pfadpunkte zu kriegen. Man muss sich ja den PathIterator holen. Glaub der wird erst "gebaut".

Ich haette mich gefreut wenn es eine mathematisch eindeutige Loesung gaebe zu dem Problem. Gibts scheinbar nicht.

 

[Dumdidum]

Mit "Eckpunkt" meinte ich einen deiner Punkte am Rand des Shapes, die diesen ja definieren.

Aber für einen floodFill algorithmus würde dir ein Eckpunkt natürlich nicht ausreichen.


Allerdings erschließt sich mir nicht ganz, warum du überhaupt ein Floodfill algorithmus benutzt? Und ned einfach auf deinem Graphics Object "fill" aufrufst!? Aber ist sicher ne Übungsaufgabe oder sowas wo ihr eben Floodfill benutzen müsst?!

 

[sirbender]

Genau