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 <stdlib.h>
16 #include <stdio.h>
17 #include <setjmp.h>
18 #ifdef HAVE_MALLOC_H
19 #include <malloc.h>
20 #endif
21 #include <math.h>
22 #include "pathutil.h"
23 #include "solvers.h"
24
25 #define EPSILON1 1E-3
26 #define EPSILON2 1E-6
27
28 #define ABS(a) ((a) >= 0 ? (a) : -(a))
29
30 typedef struct tna_t {
31 double t;
32 Ppoint_t a[2];
33 } tna_t;
34
35 #define prerror(msg) \
36 fprintf (stderr, "libpath/%s:%d: %s\n", __FILE__, __LINE__, (msg))
37
38 #define DISTSQ(a, b) ( \
39 (((a).x - (b).x) * ((a).x - (b).x)) + (((a).y - (b).y) * ((a).y - (b).y)) \
40 )
41
42 #define POINTSIZE sizeof (Ppoint_t)
43
44 #define LT(pa, pbp) ((pa.y > pbp->y) || ((pa.y == pbp->y) && (pa.x < pbp->x)))
45 #define GT(pa, pbp) ((pa.y < pbp->y) || ((pa.y == pbp->y) && (pa.x > pbp->x)))
46
47 typedef struct p2e_t {
48 Ppoint_t *pp;
49 Pedge_t *ep;
50 } p2e_t;
51
52 typedef struct elist_t {
53 Pedge_t *ep;
54 struct elist_t *next, *prev;
55 } elist_t;
56
57 static jmp_buf jbuf;
58
59 #if 0
60 static p2e_t *p2es;
61 static int p2en;
62 #endif
63
64 #if 0
65 static elist_t *elist;
66 #endif
67
68 static Ppoint_t *ops;
69 static int opn, opl;
70
71 static int reallyroutespline(Pedge_t *, int,
72 Ppoint_t *, int, Ppoint_t, Ppoint_t);
73 static int mkspline(Ppoint_t *, int, tna_t *, Ppoint_t, Ppoint_t,
74 Ppoint_t *, Ppoint_t *, Ppoint_t *, Ppoint_t *);
75 static int splinefits(Pedge_t *, int, Ppoint_t, Pvector_t, Ppoint_t,
76 Pvector_t, Ppoint_t *, int);
77 static int splineisinside(Pedge_t *, int, Ppoint_t *);
78 static int splineintersectsline(Ppoint_t *, Ppoint_t *, double *);
79 static void points2coeff(double, double, double, double, double *);
80 static void addroot(double, double *, int *);
81
82 static Pvector_t normv(Pvector_t);
83
84 static void growops(int);
85
86 static Ppoint_t add(Ppoint_t, Ppoint_t);
87 static Ppoint_t sub(Ppoint_t, Ppoint_t);
88 static double dist(Ppoint_t, Ppoint_t);
89 static Ppoint_t scale(Ppoint_t, double);
90 static double dot(Ppoint_t, Ppoint_t);
91 static double B0(double t);
92 static double B1(double t);
93 static double B2(double t);
94 static double B3(double t);
95 static double B01(double t);
96 static double B23(double t);
97 #if 0
98 static int cmpp2efunc(const void *, const void *);
99
100 static void listdelete(Pedge_t *);
101 static void listreplace(Pedge_t *, Pedge_t *);
102 static void listinsert(Pedge_t *, Ppoint_t);
103 #endif
104
105 /* Proutespline:
106 * Given a set of edgen line segments edges as obstacles, a template
107 * path input, and endpoint vectors evs, construct a spline fitting the
108 * input and endpoing vectors, and return in output.
109 * Return 0 on success and -1 on failure, including no memory.
110 */
Proutespline(Pedge_t * edges,int edgen,Ppolyline_t input,Ppoint_t * evs,Ppolyline_t * output)111 int Proutespline(Pedge_t * edges, int edgen, Ppolyline_t input,
112 Ppoint_t * evs, Ppolyline_t * output)
113 {
114 #if 0
115 Ppoint_t p0, p1, p2, p3;
116 Ppoint_t *pp;
117 Pvector_t v1, v2, v12, v23;
118 int ipi, opi;
119 int ei, p2ei;
120 Pedge_t *e0p, *e1p;
121 #endif
122 Ppoint_t *inps;
123 int inpn;
124
125 /* unpack into previous format rather than modify legacy code */
126 inps = input.ps;
127 inpn = input.pn;
128
129 #if 0
130 if (!(p2es = (p2e_t *) malloc(sizeof(p2e_t) * (p2en = edgen * 2)))) {
131 prerror("cannot malloc p2es");
132 return -1;
133 }
134 for (ei = 0, p2ei = 0; ei < edgen; ei++) {
135 if (edges[ei].a.x == edges[ei].b.x
136 && edges[ei].a.y == edges[ei].b.y)
137 continue;
138 p2es[p2ei].pp = &edges[ei].a;
139 p2es[p2ei++].ep = &edges[ei];
140 p2es[p2ei].pp = &edges[ei].b;
141 p2es[p2ei++].ep = &edges[ei];
142 }
143 p2en = p2ei;
144 qsort(p2es, p2en, sizeof(p2e_t), cmpp2efunc);
145 elist = NULL;
146 for (p2ei = 0; p2ei < p2en; p2ei += 2) {
147 pp = p2es[p2ei].pp;
148 #if DEBUG >= 1
149 fprintf(stderr, "point: %d %lf %lf\n", p2ei, pp->x, pp->y);
150 #endif
151 e0p = p2es[p2ei].ep;
152 e1p = p2es[p2ei + 1].ep;
153 p0 = (&e0p->a == p2es[p2ei].pp) ? e0p->b : e0p->a;
154 p1 = (&e0p->a == p2es[p2ei + 1].pp) ? e1p->b : e1p->a;
155 if (LT(p0, pp) && LT(p1, pp)) {
156 listdelete(e0p), listdelete(e1p);
157 } else if (GT(p0, pp) && GT(p1, pp)) {
158 listinsert(e0p, *pp), listinsert(e1p, *pp);
159 } else {
160 if (LT(p0, pp))
161 listreplace(e0p, e1p);
162 else
163 listreplace(e1p, e0p);
164 }
165 }
166 #endif
167 if (setjmp(jbuf))
168 return -1;
169
170 /* generate the splines */
171 evs[0] = normv(evs[0]);
172 evs[1] = normv(evs[1]);
173 opl = 0;
174 growops(4);
175 ops[opl++] = inps[0];
176 if (reallyroutespline(edges, edgen, inps, inpn, evs[0], evs[1]) == -1)
177 return -1;
178 output->pn = opl;
179 output->ps = ops;
180
181 #if 0
182 fprintf(stderr, "edge\na\nb\n");
183 fprintf(stderr, "points\n%d\n", inpn);
184 for (ipi = 0; ipi < inpn; ipi++)
185 fprintf(stderr, "%f %f\n", inps[ipi].x, inps[ipi].y);
186 fprintf(stderr, "splpoints\n%d\n", opl);
187 for (opi = 0; opi < opl; opi++)
188 fprintf(stderr, "%f %f\n", ops[opi].x, ops[opi].y);
189 #endif
190
191 return 0;
192 }
193
reallyroutespline(Pedge_t * edges,int edgen,Ppoint_t * inps,int inpn,Ppoint_t ev0,Ppoint_t ev1)194 static int reallyroutespline(Pedge_t * edges, int edgen,
195 Ppoint_t * inps, int inpn, Ppoint_t ev0,
196 Ppoint_t ev1)
197 {
198 Ppoint_t p1, p2, cp1, cp2, p;
199 Pvector_t v1, v2, splitv, splitv1, splitv2;
200 double maxd, d, t;
201 int maxi, i, spliti;
202
203 static tna_t *tnas;
204 static int tnan;
205
206 if (tnan < inpn) {
207 if (!tnas) {
208 if (!(tnas = malloc(sizeof(tna_t) * inpn)))
209 return -1;
210 } else {
211 if (!(tnas = realloc(tnas, sizeof(tna_t) * inpn)))
212 return -1;
213 }
214 tnan = inpn;
215 }
216 tnas[0].t = 0;
217 for (i = 1; i < inpn; i++)
218 tnas[i].t = tnas[i - 1].t + dist(inps[i], inps[i - 1]);
219 for (i = 1; i < inpn; i++)
220 tnas[i].t /= tnas[inpn - 1].t;
221 for (i = 0; i < inpn; i++) {
222 tnas[i].a[0] = scale(ev0, B1(tnas[i].t));
223 tnas[i].a[1] = scale(ev1, B2(tnas[i].t));
224 }
225 if (mkspline(inps, inpn, tnas, ev0, ev1, &p1, &v1, &p2, &v2) == -1)
226 return -1;
227 if (splinefits(edges, edgen, p1, v1, p2, v2, inps, inpn))
228 return 0;
229 cp1 = add(p1, scale(v1, 1 / 3.0));
230 cp2 = sub(p2, scale(v2, 1 / 3.0));
231 for (maxd = -1, maxi = -1, i = 1; i < inpn - 1; i++) {
232 t = tnas[i].t;
233 p.x = B0(t) * p1.x + B1(t) * cp1.x + B2(t) * cp2.x + B3(t) * p2.x;
234 p.y = B0(t) * p1.y + B1(t) * cp1.y + B2(t) * cp2.y + B3(t) * p2.y;
235 if ((d = dist(p, inps[i])) > maxd)
236 maxd = d, maxi = i;
237 }
238 spliti = maxi;
239 splitv1 = normv(sub(inps[spliti], inps[spliti - 1]));
240 splitv2 = normv(sub(inps[spliti + 1], inps[spliti]));
241 splitv = normv(add(splitv1, splitv2));
242 reallyroutespline(edges, edgen, inps, spliti + 1, ev0, splitv);
243 reallyroutespline(edges, edgen, &inps[spliti], inpn - spliti, splitv,
244 ev1);
245 return 0;
246 }
247
mkspline(Ppoint_t * inps,int inpn,tna_t * tnas,Ppoint_t ev0,Ppoint_t ev1,Ppoint_t * sp0,Ppoint_t * sv0,Ppoint_t * sp1,Ppoint_t * sv1)248 static int mkspline(Ppoint_t * inps, int inpn, tna_t * tnas, Ppoint_t ev0,
249 Ppoint_t ev1, Ppoint_t * sp0, Ppoint_t * sv0,
250 Ppoint_t * sp1, Ppoint_t * sv1)
251 {
252 Ppoint_t tmp;
253 double c[2][2], x[2], det01, det0X, detX1;
254 double d01, scale0, scale3;
255 int i;
256
257 scale0 = scale3 = 0.0;
258 c[0][0] = c[0][1] = c[1][0] = c[1][1] = 0.0;
259 x[0] = x[1] = 0.0;
260 for (i = 0; i < inpn; i++) {
261 c[0][0] += dot(tnas[i].a[0], tnas[i].a[0]);
262 c[0][1] += dot(tnas[i].a[0], tnas[i].a[1]);
263 c[1][0] = c[0][1];
264 c[1][1] += dot(tnas[i].a[1], tnas[i].a[1]);
265 tmp = sub(inps[i], add(scale(inps[0], B01(tnas[i].t)),
266 scale(inps[inpn - 1], B23(tnas[i].t))));
267 x[0] += dot(tnas[i].a[0], tmp);
268 x[1] += dot(tnas[i].a[1], tmp);
269 }
270 det01 = c[0][0] * c[1][1] - c[1][0] * c[0][1];
271 det0X = c[0][0] * x[1] - c[0][1] * x[0];
272 detX1 = x[0] * c[1][1] - x[1] * c[0][1];
273 if (ABS(det01) >= 1e-6) {
274 scale0 = detX1 / det01;
275 scale3 = det0X / det01;
276 }
277 if (ABS(det01) < 1e-6 || scale0 <= 0.0 || scale3 <= 0.0) {
278 d01 = dist(inps[0], inps[inpn - 1]) / 3.0;
279 scale0 = d01;
280 scale3 = d01;
281 }
282 *sp0 = inps[0];
283 *sv0 = scale(ev0, scale0);
284 *sp1 = inps[inpn - 1];
285 *sv1 = scale(ev1, scale3);
286 return 0;
287 }
288
dist_n(Ppoint_t * p,int n)289 static double dist_n(Ppoint_t * p, int n)
290 {
291 int i;
292 double rv;
293
294 rv = 0.0;
295 for (i = 1; i < n; i++) {
296 rv +=
297 sqrt((p[i].x - p[i - 1].x) * (p[i].x - p[i - 1].x) +
298 (p[i].y - p[i - 1].y) * (p[i].y - p[i - 1].y));
299 }
300 return rv;
301 }
302
splinefits(Pedge_t * edges,int edgen,Ppoint_t pa,Pvector_t va,Ppoint_t pb,Pvector_t vb,Ppoint_t * inps,int inpn)303 static int splinefits(Pedge_t * edges, int edgen, Ppoint_t pa,
304 Pvector_t va, Ppoint_t pb, Pvector_t vb,
305 Ppoint_t * inps, int inpn)
306 {
307 Ppoint_t sps[4];
308 double a, b;
309 #if 0
310 double d;
311 #endif
312 int pi;
313 int forceflag;
314 int first = 1;
315
316 forceflag = (inpn == 2 ? 1 : 0);
317
318 #if 0
319 d = sqrt((pb.x - pa.x) * (pb.x - pa.x) +
320 (pb.y - pa.y) * (pb.y - pa.y));
321 a = d, b = d;
322 #else
323 a = b = 4;
324 #endif
325 for (;;) {
326 sps[0].x = pa.x;
327 sps[0].y = pa.y;
328 sps[1].x = pa.x + a * va.x / 3.0;
329 sps[1].y = pa.y + a * va.y / 3.0;
330 sps[2].x = pb.x - b * vb.x / 3.0;
331 sps[2].y = pb.y - b * vb.y / 3.0;
332 sps[3].x = pb.x;
333 sps[3].y = pb.y;
334
335 /* shortcuts (paths shorter than the shortest path) not allowed -
336 * they must be outside the constraint polygon. this can happen
337 * if the candidate spline intersects the constraint polygon exactly
338 * on sides or vertices. maybe this could be more elegant, but
339 * it solves the immediate problem. we could also try jittering the
340 * constraint polygon, or computing the candidate spline more carefully,
341 * for example using the path. SCN */
342
343 if (first && (dist_n(sps, 4) < (dist_n(inps, inpn) - EPSILON1)))
344 return 0;
345 first = 0;
346
347 if (splineisinside(edges, edgen, &sps[0])) {
348 growops(opl + 4);
349 for (pi = 1; pi < 4; pi++)
350 ops[opl].x = sps[pi].x, ops[opl++].y = sps[pi].y;
351 #if defined(DEBUG) && DEBUG >= 1
352 fprintf(stderr, "success: %f %f\n", a, b);
353 #endif
354 return 1;
355 }
356 if (a == 0 && b == 0) {
357 if (forceflag) {
358 growops(opl + 4);
359 for (pi = 1; pi < 4; pi++)
360 ops[opl].x = sps[pi].x, ops[opl++].y = sps[pi].y;
361 #if defined(DEBUG) && DEBUG >= 1
362 fprintf(stderr, "forced straight line: %f %f\n", a, b);
363 #endif
364 return 1;
365 }
366 break;
367 }
368 if (a > .01)
369 a /= 2, b /= 2;
370 else
371 a = b = 0;
372 }
373 #if defined(DEBUG) && DEBUG >= 1
374 fprintf(stderr, "failure\n");
375 #endif
376 return 0;
377 }
378
splineisinside(Pedge_t * edges,int edgen,Ppoint_t * sps)379 static int splineisinside(Pedge_t * edges, int edgen, Ppoint_t * sps)
380 {
381 double roots[4];
382 int rooti, rootn;
383 int ei;
384 Ppoint_t lps[2], ip;
385 double t, ta, tb, tc, td;
386
387 for (ei = 0; ei < edgen; ei++) {
388 lps[0] = edges[ei].a, lps[1] = edges[ei].b;
389 /* if ((rootn = splineintersectsline (sps, lps, roots)) == 4)
390 return 1; */
391 if ((rootn = splineintersectsline(sps, lps, roots)) == 4)
392 continue;
393 for (rooti = 0; rooti < rootn; rooti++) {
394 if (roots[rooti] < EPSILON2 || roots[rooti] > 1 - EPSILON2)
395 continue;
396 t = roots[rooti];
397 td = t * t * t;
398 tc = 3 * t * t * (1 - t);
399 tb = 3 * t * (1 - t) * (1 - t);
400 ta = (1 - t) * (1 - t) * (1 - t);
401 ip.x = ta * sps[0].x + tb * sps[1].x +
402 tc * sps[2].x + td * sps[3].x;
403 ip.y = ta * sps[0].y + tb * sps[1].y +
404 tc * sps[2].y + td * sps[3].y;
405 if (DISTSQ(ip, lps[0]) < EPSILON1 ||
406 DISTSQ(ip, lps[1]) < EPSILON1)
407 continue;
408 return 0;
409 }
410 }
411 return 1;
412 }
413
splineintersectsline(Ppoint_t * sps,Ppoint_t * lps,double * roots)414 static int splineintersectsline(Ppoint_t * sps, Ppoint_t * lps,
415 double *roots)
416 {
417 double scoeff[4], xcoeff[2], ycoeff[2];
418 double xroots[3], yroots[3], tv, sv, rat;
419 int rootn, xrootn, yrootn, i, j;
420
421 xcoeff[0] = lps[0].x;
422 xcoeff[1] = lps[1].x - lps[0].x;
423 ycoeff[0] = lps[0].y;
424 ycoeff[1] = lps[1].y - lps[0].y;
425 rootn = 0;
426 if (xcoeff[1] == 0) {
427 if (ycoeff[1] == 0) {
428 points2coeff(sps[0].x, sps[1].x, sps[2].x, sps[3].x, scoeff);
429 scoeff[0] -= xcoeff[0];
430 xrootn = solve3(scoeff, xroots);
431 points2coeff(sps[0].y, sps[1].y, sps[2].y, sps[3].y, scoeff);
432 scoeff[0] -= ycoeff[0];
433 yrootn = solve3(scoeff, yroots);
434 if (xrootn == 4)
435 if (yrootn == 4)
436 return 4;
437 else
438 for (j = 0; j < yrootn; j++)
439 addroot(yroots[j], roots, &rootn);
440 else if (yrootn == 4)
441 for (i = 0; i < xrootn; i++)
442 addroot(xroots[i], roots, &rootn);
443 else
444 for (i = 0; i < xrootn; i++)
445 for (j = 0; j < yrootn; j++)
446 if (xroots[i] == yroots[j])
447 addroot(xroots[i], roots, &rootn);
448 return rootn;
449 } else {
450 points2coeff(sps[0].x, sps[1].x, sps[2].x, sps[3].x, scoeff);
451 scoeff[0] -= xcoeff[0];
452 xrootn = solve3(scoeff, xroots);
453 if (xrootn == 4)
454 return 4;
455 for (i = 0; i < xrootn; i++) {
456 tv = xroots[i];
457 if (tv >= 0 && tv <= 1) {
458 points2coeff(sps[0].y, sps[1].y, sps[2].y, sps[3].y,
459 scoeff);
460 sv = scoeff[0] + tv * (scoeff[1] + tv *
461 (scoeff[2] + tv * scoeff[3]));
462 sv = (sv - ycoeff[0]) / ycoeff[1];
463 if ((0 <= sv) && (sv <= 1))
464 addroot(tv, roots, &rootn);
465 }
466 }
467 return rootn;
468 }
469 } else {
470 rat = ycoeff[1] / xcoeff[1];
471 points2coeff(sps[0].y - rat * sps[0].x, sps[1].y - rat * sps[1].x,
472 sps[2].y - rat * sps[2].x, sps[3].y - rat * sps[3].x,
473 scoeff);
474 scoeff[0] += rat * xcoeff[0] - ycoeff[0];
475 xrootn = solve3(scoeff, xroots);
476 if (xrootn == 4)
477 return 4;
478 for (i = 0; i < xrootn; i++) {
479 tv = xroots[i];
480 if (tv >= 0 && tv <= 1) {
481 points2coeff(sps[0].x, sps[1].x, sps[2].x, sps[3].x,
482 scoeff);
483 sv = scoeff[0] + tv * (scoeff[1] +
484 tv * (scoeff[2] + tv * scoeff[3]));
485 sv = (sv - xcoeff[0]) / xcoeff[1];
486 if ((0 <= sv) && (sv <= 1))
487 addroot(tv, roots, &rootn);
488 }
489 }
490 return rootn;
491 }
492 }
493
points2coeff(double v0,double v1,double v2,double v3,double * coeff)494 static void points2coeff(double v0, double v1, double v2, double v3,
495 double *coeff)
496 {
497 coeff[3] = v3 + 3 * v1 - (v0 + 3 * v2);
498 coeff[2] = 3 * v0 + 3 * v2 - 6 * v1;
499 coeff[1] = 3 * (v1 - v0);
500 coeff[0] = v0;
501 }
502
addroot(double root,double * roots,int * rootnp)503 static void addroot(double root, double *roots, int *rootnp)
504 {
505 if (root >= 0 && root <= 1)
506 roots[*rootnp] = root, (*rootnp)++;
507 }
508
normv(Pvector_t v)509 static Pvector_t normv(Pvector_t v)
510 {
511 double d;
512
513 d = v.x * v.x + v.y * v.y;
514 if (d > 1e-6) {
515 d = sqrt(d);
516 v.x /= d, v.y /= d;
517 }
518 return v;
519 }
520
growops(int newopn)521 static void growops(int newopn)
522 {
523 if (newopn <= opn)
524 return;
525 if (!ops) {
526 if (!(ops = (Ppoint_t *) malloc(POINTSIZE * newopn))) {
527 prerror("cannot malloc ops");
528 longjmp(jbuf,1);
529 }
530 } else {
531 if (!(ops = (Ppoint_t *) realloc((void *) ops,
532 POINTSIZE * newopn))) {
533 prerror("cannot realloc ops");
534 longjmp(jbuf,1);
535 }
536 }
537 opn = newopn;
538 }
539
add(Ppoint_t p1,Ppoint_t p2)540 static Ppoint_t add(Ppoint_t p1, Ppoint_t p2)
541 {
542 p1.x += p2.x, p1.y += p2.y;
543 return p1;
544 }
545
sub(Ppoint_t p1,Ppoint_t p2)546 static Ppoint_t sub(Ppoint_t p1, Ppoint_t p2)
547 {
548 p1.x -= p2.x, p1.y -= p2.y;
549 return p1;
550 }
551
dist(Ppoint_t p1,Ppoint_t p2)552 static double dist(Ppoint_t p1, Ppoint_t p2)
553 {
554 double dx, dy;
555
556 dx = p2.x - p1.x, dy = p2.y - p1.y;
557 return sqrt(dx * dx + dy * dy);
558 }
559
scale(Ppoint_t p,double c)560 static Ppoint_t scale(Ppoint_t p, double c)
561 {
562 p.x *= c, p.y *= c;
563 return p;
564 }
565
dot(Ppoint_t p1,Ppoint_t p2)566 static double dot(Ppoint_t p1, Ppoint_t p2)
567 {
568 return p1.x * p2.x + p1.y * p2.y;
569 }
570
B0(double t)571 static double B0(double t)
572 {
573 double tmp = 1.0 - t;
574 return tmp * tmp * tmp;
575 }
576
B1(double t)577 static double B1(double t)
578 {
579 double tmp = 1.0 - t;
580 return 3 * t * tmp * tmp;
581 }
582
B2(double t)583 static double B2(double t)
584 {
585 double tmp = 1.0 - t;
586 return 3 * t * t * tmp;
587 }
588
B3(double t)589 static double B3(double t)
590 {
591 return t * t * t;
592 }
593
B01(double t)594 static double B01(double t)
595 {
596 double tmp = 1.0 - t;
597 return tmp * tmp * (tmp + 3 * t);
598 }
599
B23(double t)600 static double B23(double t)
601 {
602 double tmp = 1.0 - t;
603 return t * t * (3 * tmp + t);
604 }
605
606 #if 0
607 static int cmpp2efunc(const void *v0p, const void *v1p)
608 {
609 p2e_t *p2e0p, *p2e1p;
610 double x0, x1;
611
612 p2e0p = (p2e_t *) v0p, p2e1p = (p2e_t *) v1p;
613 if (p2e0p->pp->y > p2e1p->pp->y)
614 return -1;
615 else if (p2e0p->pp->y < p2e1p->pp->y)
616 return 1;
617 if (p2e0p->pp->x < p2e1p->pp->x)
618 return -1;
619 else if (p2e0p->pp->x > p2e1p->pp->x)
620 return 1;
621 x0 = (p2e0p->pp == &p2e0p->ep->a) ? p2e0p->ep->b.x : p2e0p->ep->a.x;
622 x1 = (p2e1p->pp == &p2e1p->ep->a) ? p2e1p->ep->b.x : p2e1p->ep->a.x;
623 if (x0 < x1)
624 return -1;
625 else if (x0 > x1)
626 return 1;
627 return 0;
628 }
629
630 static void listdelete(Pedge_t * ep)
631 {
632 elist_t *lp;
633
634 for (lp = elist; lp; lp = lp->next) {
635 if (lp->ep != ep)
636 continue;
637 if (lp->prev)
638 lp->prev->next = lp->next;
639 if (lp->next)
640 lp->next->prev = lp->prev;
641 if (elist == lp)
642 elist = lp->next;
643 free(lp);
644 return;
645 }
646 if (!lp) {
647 prerror("cannot find list element to delete");
648 abort();
649 }
650 }
651
652 static void listreplace(Pedge_t * oldep, Pedge_t * newep)
653 {
654 elist_t *lp;
655
656 for (lp = elist; lp; lp = lp->next) {
657 if (lp->ep != oldep)
658 continue;
659 lp->ep = newep;
660 return;
661 }
662 if (!lp) {
663 prerror("cannot find list element to replace");
664 abort();
665 }
666 }
667
668 static void listinsert(Pedge_t * ep, Ppoint_t p)
669 {
670 elist_t *lp, *newlp, *lastlp;
671 double lx;
672
673 if (!(newlp = (elist_t *) malloc(sizeof(elist_t)))) {
674 prerror("cannot malloc newlp");
675 abort();
676 }
677 newlp->ep = ep;
678 newlp->next = newlp->prev = NULL;
679 if (!elist) {
680 elist = newlp;
681 return;
682 }
683 for (lp = elist; lp; lp = lp->next) {
684 lastlp = lp;
685 lx = lp->ep->a.x + (lp->ep->b.x - lp->ep->a.x) * (p.y -
686 lp->ep->a.y) /
687 (lp->ep->b.y - lp->ep->a.y);
688 if (lx <= p.x)
689 continue;
690 if (lp->prev)
691 lp->prev->next = newlp;
692 newlp->prev = lp->prev;
693 newlp->next = lp;
694 lp->prev = newlp;
695 if (elist == lp)
696 elist = newlp;
697 return;
698 }
699 lastlp->next = newlp;
700 newlp->prev = lastlp;
701 if (!elist)
702 elist = newlp;
703 }
704 #endif
705