minimalny pas obejmujący punkty
-
porschelukas
- Użytkownik
- Posty: 18
- Rejestracja: 14 paź 2010, o 10:49
- Płeć: Mężczyzna
- Lokalizacja: Konopnica/Lublin
- Podziękował: 1 raz
minimalny pas obejmujący punkty
Witam, potrzebuje jakiejś metody znajdującej pas o jak najmniejszej szerokości obejmujący dane punkty, może nie tyle równania prostych opisujących ten pas, a dokładnie jego szerokość. Z pewnością muszę wyznaczyć otoczkę wypukłą i to już zrobiłem, ale nie mam pomysłu co dalej. Nie mam pomysłu jak się do tego zabrać. Potrzebne jest mi to do kodu programu, dlatego fajnie by było gdyby ktoś mi powiedział w kolejnych etapach co powinienem aby dostać to czego chcę, ale jeśli tylko sposób to też będę wdzięczny, zaprogramować jakoś dam radę;)
-
szw1710
minimalny pas obejmujący punkty
Ideowo słuszne, bo pas jest zbiorem wypukłym, więc jeśli ma zawierać wszystkie punkty, to musi zawierać i ich otoczkę wypukłą. Można by się więc ograniczyć na razie do punktów ograniczających wielokąt wypukły. Ale na razie nie wiem więcej.
Wydaje mi się, że następujący algorytm mógłby być skuteczny (niekoniecznie punkty ograniczają wielokąt wypukły, są dowolnie ułożone):
Wybieramy wszystkie podzbiory dwuelementowe ze zbioru zadanych punktów.
Mamy do analizy jakiś zbiór dwuelementowy. Piszemy równanie prostej przechodzącej przez te dwa punkty. Sprawdzamy czy wszystkie pozostałe leżą po jej jednej stronie. Jeśli nie, idziemy dalej. Jeśli tak, to znajdujemy punkt najbardziej odległy od tej prostej. Jego odległość daje szerokość pasa zawierającego te punkty.
Badamy w ten sposób wszystkie układy dwóch punktów i ze znalezionych odległości wybieramy najmniejszą.
Jak sprawdzić czy punkty leżą po jednej stronie prostej? Łatwo: równanie prostej: \(\displaystyle{ ax+by+c=0.}\) Półpłaszczyzny (domknięte) na jakie prosta dzieli płaszczyznę są określone nierównościami \(\displaystyle{ ax+by+c\ge 0}\) oraz \(\displaystyle{ ax+by+c\le 0}\). Wystarczy sprawdzić czy wszystkie punkty spełniają tę samą nierówność.
Odległość punktu \(\displaystyle{ P(x_0,y_0)}\) od prostej \(\displaystyle{ ax+by+x=0}\) to
\(\displaystyle{ d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}}\)
Wydaje mi się, że następujący algorytm mógłby być skuteczny (niekoniecznie punkty ograniczają wielokąt wypukły, są dowolnie ułożone):
Wybieramy wszystkie podzbiory dwuelementowe ze zbioru zadanych punktów.
Mamy do analizy jakiś zbiór dwuelementowy. Piszemy równanie prostej przechodzącej przez te dwa punkty. Sprawdzamy czy wszystkie pozostałe leżą po jej jednej stronie. Jeśli nie, idziemy dalej. Jeśli tak, to znajdujemy punkt najbardziej odległy od tej prostej. Jego odległość daje szerokość pasa zawierającego te punkty.
Badamy w ten sposób wszystkie układy dwóch punktów i ze znalezionych odległości wybieramy najmniejszą.
Jak sprawdzić czy punkty leżą po jednej stronie prostej? Łatwo: równanie prostej: \(\displaystyle{ ax+by+c=0.}\) Półpłaszczyzny (domknięte) na jakie prosta dzieli płaszczyznę są określone nierównościami \(\displaystyle{ ax+by+c\ge 0}\) oraz \(\displaystyle{ ax+by+c\le 0}\). Wystarczy sprawdzić czy wszystkie punkty spełniają tę samą nierówność.
Odległość punktu \(\displaystyle{ P(x_0,y_0)}\) od prostej \(\displaystyle{ ax+by+x=0}\) to
\(\displaystyle{ d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}}\)