Geométricos‎ > ‎

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