50#define CROSS(v0, v1, v2) (((v1).x - (v0).x)*((v2).y - (v0).y) - \
51 ((v1).y - (v0).y)*((v2).x - (v0).x))
67 qnodes_append(qs, (
qnode_t){0});
68 return qnodes_size(qs) - 1;
128 qnodes_at(qs, i1)->nodetype =
T_Y;
129 qnodes_at(qs, i1)->yval =
max_(
s->v0,
s->v1);
130 const size_t root = i1;
133 qnodes_at(qs, i1)->right = i2;
134 qnodes_at(qs, i2)->nodetype =
T_SINK;
135 qnodes_at(qs, i2)->parent = i1;
138 qnodes_at(qs, i1)->left = i3;
139 qnodes_at(qs, i3)->nodetype =
T_Y;
140 qnodes_at(qs, i3)->yval =
min_(
s->v0,
s->v1);
141 qnodes_at(qs, i3)->parent = i1;
144 qnodes_at(qs, i3)->left = i4;
145 qnodes_at(qs, i4)->nodetype =
T_SINK;
146 qnodes_at(qs, i4)->parent = i3;
149 qnodes_at(qs, i3)->right = i5;
150 qnodes_at(qs, i5)->nodetype =
T_X;
151 qnodes_at(qs, i5)->segnum = segnum;
152 qnodes_at(qs, i5)->parent = i3;
155 qnodes_at(qs, i5)->left = i6;
156 qnodes_at(qs, i6)->nodetype =
T_SINK;
157 qnodes_at(qs, i6)->parent = i5;
160 qnodes_at(qs, i5)->right = i7;
161 qnodes_at(qs, i7)->nodetype =
T_SINK;
162 qnodes_at(qs, i7)->parent = i5;
169 tr->
data[t1].
hi = qnodes_get(qs, i1).yval;
170 tr->
data[t2].
hi = qnodes_get(qs, i1).yval;
171 tr->
data[t4].
lo = qnodes_get(qs, i1).yval;
172 tr->
data[t1].
lo = qnodes_get(qs, i3).yval;
173 tr->
data[t2].
lo = qnodes_get(qs, i3).yval;
174 tr->
data[t3].
hi = qnodes_get(qs, i3).yval;
200 qnodes_at(qs, i2)->trnum = t4;
201 qnodes_at(qs, i4)->trnum = t3;
202 qnodes_at(qs, i6)->trnum = t1;
203 qnodes_at(qs, i7)->trnum = t2;
205 s->is_inserted =
true;
233 area =
CROSS(
s->v0,
s->v1, *v);
250 area =
CROSS(
s->v1,
s->v0, (*v));
272 qnode_t *rptr = qnodes_at(qs, r);
339 const size_t ptnext = qnodes_get(qs, tr->
data[tnext].
sink).parent;
341 if (qnodes_get(qs, ptnext).
left == tr->
data[tnext].
sink)
342 qnodes_at(qs, ptnext)->left = tr->
data[t].
sink;
344 qnodes_at(qs, ptnext)->right = tr->
data[t].
sink;
378 size_t t,
size_t tn) {
417 const size_t tmp_u = tr->
data[t].
u0;
451 size_t tfirst, tlast;
452 size_t tfirstr = 0, tlastr = 0;
463 else is_swapped =
false;
495 const size_t sk = tr->
data[tu].
sink;
497 qnodes_at(qs, sk)->nodetype =
T_Y;
498 qnodes_at(qs, sk)->yval =
s.v0;
499 qnodes_at(qs, sk)->segnum = segnum;
500 qnodes_at(qs, sk)->left = i2;
501 qnodes_at(qs, sk)->right = i1;
503 qnodes_at(qs, i1)->nodetype =
T_SINK;
504 qnodes_at(qs, i1)->trnum = tu;
505 qnodes_at(qs, i1)->parent = sk;
507 qnodes_at(qs, i2)->nodetype =
T_SINK;
508 qnodes_at(qs, i2)->trnum = tl;
509 qnodes_at(qs, i2)->parent = sk;
552 const size_t sk = tr->
data[tu].
sink;
554 qnodes_at(qs, sk)->nodetype =
T_Y;
555 qnodes_at(qs, sk)->yval =
s.v1;
556 qnodes_at(qs, sk)->segnum = segnum;
557 qnodes_at(qs, sk)->left = i2;
558 qnodes_at(qs, sk)->right = i1;
560 qnodes_at(qs, i1)->nodetype =
T_SINK;
561 qnodes_at(qs, i1)->trnum = tu;
562 qnodes_at(qs, i1)->parent = sk;
564 qnodes_at(qs, i2)->nodetype =
T_SINK;
565 qnodes_at(qs, i2)->trnum = tl;
566 qnodes_at(qs, i2)->parent = sk;
591 qnodes_at(qs, sk)->nodetype =
T_X;
592 qnodes_at(qs, sk)->segnum = segnum;
593 qnodes_at(qs, sk)->left = i1;
594 qnodes_at(qs, sk)->right = i2;
596 qnodes_at(qs, i1)->nodetype =
T_SINK;
597 qnodes_at(qs, i1)->trnum = t;
598 qnodes_at(qs, i1)->parent = sk;
600 qnodes_at(qs, i2)->nodetype =
T_SINK;
602 qnodes_at(qs, i2)->trnum = tn;
604 qnodes_at(qs, i2)->parent = sk;
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))
689 tmptriseg = seg[segnum].
prev;
691 tmptriseg = seg[segnum].
next;
693 if (tmptriseg > 0 &&
is_left_of(tmptriseg, seg, &
s.v0))
750 yt = (y0 -
s.v0.y)/(
s.v1.y -
s.v0.y);
751 tmppt.
x =
s.v0.x + yt * (
s.v1.x -
s.v0.x);
825 const size_t tfirstl = tfirst;
826 const size_t tlastl = tlast;
841 if (
s->is_inserted)
return;
856 for (i = 0, v = (
double) n; v >= 1; i++)
867 for (i = 0, v = (
double) n; i < h; i++)
870 return (
int)ceil(1.0 * n / v);
882 qnodes_append(&qs, (
qnode_t){0});
893 for (i = 1; i <= nseg; i++)
894 seg[i].root0 = seg[i].root1 = root;
897 for (h = 1; h <= logstar; h++) {
898 for (i =
math_N(nseg, h -1) + 1; i <=
math_N(nseg, h); i++)
902 for (i = 1; i <= nseg; i++)
906 for (i =
math_N(nseg, logstar) + 1; i <= nseg; i++)
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
static void * gv_calloc(size_t nmemb, size_t size)
geometric types and macros (e.g. points and boxes)
Arithmetic helper functions.
#define DEFINE_LIST(name, type)
size_t parent
doubly linked DAG
size_t sink
pointer to corresponding in Q
size_t usave
I forgot what this means.
int uside
I forgot what this means.
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 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)
#define CROSS(v0, v1, v2)
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 newnode(qnodes_t *qs)
an array of qnodes
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