Calcular rectángulo mínimo delimitador de forma 2D por coordenadas

Question

Tengo una solución que utiliza datos espaciales para representar un grupo de puntos en un mapa. Tengo la necesidad de utilizar las coordenadas que representan las extensiones de un clúster para encontrar el rectángulo delimitador mínimo que puede contener dicho grupo de puntos.

¿Existe algún algoritmo simple para poder calcular esto o hay alguna funcionalidad incorporada en C# para lograr esto? Soy consciente de NetTopologySuite pero no estoy seguro de cómo/si podría usar esto para lograr el mismo objetivo. Tengo una lista de coordenadas, así que necesitaría pasar esta lista de cadenas y sacar el MBR.

Answer 1

La solución más fácil, y supongo que la que es más probable que esté buscando, es calcular el cuadro delimitador alineado con el eje, que es simplemente el caso de encontrar los valores mín/máx x & y, luego construyendo una caja de esos.

les daré pseudo-código para que, teniendo en cuenta que usted no ha publicado los tipos que su geometría se expresa en ...

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 } 
    }; 
} 

Así Dadas estas:

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

Todo lo siguiente será cierto:

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

por supuesto, si el sistema de coordenadas tiene las coordenadas más bajas en el t op (p. ej. como una pantalla típica) - entonces tiene que invertir el cálculo; o calcule el resultado en el espacio del objeto primero y luego traduzca al espacio lógico después.

Aviso He elegido un tipo para la caja que expresa las cuatro esquinas, en caso de que decida en el futuro actualizar a una caja arbitrariamente alineada en el futuro (aunque de la misma manera podría simplemente usar un punto + 2 vectores para eso).

Answer 2

Una posible, aunque simple, forma de hacerlo podría ser así:

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)); 
} 

Esto hace, por supuesto, a suponer que usted está buscando un rectángulo que está alineado verticalmente y horizontalmente. Entonces, si está buscando el rectángulo más pequeño posible, sin importar cómo se gire, no es para usted.

Answer 3

Try G # al http://www.ceometric.com/products/g.html

Cuenta con área mínima y el perímetro mínimo que encierran rectángulos y círculos también mínimos de cerramiento.