A curva dragão Heighway ou dragão Jurassic Park foi investigada primeiramente pelos físicos da NASA John Heighway, Bruce Banks, e William Harter.

Já foi descrita por Martin Gardner em sua coluna na Scientific American de Jogos Matemáticos em 1967. Teve várias de suas propriedades publicadas primeiro por Chandler Davis e Donald Knuth. O fractal da curva dragão também tem uma aparição famosa no livro Jurassic Park de Michael Crichton.

Nesta implementação, uso uma abordagem diferente da tradicional.

• Download dragao.c
• Enviar nova versão

Esconder código-fonte

/*
*   Copyright (C) 2008, 2008 Rafael Siqueira Telles Vieira
*
*   This program is free software; you can redistribute it and/or modify
*   it under the terms of the GNU General Public License as published by
*   the Free Software Foundation; either version 2 of the License, or
*   (at your option) any later version.
*
*   This program is distributed in the hope that it will be useful,
*   but WITHOUT ANY WARRANTY; without even the implied warranty of
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*   See the GNU General Public License for more details.
*
*   License: http://www.lia.ufc.br/~rafaelstv/licenca_GPL_pt.txt
*
*   You should have received a copy of the GNU General Public License
*   along with this program; if not, write to the Free Software Foundation,
*   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*
*/

#include <stdio.h>
#include <math.h>
#include <GL/glut.h>

#define NIVEL 25

float pmax[2];
float pmin[2];
float ponto_inicial[2], ponto_final[2];

float tamanho(float A[2],float B[2])
{
   float vetor[2];

   vetor[0] = A[0] - B[0];
   vetor[1] = A[1] - B[1];

   return sqrt(vetor[0]*vetor[0] + vetor[1]*vetor[1]);
}

void normaliza(float vetor[2])
{
   float d = sqrt(vetor[0]*vetor[0] + vetor[1]*vetor[1]);

   vetor[0] /= d;
   vetor[1] /= d;
}

void ajustaTamanho()
{
   glMatrixMode(GL_PROJECTION);   
   glLoadIdentity();
   glOrtho(pmin[0]-0.1f, pmax[0]+0.1f, pmin[1]-0.1f, pmax[1]+0.1f, 1.0f, -1.0f);
 
   glMatrixMode(GL_MODELVIEW);
}
// desenha o dragao
void geraDragao(float pi[2],float pf[2], int nivel)
{
   float pc[2];   

   pc[0] = (pi[0] + pf[0])/ 2;
   pc[1] = (pi[1] + pf[1])/ 2;

   float vetor[2];

   vetor[0] = pf[0] - pi[0];
   vetor[1] = pf[1] - pi[1];
   
   float normal[2];

   normal[0] = vetor[1];
   normal[1] = -vetor[0];   

   normaliza(normal);   

   float pm[2],d;   

   d = tamanho(pi,pf);
   d /= 2.0f;

   pm[0] = pc[0] + normal[0]*d;
   pm[1] = pc[1] + normal[1]*d;

   if (nivel > 0)   
   {
   if (nivel == NIVEL)
   {
      glColor3f(0.0f,1.0f,0.0f);
      geraDragao(pi, pm, nivel-1);
      glColor3f(1.0f,0.0f,0.0f);
      geraDragao(pf, pm, nivel-1);
   }
   else
   {
      geraDragao(pi, pm, nivel-1);
      geraDragao(pf, pm, nivel-1);
   }
   }   
   else
   {      

   glBegin(GL_LINES);
     glVertex2f(pi[0],pi[1]);
     glVertex2f(pm[0],pm[1]);
   glEnd();
    
   glBegin(GL_LINES);
     glVertex2f(pm[0],pm[1]);
     glVertex2f(pf[0],pf[1]);
   glEnd();
   }
}
// gera o dragao para descobrir o pmax e pmin da tela
void geraLimites(float pi[2],float pf[2], int nivel)
{
   float pc[2];   

   pc[0] = (pi[0] + pf[0])/ 2;
   pc[1] = (pi[1] + pf[1])/ 2;

   float vetor[2];

   vetor[0] = pf[0] - pi[0];
   vetor[1] = pf[1] - pi[1];
   
   float normal[2];

   normal[0] = vetor[1];
   normal[1] = -vetor[0];   

   normaliza(normal);   

   float pm[2],d;   

   d = tamanho(pi,pf);
   d /= 2.0f;

   pm[0] = pc[0] + normal[0]*d;
   pm[1] = pc[1] + normal[1]*d;

   if (pi[0] > pmax[0])
   pmax[0] = pi[0];
   if (pi[1] > pmax[1])
   pmax[1] = pi[1];
   if (pf[0] > pmax[0])
   pmax[0] = pf[0];
   if (pf[1] > pmax[1])
   pmax[1] = pf[1];
   if (pm[0] > pmax[0])
   pmax[0] = pm[0];
   if (pm[1] > pmax[1])
   pmax[1] = pm[1];

   if (pf[0] < pmin[0])
   pmin[0] = pf[0];
   if (pf[1] < pmin[1])
   pmin[1] = pf[1];
   if (pi[0] < pmin[0])
   pmin[0] = pi[0];
   if (pi[1] < pmin[1])
   pmin[1] = pi[1];
   if (pm[0] < pmin[0])
   pmin[0] = pm[0];
   if (pm[1] < pmin[1])
   pmin[1] = pm[1];

   if (nivel > 0)   
   {
   geraLimites(pi, pm, nivel-1);
   geraLimites(pf, pm, nivel-1);
   }   
}

void inicio()
{
   pmax[0] = 0.0f;
   pmax[1] = 0.0f;
   pmin[0] = 0.0f;
   pmin[1] = 0.0f;

   ponto_inicial[0] = -0.9f;    
   ponto_inicial[1] = -0.9f;    

   ponto_final[0] = 0.9f;   
   ponto_final[1] = 0.9f;   

   geraLimites(ponto_inicial, ponto_final, NIVEL);
   ajustaTamanho();
}

void exibe(void)
{   
   glClearColor(1.0f,1.0f,1.0f,1.0f);   
   glClear(GL_COLOR_BUFFER_BIT);

   geraDragao(ponto_inicial, ponto_final, NIVEL);

   glFlush();
}


int main(int argc, char** argv)
{
   glutInit(&argc,argv);
   glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
   glutInitWindowSize(400,400);
   glutInitWindowPosition(20,20);
   glutCreateWindow("Desenhando uma curva Dragao");
   glutDisplayFunc(exibe);
   inicio();   
   glutMainLoop();

   return 0;
}

Fila

Lista Duplamente

Algoritmo do método de Newton

Lista duplamente encadeada com cabecalho

Lista encadeada