static void merge edge r_cw_l point edge l_ccw_r point edge l_tangent

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
static void merge(edge *r_cw_l, point *s, edge *l_ccw_r, point *u, edge **l_tangent)
{
edge *base, *l_cand, *r_cand;
point *org_base, *dest_base;
real u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b;
real u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b;
real c_p_l_cand, c_p_r_cand;
real d_p_l_cand, d_p_r_cand;
boolean above_l_cand, above_r_cand, above_next, above_prev;
point *dest_l_cand, *dest_r_cand;
real cot_l_cand, cot_r_cand;
edge *l_lower, *r_lower;
point *org_r_lower, *org_l_lower;
/* Create first cross edge by joining lower common tangent */
lower_tangent(r_cw_l, s, l_ccw_r, u, &l_lower, &org_l_lower, &r_lower, &org_r_lower);
base = join(l_lower, org_l_lower, r_lower, org_r_lower, right);
org_base = org_l_lower;
dest_base = org_r_lower;
/* Need to return lower tangent. */
*l_tangent = base;
/* Main merge loop */
do
{
/* Initialise l_cand and r_cand */
l_cand = Next(base, org_base);
r_cand = Prev(base, dest_base);
dest_l_cand = Other_point(l_cand, org_base);
dest_r_cand = Other_point(r_cand, dest_base);
/* Vectors for above and "in_circle" tests. */
Vector(dest_l_cand, org_base, u_l_c_o_b, v_l_c_o_b);
Vector(dest_l_cand, dest_base, u_l_c_d_b, v_l_c_d_b);
Vector(dest_r_cand, org_base, u_r_c_o_b, v_r_c_o_b);
Vector(dest_r_cand, dest_base, u_r_c_d_b, v_r_c_d_b);
/* Above tests. */
c_p_l_cand = Cross_product_2v(u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b);
c_p_r_cand = Cross_product_2v(u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b);
above_l_cand = c_p_l_cand > 0.0;
above_r_cand = c_p_r_cand > 0.0;
if (!above_l_cand && !above_r_cand)
break; /* Finished. */
/* Advance l_cand ccw, deleting the old l_cand edge, until the
"in_circle" test fails. */
if (above_l_cand)
{
real u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b;
real c_p_next, d_p_next, cot_next;
edge *next;
point *dest_next;
d_p_l_cand = Dot_product_2v(u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b);
cot_l_cand = d_p_l_cand / c_p_l_cand;
do
{
next = Next(l_cand, org_base);
dest_next = Other_point(next, org_base);
Vector(dest_next, org_base, u_n_o_b, v_n_o_b);
Vector(dest_next, dest_base, u_n_d_b, v_n_d_b);
c_p_next = Cross_product_2v(u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b);
above_next = c_p_next > 0.0;
if (!above_next)
break; /* Finished. */
d_p_next = Dot_product_2v(u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b);
cot_next = d_p_next / c_p_next;
if (cot_next > cot_l_cand)
break; /* Finished. */
delete_edge(l_cand);
l_cand = next;
cot_l_cand = cot_next;
} while (TRUE);
}
/* Now do the symmetrical for r_cand */
if (above_r_cand)
{
real u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b;
real c_p_prev, d_p_prev, cot_prev;
edge *prev;
point *dest_prev;
d_p_r_cand = Dot_product_2v(u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b);
cot_r_cand = d_p_r_cand / c_p_r_cand;
do
{
prev = Prev(r_cand, dest_base);
dest_prev = Other_point(prev, dest_base);
Vector(dest_prev, org_base, u_p_o_b, v_p_o_b);
Vector(dest_prev, dest_base, u_p_d_b, v_p_d_b);
c_p_prev = Cross_product_2v(u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b);
above_prev = c_p_prev > 0.0;
if (!above_prev)
break; /* Finished. */
d_p_prev = Dot_product_2v(u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b);
cot_prev = d_p_prev / c_p_prev;
if (cot_prev > cot_r_cand)
break; /* Finished. */
delete_edge(r_cand);
r_cand = prev;
cot_r_cand = cot_prev;
} while (TRUE);
}
/*
* Now add a cross edge from base to either l_cand or r_cand.
* If both are valid choose on the basis of the in_circle test .
* Advance base and whichever candidate was chosen.
*/
dest_l_cand = Other_point(l_cand, org_base);
dest_r_cand = Other_point(r_cand, dest_base);
if (!above_l_cand || (above_l_cand && above_r_cand && cot_r_cand < cot_l_cand))
{
/* Connect to the right */
base = join(base, org_base, r_cand, dest_r_cand, right);
dest_base = dest_r_cand;
} else {
/* Connect to the left */
base = join(l_cand, dest_l_cand, base, dest_base, right);
org_base = dest_l_cand;
}
} while (TRUE);
}