[C/C++] Konveksna lupina - brute force

Delam program, ki izriše konveksno lupino. Sam program imam, vendar se mi zdi, da sem že vidla hitrejše. namreč tale je s tremi for - zankami. A ima mogoče kdo kakšnega drugega za "posodit"

To je pa ta alg.::

for (int i = 0; i < steviloTock; i++)
		{
                        // dobimo vse mozne dvojice tock (ki predstavljajo krajisci daljice (dolocata premico))
			for (int j = (i + 1); j < steviloTock; j++)
			{
				A.x = tocke[j].x - tocke[i].x;
				A.y = tocke[j].y - tocke[i].y;

				preglediTock = 0;
				
				for (int k = 0; k < steviloTock; k++)	// preverimo ali je vse na eni strani
				{
					if ( (k != i) && (k != j) )	// Ne gledamo istih tock
					{
						B.x = tocke[k].x - tocke[i].x;
						B.y = tocke[k].y - tocke[i].y;

						if (preglediTock == 0)	
							if (vektorskiProdukt(B,A) > 0)	
								vprod_vec_nic = true;
							else  
								vprod_vec_nic = false;
					
						if ( (vektorskiProdukt(B,A) > 0) && (vprod_vec_nic != true) )	
							break;		
						if ( (vektorskiProdukt(B,A) < 0) && (vprod_vec_nic != false) )
							break;	

						preglediTock++;
					}
				}

				// odvzamemo 2 tocki, ki dolocata premico
				if (preglediTock == (steviloTock - 2))	
				{
					// Skranimo tocke
					tockeLupina[steviloTockLupina++] = tocke[i];
					tockeLupina[steviloTockLupina++] = tocke[j];
				}
			}

[Edit: za tako jezikovno specifične teme v bodoče prosim, da se v ime teme napiše jezik; pa tudi bolj natančen naslov ni odveč - Gundolf]

Lej.

http://www.critticall.com

Prevedeš v "crittical c", pa ti bo zagotovo izboljšal algoritem, če se da.

Bi ti jest, pa nimam časa, res.

Tale algoritem ma zahtevnost O(n3). Na hiter se ga da izboljšat za konstanto s tem da vektorski produkt izračunaš le enkrat in ne v vsakem IFu znova. Glede na to, da se v najbolj notranji zanki ne dogaja skoraj nič drugega, bi že samo to precej popravilo samo brzino (na pamet bi reku da za kakih 30%-50%). Bi se pa stvar precej bol popravla tkoke:

1. točke urediš po X koordinati in shraniš vse točke, ki imajo minimalni in maksimalni X
2 točke urediš po Y koordinati in shraniš vse točke, ki imajo minimalni in maksimalni Y

Te točke so sigurno del ovojnice. Med njimi potegneš vse možne daljice in izločiš vse, ki se med sabo sekajo. To kar ostane vzameš za prvi približek. Nato za vse preostale točke, ki niso del tega približka, eno za drugo, preveriš ali ležijo v notranjosti trenutnega prbližka ovojnice:
- če da, jih izločiš iz nadaljnega iskanja (od tle pride maksimalni profit)
- če ne, točko dodaš v v približek, da dobiš nov približek

Ko ti zmanjka točk, je takratni približek kr tvoj rezultat. Ali opazovana točka leži v notranjosti ali ne, ugotoviš tako da iz nje potegneš vse daljice do točk v trenutnem približku ovojnice. Nato preveriš, če se katera od teh daljic seka s trenutno ovojnico. Če ne, je točka očitno v notranjosti in jo izločiš iz iskanja. Če pa se, je točka očitno zunaj trenutne ovojnice. Njo vključiš v nov približek.

Zahtevnost tega postopka je še vedno O(n3) - n-krat gradiš približek ovojnice ki ma zahtevnost n2, ampak so pa konstante bistveno nižje. Samo sortiranje ma lahko zahtevnost O(nLogN) in tako ne igra bistvene vloge v oceni.

P.S. v zgonjem algoritmu ni vidit kakšni C++ zadev, tako da bi lahk datoteko enostavno preimenovala v .c in v kompajlerju pač naštelala da gre za C projekt, namesto C++ projekt. Ni pa nujno da je to možno, odvisno od kompajlerja ku ga maš.

študiram, kaj bi bil worstcase primer za tak iterativn pristop. Se mi zdi da, kadar vse točke ležijo na krožnici, saj takrat vsaka naslednja točka postane del novega približka. V takem primeru bi znal bit ta pristop celo počasnejši od zgornjega bruteforce pristopa zaradi malo dražjih izračunov - ugotavljanje sekanja daljic.