Kluczowym określeniem jest wyliczenie wierzchołków z polytopy P. Ideą opisanego poniżej algorytmu jest rozważenie polytopy P *. Następnie wierzchołki P odpowiadają płaszczyznom P *. Aspekty P * są efektywnie obliczane za pomocą Qhull, a następnie pozostaje znaleźć wierzchołki, rozwiązując odpowiednie podsystemy równań liniowych.
Algorytm jest zaimplementowany w zestawie narzędzi licencjonowanych BSD Analyze N-dimensional Polyhedra in terms of Vertices or (In)Equalities dla Matlab, autor: Matt J, w szczególności jego komponentu lcon2vert. Jednak w celu odczytywania algorytmu i ponownego implementowania go w innym języku łatwiej jest pracować ze starszym i prostszym plikiem Michaela Kledera, którego projekt Matta J opiera się na starszym pliku con2vert.
Wyjaśnię, co robi krok po kroku. Poszczególne polecenia Matlab (np. convhulln) są dokumentowane na stronie MathWorks, z odniesieniami do podstawowych algorytmów.
wejściowy składa się ze zbioru liniowych nierówności postaci Ax<=b, gdzie A jest macierzą, a B oznacza wektor kolumn.
Etap 1. Próba zlokalizowania wewnętrzny punkt Polytope
Pierwsza próba jest c = A\b, co jest rozwiązaniem najmniejszych kwadratów nadokreślony układzie liniowym Ax=b. Jeśli A*c<b jest zgodny, to jest to punkt wewnętrzny. w przeciwnym razie usiłuje się zminimalizować wielowymiarowość, przy czym funkcją celu jest maksymalna liczba 0 i wszystkie liczby A*c-b. Jeśli nie uda się znaleźć punktu, w którym znajduje się A*c-b<0, program wychodzi z "niemożnością znalezienia punktu wewnętrznego".
Krok 2. Przetłumacz Polytope tak, że pochodzenie jest jego wnętrze punkt
Odbywa się to poprzez b = b - A*c w Matlab. Ponieważ 0 jest teraz punktem wewnętrznym, wszystkie wpisy b są dodatnie.
Etap 3. Normalizacja tak, że prawa strona ma 1
to tylko podział ITH rzędzie przez b (I), odbywa się przez D = A ./ repmat(b,[1 size(A,2)]); w Matlab. Odtąd używana jest tylko matryca D. Zwróć uwagę, że rzędy D są wierzchołkami podwójnej polytopy P * wspomnianymi na początku.
Krok 4. Sprawdź, czy Polytope P jest ograniczony
Polytope P jest nieograniczona jeśli wierzchołki jego podwójnej P * leżą na tej samej stronie pewnej hiperpłaszczyzny przez początek układu współrzędnych. Wykrywane jest to za pomocą wbudowanej funkcji convhulln, która oblicza objętość wypukłego kadłuba danego punktu.Autor sprawdza, czy dołączenie zerowego wiersza do macierzy D zwiększa objętość wypukłego kadłuba; jeśli tak, program wychodzi z "wykrytymi ograniczeniami ograniczającymi".
Etap 5. Obliczanie wierzchołków
to pętla
for ix = 1:size(k,1)
F = D(k(ix,:),:);
G(ix,:)=F\ones(size(F,1),1);
end
W tym przypadku matryca K koduje aspektów podwójnego Polytope p *, przy czym każdy rząd wymieniającego wierzchołków aspekt. Macierz F jest submatrix D składającą się z wierzchołków aspektu P *. Backslash wywołuje linear solver i znajduje się wierzchołek P.
Etap 6: Oczyszczanie
Ponieważ Polytope został przeliczane w etapie 2, to tłumaczenie jest cofnięta z V = G + repmat(c',[size(G,1),1]);. Pozostałe dwie linie próbują wyeliminować powtarzające się wierzchołki (nie zawsze z powodzeniem).
Czy chcesz znaleźć * wszystkie * skrajne punkty, czy tylko ich podzbiór? – templatetypedef
Jeśli mam teorię w prawo, aby zdefiniować zbiór wypukły, potrzebuję wszystkich skrajnych punktów. Zależy od dokładnej definicji skrajnych punktów. Myślę o punkcie skrajnym jako punkcie, którego nie można uzyskać przez p = p0 * t + p1 * (1-t) dla 0 <= t <= 1 i p0! = P1, oba w kształcie wypukłym. Innymi słowy, chcę minimalny zestaw punktów, które generują wypukły zestaw. –
Rozumiem, mogą być zdegenerowane przypadki .... Edycja: myślę dwa razy, nie widzę jasno, nie od razu. –