Skip to content

Instantly share code, notes, and snippets.

@ArturoNereu
Created May 6, 2018 03:15
Show Gist options
  • Save ArturoNereu/771b978c9cc430137064c9901ed6225e to your computer and use it in GitHub Desktop.
Save ArturoNereu/771b978c9cc430137064c9901ed6225e to your computer and use it in GitHub Desktop.
Delaunay and Voronoi in CPP with OpenGL
/***************************************************
12 de marzo del 2011
Arturo Nereu Nunez Martinez
***************************************************/
#include <windows.h>
#include <GL/glut.h>
#include <stdio.h>
#include <math.h>
#define PI 3.1416
bool drawCircle = true;
bool drawTriangle = true;
bool drawVertex = true;
bool drawCenterOfCircle = true;
bool drawVoronoi = true;
// A struct that represents a vertex in 2D
typedef struct Vertex
{
float x, y;
} Vertex;
// A struct for a CustomCircle created from three vertices
typedef struct CustomTriangle
{
Vertex *a, *b, *c, circuncentro;
float radius;
void calculateCenter(void)
{
float x1 = (a->x + b->x) / 2;
float y1 = (a->y + b->y) / 2;
float x2 = (a->x + c->x) / 2;
float y2 = (a->y + c->y) / 2;
float pm1 = (a->y - b->y) / (a->x - b->x);
float pm2 = (a->y - c->y) / (a->x - c->x);
if(pm1 == 0)
pm1 = 0.000000001f;
if(pm2 == 0)
pm2 = 0.000000001f;
float inv1 = -1/pm1;
float inv2 = -1/pm2;
circuncentro.x = (x1 * inv1 - y1 - x2 * inv2 + y2) / (inv1 - inv2);
circuncentro.y = (circuncentro.x * inv1) - (x1 * inv1) + y1;
}
void calculateRadius(void)
{
radius = sqrt(pow(a->x - circuncentro.x, 2) + pow(a->y - circuncentro.y, 2));
}
void drawCircle(void)
{
calculateRadius();
glColor3f(0, 0, 1);
glBegin(GL_LINES);
for(int i = 0; i < 180; i++)
{
float x = radius * cos(i) + circuncentro.x;
float y = radius * sin(i) + circuncentro.y;
float x1 = radius * cos(i+0.1) + circuncentro.x;
float y1 = radius * sin(i+0.1) + circuncentro.y;
glVertex2f(x, y);
glVertex2f(x1, y1);
}
glEnd();
}
void drawCenter(void)
{
calculateCenter();
glColor3f(1, 0, 0);
glBegin(GL_POINTS);
glVertex2f(circuncentro.x, circuncentro.y);
glEnd();
}
void drawTriangle(void)
{
glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
glColor3f(0.2, 0.2, 0.2);
glBegin(GL_TRIANGLES);
glVertex2f(a->x, a->y);
glVertex2f(b->x, b->y);
glVertex2f(c->x, c->y);
glEnd();
}
bool isVertexInside(Vertex *vertex)
{
calculateCenter();
calculateRadius();
float distance = sqrt(pow(vertex->x - circuncentro.x , 2) + pow(vertex->y - circuncentro.y, 2));
return distance <= radius;
}
bool isNeighbor(CustomTriangle *posibleNeighbor)
{
int numberOfSameVertices = 0;
bool isSameA = posibleNeighbor->a == a || posibleNeighbor->a == b || posibleNeighbor->a == c;
bool isSameB = posibleNeighbor->b == a || posibleNeighbor->b == b || posibleNeighbor->b == c;
bool isSameC = posibleNeighbor->c == a || posibleNeighbor->c == b || posibleNeighbor->c == c;
if(isSameA) numberOfSameVertices++;
if(isSameB) numberOfSameVertices++;
if(isSameC) numberOfSameVertices++;
if(numberOfSameVertices >= 2)
return true;
else
return false;
}
Vertex getCircuncentro(void)
{
calculateCenter();
return circuncentro;
}
} CustomTriangle;
//Holds the Vertices in the scene
int numberOfVertices = 0;
Vertex **vertexList;
//Holds the Circles in the scene
int numberOfCircles = 0;
CustomTriangle **circlesList;
//Flag for mouse touching feature
int vertexTouched = 0;
//Testing circle
float testingX = 0.0;
float testingY = 0.0;
bool isAnyVertexInsideCircle(CustomTriangle *subject, int v1, int v2, int v3)
{
for(int i = 0; i < numberOfVertices; i++)
{
//Scape the test over the vertices of the current CustomCircle
if(i == v1 || i == v2 || i == v3)
{
continue;
}
else
{
if(subject->isVertexInside(vertexList[i]))
{
return true;
}
}
}
return false;
}
void insertNewCircle(CustomTriangle *circleToAdd)
{
numberOfCircles++;
circlesList = (CustomTriangle **)realloc(circlesList, sizeof(CustomTriangle) * numberOfCircles);
circlesList[numberOfCircles-1] = circleToAdd;
}
void drawVoronoiCells(void)
{
glColor3f(0, 0, 0);
for(int i = 0; i < numberOfCircles; i++)
{
for(int j = i + 1; j < numberOfCircles; j++)
{
if(circlesList[i]->isNeighbor(circlesList[j]))
{
glBegin(GL_LINES);
glVertex2f(circlesList[i]->getCircuncentro().x, circlesList[i]->getCircuncentro().y);
glVertex2f(circlesList[j]->getCircuncentro().x, circlesList[j]->getCircuncentro().y);
glEnd();
}
}
}
}
void generateTriangles(void)
{
bool hasVertexInside = false;
//Make all the posible combinations of vertices to create valid trigangles
for(int i = 0; i < numberOfVertices; i++)
{
for(int j = i+1; j < numberOfVertices; j++)
{
for(int k = j+1; k < numberOfVertices; k++)
{
CustomTriangle *tempCircle = (CustomTriangle *)malloc(sizeof(CustomTriangle));
tempCircle->a = vertexList[i];
tempCircle->b = vertexList[j];
tempCircle->c = vertexList[k];
hasVertexInside = isAnyVertexInsideCircle(tempCircle, i, j, k);
if(!hasVertexInside)
insertNewCircle(tempCircle);
}
}
}
}
void insertVertex(int x, int y)
{
Vertex *tmp = (Vertex *)malloc(sizeof(Vertex));
numberOfVertices++;
tmp->x = x;
tmp->y = y;
vertexList = (Vertex **)realloc(vertexList, sizeof(Vertex*) * numberOfVertices);
vertexList[numberOfVertices-1] = tmp;
}
void initializeGL(void)
{
glClearColor(1, 1, 1, 1);
}
void drawVertices()
{
glColor3f(0.5, 0.5, 0.5);
for(int i = 0; i < numberOfVertices; i++)
{
glBegin(GL_POINTS);
glVertex2f(vertexList[i]->x, vertexList[i]->y);
glEnd();
}
}
void draw(void)
{
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0, 0, 0);
glPointSize(5);
if(drawVertex)
{
drawVertices();
}
for(int i = 0; i < numberOfCircles; i++)
{
if(drawCenterOfCircle)
circlesList[i]->drawCenter();
if(drawCircle)
circlesList[i]->drawCircle();
if(drawTriangle)
circlesList[i]->drawTriangle();
}
if(drawVoronoi)
drawVoronoiCells();
glutSwapBuffers();
}
void resetTriangulation(void)
{
numberOfCircles = 0;
circlesList = NULL;
}
void resetProgram(void)
{
resetTriangulation();
numberOfVertices = 0;
vertexList = NULL;
}
void key(unsigned char key, int x, int y)
{
if(key == 't') drawTriangle = !drawTriangle;
if(key == 'c') drawCircle = !drawCircle;
if(key == 'p') drawVertex = !drawVertex;
if(key == 's') drawCenterOfCircle = !drawCenterOfCircle;
if(key == 'v') drawVoronoi = !drawVoronoi;
if(key == 'i') resetProgram();
glutPostRedisplay();
}
void mouse(int button, int state, int x, int y)
{
if(button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
{
float newX = x - 400;
float newY = -(y - 300);
for(int i = 0; i < numberOfVertices; i++)
{
if(newX > vertexList[i]->x - 5 && newX < vertexList[i]->x + 5 && newY < vertexList[i]->y + 5 && newY > vertexList[i]->y - 5)
{
vertexTouched = i + 1;
break;
}
else
{
vertexTouched = 0;
}
}
if(vertexTouched == 0)
{
testingX = x - 400;
testingY = -(y - 300);
insertVertex(testingX, testingY);
}
if(numberOfVertices >= 3)
{
resetTriangulation();
generateTriangles();
}
glutPostRedisplay();
}
}
void mouseMotion(int x, int y){
if(vertexTouched){
vertexList[vertexTouched-1]->x = x - 400;
vertexList[vertexTouched-1]->y = -(y - 300);
resetTriangulation();
generateTriangles();
glutPostRedisplay();
}
}
int main(int argc, char **argv)
{
glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);
glutInitWindowSize(800, 600);
glutInitWindowPosition(0, 0);
glutCreateWindow("Cells");
glutDisplayFunc(draw);
gluOrtho2D(-400, 400, -300, 300);
glutMouseFunc(mouse);
glutMotionFunc(mouseMotion);
glutKeyboardFunc(key);
initializeGL();
glutMainLoop();
}
@arcanosam
Copy link

arcanosam commented May 21, 2020

thanks for share. I will use to study and understand better Voronoi e Delauney algorithms 👍

@cesartiago
Copy link

In my case, I have to add the code: "glutInit(&argc, argv);" (on line 14, above "glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);". And it works! Thank you a lot!

No meu caso, eu tenho que adicionar "glutInit(&argc, argv);" (na linha 14, acima de "glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);".
Muito obgd! (PT-BR)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment