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#ifndef TRAP_H
15#define TRAP_H
16
17/* Segment attributes */
18
19typedef struct {
20 pointf v0, v1; /* two endpoints */
21 int is_inserted; /* inserted in trapezoidation yet ? */
22 int root0, root1; /* root nodes in Q */
23 int next; /* Next logical segment */
24 int prev; /* Previous segment */
25} segment_t;
26
27
28/* Trapezoid attributes */
29
30typedef struct {
31 int lseg, rseg; /* two adjoining segments */
32 pointf hi, lo; /* max/min y-values */
33 int u0, u1;
34 int d0, d1;
35 int sink; /* pointer to corresponding in Q */
36 int usave, uside; /* I forgot what this means */
37 int state;
38} trap_t;
39
40#define ST_VALID 1 /* for trapezium state */
41#define ST_INVALID 2
42
43#define C_EPS 1.0e-7 /* tolerance value: Used for making */
44 /* all decisions about collinearity or */
45 /* left/right of segment. Decrease */
46 /* this value if the input points are */
47 /* spaced very close together */
48#define FP_EQUAL(s, t) (fabs(s - t) <= C_EPS)
49
50#define _equal_to(v0,v1) \
51 (FP_EQUAL((v0)->y, (v1)->y) && FP_EQUAL((v0)->x, (v1)->x))
52
53#define _greater_than(v0, v1) \
54 (((v0)->y > (v1)->y + C_EPS) ? TRUE : (((v0)->y < (v1)->y - C_EPS) ? FALSE : ((v0)->x > (v1)->x)))
55
56extern int construct_trapezoids(int, segment_t*, int*, int, trap_t*);
57
58#endif
59