Graphviz 14.0.2~dev.20251009.1020
Loading...
Searching...
No Matches
triang.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <assert.h>
12#include <stdbool.h>
13#include <stdio.h>
14#include <math.h>
15#include <stdlib.h>
16#include <pathplan/pathutil.h>
17#include <pathplan/tri.h>
18#include <util/alloc.h>
19
20static int triangulate(Ppoint_t **pointp, size_t pointn,
21 void (*fn)(void *, const Ppoint_t *), void *vc);
22
23int ccw(Ppoint_t p1, Ppoint_t p2, Ppoint_t p3) {
24 double d = (p1.y - p2.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p1.x - p2.x);
25 return d > 0 ? ISCW : (d < 0 ? ISCCW : ISON);
26}
27
28static Ppoint_t point_indexer(void *base, size_t index) {
29 Ppoint_t **b = base;
30 return *b[index];
31}
32
33/* Ptriangulate:
34 * Return 0 on success; non-zero on error.
35 */
36int Ptriangulate(Ppoly_t *polygon, void (*fn)(void *, const Ppoint_t *),
37 void *vc) {
38 Ppoint_t **pointp;
39
40 const size_t pointn = polygon->pn;
41
42 pointp = gv_calloc(pointn, sizeof(Ppoint_t*));
43
44 for (size_t i = 0; i < pointn; i++)
45 pointp[i] = &(polygon->ps[i]);
46
47 assert(pointn >= 3);
48 if (triangulate(pointp, pointn, fn, vc) != 0) {
49 free(pointp);
50 return 1;
51 }
52
53 free(pointp);
54 return 0;
55}
56
57/* triangulate:
58 * Triangulates the given polygon.
59 * Returns non-zero if no diagonal exists.
60 */
61static int triangulate(Ppoint_t **pointp, size_t pointn,
62 void (*fn)(void *, const Ppoint_t *), void *vc) {
63 assert(pointn >= 3);
64 Ppoint_t A[3];
65 if (pointn > 3) {
66 for (size_t i = 0; i < pointn; i++) {
67 const size_t ip1 = (i + 1) % pointn;
68 const size_t ip2 = (i + 2) % pointn;
69 if (isdiagonal(i, ip2, pointp, pointn, point_indexer)) {
70 A[0] = *pointp[i];
71 A[1] = *pointp[ip1];
72 A[2] = *pointp[ip2];
73 fn(vc, A);
74 size_t j = 0;
75 for (i = 0; i < pointn; i++)
76 if (i != ip1)
77 pointp[j++] = pointp[i];
78 return triangulate(pointp, pointn - 1, fn, vc);
79 }
80 }
81 return -1;
82 } else {
83 A[0] = *pointp[0];
84 A[1] = *pointp[1];
85 A[2] = *pointp[2];
86 fn(vc, A);
87 }
88 return 0;
89}
90
92static bool between(Ppoint_t pa, Ppoint_t pb, Ppoint_t pc) {
93 const Ppoint_t pba = {.x = pb.x - pa.x, .y = pb.y - pa.y};
94 const Ppoint_t pca = {.x = pc.x - pa.x, .y = pc.y - pa.y};
95 if (ccw(pa, pb, pc) != ISON)
96 return false;
97 return pca.x * pba.x + pca.y * pba.y >= 0 &&
98 pca.x * pca.x + pca.y * pca.y <= pba.x * pba.x + pba.y * pba.y;
99}
100
102static bool intersects(Ppoint_t pa, Ppoint_t pb, Ppoint_t pc, Ppoint_t pd) {
103 int ccw1, ccw2, ccw3, ccw4;
104
105 if (ccw(pa, pb, pc) == ISON || ccw(pa, pb, pd) == ISON ||
106 ccw(pc, pd, pa) == ISON || ccw(pc, pd, pb) == ISON) {
107 if (between(pa, pb, pc) || between(pa, pb, pd) || between(pc, pd, pa) ||
108 between(pc, pd, pb))
109 return true;
110 } else {
111 ccw1 = ccw(pa, pb, pc) == ISCCW ? 1 : 0;
112 ccw2 = ccw(pa, pb, pd) == ISCCW ? 1 : 0;
113 ccw3 = ccw(pc, pd, pa) == ISCCW ? 1 : 0;
114 ccw4 = ccw(pc, pd, pb) == ISCCW ? 1 : 0;
115 return (ccw1 ^ ccw2) && (ccw3 ^ ccw4);
116 }
117 return false;
118}
119
120bool isdiagonal(size_t i, size_t ip2, void *pointp, size_t pointn,
121 indexer_t indexer) {
122 int res;
123
124 /* neighborhood test */
125 const size_t ip1 = (i + 1) % pointn;
126 const size_t im1 = (i + pointn - 1) % pointn;
127 /* If P[i] is a convex vertex [ i+1 left of (i-1,i) ]. */
128 if (ccw(indexer(pointp, im1), indexer(pointp, i), indexer(pointp, ip1)) == ISCCW)
129 res = ccw(indexer(pointp, i), indexer(pointp, ip2), indexer(pointp, im1)) == ISCCW &&
130 ccw(indexer(pointp, ip2), indexer(pointp, i), indexer(pointp, ip1)) == ISCCW;
131 /* Assume (i - 1, i, i + 1) not collinear. */
132 else
133 res = ccw(indexer(pointp, i), indexer(pointp, ip2), indexer(pointp, ip1)) == ISCW;
134 if (!res) {
135 return false;
136 }
137
138 /* check against all other edges */
139 for (size_t j = 0; j < pointn; j++) {
140 const size_t jp1 = (j + 1) % pointn;
141 if (!(j == i || jp1 == i || j == ip2 || jp1 == ip2))
142 if (intersects
143 (indexer(pointp, i), indexer(pointp, ip2), indexer(pointp, j), indexer(pointp, jp1))) {
144 return false;
145 }
146 }
147 return true;
148}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define A(n, t)
Definition expr.h:76
void free(void *)
double x
Definition pathgeom.h:38
double y
Definition pathgeom.h:38
@ ISON
co-linear
Definition tri.h:43
@ ISCW
clockwise
Definition tri.h:42
@ ISCCW
counter-clockwise
Definition tri.h:41
Ppoint_t(* indexer_t)(void *base, size_t index)
Definition tri.h:49
bool isdiagonal(size_t i, size_t ip2, void *pointp, size_t pointn, indexer_t indexer)
is (i, i + 2) a diagonal?
Definition triang.c:120
static bool between(Ppoint_t pa, Ppoint_t pb, Ppoint_t pc)
is pb between pa and pc?
Definition triang.c:92
static Ppoint_t point_indexer(void *base, size_t index)
Definition triang.c:28
int ccw(Ppoint_t p1, Ppoint_t p2, Ppoint_t p3)
are the given points counter-clockwise, clockwise, or co-linear?
Definition triang.c:23
static int triangulate(Ppoint_t **pointp, size_t pointn, void(*fn)(void *, const Ppoint_t *), void *vc)
Definition triang.c:61
static bool intersects(Ppoint_t pa, Ppoint_t pb, Ppoint_t pc, Ppoint_t pd)
line to line intersection
Definition triang.c:102
int Ptriangulate(Ppoly_t *polygon, void(*fn)(void *, const Ppoint_t *), void *vc)
Definition triang.c:36