Pomoć. c i pseudo -.-

[Teva]

ovako.
Imam algoritam u pseudokodu koji treba implementiram u C.
Al ne mogu da razumem ****ni pseudokod. Probao sam milion različitih varijanti i ništa.
Fja treba da izbaci sve antipodalne parove, i da nadje najveći od njih, tj. par sa najvećim rastojanjem.

PSEUDO
The input is a polygon P={p1,...,pn}.

begin
p0:=pn;
q:=NEXT[p];
while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q)) do
q:=NEXT[q];
q0:=q;
while (q != p0) do
begin
p:=NEXT[p];
Print(p,q);
while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q) do
begin
q:=NEXT[q];
if ((p,q) != (q0,p0)) then Print(p,q)
else return
end;
if (Area(p,NEXT[p],NEXT[q]) = Area(p,NEXT[p],q)) then
if ((p,q) != (q0,p0)) then Print(p,NEXT[q])
else Print(NEXT[p],q)
end
end.

Note that Print(p,q) signifies the output of (p,q) as an anti-podal pair and Area(p,q,r) signifies the signed-area of triangle pqr.
Although this procedure is not as intuitive as the usual Rotating Calipers algorithm, it is essentially the same, and avoids any angle computations.

MOJ KOD
antipodal antipodalni_parovi(tacka* a, int n){
tacka p0,q0;
antipodal ni[5000];
double pom = 0;
p0 = a[n-1];
int p = 0, q = 1, k = 0;
while( vektorski_proizvod(a[p],a[p+1],a[q+1]) > vektorski_proizvod(a[p],a[p+1],a[q]) ){
q = q + 1;
q0 = a[q];
while( !poredjenje(a[q],p0) ){
p = p + 1;
ni[k] = output(a,p,q);
k++;
while( vektorski_proizvod(a[p],a[p+1],a[q+1]) > vektorski_proizvod(a[p],a[p+1],a[q]) ){
q = q + 1;
if(rastojanje(a[p],a[q]) != rastojanje(q0,p0) ){// !( poredjenje(a[p],q0) && poredjenje(a[q], p0) ) ){
ni[k] = output(a,p,q);
k++;
}
else break;
}
if( vektorski_proizvod(a[p],a[p+1],a[q+1]) == vektorski_proizvod(a[p],a[p+1],a[q]) ){
if( rastojanje(a[p],a[q]) != rastojanje(q0,p0) ){
ni[k] = output(a,p,q+1);
k++;
}
else {
ni[k] = output(a,p+1,q);
k++;
}
}
}
}
int i,j;
pom = ni[0].raz;
for(i=1;i<k;i++){
if(ni[i].raz > pom){
pom = ni[i].raz;
j = i;
}
}
return ni[j];
}

a je niz koji sadrži konveksni omotač.

Antipodal struktura ima dve int vrednosti (a i b) kao pozicije dve tačke, i double vrednost (raz) razdaljinu. Output napravi strukturu i vrati, poredjenje proverava dal su obe koord tacaka iste i vraca true ako su iste i false ako nisu...

Problem je u tome što bruteforce i ovaj algoritam izbace drugačije vrednosti. Odnosno neki put se poklope neki put ne, što znači da mi je promakako neki slučaj al ja ne znam koji. Ceo dan gledam i ne shvatam.

[ivan90BG]

Ne valja ti vektorski_proizvod. U pseudo kodu je na tim mestima funkcija Area za koju je objašnjeno da daje signed-area trougla koji formiraju tri tačke (površinu koja (valjda :)) može da bude i negativna, ako je (valjda :)) veći deo trougla ispod x-ose (kao kod integrala, ako je funkcija na intervalu integracije ispod x-ose, integral će biti negativan, odnosno dobiće se negativna površina))

Formula za "potpisanu" površinu trougla tri tačke je:

1 |x1 y1 1|
P = --- |x2 y2 1| <-- determinanta
2! |x3 y3 1|


Sve osim onoga o integralima sam izgooglao, tako da ništa ne garantujem :). Probaj pa javi.

[Teva]

znači u principu treba da polovim vektorski proizvod? Jer determinanta je u principu vektorski proizvod tri tačke...

[ivan90BG]

A šta ta tvoja funkcija vektorski_proizvod u stvari vraća (jel površinu).

Rezultat vektorskog proizvoda je vektor čija dužina je jednaka površini paralelograma koji grade polazni vektori. Ako se podeli sa dva dobija se površina trolgla, ali je to pozitivna površina (odnosno apsolutna). A ovde se traži označena površina (recimo da je polovina površine trougla iznad x-ose, a polovina ispod, ja kapiram da će tada označena površina biti jednaka 0, jer se deo ispod x-ose smatra negativnim).

Ali pored toga vektorski proizvod važi samo u 3D prostoru, a ovde se radi sa 2D-om (tačke imaju samo x i y koordinate) i ova formula koju sam našao zadovoljava taj uslov (uzima tri tačke u 2D prostoru i daje označenu površinu), dok formula vektorskog proizvoda uzima dve tačke u 3D prostoru i daje vektor u 3D prostoru (u oba slučaj 6 vrednosti pa si možda zbog toga pomislio da je isto, ali ipak ta determinanta nije formula vektorskog proizvoda).
Ovo je formula vektorskog proizvoda, jel vidiš razliku:

|i j k |
v1 x v2 = |x1 y1 z1| (i,j,k su jedinični vektori)
|x2 y2 z2|

[Teva]

Ok. Shvatam šta mi govoriš. Ali ja sam imao u okviru istog programa i kreiranje konveksnog omotača, gde se koristi ista stvar (signed area of triangle) za određivanje dal je levi il desni zaokret...

Pa sam samo prekopirao... Kreiranje konveksnog omotača mi radi super al ovde iz nekog razloga ne želi da radi....

[ivan90BG]

Proguglao sam još i otkrio štaje u stvari "Signed area of triangle". Zaboravi ono što sam napisao gore. Označena površina nema veze sa x-osom.

Ako su tri tačke koje su ulaz u formulu orijentisane u smeru suprotnom od kazaljke na satu označena površina će biti pozitivna, a ako su orijentisane u semu kazaljek na satu biće negativna. Tako da je to formula za određivanje kako su bilo koje tri tačke poređane u kooordinatnom sistemu.

(x1,y1)------(x3,y3)
\ / |x1 y1 1|
\ / |x2 y2 1| > 0
\ / |x3 y3 1|
\ /
(x2,y2)

(x1,y1)------(x2,y2)
\ / |x1 y1 1|
\ / |x2 y2 1| < 0
\ / |x3 y3 1|
\ /
(x3,y3)