50 return (v1.
x - v0.
x) * (v2.
y - v0.
y) - (v1.
y - v0.
y) * (v2.
x - v0.
x);
66static size_t newnode(qnodes_t *qs) {
129 const size_t root = i1;
150 LIST_AT(qs, i5)->segnum = segnum;
174 LIST_AT(tr, t4)->hi.y = DBL_MAX;
175 LIST_AT(tr, t4)->hi.x = DBL_MAX;
176 LIST_AT(tr, t3)->lo.y = -DBL_MAX;
177 LIST_AT(tr, t3)->lo.x = -DBL_MAX;
178 LIST_AT(tr, t1)->rseg = segnum;
179 LIST_AT(tr, t2)->lseg = segnum;
194 LIST_AT(tr, t1)->is_valid =
true;
195 LIST_AT(tr, t2)->is_valid =
true;
196 LIST_AT(tr, t3)->is_valid =
true;
197 LIST_AT(tr, t4)->is_valid =
true;
204 s->is_inserted =
true;
232 area =
cross(
s->v0,
s->v1, *v);
249 area =
cross(
s->v1,
s->v0, *v);
317 traps_t *tr, qnodes_t *qs) {
363 LIST_AT(tr, tnext)->is_valid =
false;
377 size_t t,
size_t tn) {
416 const size_t tmp_u =
LIST_GET(tr, t).u0;
450 size_t tfirst, tlast;
451 size_t tfirstr = 0, tlastr = 0;
462 else is_swapped =
false;
494 const size_t sk =
LIST_GET(tr, tu).sink;
498 LIST_AT(qs, sk)->segnum = segnum;
551 const size_t sk =
LIST_GET(tr, tu).sink;
555 LIST_AT(qs, sk)->segnum = segnum;
587 const size_t sk =
LIST_GET(tr, t).sink;
592 LIST_AT(qs, sk)->segnum = segnum;
603 LIST_AT(tr, tn)->is_valid =
true;
614 const size_t t_sav = t;
615 const size_t tn_sav = tn;
621 fprintf(stderr,
"add_segment: error\n");
638 tmptriseg = seg[segnum].
prev;
640 tmptriseg = seg[segnum].
next;
642 if (tmptriseg > 0 &&
is_left_of(tmptriseg, seg, &
s.v0))
688 tmptriseg = seg[segnum].
prev;
690 tmptriseg = seg[segnum].
next;
692 if (tmptriseg > 0 &&
is_left_of(tmptriseg, seg, &
s.v0))
748 yt = (y0 -
s.v0.y)/(
s.v1.y -
s.v0.y);
749 tmppt.
x =
s.v0.x + yt * (
s.v1.x -
s.v0.x);
814 LIST_AT(tr, t_sav)->rseg = segnum;
815 LIST_AT(tr, tn_sav)->lseg = segnum;
823 const size_t tfirstl = tfirst;
824 const size_t tlastl = tlast;
839 if (
s->is_inserted)
return;
852 for (
double v = n; v >= 1; i++)
861 for (
int i = 0; i < h; i++)
864 return (
int)ceil(n / v);
886 for (i = 1; i <= nseg; i++)
887 seg[i].root0 = seg[i].root1 = root;
890 for (h = 1; h <= logstar; h++) {
891 for (i =
math_N(nseg, h -1) + 1; i <=
math_N(nseg, h); i++)
895 for (i = 1; i <= nseg; i++)
899 for (i =
math_N(nseg, logstar) + 1; i <= nseg; i++)
Memory allocation wrappers that exit on failure.
static Agnode_t * newnode(Agraph_t *g, IDTYPE id, uint64_t seq)
geometric types and macros (e.g. points and boxes)
Arithmetic helper functions.
type-generic dynamically expanding list
#define LIST_AT(list, index)
#define LIST_APPEND(list, item)
#define LIST_SET(list, index, item)
#define LIST_GET(list, index)
size_t parent
doubly linked DAG
trapezoid elements and utilities for partition.c
static bool is_valid_trap(size_t index)
static bool equal_to(pointf v0, pointf v1)
static bool greater_than(pointf v0, pointf v1)
static bool fp_equal(double s, double t)
static double cross(pointf v0, pointf v1, pointf v2)
static bool less_than(pointf v0, pointf v1)
static size_t locate_endpoint(pointf *v, pointf *vo, size_t r, segment_t *seg, qnodes_t *qs)
static pointf max_(pointf v0, pointf v1)
return the maximum of the two points
static int math_logstar_n(int n)
static int math_N(int n, int h)
static void update_trapezoid(segment_t *s, segment_t *seg, traps_t *tr, size_t t, size_t tn)
static bool greater_than_equal_to(pointf v0, pointf v1)
static void merge_trapezoids(int segnum, size_t tfirst, size_t tlast, int side, traps_t *tr, qnodes_t *qs)
static void find_new_roots(int segnum, segment_t *seg, traps_t *tr, qnodes_t *qs)
traps_t construct_trapezoids(int nseg, segment_t *seg, int *permute)
static pointf min_(pointf v0, pointf v1)
return the minimum of the two points
static size_t init_query_structure(int segnum, segment_t *seg, traps_t *tr, qnodes_t *qs)
static bool inserted(int segnum, segment_t *seg, int whichpt)
static bool is_left_of(int segnum, segment_t *seg, pointf *v)
static void add_segment(int segnum, segment_t *seg, traps_t *tr, qnodes_t *qs)
static size_t newtrap(traps_t *tr)
graphs, nodes and edges info: Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t