Huellfindungs-Algorithmus

[LoCrux]

Hi,

I need help.... Kennt einer einen effizienten Alogrithmus, der mir aus einer unsortierten Menge N mit n Punkten (der Eigenschaft n(x,y) und x,y Element R), diejnige Menge M echte oder unechte Teilmenge von N (|M|<=|N|) findet, so dass die
Menge M alle Elemente der Menge N umschliesst (grafisch waere das ein Huell-Polygon)?
Mit der Bedingung, dass das Huell-Polygon nicht ueberschneidend ist (konkav oder konvex waere egal).

ThanX 4 Help

[Reinhard Kern]

Zitat von LoCrux:

Hi,

I need help.... Kennt einer einen effizienten Alogrithmus, der mir aus einer unsortierten Menge N mit n Punkten (der Eigenschaft n(x,y) und x,y Element R), diejnige Menge M echte oder unechte Teilmenge von N (|M|<=|N|) findet, so dass die
Menge M alle Elemente der Menge N umschliesst (grafisch waere das ein Huell-Polygon)?
Mit der Bedingung, dass das Huell-Polygon nicht ueberschneidend ist (konkav oder konvex waere egal).

ThanX 4 Help

Hallo,

meinst du die kleinste solche Menge? Oder die mit der kleinsten Fläche? Sonst ist die Aufgabe nicht eindeutig lösbar (einen konkaven Eckpunkt kann man eliminieren, damit stellt sich auch die Frage konvex/konkav nicht mehr).

Gruss Reinhard

[LoCrux]

@Reinhard Kern,

hab mal eine Beispielgrafik dazu erstellt.
Es waere die kleinste Menge mit der Maximalen Flaeche.

[deep_thought]

... also _kennen_ tu ich keinen, aber ich würd's so machen:
du nimmst den tiefsten, höchsten , am weitesten links liegenden und den am weitesten rechts liegenden Punkt und schmeißt sie in M.
Dann betrachtest du für links oben die Gerade zwischen dem linken und dem oberen, transformierst deine Koordinaten aus N so, dass diese Gerade parallel zur x-achse wird und dann nimmste einfach noch den Punkt mit der größten y-Koordinate dazu (sofern vorhanden haste dann 2 neue geraden, mit denen du weiter machst, ansonsten lässt du den punkt weg und brichst diesen Teil des Algörithmus ab [und machst mit anderen Geraden weiter, die noch "offen" sind])
und das machste dann auch noch links unten, rechts unten und rechts oben (halt auch immer in der entsprechenden richtung)
.... das kann man bestimmt gut rekursiv implementieren: du fängst an, die 4 Punkte zu ermitteln und dann rfst du sowas wie "suche äußersten Punkt oberhalb" für links und rechts oben auf und "suche äußersten Punkt unterhalb" für rechts und links unten und da drinnen ruft das dann immerwieder das entsprechende auf (um den am meisten außerhalb gelegenen Punmkt wieder zu finden) ...
ich hoffe, du verstehst, was ich meine ...
mfg deep42thought

[marabu]

Moin,

hier ist eine schöne Einstiegsseite zum Thema: klick

Grüße vom marabu

[LoCrux]

@marabu

ThanX.. ziehs mir mal rein!!!