Finden der äußeren Grenzen aus der Liste der zufälligen Koordinaten

Question

Ich habe eine riesige Liste (60 000+) von Koordinaten und ich habe keinen Weg gefunden, die äußeren Grenzen zu erkennen.

Die Liste der Koordinaten ist ziemlich zufällig, aber sie definieren einen bestimmten Bereich.

Ich sollte in der Lage sein, einen Bereich zu zeichnen, indem Sie diese Liste verwenden, indem Sie OpenLayers verwenden, also sollten sie auch in Reihenfolge sein.

Dies schien relativ einfach zu brechen, aber hat sich als ziemlich schwierig erwiesen.

Was könnte der beste Ansatz für dieses Problem sein?

• Heikki

Answer 1

Sind Sie auf der Suche nach einem convex hull?

Answer 2

Wenn Sie nur den Begrenzungsrahmen wollen, ist es einfach genug:

min_x = MAX_INT; 
min_y = MAX_INT; 
max_x = MIN_INT; 
max_y = MIN_INT; 

for p in points: 
    if p.x < min_x then min_x = p.x; 
    if p.y < min_y then min_y = p.y; 
    if p.x > max_x then max_x = p.x; 
    if p.y > max_y then max_y = p.x; 

Wenn gibt es keine einfache Äquivalent MAX_INT und MIN_INT auf Ihrer Plattform, wählen Sie einfach die erste In der Liste. Es ist möglicherweise weniger "schöner" Code, aber es ist möglicherweise auch schneller durch eine bedeutungslose Menge.

Natürlich, wenn Ihre Daten in einer signifikanten Weise bestellt wurden, könnten Sie etwas schlauer als das Iterieren über 60.000 Elemente und das Durchführen von 240k-Vergleichen machen. (Denken Sie daran, dass die Bestellung von 60k-Punkten in einer signifikanten Weise nur für diese möglicherweise nicht für sich selbst zahlen.)

Answer 3

Convex Rumpf ist das Thema, was ich gesucht habe. Ich fand ein wirklich nettes Skript von http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/.

Vielen Dank für alle Teilnehmer!