1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15#include <stdio.h>
16#include <math.h>
17#include <stdlib.h>
18#include <setjmp.h>
19#include "pathutil.h"
20#include "tri.h"
21
22#ifdef DMALLOC
23#include "dmalloc.h"
24#endif
25
26typedef struct lvertex_2_t {
27 double x, y;
28} lvertex_2_t;
29
30typedef struct dpd_triangle {
31 Ppoint_t *v[3];
32} ltriangle_t;
33
34#define ISCCW 1
35#define ISCW 2
36#define ISON 3
37
38#ifndef TRUE
39#define TRUE 1
40#define FALSE 0
41#endif
42
43static jmp_buf jbuf;
44static int dpd_ccw(Ppoint_t *, Ppoint_t *, Ppoint_t *);
45static int dpd_isdiagonal(int, int, Ppoint_t **, int);
46static int dpd_intersects(Ppoint_t *, Ppoint_t *, Ppoint_t *, Ppoint_t *);
47static int dpd_between(Ppoint_t *, Ppoint_t *, Ppoint_t *);
48static void triangulate(Ppoint_t ** pointp, int pointn,
49 void (*fn) (void *, Ppoint_t *), void *vc);
50
51static int dpd_ccw(Ppoint_t * p1, Ppoint_t * p2, Ppoint_t * p3)
52{
53 double d =
54 ((p1->y - p2->y) * (p3->x - p2->x)) -
55 ((p3->y - p2->y) * (p1->x - p2->x));
56 return (d > 0) ? ISCW : ((d < 0) ? ISCCW : ISON);
57}
58
59/* Ptriangulate:
60 * Return 0 on success; non-zero on error.
61 */
62int Ptriangulate(Ppoly_t * polygon, void (*fn) (void *, Ppoint_t *),
63 void *vc)
64{
65 int i;
66 int pointn;
67 Ppoint_t **pointp;
68
69 pointn = polygon->pn;
70
71 pointp = (Ppoint_t **) malloc(pointn * sizeof(Ppoint_t *));
72
73 for (i = 0; i < pointn; i++)
74 pointp[i] = &(polygon->ps[i]);
75
76 if (setjmp(jbuf)) {
77 free(pointp);
78 return 1;
79 }
80 triangulate(pointp, pointn, fn, vc);
81
82 free(pointp);
83 return 0;
84}
85
86/* triangulate:
87 * Triangulates the given polygon.
88 * Throws an exception if no diagonal exists.
89 */
90static void
91triangulate(Ppoint_t ** pointp, int pointn,
92 void (*fn) (void *, Ppoint_t *), void *vc)
93{
94 int i, ip1, ip2, j;
95 Ppoint_t A[3];
96 if (pointn > 3) {
97 for (i = 0; i < pointn; i++) {
98 ip1 = (i + 1) % pointn;
99 ip2 = (i + 2) % pointn;
100 if (dpd_isdiagonal(i, ip2, pointp, pointn)) {
101 A[0] = *pointp[i];
102 A[1] = *pointp[ip1];
103 A[2] = *pointp[ip2];
104 fn(vc, A);
105 j = 0;
106 for (i = 0; i < pointn; i++)
107 if (i != ip1)
108 pointp[j++] = pointp[i];
109 triangulate(pointp, pointn - 1, fn, vc);
110 return;
111 }
112 }
113 longjmp(jbuf,1);
114 } else {
115 A[0] = *pointp[0];
116 A[1] = *pointp[1];
117 A[2] = *pointp[2];
118 fn(vc, A);
119 }
120}
121
122/* check if (i, i + 2) is a diagonal */
123static int dpd_isdiagonal(int i, int ip2, Ppoint_t ** pointp, int pointn)
124{
125 int ip1, im1, j, jp1, res;
126
127 /* neighborhood test */
128 ip1 = (i + 1) % pointn;
129 im1 = (i + pointn - 1) % pointn;
130 /* If P[i] is a convex vertex [ i+1 left of (i-1,i) ]. */
131 if (dpd_ccw(pointp[im1], pointp[i], pointp[ip1]) == ISCCW)
132 res = (dpd_ccw(pointp[i], pointp[ip2], pointp[im1]) == ISCCW) &&
133 (dpd_ccw(pointp[ip2], pointp[i], pointp[ip1]) == ISCCW);
134 /* Assume (i - 1, i, i + 1) not collinear. */
135 else
136 res = ((dpd_ccw(pointp[i], pointp[ip2], pointp[ip1]) == ISCW)
137 );
138/*
139 &&
140 (dpd_ccw (pointp[ip2], pointp[i], pointp[im1]) != ISCW));
141*/
142 if (!res) {
143 return FALSE;
144 }
145
146 /* check against all other edges */
147 for (j = 0; j < pointn; j++) {
148 jp1 = (j + 1) % pointn;
149 if (!((j == i) || (jp1 == i) || (j == ip2) || (jp1 == ip2)))
150 if (dpd_intersects
151 (pointp[i], pointp[ip2], pointp[j], pointp[jp1])) {
152 return FALSE;
153 }
154 }
155 return TRUE;
156}
157
158/* line to line intersection */
159static int dpd_intersects(Ppoint_t * pa, Ppoint_t * pb, Ppoint_t * pc,
160 Ppoint_t * pd)
161{
162 int ccw1, ccw2, ccw3, ccw4;
163
164 if (dpd_ccw(pa, pb, pc) == ISON || dpd_ccw(pa, pb, pd) == ISON ||
165 dpd_ccw(pc, pd, pa) == ISON || dpd_ccw(pc, pd, pb) == ISON) {
166 if (dpd_between(pa, pb, pc) || dpd_between(pa, pb, pd) ||
167 dpd_between(pc, pd, pa) || dpd_between(pc, pd, pb))
168 return TRUE;
169 } else {
170 ccw1 = (dpd_ccw(pa, pb, pc) == ISCCW) ? 1 : 0;
171 ccw2 = (dpd_ccw(pa, pb, pd) == ISCCW) ? 1 : 0;
172 ccw3 = (dpd_ccw(pc, pd, pa) == ISCCW) ? 1 : 0;
173 ccw4 = (dpd_ccw(pc, pd, pb) == ISCCW) ? 1 : 0;
174 return (ccw1 ^ ccw2) && (ccw3 ^ ccw4);
175 }
176 return FALSE;
177}
178
179static int dpd_between(Ppoint_t * pa, Ppoint_t * pb, Ppoint_t * pc)
180{
181 Ppoint_t pba, pca;
182
183 pba.x = pb->x - pa->x, pba.y = pb->y - pa->y;
184 pca.x = pc->x - pa->x, pca.y = pc->y - pa->y;
185 if (dpd_ccw(pa, pb, pc) != ISON)
186 return FALSE;
187 return (pca.x * pba.x + pca.y * pba.y >= 0) &&
188 (pca.x * pca.x + pca.y * pca.y <= pba.x * pba.x + pba.y * pba.y);
189}
190