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. Musi działać to w czasie nie dłuższym (n*log(n)) w zależności od liczby punktów otoczki wypukłej. Nie mam pomysłu jak się do tego zabrać. Dla przykładu chciałbym np znaleźć pas o minimalnej szerokości obejmujący punkty:

(1, -1)
(3, -1)
(4, 2)
(-1, 3)
(-2, 2)
(-3, 0)

Dzięki z góry;)

Uwaga, wymyślam z głowy, i nie wiem czy taki algorytm będzie najszybszy:

jak już masz otoczkę wypukłą, punkty znajdujące się wewnątrz tracą na znaczeniu - nie bierzesz ich dalej pod uwagę.

Bierzesz po kolei dwa sąsiadujące ze sobą wierzchołki otoczki, i bok (odcinek) między nimi, który to bok sobie przedłużasz do prostej. Dla każdej takiej prostej sprawdzasz odległość od prostej do wszystkich pozostałych wierzchołków (czyli poza dwoma, które należą do tej prostej).
Dla każdej prostej zapamiętujesz największą odległość wierzchołka od prostej.
Grubość pasa to najmniejsza odległość ze wszystkich największych dla wszystkich prostych.

Czerwone punkty są wewnątrz, zatem nieistotne.
Niebieska prosta to jeden z przedłużonych boków otoczki.
Różowy odcinek to odległość od prostej do najdalszego wierzchołka. Spośród wszystkich boków szukamy najmniejszego odcinka różowego.

To tak raczej na pałę, bo złożoność wydaje mi się

to faktycznie powinno działać, jednak złożoność nie pozwoli mi zaliczyć tego zadania... wiem, że chyba była jakaś metoda aby szybko odrzucić niektóre punkty (oprócz tych wewnątrz otoczki) i ich nie sprawdzać

Otoczko zapewnia nam, że wszystkie kąty wewnętrzne będę niewypukłe (<=180*). Jeśli będziemy przesuwać się po otoczce w jednym kierunku to sprawa się uprości. Pas będzie się "kręcić" cały czas w jednym kierunku. Gwarantuje nam to, że ten najbardziej odległy punkt od brzegu (od niebieskiej prostej) którego szukamy będzie nie wcześniej niż punkt z poprzedniego kroku. Pełne wyszukiwanie wystarczy przeprowadzić w pierwszym kroku. W kolejnych krokach wystarczy przechodzić do następnego punktu otoczki dopóki odległość od brzegu się zwiększa. W ten sposób upraszcza nam się wszystko do O(n).

dzięki właśnie tego potrzebowałem, jutro zabieram się do implementacji;) być może jeszcze się odezwę jak napotkam jakiś problem

Dodam jeszcze jak liczyć odległość.

A - początkowy punkt odcinka obwiedni
B - końcowy punkt odcinka obwiedni
P - punkt do którego odległość sprawdzamy

q=B-A
p=P-A
Rzutujemy p na q (zob. http://pl.wikipedia.org/wiki/Iloczyn_skalarny#Interpretacja_geometryczna)
r=q·(p*q)/(q*q)
gdzie * to iloczyn skalarny.
Odległość to:
k=p-r

otoczka3.png

wziąłem się za implementacje tego, już trochę przesiedziałem, ale nie do końca wiem kiedy przerywać to liczenie.
To co napisałem do tej pory:

	for (int i = 0; i < drzewa.size()-3; i++){//vector z kolejnymi punktami otoczki
		temp = drzewa[i];
		temp2 = drzewa[i+1];
		max=0;
		for (int j = i+2; j < drzewa.size(); j++){
			odl = odleglosc(temp, temp2, drzewa[j]);//odleglosc miedzy prosta przez temp-temp2 a punktem drzewa[k]
			if(odl > max){
				max = odl;
			}
		}
		if(max < pas)
			pas=max;//szerokość pasa
	} 

jeśli można to prosiłbym o jakieś wskazówki gdzie i jaki warunek dostawić, żeby to przerwać. To coś liczy trochę tylko później nadpisuje coraz mniejszymi wartościami...

int a; // indeks punktu A
int b; // indeks punktu B
int p = 2; // indeks punktu P

for (a = 0; a < drzewa.size(); a++) { // uwaga! miałeś za mało iteracji
	b = (a + 1) % drzewa.size(); // nie wystarczy dodać 1

	/* najpierw liczysz odległość do aktualnego punktu P */
	max = odleglosc(drzewa[a], drzewa[b], drzewa[p]);

	/* przechodzimy do kolejnego punktu P dopóki odległość się zwiększa */
	for (;;) {
		next_p = (p + 1) % drzewa.size();
		next_max = odleglosc(drzewa[a], drzewa[b], drzewa[next_p]);
		if (next_max < max - EPSILON) break; // kolejny punkt jest bliżej - przerywamy
		p = next_p;
		max = next_max;
	}

	if(max < pas) pas = max;
}

// edycja
Uwaga! Dodałem jeszcze EPSILON. Musisz porównywać liczby w pewnym przybliżeniu gdyż błędy zaokrągleń mogą schrzanić cały algorytm. Bez EPSLON'a mogły by być problemy gdyby kilka kolejnych punktów otoczki ułożyło się prawie współliniowo.

dzięki;) teraz jest zdecydowanie lepiej niż było, tylko zapętla się w for(;;), coś muszę jeszcze pokombinować żeby to zmienić, np jeśli otoczka to kwadrat o punktach: (1,1), (3,1), (3,3), (1,3), wtedy się zapętli przy drugim wejściu do tego fora

edit. ale to chyba moja funkcja zwracająca odległość jest jakaś zła;) bo nie zwraca 0 jeśli badam punkt należący do prostej tylko jakieś "-1.#IND000" cokolwiek to znaczy

Nic nie szkodzi, przy drugiej iteracji a == p więc odległość wyniesie 0 co przerwie pętlę.