Graphviz 13.0.0~dev.20250511.0440
Loading...
Searching...
No Matches
trap.h
Go to the documentation of this file.
1
9/*************************************************************************
10 * Copyright (c) 2011 AT&T Intellectual Property
11 * All rights reserved. This program and the accompanying materials
12 * are made available under the terms of the Eclipse Public License v1.0
13 * which accompanies this distribution, and is available at
14 * https://www.eclipse.org/legal/epl-v10.html
15 *
16 * Contributors: Details at https://graphviz.org
17 *************************************************************************/
18
19#pragma once
20
21#include <math.h>
22#include <stdbool.h>
23#include <stddef.h>
24#include <stdint.h>
25#include <util/list.h>
26
27/* Segment attributes */
28
29typedef struct {
30 pointf v0, v1; /* two endpoints */
31 bool is_inserted; /* inserted in trapezoidation yet ? */
32 size_t root0, root1;
33 int next; /* Next logical segment */
34 int prev; /* Previous segment */
35} segment_t;
36
37
38/* Trapezoid attributes */
39
40typedef struct {
41 int lseg, rseg; /* two adjoining segments */
42 pointf hi, lo; /* max/min y-values */
43 size_t u0, u1;
44 size_t d0, d1;
45 size_t sink;
46 size_t usave;
47 int uside;
48 int state;
49} trap_t;
50
56static inline bool is_valid_trap(size_t index) {
57 return index != 0 && index != SIZE_MAX;
58}
59
61DEFINE_LIST(traps, trap_t)
62
63#define ST_VALID 1 /* for trapezium state */
64#define ST_INVALID 2
65
66#define C_EPS 1.0e-7 /* tolerance value: Used for making */
67 /* all decisions about collinearity or */
68 /* left/right of segment. Decrease */
69 /* this value if the input points are */
70 /* spaced very close together */
71
72static inline bool fp_equal(double s, double t) { return fabs(s - t) <= C_EPS; }
73
82static inline int dfp_cmp(double f1, double f2) {
83 double d = f1 - f2;
84 if (d < -C_EPS)
85 return -1;
86 if (d > C_EPS)
87 return 1;
88 return 0;
89}
90
91static inline bool equal_to(pointf v0, pointf v1) {
92 return fp_equal(v0.y, v1.y) && fp_equal(v0.x, v1.x);
93}
94
95static inline bool greater_than(pointf v0, pointf v1) {
96 return v0.y > v1.y + C_EPS ? true
97 : (v0.y < v1.y - C_EPS ? false : v0.x > v1.x);
98}
99
100extern traps_t construct_trapezoids(int, segment_t*, int*);
#define SIZE_MAX
Definition gmlscan.c:347
#define DEFINE_LIST(name, type)
Definition list.h:22
double x
Definition geom.h:29
double y
Definition geom.h:29
size_t root0
Definition trap.h:32
pointf v0
Definition trap.h:30
int prev
Definition trap.h:34
int next
Definition trap.h:33
bool is_inserted
Definition trap.h:31
Definition trap.h:40
size_t sink
pointer to corresponding in Q
Definition trap.h:45
size_t d0
Definition trap.h:44
int state
Definition trap.h:48
size_t usave
I forgot what this means.
Definition trap.h:46
pointf hi
Definition trap.h:42
size_t u0
Definition trap.h:43
int uside
I forgot what this means.
Definition trap.h:47
int lseg
Definition trap.h:41
static bool is_valid_trap(size_t index)
Definition trap.h:56
traps_t construct_trapezoids(int, segment_t *, int *)
Definition trapezoid.c:872
static bool equal_to(pointf v0, pointf v1)
Definition trap.h:91
static bool greater_than(pointf v0, pointf v1)
Definition trap.h:95
#define C_EPS
Definition trap.h:66
static int dfp_cmp(double f1, double f2)
double floating point three-way comparison
Definition trap.h:82
static bool fp_equal(double s, double t)
Definition trap.h:72
Definition grammar.c:93