Algorithmus Ecken eines Vierecks finden

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo,
ich versuche einen Algorithmus zu finden mit dem ich die Ecken eines Vierecks bestimmen kann.
Das Viereck ist mir gegeben als zweidimensionaler Array der mir für jede Koordinate x/y sagt ob dieser Punkt Teil des Vierecks ist. Zusätzlich ist bereits ein Koordinatenpaar gegeben das im Viereck liegt und gleichzeitig eine der Ecken darstellt (genauer gesagt ist es der oberste Punkt).
Das Viereck kann auf verschiedene Arten gedreht/gestreckt/verzerrt sein.

Meine bisherigen Überlegungen sind immer gescheitert, weil das Viereck eben auch eine Raute oder ein Trapez sein kann. Ich sehe noch eine Möglichkeit mich vom gegebenen Punkt aus am Rand entlang zu bewegen und dabei über Richtungsvektoren festzustellen ob ich eine Ecke passiert habe. Das kommt mir aber sehr kompliziert vor …

Schonmal vielen Dank im voraus,
Dorwan

#2

Moien

Zusätzlich ist bereits ein Koordinatenpaar
gegeben das im Viereck liegt und gleichzeitig eine der Ecken
darstellt (genauer gesagt ist es der oberste Punkt).

Das kann man doch sehr schön nutzen:

  • Bestimme die Breite des Gebilde für jede Höhe y
  • Suche das Ende (Breite = 0)(da liegt die 2. Ecke)
  • Suche Knicke in dem Verlauf der Höhen.

Wenn es keinen Knick gibt ist das Viereck horizontal ausgerichtet.
Wenn es nur einen Knick gibt liegen die beiden „mittleren“ Ecken auf der gleichen Höhe.

cu

#3

Danke schonmal.

  • Suche Knicke in dem Verlauf der Höhen.

Meinst du damit, für jede Höhe die Steigung im Vergleich zur vorigen berechnen und dann schauen wo sich die Steigung ändert?

#4

Moien

Meinst du damit, für jede Höhe die Steigung im Vergleich zur
vorigen berechnen und dann schauen wo sich die Steigung
ändert?

Ja.

Aber du hast eine diskrete Darstellung. D.h. es wird immer eine Art Treppenform in der Breite geben. Da hilft (also erste von vielen Optionen) eine Trendkurve.

cu