Algorytmy minimalnych ramek ograniczających
W geometrii obliczeniowej najmniejszym problemem związanym z polem jest znalezienie zorientowanej minimalnej ramki ograniczającej obejmującej zbiór punktów. Jest to rodzaj objętości ograniczającej . „Najmniejszy” może odnosić się do objętości , powierzchni , obwodu itp . pudełka.
Wystarczy znaleźć najmniejszą skrzynkę zawierającą wypukłą otoczkę omawianych obiektów. Łatwo jest znaleźć najmniejsze otaczające pudełko, które ma boki równoległe do osi współrzędnych; najtrudniejszą częścią problemu jest określenie orientacji pudełka.
Dwa wymiary
Dla wielokąta wypukłego znany jest liniowy algorytm czasu dla prostokąta obejmującego minimalną powierzchnię . Opiera się na obserwacji, że bok pudełka zawierającego pole o minimalnej powierzchni musi być współliniowy z bokiem wielokąta wypukłego. Możliwe jest wyliczenie tego rodzaju pudełek w czasie liniowym za pomocą podejścia zwanego obrotowymi suwmiarkami autorstwa Godfrieda Toussainta w 1983 r. To samo podejście można zastosować do znalezienia prostokąta obejmującego minimalny obwód . Dostępna jest implementacja algorytmu w języku C++, która jest odporna na błędy zmiennoprzecinkowe.
Trzy wymiary
W 1985 roku Joseph O'Rourke opublikował algorytm czasu sześciennego, aby znaleźć pudełko otaczające minimalną objętość trójwymiarowego zbioru punktów. Podejście O'Rourke'a wykorzystuje technikę trójwymiarowych obrotowych suwmiarek i opiera się na lematach charakteryzujących minimalne otaczające pudełko:
- Muszą istnieć dwie sąsiednie ściany pudełka zawierającego najmniejszą objętość, z których obie zawierają krawędź wypukłej otoczki zbioru punktowego. Kryterium to spełnia pojedyncza wypukła krawędź kadłuba współliniowa z krawędzią pudełka lub dwie odrębne krawędzie kadłuba leżące na sąsiednich ścianach pudełka.
- Pozostałe cztery ściany muszą zawierać tylko punkt wypukłej otoczki. Ponownie, punkty, które zawierają, nie muszą być różne: pojedynczy punkt kadłuba leżący w rogu pudełka już spełnia trzy z tych czterech kryteriów.
W najbardziej ogólnym przypadku, gdy żadne wypukłe wierzchołki kadłuba nie leżą na krawędziach minimalnego otaczającego pudełka, co najmniej 8 wypukłych punktów kadłuba musi leżeć w obrębie ścian pudełka: dwa punkty końcowe każdej z dwóch krawędzi i cztery kolejne punkty, po jednym dla każdej z pozostałych czterech ścian pudełka. I odwrotnie, jeśli wypukła powłoka składa się z 7 lub mniej wierzchołków, co najmniej jeden z nich musi leżeć w obrębie krawędzi minimalnego otaczającego pudełka kadłuba.
Możliwe jest również przybliżenie minimalnej objętości prostokąta ograniczającego z dokładnością do dowolnego stałego czynnika większego niż jeden w czasie liniowym . Algorytm wykonania tego polega na znalezieniu przybliżenia średnicy zestawu punktów i użyciu pudełka zorientowanego w kierunku tej średnicy jako początkowego przybliżenia prostokąta ograniczającego minimalną objętość. Następnie ta początkowa ramka graniczna jest dzielona na siatkę mniejszych sześcianów, a punkty siatki w pobliżu granicy wypukłej otoczki wejściowej są używane jako zestaw podstawowy , mały zbiór punktów, których optymalna ramka ograniczająca jest zbliżona do optymalnej ramki ograniczającej pierwotnego wejścia. Na koniec algorytm O'Rourke'a jest stosowany do znalezienia dokładnej optymalnej ramki ograniczającej tego zestawu rdzeni.
Dostępna jest implementacja algorytmu w Matlabie.
Minimalnym pudełkiem otaczającym czworościanu foremnego jest sześcian o boku długości 1/ √ 2 długości boku czworościanu; na przykład regularny czworościan o długości boku √ 2 mieści się w sześcianie jednostkowym , z wierzchołkami czworościanu leżącymi na wierzchołkach (0,0,0), (0,1,1), (1,0,1) i ( 1,1,0) sześcianu jednostkowego.
Zobacz też
- Bibliografia _ _ Shapira, R. (1975), „Określanie prostokąta obejmującego minimalną powierzchnię dla dowolnej krzywej zamkniętej”, Communications of the ACM , 18 (7): 409–413, doi : 10.1145/360881.360919 , MR 0375828 , S2CID 2079688 .
- ^ a b Toussaint, GT (1983), „Rozwiązywanie problemów geometrycznych z obracającymi się zaciskami” (PDF) , Proc. MELECON '83, Ateny .
- ^ Eberly, D. (2015), „Prostokąt o minimalnej powierzchni zawierający zestaw punktów” , Geometric Tools, LLC .
- Bibliografia _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
- Bibliografia _ Har-Peled, Sariel (2001), „Efektywne zbliżenie prostokąta ograniczającego o minimalnej objętości punktu ustawionego w trzech wymiarach”, Journal of Algorithms , 38 (1): 91–109, doi : 10,1006 / jagm.2000,1127 , MR 1810433 , S2CID 1542799 .
- ^ Melchior, Samuel (2018). „Implementacja w Matlabie algorytmu ramki ograniczającej o minimalnej objętości” . GitHub . .
- ^ O'Rourke (1985) , ryc. 1, s. 186.