|
|
|
#include "vertex.h"
|
|
|
|
#include "math.h"
|
|
|
|
|
|
|
|
struct Vertex *new_vertex(int number, int x, int y)
|
|
|
|
{
|
|
|
|
struct Vertex *newv = (struct Vertex *)malloc(sizeof(struct Vertex));
|
|
|
|
|
|
|
|
if (newv == NULL) {
|
|
|
|
printf("Out of memory");
|
|
|
|
exit(EXIT_FAILURE);
|
|
|
|
}
|
|
|
|
|
|
|
|
newv->number = number;
|
|
|
|
newv->coordinates[0] = x;
|
|
|
|
newv->coordinates[1] = y;
|
|
|
|
newv->ear = false;
|
|
|
|
|
|
|
|
return newv;
|
|
|
|
}
|
|
|
|
|
|
|
|
void add_vertex(struct Vertex *head, struct Vertex *parent,
|
|
|
|
struct Vertex *child)
|
|
|
|
{
|
|
|
|
parent->next = child;
|
|
|
|
child->prev = parent;
|
|
|
|
child->next = head;
|
|
|
|
head->prev = child;
|
|
|
|
};
|
|
|
|
|
|
|
|
void free_vertex(struct Vertex *vertex)
|
|
|
|
{
|
|
|
|
if (vertex != NULL) {
|
|
|
|
free(vertex);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
void free_polygon(struct Vertex **head)
|
|
|
|
{
|
|
|
|
if(head == NULL) {
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
while(*head != NULL) {
|
|
|
|
// Double pointer so we can set the pointer itself to null.
|
|
|
|
struct Vertex **temp = head;
|
|
|
|
(*head) = (*head)->next;
|
|
|
|
free(*temp);
|
|
|
|
*temp = NULL;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
void print_vertex(const struct Vertex *vertex)
|
|
|
|
{
|
|
|
|
printf("VERTEX {number: %d x: %d y: %d ear: %d}\n", vertex->number,
|
|
|
|
vertex->coordinates[X], vertex->coordinates[Y], vertex->ear);
|
|
|
|
}
|
|
|
|
|
|
|
|
void print_polygon(const struct Vertex *head) {
|
|
|
|
const struct Vertex *v = head->next;
|
|
|
|
|
|
|
|
while(v != head) {
|
|
|
|
print_vertex(v);
|
|
|
|
v = v->next;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
void init_ear(struct Vertex *head)
|
|
|
|
{
|
|
|
|
// 3 consecutive vertices
|
|
|
|
struct Vertex *v0;
|
|
|
|
struct Vertex *v1;
|
|
|
|
struct Vertex *v2;
|
|
|
|
|
|
|
|
// Initialize v1->ear for all vertices
|
|
|
|
v1 = head;
|
|
|
|
|
|
|
|
do {
|
|
|
|
v2 = v1->next;
|
|
|
|
v0 = v1->prev;
|
|
|
|
|
|
|
|
// If v0v2 is a diagonal, v1 is an ear by definition.
|
|
|
|
v1->ear = diagonal(head, v0, v2);
|
|
|
|
|
|
|
|
// Move one point over and run it again.
|
|
|
|
v1 = v1->next;
|
|
|
|
} while (v1 != head);
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int vertex_count(const struct Vertex *head)
|
|
|
|
{
|
|
|
|
int sum = 1;
|
|
|
|
const struct Vertex *v = head->next;
|
|
|
|
|
|
|
|
while(v != head) {
|
|
|
|
sum++;
|
|
|
|
v = v->next;
|
|
|
|
}
|
|
|
|
|
|
|
|
return sum;
|
|
|
|
}
|