Geométricos - Implementações

Produto Escalar

Calcula o produto escalar entre dois pontos.

Entrada:

• Pontos pta e ptb e origem pto.

Saída:

• Valor do produto escalar (pta - pto) . (ptb - pto).

Complexidade: O( 1 )

Global:

long long prodesc(int pto[2], int pta[2], int ptb[2]) {

long long v1 = ((long long) pta[0]-pto[0])*(ptb[0]-pto[0]);

long long v2 = ((long long) pta[1]-pto[1])*(ptb[1]-pto[1]);

return v1+v2;

}

Produto Vetorial

Calcula o produto vetorial entre dois pontos.

Entrada:

• Pontos pta e ptb e origem pto.

Saída:

• Valor do produto vetorial (pta - pto) X (ptb - pto).

Complexidade: O( 1 )

Global:

long long prodvet(int pto[2], int pta[2], int ptb[2]) {

 long long v1 = ((long long) pta[0]-pto[0])*(ptb[1]-pto[1]);

 long long v2 = ((long long) pta[1]-pto[1])*(ptb[0]-pto[0]);

 return v1-v2;

}

Produto Vetorial (Sinal)

Calcula o sinal do produto vetorial entre dois pontos de forma "segura", evitando overflow.

Entrada:

• Pontos pta e ptb e origem pto.

Saída:

• Sinal do produto vetorial (pta - pto) X (ptb - pto).

Complexidade: O( 1 )

Global:

int prodvetsn(int pto[2], int pta[2], int ptb[2]) {

 long long v1 = ((long long) pta[0]-pto[0])*(ptb[1]-pto[1]);

 long long v2 = ((long long) pta[1]-pto[1])*(ptb[0]-pto[0]);

 if( v1 < v2 )  return -1;

 else if( v1 > v2 ) return +1;

 else return 0;

}

Teste de Pertinência de Ponto em Segmento

Testa se um ponto pertence a um segmento. Depende de prodesc e prodvet.

Entrada:

• Ponto p e segmento (a,b).

Saída:

• Valor booleano que indica se o segmento contém o ponto ou não.

Complexidade: O( 1 )

Global:

bool interPtSeg(int p[2], int a[2], int b[2]) {

  if(prodesc(a,b,b)==0)  // B == A.

    return prodesc(a,p,p)==0;

  else

    return prodvet(p,a,b)==0 && prodesc(a,p,b)>=0 && prodesc(b,p,a)>=0;

}

Distância de Ponto a Segmento

Retorna o quadrado da distância de um ponto a um segmento. A computação é exata, não estando sujeita a erros de precisão. Depende de prodesc e prodvet.

Entrada:

• Ponto p e segmento (a,b).

Saída:

• num e den inteiros tais que num/den == dist(P, AB)^2.

Complexidade: O( 1 )

Global:

void dist2PtSeg(int p[2], int a[2], int b[2], long long *num, long long *den) {

  if(prodesc(a,b,b)>0 && prodesc(a,p,b)>=0 && prodesc(b,p,a)>=0) {

    *num = prodvet(p,a,b); *num *= *num;

    *den = prodesc(a,b,b);

  } else {

    *num = min(prodesc(a,p,p), prodesc(b,p,p));

    *den = 1L;

  }

}

Teste de Pertinência de Ponto em Polígono

Testa se um ponto pertence a um polígono. Ponto na borda é considerado contido. Depende de interPtSeg.

Entrada:

• Ponto p e polígono (poly[][2], n), onde n é o numero de pontos em poly.

Saída:

• Valor booleano que indica se o polígono contém o ponto ou não.

Complexidade: O( n )

Global:

bool interPtPoly(int p[2], int (*poly)[2], int n) {

  // Testa borda.

  for(int i=0; i<n; i++)

    if(interPtSeg(p, poly[i], poly[(i+1)%n]))

      return true;

  // Testa ponto estritament dentro do polígono.

  double anguloTotal = 0;

  for(int i=0; i<n; i++) {

    int *a, *b;

    a = poly[i]; 

    b = poly[(i+1)%n];

    double angulo = atan2(b[0]-p[0],b[1]-p[1]) - atan2(a[0]-p[0],a[1]-p[1]);

    if(angulo>PI)

      angulo -= 2*PI;

    else if(angulo<-PI)

      angulo += 2*PI;

    anguloTotal += angulo;

  }

  return fabs(anguloTotal) > PI;  // fora: 0, dentro: 2*PI

}

Teste de Interseção de Segmentos

Testa se dois segmentos possuem interseção não vazia. Depende de prodvetsn, MIN e MAX.

Entrada:

• Segmentos (a,b) e (c,d).

Saída:

• Valor booleano que indica se os segmentos se intersectam ou não.

Complexidade: O( 1 )

Global:

bool interSegSeg(int a[2], int b[2], int c[2], int d[2]) {

 int i, r1, r2;

 for(i=0; i<2; i++)

  if( MIN(a[i],b[i]) > MAX(c[i],d[i]) || MAX(a[i],b[i]) < MIN(c[i],d[i]) )

   return 0;

 r1 = prodvetsn(a, c, b) * prodvetsn(a, d, b);

 r2 = prodvetsn(c, a, d) * prodvetsn(c, b, d);

 return r1<=0 && r2<=0;

}