Definitionen von Durchmesser, Umfang etc. von Polygonen

Neue Frage »

VerwirrterWirrkopf Auf diesen Beitrag antworten »
Definitionen von Durchmesser, Umfang etc. von Polygonen
Meine Frage:
Hallo,

ich bin gerade dabei ein Programm zu schreiben, dass von 2D-Punktwolken diverse Eigenschaften (Fläche, Rundheit, usw.) ausrechnen soll und habe ein kleines Definitionsproblem:



Meine Ideen:
Es fängt schon beim Durchmesser an:
Wenn ich einen (verformten) Kreisring habe und davon den maximalen und minimalen Durchmesser wissen möchte, habe ich mir überlegt, brauche ich erstmal den Mittelpunkt/Schwerpunkt.
Beim Kreisring liegt der außerhalb der Wolke. Das heißt beim Messen der "Dicke" "in Richtung Schwerpunkt" geht meine Messung nicht durch den Schwerpunkt.
Oder messe ich dann vom Randpunkt durch den Schwerpunkt bis zum Rand der konvexen Hülle?

Aber ist das dann noch der Druchmesser? Schließlich wäre das nicht 2*r wenn man den Schwerpunkt als Mitte annimmt.

Und was wäre von so einem konkaven Ding der Umfang? Der summierte Abstand aller Randpunkte oder nach Definition des Umkreises der Umfang des Umkreises?

Kennt eventuell jemand eine Seite, auf der das alles klar definiert und beschrieben steht?

Danke schonmal.
HAL 9000 Auf diesen Beitrag antworten »

Es gibt verschiedene Ansichten darüber, was unter "Durchmesser" zu verstehen ist.

1) Normalerweise definiert man den Durchmesser einer Punktmenge gemäß , d.h., der Durchmesser ist der maximale (supremale) Abstand zweier beliebiger Punkte der Menge.

2) Eine andere Ansicht wäre , d.h. der Durchmesser ist der Durchmesser des kleinsten Kreises (Kugel etc.), der die gegebene Menge vollständig enthält.

Klar ist , und für viele Mengen gilt echt <: Z.B. bei einem gleichseitigen Dreieck der Seitenlänge 1 sind sowie .


Dein Vorgehen tendiert eher zu Ansicht 2, aber es ist nicht gesagt, dass der Schwerpunkt jener Punkt in der Definition ist: Man kann sich lediglich sicher sein, dass ist.
 
 
VerwirrterWirrkopf Auf diesen Beitrag antworten »

Hi,

danke für die Antwort.

Klingt so, als wäre Variante 1 das Standardvorgehen und Variante 2 dafür anschaulicher.
Muss ich mir mal überlegen was ich nehme, den maximalen Abstand zweier Punkte hatte ich instinktiv schon umgesetzt, die Zweifel kamen erst, als ich mir mehr Gedanken darüber gemacht hatte Big Laugh

Wie siehts denn mit dem Umfang aus?
Bei einer Punktwolke, die man als geschlossen ansehen kann, also z.B. ein gezeichnetes Polygon wäre der Umfang die Summe der einzelnen Teilverbindungen.

Aber die Punktewolke ist als solche ja nicht geschlossen, und hat auch keine eindeutige konkave Hülle.
Geht man da dann auch eher über den Umfang eines fest definierbaren Kreises?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von VerwirrterWirrkopf
Aber die Punktewolke ist als solche ja nicht geschlossen, und hat auch keine eindeutige konkave Hülle.

Du meinst konvexe Hülle.

Wieso meinst du, die ist nicht eindeutig? Wenn beschränkt ist, dann ist m.E. die konvexe Hülle eindeutig definiert. verwirrt
VerwirrterWirrkopf Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zitat:
Original von VerwirrterWirrkopf
Aber die Punktewolke ist als solche ja nicht geschlossen, und hat auch keine eindeutige konkave Hülle.

Du meinst konvexe Hülle.

Wieso meinst du, die ist nicht eindeutig? Wenn beschränkt ist, dann ist m.E. die konvexe Hülle eindeutig definiert. verwirrt


Nene, ich meine schon die konkave Hülle.

Bei einem konkaven Polygon, das fertig gezeichnet mit allen Verbindungen angegeben ist, wäre der gezeichnete Rand die konkave Hülle. Die konvexe Hülle wäre größer (von der Fläche, nicht vom Umfang her).
Dann könnte man über die Verbindungen der Einzelpunkte den Umfang im Sinne der "Summe der Randstücke" berechnen.

Wenn keine Verbindungen vorgegeben sind kann man keine eindeutige konkave Hülle mehr bilden.
Jetzt will aber jemand den Umfang wissen. Nimmt man dann den Umfang der konkaven Hülle oder des Umkreises oder was ganz anderes?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von VerwirrterWirrkopf
Nene, ich meine schon die konkave Hülle.

Den Begriff kenne ich nicht. Was du beschreibst, ist einfach schlicht nur der Umfang eines Polygons. Wie eine solche "konkave Hülle" bei Punktmengen (ohne jede Ordnung wie bei der Eckpunktfolge eines Polygons) aussehen soll, noch dazu bei unendlichen vielleicht gar überabzählbaren Punktmengen, musst du erstmal definieren. unglücklich
VerwirrterWirrkopf Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zitat:
Original von VerwirrterWirrkopf
Nene, ich meine schon die konkave Hülle.

Den Begriff kenne ich nicht. Was du beschreibst, ist einfach schlicht nur der Umfang eines Polygons. Wie eine solche "konkave Hülle" bei Punktmengen (ohne jede Ordnung wie bei der Eckpunktfolge eines Polygons) aussehen soll, noch dazu bei unendlichen vielleicht gar überabzählbaren Punktmengen, musst du erstmal definieren. unglücklich


Das müsste man wohl, das kann ich aber nicht leisten.

Ich kenne eine konkave Hülle aus Berechnungen unter der Zuhilfenahme von maximalen (aber frei wählbaren) einschließbaren Winklen zwischen zwei aufeinanderfolgenden Verbindungen. Da kommt dann je nach Parametern was raus, was dem ähnelt, wenn man jemanden sagt "mal mal den Rand nach". Im schlimmsten Fall kommt nur der minimum spanning tree bei rum.

Aber dann sind wir uns ja einig, dass man das nicht definieren kann Big Laugh

Was mich wieder zum Umfang bringt. Ich würde wohl den Umfang der konkaven Hülle als Umfang angeben und das eben entsprechend beschreiben.
Alles andere erscheint mir nicht so sinnvoll.
HAL 9000 Auf diesen Beitrag antworten »

Ich halte den Umfang der konvexen Hülle doch für ein sinnvolles Maß, zumal er höchstens so groß ist wie der (wie auch immer definierte) Konkavumfang.
zyko Auf diesen Beitrag antworten »

Hallo VerwirrterWirrkopf

Schau mal in das Paper

https://pdfs.semanticscholar.org/dcd6/bd...88b341562cb.pdf

Hierin werden über die Eigenwerte der Kovarianzmatrix aller Punkte der Punktwolke verschiedene Eigenschaften definiert, bzw. diese für die weitere Verarbeitung genutzt. S. dazu besonders Kapitel 3, besonders Definitionen (12)-(17).
Selbstverständlich kannst du irgendeines der vorgeschlagenen Maße als Durchmesser definieren.
Ob dies für deine spezifische Aufgabe ideal ist, kann nur beurteilt werden, wenn geklärt ist wozu dein Maß eingesetzt werden soll, also z.B. zur Charakterisierung der Punktwolke.
Erst wenn geklärt ist, wie und wozu deine Größen verwendet werden sollen, ist es möglich eine spezifische Berechnungsformel zu definieren.
IfindU Auf diesen Beitrag antworten »

Eine Möglichkeit wäre den Umfang als Lösung des Traveling Salesman Problem (TSP) zu definieren. Bonus: Wenn du es "effizient" implementierst, kriegst du jede Menge Preise Big Laugh
VerwirrterWirrkopf Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Ich halte den Umfang der konvexen Hülle doch für ein sinnvolles Maß, zumal er höchstens so groß ist wie der (wie auch immer definierte) Konkavumfang.


Zitat:
Original von zyko
Hallo VerwirrterWirrkopf

Selbstverständlich kannst du irgendeines der vorgeschlagenen Maße als Durchmesser definieren.
Ob dies für deine spezifische Aufgabe ideal ist, kann nur beurteilt werden, wenn geklärt ist wozu dein Maß eingesetzt werden soll, also z.B. zur Charakterisierung der Punktwolke.
Erst wenn geklärt ist, wie und wozu deine Größen verwendet werden sollen, ist es möglich eine spezifische Berechnungsformel zu definieren.


Das ist wohl der eigentliche Punktusknackus. Werde das mal durchsprechen und entsprechend entscheiden und dokumentieren. Und mich dabei wenn möglich an 'übliche' Vorgehensweien halten (abgucken Big Laugh ).

Zitat:
Original von IfindU
Eine Möglichkeit wäre den Umfang als Lösung des Traveling Salesman Problem (TSP) zu definieren. Bonus: Wenn du es "effizient" implementierst, kriegst du jede Menge Preise Big Laugh


1. Aufgabe gescheit lösen
2. ???
3. Preise abräumen Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

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