Geometrie in der Praxis: Distanzen auf unregelmäßige Flächen

ChrisPlusPlus

Kurze Einleitung:
Ich suche ein Verfahren (kostengünstig, soll programmiert werden), welches mir zu einer (unregelmäßigen) Fläche die größte Distanz zweier darin befindlicher Punkte liefert.

Konkretes Beispiel:
Die größte Distanz auf einem Quadrat bilden die jeweils gegenüberligenden Eckpunkte. Bei einem Quadrat der Seitenlänge = 1, wäre die größte Distanz dieser Fläche Wurzel 2.

Ich dachte da zuerst an den kleinstmöglichen Umkreis der Fläche, dessen Durchmesser die gesuchte Distanz wäre.

Gibt es da noch ein einfacheres Verfahren? Und wenn nein, wie kann bei einem unregelmäßigen Körper die eben erkläret Distanz ermitteln.

Na, hat da irgend ein kleiner Mathematicus eine Idee?

Alle möglichen Paare von Eckpunkten nehmen und jeweils den Abstand bestimmen - der größte Wert daraus ist der maximale Abstand im Objekt.

for i=1 to eckenzahl-1
  for j=i+1 to eckenzahl
    dist=distanz(ecken[i],ecken[j])
    if dist>max_dist then max_dist=dist
  next
next

PS: Das mit dem Umkreisradius klappt ziemlich sicher nicht so, wie du dir das gedacht hast - beim Quadrat haut's hin, aber beim gleichseitigen Dreieck schon nicht mehr (Maximaldistanz = a, Umkreisdurchmesser = 2a/sqr(3)).

ChrisPlusPlus

Ich habe nur eine Punktemenge (Pixelgrafik und keine Vektorgraphik) zur Verfügung und im seltesten Falle eine geometrische Figur.

Ich müßte also die Distianz jeden Punktes mit allen Punkten messen, daß ist leider nicht kostengünstig!

Schade, aber dennoch danke für die Antwort!

CStoll

Du könntest deine Punktmenge eventuell etwas einschränken, indem du nur die Pixel auf der Objektkante verwendest (die Objektkante findest du z.B., indem du überprüfst, wieviele Nachbarn des Punktes auch zu deinem Objekt gehören).

XFame

Ich hab da generell mal eine Frage:

Was ist mit der groessten Distanz zweier Punkte gemeint?
Der Abstand der zwei Punkte, die am weitesten von einander entfernt sind?
Oder ist es die kuerzeste, auf der Flaeche liegende, Verbindung zwischen zwei Punkten, wo die Verbindung am groessten wird.
(Ich hoffe es ist nicht zu undeutlich.)

Der Unterschied wird schnell klar:
Direkte Verbindung:

*----\
|\----\
| \----\
|  \----\
|  /----/
| /----/
|/----/
*----/

Der "Weg" also die kuerzeste Verbindung auf der Flaeche (genau an der "inneren" Kante):

*----\
 \----\
  \----\
   \----\
   /----/
  /----/
 /----/
*----/

Jester

Vielleicht kannst Du bei der Gelegenheit gleich noch verraten was eine "unregelmäßige Fläche" ist. Ist das ein Polygon? Oder eine beliebige zusammenhängende Figur? Oder was soll das genau sein?