Punkte innerhalb Fläche - Grenzlinie finden

Hi

Folgendes Problem:
Auf einem Bild dieser Art http://img96.imageshack.us/img96/9725/punkteii9.jpg soll die Grenzlinie gefunden werden.
Dh wenn ich jeden Punkt mit jedem Verbinde sollen die äussersten Linien bestimmt werden und ihre Endpunkte.
Also das Resultat soll so sein: http://img411.imageshack.us/img411/9268/punktelinienzu4.jpg
Brauche dabei keine graphische Lösung, sondern nur rechnerisch mit Koordinaten welche Punkte verbunden werden müssen.
Habe aber zuwenig Ahnung von Mathe um das zu lösen

Danke im voraus
MfG

Fischi

du suchst die konvexe Hülle einer Punktmenge.
Das ist ein Standardproblem. Wenn du danach googlest findest du eine Unmenge von Treffern
z.B.
http://www.inf.fh-flensburg.de/lang/algorithmen/geo/convex.htm

Viele Grüße
Fischi

Ah danke.
Wenn man erstmal weiss wie ein Problem heisst ist das googlen leicht.

Jetzt hat mir sicher noch jemand nen Tip welche C++ Lib da am effizientesten ist

Hab mal spontan http://www.qhull.org/ gefunden via boost..

Selber schreiben macht schlau..danke für den Link..hat sich erledigt..

rapso

hab ich letztens auch mal imlpementiert, ganz stumpf geht das so:

1.untersten punkt finden
2.initial normale definieren (1|0)
3.fuer jeden punkt der restmenge den vector zum punkt ausrechnen (normalisiert) und dot mit der normale um den cosinus zu erhalten
4.punkt mit groestem cosinus ist neuer punkt
5.normale is die strecke vom alten zum neuen punkt, normalisiert
6.falls nicht am untersten punkt angekommen, gehe zu 3.

die meisten algorithmen fuer convex hulls die du finden wirst sind stumpfe adaptionen aus dem 3d-bereich und um einiges komplexer (nicht nur wegen der implementierung, sondern auch wegen der stabilitaet von float/double).

Danke nochmal.

Auf dem Link von Fischi ist sowas beschrieben, (Quick Hull?) und eine Implementierung in Java, die hab ich umgesetzt und sie funktioniert.