You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
207 lines
5.8 KiB
207 lines
5.8 KiB
4 years ago
|
#include "math.h"
|
||
|
#include <vertex.h>
|
||
|
|
||
|
int area2(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c)
|
||
|
{
|
||
|
return ((b->coordinates[X] - a->coordinates[X]) *
|
||
|
(c->coordinates[Y] - a->coordinates[Y])) -
|
||
|
((c->coordinates[X] - a->coordinates[X]) *
|
||
|
(b->coordinates[Y] - a->coordinates[Y]));
|
||
|
}
|
||
|
|
||
|
int area_poly_2(const struct Vertex *head)
|
||
|
{
|
||
|
int sum = 0;
|
||
|
struct Vertex *a = head->next;
|
||
|
|
||
|
do {
|
||
|
sum += area2(head, a, a->next);
|
||
|
a = a->next;
|
||
|
} while (a->next != head);
|
||
|
|
||
|
return sum;
|
||
|
}
|
||
|
|
||
|
bool left(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c)
|
||
|
{
|
||
|
return area2(a, b, c) > 0;
|
||
|
}
|
||
|
|
||
|
bool left_on(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c)
|
||
|
{
|
||
|
return area2(a, b, c) >= 0;
|
||
|
}
|
||
|
|
||
|
bool collinear(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c)
|
||
|
{
|
||
|
return area2(a, b, c) == 0;
|
||
|
}
|
||
|
|
||
|
bool intersect_prop(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c, const struct Vertex *d)
|
||
|
{
|
||
|
if (collinear(a, b, c) || collinear(a, b, d) || collinear(c, d, a) ||
|
||
|
collinear(c, d, b)) {
|
||
|
return false;
|
||
|
}
|
||
|
|
||
|
// The arguments are negated to insure they are 0/1
|
||
|
return !left(a, b, c) ^ !left(a, b, d) && !left(c, d, a) ^ !left(c, d, b);
|
||
|
}
|
||
|
|
||
|
bool between(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c)
|
||
|
{
|
||
|
if (!collinear(a, b, c)) {
|
||
|
return false;
|
||
|
}
|
||
|
|
||
|
// if ab is not vertical, check betweenness on x, else on y.
|
||
|
if (a->coordinates[X] != b->coordinates[X]) {
|
||
|
return ((a->coordinates[X] <= c->coordinates[X]) &&
|
||
|
(c->coordinates[X] <= b->coordinates[X])) ||
|
||
|
((a->coordinates[X] >= c->coordinates[X]) &&
|
||
|
(c->coordinates[X] >= b->coordinates[X]));
|
||
|
} else {
|
||
|
return ((a->coordinates[Y] <= c->coordinates[Y]) &&
|
||
|
(c->coordinates[Y] <= b->coordinates[Y])) ||
|
||
|
((a->coordinates[Y] >= c->coordinates[Y]) &&
|
||
|
(c->coordinates[Y] >= b->coordinates[Y]));
|
||
|
}
|
||
|
}
|
||
|
|
||
|
bool intersect(const struct Vertex *a, const struct Vertex *b,
|
||
|
const struct Vertex *c, const struct Vertex *d)
|
||
|
{
|
||
|
// First check for proper intersection - the intersection that you
|
||
|
// normally think of (two lines forming a kind of cross).
|
||
|
if (intersect_prop(a, b, c, d)) {
|
||
|
return true;
|
||
|
} else if (between(a, b, c) || between(a, b, d) || between(c, d, a) ||
|
||
|
between(c, d, b)) {
|
||
|
|
||
|
// Improper intersection - where an endpoint of one line
|
||
|
// segment is intersected on another line segment.
|
||
|
return true;
|
||
|
} else {
|
||
|
return false;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
bool diagonalie(const struct Vertex *head, const struct Vertex *a,
|
||
|
const struct Vertex *b)
|
||
|
{
|
||
|
struct Vertex *c;
|
||
|
struct Vertex *c1;
|
||
|
|
||
|
c = head;
|
||
|
|
||
|
// For each edge (c, c1) of the polygon represented by head
|
||
|
do {
|
||
|
c1 = c->next;
|
||
|
|
||
|
/* Skip the edge (c, c1) if it is incident with (a, b).
|
||
|
In this case we are testing first to make sure the chosen points
|
||
|
aren't the same points as our test edge ab (trivial case of
|
||
|
incidence) and then testing to make sure there is no intersection
|
||
|
(normal idea of incidence of two line segments).
|
||
|
*/
|
||
|
if ((c != a) && (c1 != a) && (c != b) && (c1 != b) &&
|
||
|
intersect(a, b, c, c1)) {
|
||
|
return false;
|
||
|
}
|
||
|
|
||
|
c = c->next;
|
||
|
} while (c != head);
|
||
|
|
||
|
return true;
|
||
|
}
|
||
|
|
||
|
bool in_cone(const struct Vertex *a, const struct Vertex *b)
|
||
|
{
|
||
|
struct Vertex *a0;
|
||
|
struct Vertex *a1;
|
||
|
|
||
|
a1 = a->next;
|
||
|
a0 = a->prev;
|
||
|
|
||
|
// If a is a convex vertex...
|
||
|
if (left_on(a, a1, a0)) {
|
||
|
return left(a, b, a0) && left(b, a, a1);
|
||
|
}
|
||
|
|
||
|
// Otherwise a is reflex...
|
||
|
// The result is a0 and a1 will be "further outside" of a, so the
|
||
|
// diagonal formed by a0a1 is external to the cone.
|
||
|
return !(left_on(a, b, a1) && left_on(b, a, a0));
|
||
|
}
|
||
|
|
||
|
bool diagonal(const struct Vertex *head, const struct Vertex *a,
|
||
|
const struct Vertex *b)
|
||
|
{
|
||
|
// Performance wise in_cone is called first because it is a constant
|
||
|
// time operation that, when it fails, prevents a call to the more
|
||
|
// potentially performance heavy looping in diagonalie.
|
||
|
return in_cone(a, b) && in_cone(b, a) && diagonalie(head, a, b);
|
||
|
}
|
||
|
|
||
|
void triangulate(const struct Vertex *head)
|
||
|
{
|
||
|
// 5 consecutive vertices
|
||
|
struct Vertex *v0;
|
||
|
struct Vertex *v1;
|
||
|
struct Vertex *v2;
|
||
|
struct Vertex *v3;
|
||
|
struct Vertex *v4;
|
||
|
|
||
|
int n = vertex_count(head);
|
||
|
|
||
|
// Each step of the outer loop removes one ear
|
||
|
while (n > 3) {
|
||
|
// Inner loop searches for an ear.
|
||
|
v2 = head;
|
||
|
do {
|
||
|
if (v2->ear) {
|
||
|
// Found an ear, fill the variables
|
||
|
v3 = v2->next;
|
||
|
v4 = v3->next;
|
||
|
v1 = v2->prev;
|
||
|
v0 = v1->prev;
|
||
|
|
||
|
// Print the diagonal
|
||
|
printf("DIAGONAL: (%d, %d)\n", v1->number, v3->number);
|
||
|
|
||
|
// Update the earity of the remaining diagonal endpoints
|
||
|
v1->ear = diagonal(head, v0, v3);
|
||
|
v3->ear = diagonal(head, v1, v4);
|
||
|
|
||
|
// Cut off the ear v2.
|
||
|
v1->next = v3;
|
||
|
v3->prev = v1;
|
||
|
head = v3;
|
||
|
n--;
|
||
|
|
||
|
break;
|
||
|
}
|
||
|
|
||
|
if(v2 -> ear) {
|
||
|
struct Vertex *temp = v2->next;
|
||
|
|
||
|
// Since we have pointed around v2 (ear removal) there is no
|
||
|
// way to reach it anymore. As a result a free call is necessary
|
||
|
// to clean it up.
|
||
|
free_vertex(v2);
|
||
|
|
||
|
v2 = temp;
|
||
|
} else {
|
||
|
v2 = v2->next;
|
||
|
}
|
||
|
|
||
|
} while (v2 != head);
|
||
|
}
|
||
|
}
|