Obliczyć minimalny prostokąt ograniczający kształtu 2D według współrzędnych

Question

Mam rozwiązanie, które wykorzystuje dane przestrzenne do reprezentowania skupiska punktów na mapie. Mam potrzebę użycia współrzędnych reprezentujących zakresy klastra, aby znaleźć minimalny prostokąt ograniczający, który może zawierać wspomniane skupienie punktów.

Czy istnieje jakiś prosty algorytm, aby móc to obliczyć, lub czy istnieje jakaś wbudowana funkcja w języku C#, aby to osiągnąć. Zdaję sobie sprawę z NetTopologySuite, ale nie jestem pewien, w jaki sposób/jeśli mógłbym użyć tego do osiągnięcia tego samego celu. Mam listę współrzędnych, więc muszę przekazać tę listę łańcuchów i pobrać MBR.

Answer 1

Najprostszym rozwiązaniem, i zakładam, że najprawdopodobniej szukasz, jest obliczenie wyrównanego do osi prostokąta ograniczającego, który jest po prostu przypadkiem znalezienia wartości min/max x & y, a następnie budując z nich pudełko.

dam ci pseudo-kod, który, biorąc pod uwagę, że nie napisali rodzaje że geometria jest wyrażona w ...

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

Więc podane są:

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

Wszystkie poniższe będzie prawdziwe:

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

oczywiście, jeśli układ współrzędnych ma najniższe współrzędne na t op (np. jak typowy wyświetlacz) - wtedy musisz odwrócić obliczenia; lub najpierw obliczyć wynik w przestrzeni obiektowej, a następnie przekształcić go w przestrzeń logiczną.

Zauważyłem, że szukałem typu w polu, które wyraża wszystkie cztery rogi, na wypadek gdyby w przyszłości zdecydowałeś się na aktualizację do arbitralnie wyrównanego pola (chociaż z tego samego powodu możesz po prostu użyć punktu + 2 wektory na to).

Answer 2

Jednym z możliwych, choć prosty sposób zrobić to może być tak:

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

to robi oczywiście założyć, że szukasz prostokąta, który jest wyrównany w pionie i poziomie. Jeśli szukasz najmniejszego możliwego prostokąta, niezależnie od tego, jak jest obrócony, nie jest to dla ciebie.

Answer 3

Spróbuj G # w http://www.ceometric.com/products/g.html

Ma minimalną powierzchnię i minimalny obwód załączając prostokąty, a także minimum okręgi okalającego.