Calcolo del rettangolo di delimitazione minima della forma 2D per coordinate

Question

Ho una soluzione che utilizza dati spaziali per rappresentare un cluster di punti su una mappa. Ho bisogno di usare le coordinate che rappresentano le estensioni di un cluster per trovare il rettangolo di limitazione minimo che può contenere detto gruppo di punti.

Esiste un semplice algoritmo per poter calcolare questo o esiste una funzionalità incorporata in C# per ottenere ciò. Sono a conoscenza di NetTopologySuite ma non sono sicuro di come/se potrei usarlo per raggiungere lo stesso obiettivo. Ho una lista di coordinate quindi dovrei passare questa lista di stringhe e ottenere l'MBR.

Answer 1

La soluzione più semplice, e presumo quella che è più probabile che stiate cercando, consiste nel calcolare il riquadro di delimitazione allineato all'asse, che è semplicemente il caso di trovare i valori min/max x & y, quindi costruendo una scatola da quelli.

ti darò pseudo-codice per questo, dato che non avete pubblicato i tipi che la geometria è espresso in ...

type point { float x; float y; } 
type box { point topleft; point topright; point bottomleft; point 

function bounding_box(points) 
{ 
    xmin = min(points.x) 
    xmax = max(points.x) 
    ymin = min(points.y) 
    ymax = max(points.y) 

    return new box{ 
    topleft = { x = xmin, y = ymax }, 
    topright = { x = xmax, y = ymax }, 
    bottomleft = { x = xmin, y = ymin }, 
    bottomright = { x = xmax, y = ymin } 
    }; 
} 

Quindi, dato questi:

point[] points = [[x = -2, y = 0], [x = 1, y = 2], [x = 1, y = 1], [x = -1, y = -2]]; 
box bounds = bounding_box(points); 

Tutti i seguenti sarà vero:

bounds.topleft == [x = -2, y = 2]; 
bounds.topright == [x = 1, y = 2]; 
bounds.bottomleft == [x = -2, y = -2]; 
bounds.bottomright == [x = -1, y = -2]; 

Naturalmente, se il sistema di coordinate ha le coordinate bassi al t op (ad es. come un tipico display) - quindi è necessario invertire il calcolo; o calcola prima il risultato nello spazio-oggetto e poi traduci nello spazio logico in seguito.

Avviso Sono andato per un tipo per la casella che esprime tutti i quattro angoli, nel caso in cui si decida in futuro di aggiornare ad una casella arbitrariamente allineata in futuro (anche se per lo stesso token si potrebbe semplicemente usare un punto + 2 vettori per quello).

Answer 2

Una possibile, anche se semplice, modo per farlo potrebbe essere simile a questo:

public Rectangle Test(List<Point> points) 
{ 
    // Add checks here, if necessary, to make sure that points is not null, 
    // and that it contains at least one (or perhaps two?) elements 

    var minX = points.Min(p => p.X); 
    var minY = points.Min(p => p.Y); 
    var maxX = points.Max(p => p.X); 
    var maxY = points.Max(p => p.Y); 

    return new Rectangle(new Point(minX, minY), new Size(maxX-minX, maxY-minY)); 
} 

Questo ha ovviamente scontato che siete alla ricerca di un rettangolo che è allineato verticalmente che orizzontalmente. Quindi se stai cercando il rettangolo più piccolo possibile, non importa come viene ruotato, questo non fa per te.

Answer 3

Prova G # in http://www.ceometric.com/products/g.html

Ha superficie minima e il perimetro minimo racchiudono rettangoli e cerchi anche minime di cinta.