Graphviz  2.39.20141218.0545
triang.c
Go to the documentation of this file.
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 
26 typedef struct lvertex_2_t {
27  double x, y;
28 } lvertex_2_t;
29 
30 typedef 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 
43 static jmp_buf jbuf;
44 static int dpd_ccw(Ppoint_t *, Ppoint_t *, Ppoint_t *);
45 static int dpd_isdiagonal(int, int, Ppoint_t **, int);
46 static int dpd_intersects(Ppoint_t *, Ppoint_t *, Ppoint_t *, Ppoint_t *);
47 static int dpd_between(Ppoint_t *, Ppoint_t *, Ppoint_t *);
48 static void triangulate(Ppoint_t ** pointp, int pointn,
49  void (*fn) (void *, Ppoint_t *), void *vc);
50 
51 static 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  */
62 int 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  */
90 static void
91 triangulate(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 */
123 static 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 */
159 static 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 
179 static 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 }
#define ISON
Definition: triang.c:36
#define ISCCW
Definition: triang.c:34
int pn
Definition: pathgeom.h:36
Ppoint_t * v[3]
Definition: triang.c:31
Definition: legal.c:39
double x
Definition: pathgeom.h:27
char * malloc()
struct dpd_triangle ltriangle_t
void free()
double x
Definition: triang.c:27
int i
Definition: gvdevice.c:448
#define ISCW
Definition: triang.c:35
double y
Definition: triang.c:27
Ppoint_t * ps
Definition: pathgeom.h:35
struct lvertex_2_t lvertex_2_t
Definition: pathgeom.h:26
int Ptriangulate(Ppoly_t *polygon, void(*fn)(void *, Ppoint_t *), void *vc)
Definition: triang.c:62
double y
Definition: pathgeom.h:27
#define FALSE
Definition: cgraph.h:24
#define TRUE
Definition: cgraph.h:27