Geometria Computacional - Algoritmos III

geometria.c

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include "geometria.h"

float dist_dots(dot_t p0, dot_t p1)
{
/********************************************************************************
 *  FUNSÃO: Calcula a distância entre dois pontos                               *
 *  ENTRADA: Ponto (dot_t) P0 e Ponto (dot_t) P1                                *
 *  SAÍDA: Distancia (float) dist                                               *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    float dist;
    int dx, dy;
    
    dx = (p1.x - p0.x);
    dy = (p1.y - p0.y);
    
    dist = pow(dx,2) + pow(dy,2); 
    dist = pow(dist, 0.5);          //Square Root
    
    return dist;    
}


int cross_product_dots(dot_t p0, dot_t p1, dot_t p2)
{
/********************************************************************************
 *  FUNSÃO: Calcular o produto vetorial entre os vetores definidos por 3 pontos *
 *  ENTRADA: Ponto (dot_t) P0, Ponto (dot_t) P1 e Ponto (dot_t) P2              *
 *  SAÍDA: Inteiro (int) det                                                    *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    int det = 0;
    
    det += ((p0.x * p1.y) + (p0.y * p2.x) + (p1.x * p2.y));  // Positive part
    det -= ((p0.x * p2.y) + (p1.x * p0.y) + (p2.x * p1.y));  // Negative part
    
    return det;
}

int cross_product(line_t u, line_t v)
{
/********************************************************************************
 *  FUNSÃO: Calcular o produto vetorial entre dois vetores.                     *
 *  ENTRADA: Vetor (line_t) U e vetor(line_t) V                                 *
 *  SAÍDA: Inteiro (int) det                                                    *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    if((u.p0.x != v.p0.x) || (u.p0.y != v.p0.y))
    {
        printf("IN CROSS_PRODUCT:\nArgumentos invalidos. Os vetores nao possuem o mesmo ponto de origem.");
        return NULL; //Zero
    }
    
    return cross_product_dots(u.p0, u.p1, v.p1);
}
    
line_t trans_vet(line_t u)
{
/********************************************************************************
 *  FUNSÃO: Retorna o vetor transposto do vetor argumento.                      *
 *  ENTRADA: Vetor (line_t) u                                                   *
 *  SAÍDA: Vetor (line_t) ut                                                    *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    line_t ut;
    
    ut.p0 = u.p1;
    ut.p1 = u.p0;
    
    return ut;
}

int area_rectangle(dot_t p0, dot_t p1)
{
/********************************************************************************
 *  FUNSÃO: Calcular a área do retando de origem em P0 e fim em P1.             *
 *  ENTRADA: 2 Pontos (dot_t) de definição do retangulo, P0 e P1.               *
 *  SAÍDA: Area (int) do retangulo.                                             *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    int area = (abs(p1.x - p0.x) * abs(p1.y - p0.y));
    return area;
}

float area_triangle(dot_t p0, dot_t p1, dot_t p2)
{
/********************************************************************************
 *  FUNSÃO: Calcular a área do triangulo formado pelos pontos P0, P1 e P2       *
 *  ENTRADA: 3 pontos (dot_t), P0, P1 e P2.                                     *
 *  SAÍDA: Area (float) do triangulo.                                           *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    float area = 0.5 * abs(cross_product_dots(p0, p1, p2));
    return area;
}

int relative_position(dot_t p, dot_t p0, dot_t p1)
{
/********************************************************************************
 *  FUNSÃO: Determina a posição relativa do ponto P ao segmento suporte formado *
 *          pelos pontos P0 e P1.                                               *
 *  ENTRADA: 3 pontos (dot_t), P, P1 e P2.                                      *
 *  SAÍDA: Inteiro (int) no valor de:                                           *
 *          0 - se os 3 pontos forem colineares;                                *
 *          1 - se P estiver à direito do segmento suporte (P1 e P2);           *
 *         -1 - se P estiver à esquerda do segmento suporte (P1 e P2);          *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 21/10/2016                                                *
 ********************************************************************************/
    
    float s;
    
    s = cross_product_dots(p, p0, p1);
    
    if(s==0)
    {
        return 0;   // line
    }
    else if(s>0)
    {
        return -1;  // left side
    }
    else
    {
        return 1;   // right side
    }
}

int pontoEmTriangulo(dot_t p, dot_t p0, dot_t p1, dot_t p2)
{
/********************************************************************************
 *  FUNSÃO: Determinar se um dado ponto P está contido no triangulo formado     *
 *          pelos pontos P0, P1 e P2.                                           *
 *  ENTRADA: 4 pontos (dot_t). P, P0, P1 e P3.                                  *
 *  SAÍDA: Inteiro (int). 0 se falso e 1 se verdadeiro.                         *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 22/10/2016                                                *
 ********************************************************************************/
    
    int d1, d2, d3;
    
    d1 = relative_position(p,p0,p1);
    d2 = relative_position(p,p1,p2);
    d3 = relative_position(p,p2,p0);
    
    if((d1 == d2) && (d2 == d3))
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

int pontoEmQuadrilatero(dot_t p, dot_t p0, dot_t p1, dot_t p2, dot_t p3)
{
/********************************************************************************
 *  FUNSÃO: Determinar se um dado ponto P está contido no quadrilatero formado  *
 *          pelos pontos P0, P1, P2 e P3.                                       *
 *  ENTRADA: 5 pontos (dot_t), P, P0, P1, P2 e P3.                              *
 *  SAÍDA: Inteiro (int). 0 se falso e 1 se verdadeiro                          *
 *                                                                              *
 *  DESENVOLVEDOR: Vitor Rodrigues Di Toro"                                     *
 *  ULTIMA ALTERAÇÃO: 22/10/2016                                                *
 ********************************************************************************/
    
    int result;
    float dist0, dist1, dist2, dist3;
    
    dist0 = dist_dots(p,p0);
    dist1 = dist_dots(p,p1);
    dist2 = dist_dots(p,p2);
    dist3 = dist_dots(p,p3);
    
    
    result = ((pontoEmTriangulo(p,p0,p1,p2) || pontoEmTriangulo(p,p2,p3,p0)) ||     //Realia a análise dividindo o quadrilatero em 2 triangulos 
              (pontoEmTriangulo(p,p0,p1,p3) || pontoEmTriangulo(p,p1,p2,p3)) ||     //Realia a análise dividindo o quadrilatero em 2 triangulos 
              ((dist0 == dist1) && (dist1 == dist2) && (dist2 == dist3)));          //Realia a análise do ponto central
              
    return result;
}

geometria.h

#ifndef _GEOMETRIA_H
#define _GEOMETRIA_H

//=== Defines ===//

#define TRUE        1
#define FALSE       0

#define MAX(x,y)    x>y?x:y
#define MIN(x,y)    x<y?x:y


//=== Structs ===//
typedef struct dot_
{
    int x;
    int y;
} dot_t;

typedef struct line_segment_
{    
    dot_t p0;
    dot_t p1;
} line_t;

typedef struct rectangle_
{
    dot_t p0;
    dot_t p1;
} rectangle_t;


//=== Prototypes ===//
float dist_dots(dot_t p0, dot_t p1);                                        // Distance between two dots 
int cross_product_dots(dot_t p0, dot_t p1, dot_t p2);                       // Cross product with 3 dots
int cross_product(line_t u, line_t v);                                      // Cross product
line_t trans_vet(line_t u);                                                 // Transposed vector
int area_rectangle(dot_t p0, dot_t p1);                                     // 
float area_triangle(dot_t p0, dot_t p1, dot_t p2);                          //
int relative_position(dot_t p, dot_t p0, dot_t p1);                         //
int pontoEmTriangulo(dot_t p, dot_t p0, dot_t p1, dot_t p2);                //
int pontoEmQuadrilatero(dot_t p, dot_t p0, dot_t p1, dot_t p2, dot_t p3);   //

#endif

testes.c

#include <stdio.h>
#include "geometria.h"

int main(int argc, char **argv)
{
    dot_t p,p0,p1,p2,p3;
    
    p0.x = 2;
    p0.y = 2;
    p1.x = 8;
    p1.y = 2;
    p2.x = 8;
    p2.y = 8;
    p3.x = 2;
    p3.y = 8;
    
    
    teste(p0,p1,p2,p3);
    
    getchar();
    getchar();
    getchar();
    
    return 0;
}

void teste(dot_t p0, dot_t p1, dot_t p2, dot_t p3)
{
    int i,j, result;
    dot_t p;
    
    for(i = 0; i<11; i++)
    {
        for(j = 0; j<11; j++)
        {
            p.x = i;
            p.y = j;
            
            result = pontoEmQuadrilatero(p, p0, p1, p2, p3);
            printf("[%d , %d] ", i,j);
            printf(result?"Sim\n":"Nao\n");
        }
    }
}