Einführung

Diesen Sommer bin ich auf einer Technologie Abschnitt in Västerås tätig. Ich habe bei der gleichen Firma und ungefähr zur gleichen Büro für drei gerade Sommern arbeitete. Die Arbeit ist sehr technisch, Spaß und Herausforderung. Im Gegensatz zu vielen anderen Sommer-Job in einem Büro, habe ich eine gefunden, wo ich Verantwortung und lernen Sie mit gemeinsamen Aufgaben zu arbeiten. Genauer gesagt, arbeite ich an der Entwicklung von Instrumenten, um die Berechnungen, die meist MatLab, GUI-Programmierung und Java zu vereinfachen. Das neue Objekt-orientierten Stil von MatLab macht den Code sehr viel klarer als vor ein paar Jahren.

Das Problem

Neulich habe ich stand vor einer kleinen Herausforderung. Vereinfacht auf der Suche nach einem Polygon, das einen Satz von komplexen Punkte, die in der Ebene verteilt sind umschließt konzentriert. Anfangs wusste ich nicht finden, die Funktion, das dies tut in Matlab, was natürlich sehr seltsam. Ich beschloss daher, einen benutzerdefinierten Algorithmus zu finden. In diesem Beitrag beschreibe ich meinen Algorithmus.

Abbildung 1. Beispiele von konvexen Hülle.

Meine Alogritm

Ich beschreibe meine BE-Algorithmus unter Verwendung Bild 2 dargestellt. Zunächst werde ich die Schwierigkeiten bei der Wohnungssuche. Die Sache ist die, dass alle Punkte in einer Struktur sind unsortiert. Wenn die Punkte um einen Mittelpunkt herum angeordnet sind, lässt sich dessen Ordnung und den Abstand vom Zentrum, um das Problem zu lösen. Jedoch dauert es mindestens O (n log (n)), um eine lineare Sortierung zu machen. Mein Algorithmus arbeitet in der unsortierten Liste und wird wohl noch mehr Zeit, denn ich habe keine Beweise abgeleitet.

Die Idee ist sicherlich mit meinem Punkt in x-Richtung zu starten und dann den Punkt finden, an dem der K-Wert wird das Maximum. dh herauszufinden:

max (k_i) = (Y_MIN - y_i) / (x_min - x_i) für i = [alle Artikel] Dies gibt Ihnen die Stelle P_2..

Alle Punkte von weniger als y-Wert X_min kann weggelassen werden. Alle Punkte mit kleineren x-Wert als P_2 kann auch zur weiteren Lektüre ausgeschlossen werden.

k_2 wird dann durch den Punkt zu finden, die minimiert gefunden:

K_1 - (y_1 - y_i) / (x_1 - x_i) für i = [alle Punkte werden nicht ausgeschlossen]

In ähnlicher Weise gefunden k_a in der Regel durch:

min (k_a-1 - (Y_A-1 - y_i) / (X_A-1 - x_i)) für i = [alle die Punkte nicht ausgeschlossen]

Die Berechnung ist für die obere Hälfte des Polygons getan, bis Sie auf den Punkt, die maximal ist in x-Richtung erhalten. Danach wird die gleiche Algorithmus auf die untere Hälfte des Polygons.

Abbildung 2. Algorithmus für die konvexe Fall.

Leistung

Die Leistung des Algorithmus hängt davon ab, wie viele Punkte, die am Ende in der Polygon. Ich mache so viele linjärsök die Liste, dass es Punkte im Polygon. Dies bedeutet, dass die Komplexität O (N * Anzahl der Suche) ist. Die Anzahl der Punkte in der optimalen Polygon ist zwischen 10 und 25 je nach Ihrer Chance Punkte. Der Algorithmus ist also relativ schnell.

Code

Der Code ist nicht öffentlich.

Matlab-Lösung - die konvexe Hülle

Mein Algorithmus macht das Gleiche wie eine Matlab-Funktion convhull . Konvexe Hülle ist also das englische Wort für ein geschlossenes Polygon oder einer konvexen Körper. Eine andere gute Quelle ist http://en.wikipedia.org/wiki/Convex_hull_algorithms erklären, dass die theoretische minimale Zeit, um eine konvexe Hülle zu finden in der Größenordnung O (n log (n)) ist.