22 void (*fn) (
void *,
Ppoint_t *),
void *vc);
25 double d = (p1.
y - p2.
y) * (p3.
x - p2.
x) - (p3.
y - p2.
y) * (p1.
x - p2.
x);
42 const size_t pointn =
polygon->pn;
46 for (
size_t i = 0; i < pointn; i++)
49 assert(pointn <= INT_MAX);
50 if (
triangulate(pointp, (
int)pointn, fn, vc) != 0) {
65 void (*fn) (
void *,
Ppoint_t *),
void *vc)
70 for (i = 0; i < pointn; i++) {
71 ip1 = (i + 1) % pointn;
72 ip2 = (i + 2) % pointn;
79 for (i = 0; i < pointn; i++)
81 pointp[j++] = pointp[i];
96 int ip1, im1, j, jp1, res;
99 ip1 = (i + 1) % pointn;
100 im1 = (i + pointn - 1) % pointn;
102 if (
ccw(indexer(pointp, im1), indexer(pointp, i), indexer(pointp, ip1)) ==
ISCCW)
103 res =
ccw(indexer(pointp, i), indexer(pointp, ip2), indexer(pointp, im1)) ==
ISCCW &&
104 ccw(indexer(pointp, ip2), indexer(pointp, i), indexer(pointp, ip1)) ==
ISCCW;
107 res =
ccw(indexer(pointp, i), indexer(pointp, ip2), indexer(pointp, ip1)) ==
ISCW;
113 for (j = 0; j < pointn; j++) {
114 jp1 = (j + 1) % pointn;
115 if (!(j == i || jp1 == i || j == ip2 || jp1 == ip2))
117 (indexer(pointp, i), indexer(pointp, ip2), indexer(pointp, j), indexer(pointp, jp1))) {
125 int ccw1, ccw2, ccw3, ccw4;
133 ccw1 =
ccw(pa, pb, pc) ==
ISCCW ? 1 : 0;
134 ccw2 =
ccw(pa, pb, pd) ==
ISCCW ? 1 : 0;
135 ccw3 =
ccw(pc, pd, pa) ==
ISCCW ? 1 : 0;
136 ccw4 =
ccw(pc, pd, pb) ==
ISCCW ? 1 : 0;
137 return (ccw1 ^ ccw2) && (ccw3 ^ ccw4);
147 return pca.
x * pba.
x + pca.
y * pba.
y >= 0 &&
148 pca.
x * pca.
x + pca.
y * pca.
y <= pba.
x * pba.
x + pba.
y * pba.
y;
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Ppoint_t(* indexer_t)(void *base, int index)
bool intersects(Ppoint_t pa, Ppoint_t pb, Ppoint_t pc, Ppoint_t pd)
line to line intersection
bool between(Ppoint_t pa, Ppoint_t pb, Ppoint_t pc)
is pb between pa and pc?
static int triangulate(Ppoint_t **pointp, int pointn, void(*fn)(void *, Ppoint_t *), void *vc)
int Ptriangulate(Ppoly_t *polygon, void(*fn)(void *, Ppoint_t *), void *vc)
int ccw(Ppoint_t p1, Ppoint_t p2, Ppoint_t p3)
are the given points counter-clockwise, clockwise, or co-linear?
static Ppoint_t point_indexer(void *base, int index)
bool isdiagonal(int i, int ip2, void *pointp, int pointn, indexer_t indexer)
is (i, i + 2) a diagonal?