W
Hallo Bernhard,
bekinect schrieb:
Danke für den Tipp. Nur kurz um es für mich genauer zu erklären. Du schlägst vor, zunächst einen Graham Scan durchzuführen, um die konvexe Hülle zu finden. Die Konvexe Hülle wird in einem zweiten Vektor gespeichert. Anschließend vergleiche ich die beiden Vektoren. Sind die Größen des unsortierten und des nach Graham sortierten Vektors gleich groß, ist die Kontur gleich der konvexen Hülle. Wenn der unsortierte Vektor größer ist, lösche ich beispielsweise die Punkte aus dem unsortierten Vektor, die in der konvexen Hülle sind.
ja - genau so.
Jetzt beginnst Du beim ersten Punkt aus der konvexen Hülle pip_{i}pi und vergleichst den folgenden Punkt pi+1p_{i+1}pi+1 und jeden Punkt qjq_jqj aus der verbleibenden unsortierten Menge jeweils paarweise. Du suchst also einen Punkt qjq_jqj, der besser als nächster Punkt von pip_ipi geeignet ist, als pi+1p_{i+1}pi+1 selbst. Falls keiner gefunden wird, bleibt pi+1p_{i+1}pi+1 der nächste Punkt und das Spiel geht bei pi+1p_{i+1}pi+1 und pi+2p_{i+2}pi+2 weiter. Findest Du einen, so wird der Punkt zwischen pip_ipi und pi+1p_{i+1}pi+1 einsortiert, und der neue Punkt wird zum aktuellen Punkt.
Als Vergleichsfunktion kannst Du z.B. den Abstand von pip_ipi und das Skalarprodukt (q_j−p_i)(pi+1−pi)(q\_j-p\_i)(p_{i+1}-p_i)(q_j−p_i)(pi+1−pi) berechnen und aus letzterem wiederum den Winkel, den der Weg nach qjq_jqj von dem Weg nach pi+1p_{i+1}pi+1 abweicht. Ist der Abstand nach qjq_jqj kleiner als der nach pi+1p_{i+1}pi+1 ist das gut; ist aber der Winkel zu groß, ist es wiederum schlecht. Gewichte beides und vergleiche.
Gruß
Werner
