Grenzen einer Punkteschar < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:13 Di 07.12.2004 | | Autor: | armin |
{Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.}
Hallöle zusammen!
In meiner Aufgabe geht es um eine Punkteschar von n Punkten.
(Diese liegen alle auf einer Ebene und werden anhand der xy - koordinaten angegeben).
Die Frage ist, wie bestimme ich die Außenpunkte, um diese zu einem Vieleck zu verbinden und dann damit weiterechnen zu können? (Vorausgesetzt ist hierbei, das mind. 3 Punkte vorhanden sind)
Meine erste Idee war, jeweils die x und y koordinaten aller Punkte zu vergleichen um somit erstmal
die "Ecken" der Punkteschar zu bestimmen. (also kleinstes x UND größtes y = linke obere Ecke, größtes x UND größtes y = rechte obere Ecke u.s.w.)
Danach die max-/minimalwerte von x (unabhängig von y) und y (unabhängig von x) bestimmen und die jeweiligen Punkte auch mit in die Menge der Eckpunkte aufnehmen.
Nun komm ich leider etwas durcheinander, weil ich ja x1 und x2 UND y1 und y2 miteinander vergleichen muss. Brächte es etwas, wenn ich x und y eines Punktes miteinander addiere und dann diese Werte vergleiche?
Was ist mit dem Fall, wenn z.B. x1>x2 aber y1<y2 ist?
Kennt irgendwer vielleicht einen Lösungsansatz dieses oder eines ähnlichen Problems?
Danke schonmal!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:07 Mi 08.12.2004 | | Autor: | wluut |
Dein Problem ist die Suche nach einer knovexen Hülle.
Es gibt da einen klassischen Algorithmus, der mit Winkeln arbeitet. Vielleicht hilft dir der folgende Link weiter:
http://www.informatik.uni-freiburg.de/~zupancic/docus/conhull.html
Oder google doch mal nach "algorithmus konvexe hülle", da findet sich sicher eine Menge.
Einfach zu programmieren ist das ganze mit einem BRUTE FORCE Alogorithmus (Für jeden Punkt, prüfe ob es eine Gerade zwischen zwei anderen Punkten gibt, so dass der Punkt "innerhalb" liegt), mit wachsender Punktezahl wird die Rechenzeit aber SEHR schnell SEHR lange, daher: Finger weg davon in der Praxis.
Viel Glück!
|
|
|
|
