Aprende Geometría Computacional en UJAEN

Tema1: Introducción a los tipos de datos geométricos Eficiencia de los algoritmos Definición de Tipos de Datos Geométricos en 2D Operaciones básicas den G.C. Estructuras de datos espaciales basadas en árboles Kd-trees Range-Trees Bibliografía

 

clase segmento:

class segmento {
   punto s,i;    //s=superior; i=inferior
public:
   segmento (): s(), i() {};
   segmento (const punto& a, const punto& b);
   segmento (const vertice &v1, const vertice &v2);
   segmento (double p1a, double p2a, double p1b, double p2b);
   punto intersecta (const segmento &se) const;
   punto leer_sup () const {return s;}
   punto leer_inf () const {return i;}
   bool es_horizontal () const {return ValorAbs(s.y-i.y)<=CERO;}
   bool es_vertical () const {return ValorAbs(s.x-i.x)<=CERO;}
   bool punto_izquierda (const punto& pt) const { //pt está a la izquierda? 
      return AreaTriangulo2 (s.x, s.y, i.x, i.y, pt.x, pt.y)>0;
   }
...
};

clase polígono:

class poligono {
protected:
   unsigned nvert;
   vertice *lis_vert;
public:
   friend class vertice;
   poligono(): lis_vert (0),nvert(0) {}
   poligono(int n){
      lis_vert = new vertice [nvert=n]; if (!lis_vert) throw 1;
   }
   poligono (const poligono &p);
   poligono& operator= (const poligono& p);
   void reserva (int tamanio){
      if (lis_vert) delete lis_vert;
      lis_vert = new vertice [nvert=tamanio]; if (!lis_vert) throw ERROR_1;
   }
   int anadir (const punto& p, unsigned posi) {
      if (posi >= nvert) throw 2;
      vertice v (p,posi,this);
      lis_vert[posi] = v;
      return 1;
   }
   vertice& operator[] (unsigned posi) {
      if (posi >= nvert) throw ERROR_2;
      return (lis_vert[posi]);
   }
   ~poligono() { if (lis_vert) delete lis_vert;}
.....
};

clase vértice:

class vertice {
   punto v;
   int pos;
   poligono *poli;
public:
   friend class poligono;
   vertice(): poli (0) {}
   vertice (const punto &a, int posi, poligono *p):v(a),pos(posi),poli(p){}
   vertice (const vertice& vert) {v=vert.v; pos=vert.pos; poli=vert.poli;}
   vertice& operator= (const vertice& vert){
      v=vert.v; pos=vert.pos; poli=vert.poli;
      return *this;
   }
   int lee_indice () {return pos;}
   punto lee_punto () const {return v;}
   vertice predecesor ();
   vertice siguiente ();
/*...*/
}

Intersección impropia de segmentos:

FUNCION IntersectaSegmento (a,b,c,d:TipoPunto):Boolean
BEGIN
   if (Colineal(a,b,c) OR Colineal(a,b,d) OR
       Colineal(c,d,a) OR Colineal(c,d,b))
   then return (false)
   else return ((Izquierda(a,b,c) XOR Izquierda(a,b,d)) AND (Izquierda(c,d,a) XOR Izquierda(c,d,b))
END

Intersección propia de segmentos:

FUNCION IntersecImpropia (a,b,c,d:TipoPunto):Boolean
begin
   if (Entre(a,b,c) OR Entre(a,b,d) OR 
       Entre(c,d,a) OR Entre(c,d,b))
   then return true
   else return ((Izquierda(a,b,c) XOR Izquierda(a,b,d)) 
            AND (Izquierda(c,d,a) XOR Izquierda(c,d,b)))
END

FUNCION Entre (a,b,c:TipoPunto):Boolean
BEGIN
   if (Not Colineal(a,b,c))
   then return (false)
   else if a[0] <> b[0]
        then return (a[0]<=b[0] AND c[0]<=b[0] OR a[0]>=c[0] AND c[0]>=b[0])
        else return (a[1]<=c[1] AND c[1]<=b[1] OR a[1]>=c[1] AND c[1]>=b[1])
END;

Cálculo de la menor tangente común a dos polígonos:

Funcion MenorTangente (A,B:Poligono;n,m,a,b:Integer)
BEGIN
   a <- MasDecha (A, n)
   b <- MasIzda (B, m)
   REPETIR
      aa <- a
      bb <- b
      MIENTRAS NO (Tangente (A,n,a,b)) 
         a <- (a-1+n) % n
      FIN_MIENTRAS
      MIENTRAS NO (Tangente (B,m,a,b)) 
         b <- (b+1) % n
      FIN_MIENTRAS
   HASTA (aa=a AND bb=b)
END