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;
}