Odległość punktu od otoczki wypukłej

[jcubic]

Potrzebuje wyznaczyć odległość punktu od otoczki wypukłej dla uproszczenia w \(\displaystyle{ R^2}\). Łatwo jest obliczyć czy punkt znajduje się wewnątrz, suma kątów między punktami a punktem musi się równać \(\displaystyle{ 360^o}\) i teraz jak obliczyć odległość punktu leżącego na zewnątrz otoczki. Jeśli punkt jest między dwoma punktami to mogę obliczyć wysokość trójkąta, ale to rozwiązanie nie uwzględnia krzywizny otoczki. Czy jest coś co można użyć aby obliczyć tą odległość. Co będzie dla 3 i więcej wymiarów.

Zadałem to pytanie ale dla 3D na ale była tylko jedna odpowiedź z ostrosłupem.

Czy za pomocą geometrii różniczkowej albo topologii można rozwiązywać tego typu problemy? Nic nie wiem o tych dwóch działach matematyki.

Czy jest coś co byłoby potrzebne, a tego jeszcze nie ma, aby rozwiązać ten problem? Będę wdzięczny za każdy pomysł, który może pomóc w rozwiązaniu tego problemu.

[szw1710]

Najprościej znaleźć algorytm dla otoczki wypukłej skończonego układu punktów, czyli - krótko mówiąc - dla wielokąta wypukłego. Zależy jaki masz problem. Jeśli wielokąt - sprawa skończona. Jeśli nie - trzeba jakoś tę otoczkę opisać. Ponadto metody przestrzeni Hilberta podają sposób znajdowania odległości punktu od zbioru. Mianowicie w zbiorze domkniętym i wypukłym w przestrzeni Hilberta istnieje dokładnie jeden element o najmniejszej normie. Element ten wyznacza się konstrukcyjnie. Powiedzmy, że Twoja otoczka jest domknięta. Oznaczmy ją przez \(\displaystyle{ D}\). Niech \(\displaystyle{ x_0\not\in D}\). Wtedy zbiór \(\displaystyle{ x_0-D=\{x_0-y:y\in D\}}\) też jest domknięty i wypukły i ma wobec tego element \(\displaystyle{ x_0-y_0\in D}\) o najmniejszej normie. Wtedy \(\displaystyle{ \|x_0-y_0\|}\) realizuje odległość \(\displaystyle{ x_0}\) od \(\displaystyle{ D}\).

[a4karo]

Jeżeli potrafisz opisac otoczkę wypukłą wzorem (np \(\displaystyle{ f(x_1,\dots,x_n)=0}\) a punkt ma współrzedne \(\displaystyle{ (a_1,\dots,a_n)}\), to otrzymujemy zagadnienie szukania ekstremum warunkowego:

Znależć najiejszą wartośc funkcji \(\displaystyle{ g(x_1,\dots,x_n)=(x_1-a_1)^2+\dots+(x_n-a_n)^2}\) pod warunkiem, że \(\displaystyle{ f(x_1,\dots,x_n)=0}\).

Sposoby rozwiazywania takich zagadnień są znane (np. metoda mnożników Lagrange'a). Opis metody i przykłady znajdziesz np. w Fichtencholzu.

@szw... autor pisze o krzywiźnie otoczki, a zatem raczej nie mamy do czynienia z wielościanem/wielokątem.

[jcubic]

Chodzi o wielościan, z tym że najbliższy punkt wcale nie będzie odległością od otoczki. chodziłoby o odległość od krzywej interpolowanej (może być liniowo). Odległość puntu od takiej lini (prawdopodobnie będzie to linia prostopadła) może być różna od odległości dla najbliższego punktu. Pierwszym pomysłem było właśnie znalezienie najmniejszej metryki ale takie rozwiązanie jest błędne.

Algorytmy do znajdowania otoczki są znane nawet dla zbioru punktów w \(\displaystyle{ R^n}\), więc można założyć że mam zbiór punktów wielokąta. Zastanawiam sie czy nie wystarczy znaleźć n najbliższych punktów i wyznaczyć wysokość simpleksa (dla 2 wymiarów trójkąta), z tym że nie mam żadnej wiedzy na temat topologii więc nie wiem jak to ugryźć. Na Wikipedii znalazłem tylko wysokość simpleksa foremnego.

PS: Próbuje znaleźć rozwiązanie, które można obliczyć na komputerze.

[szw1710]

A więc zobacz do podręczników analizy numerycznej. Problem jest tak klasyczny, że musi być gotowe rozwiązanie - algorytm. Tak też sądziłem, że potrzebny Ci jest stosunkowo najprostszy przypadek.

[a4karo]

Potrzebuje wyznaczyć odległość punktu od otoczki wypukłej

Chodzi o wielościan, z tym że najbliższy punkt wcale nie będzie odległością od otoczki.

To o co chodzi?