source: node_modules/robust-predicates/esm/incircle.js@ e4c61dd

Last change on this file since e4c61dd was e4c61dd, checked in by istevanoska <ilinastevanoska@…>, 6 months ago

Prototype 1.1
  • Property mode set to 100644
File size: 26.1 KB
Line 
1import {epsilon, splitter, resulterrbound, estimate, vec, sum, sum_three, scale} from './util.js';
2
3const iccerrboundA = (10 + 96 * epsilon) * epsilon;
4const iccerrboundB = (4 + 48 * epsilon) * epsilon;
5const iccerrboundC = (44 + 576 * epsilon) * epsilon * epsilon;
6
7const bc = vec(4);
8const ca = vec(4);
9const ab = vec(4);
10const aa = vec(4);
11const bb = vec(4);
12const cc = vec(4);
13const u = vec(4);
14const v = vec(4);
15const axtbc = vec(8);
16const aytbc = vec(8);
17const bxtca = vec(8);
18const bytca = vec(8);
19const cxtab = vec(8);
20const cytab = vec(8);
21const abt = vec(8);
22const bct = vec(8);
23const cat = vec(8);
24const abtt = vec(4);
25const bctt = vec(4);
26const catt = vec(4);
27
28const _8 = vec(8);
29const _16 = vec(16);
30const _16b = vec(16);
31const _16c = vec(16);
32const _32 = vec(32);
33const _32b = vec(32);
34const _48 = vec(48);
35const _64 = vec(64);
36
37let fin = vec(1152);
38let fin2 = vec(1152);
39
40function finadd(finlen, a, alen) {
41 finlen = sum(finlen, fin, a, alen, fin2);
42 const tmp = fin; fin = fin2; fin2 = tmp;
43 return finlen;
44}
45
46function incircleadapt(ax, ay, bx, by, cx, cy, dx, dy, permanent) {
47 let finlen;
48 let adxtail, bdxtail, cdxtail, adytail, bdytail, cdytail;
49 let axtbclen, aytbclen, bxtcalen, bytcalen, cxtablen, cytablen;
50 let abtlen, bctlen, catlen;
51 let abttlen, bcttlen, cattlen;
52 let n1, n0;
53
54 let bvirt, c, ahi, alo, bhi, blo, _i, _j, _0, s1, s0, t1, t0, u3;
55
56 const adx = ax - dx;
57 const bdx = bx - dx;
58 const cdx = cx - dx;
59 const ady = ay - dy;
60 const bdy = by - dy;
61 const cdy = cy - dy;
62
63 s1 = bdx * cdy;
64 c = splitter * bdx;
65 ahi = c - (c - bdx);
66 alo = bdx - ahi;
67 c = splitter * cdy;
68 bhi = c - (c - cdy);
69 blo = cdy - bhi;
70 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
71 t1 = cdx * bdy;
72 c = splitter * cdx;
73 ahi = c - (c - cdx);
74 alo = cdx - ahi;
75 c = splitter * bdy;
76 bhi = c - (c - bdy);
77 blo = bdy - bhi;
78 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
79 _i = s0 - t0;
80 bvirt = s0 - _i;
81 bc[0] = s0 - (_i + bvirt) + (bvirt - t0);
82 _j = s1 + _i;
83 bvirt = _j - s1;
84 _0 = s1 - (_j - bvirt) + (_i - bvirt);
85 _i = _0 - t1;
86 bvirt = _0 - _i;
87 bc[1] = _0 - (_i + bvirt) + (bvirt - t1);
88 u3 = _j + _i;
89 bvirt = u3 - _j;
90 bc[2] = _j - (u3 - bvirt) + (_i - bvirt);
91 bc[3] = u3;
92 s1 = cdx * ady;
93 c = splitter * cdx;
94 ahi = c - (c - cdx);
95 alo = cdx - ahi;
96 c = splitter * ady;
97 bhi = c - (c - ady);
98 blo = ady - bhi;
99 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
100 t1 = adx * cdy;
101 c = splitter * adx;
102 ahi = c - (c - adx);
103 alo = adx - ahi;
104 c = splitter * cdy;
105 bhi = c - (c - cdy);
106 blo = cdy - bhi;
107 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
108 _i = s0 - t0;
109 bvirt = s0 - _i;
110 ca[0] = s0 - (_i + bvirt) + (bvirt - t0);
111 _j = s1 + _i;
112 bvirt = _j - s1;
113 _0 = s1 - (_j - bvirt) + (_i - bvirt);
114 _i = _0 - t1;
115 bvirt = _0 - _i;
116 ca[1] = _0 - (_i + bvirt) + (bvirt - t1);
117 u3 = _j + _i;
118 bvirt = u3 - _j;
119 ca[2] = _j - (u3 - bvirt) + (_i - bvirt);
120 ca[3] = u3;
121 s1 = adx * bdy;
122 c = splitter * adx;
123 ahi = c - (c - adx);
124 alo = adx - ahi;
125 c = splitter * bdy;
126 bhi = c - (c - bdy);
127 blo = bdy - bhi;
128 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
129 t1 = bdx * ady;
130 c = splitter * bdx;
131 ahi = c - (c - bdx);
132 alo = bdx - ahi;
133 c = splitter * ady;
134 bhi = c - (c - ady);
135 blo = ady - bhi;
136 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
137 _i = s0 - t0;
138 bvirt = s0 - _i;
139 ab[0] = s0 - (_i + bvirt) + (bvirt - t0);
140 _j = s1 + _i;
141 bvirt = _j - s1;
142 _0 = s1 - (_j - bvirt) + (_i - bvirt);
143 _i = _0 - t1;
144 bvirt = _0 - _i;
145 ab[1] = _0 - (_i + bvirt) + (bvirt - t1);
146 u3 = _j + _i;
147 bvirt = u3 - _j;
148 ab[2] = _j - (u3 - bvirt) + (_i - bvirt);
149 ab[3] = u3;
150
151 finlen = sum(
152 sum(
153 sum(
154 scale(scale(4, bc, adx, _8), _8, adx, _16), _16,
155 scale(scale(4, bc, ady, _8), _8, ady, _16b), _16b, _32), _32,
156 sum(
157 scale(scale(4, ca, bdx, _8), _8, bdx, _16), _16,
158 scale(scale(4, ca, bdy, _8), _8, bdy, _16b), _16b, _32b), _32b, _64), _64,
159 sum(
160 scale(scale(4, ab, cdx, _8), _8, cdx, _16), _16,
161 scale(scale(4, ab, cdy, _8), _8, cdy, _16b), _16b, _32), _32, fin);
162
163 let det = estimate(finlen, fin);
164 let errbound = iccerrboundB * permanent;
165 if (det >= errbound || -det >= errbound) {
166 return det;
167 }
168
169 bvirt = ax - adx;
170 adxtail = ax - (adx + bvirt) + (bvirt - dx);
171 bvirt = ay - ady;
172 adytail = ay - (ady + bvirt) + (bvirt - dy);
173 bvirt = bx - bdx;
174 bdxtail = bx - (bdx + bvirt) + (bvirt - dx);
175 bvirt = by - bdy;
176 bdytail = by - (bdy + bvirt) + (bvirt - dy);
177 bvirt = cx - cdx;
178 cdxtail = cx - (cdx + bvirt) + (bvirt - dx);
179 bvirt = cy - cdy;
180 cdytail = cy - (cdy + bvirt) + (bvirt - dy);
181 if (adxtail === 0 && bdxtail === 0 && cdxtail === 0 && adytail === 0 && bdytail === 0 && cdytail === 0) {
182 return det;
183 }
184
185 errbound = iccerrboundC * permanent + resulterrbound * Math.abs(det);
186 det += ((adx * adx + ady * ady) * ((bdx * cdytail + cdy * bdxtail) - (bdy * cdxtail + cdx * bdytail)) +
187 2 * (adx * adxtail + ady * adytail) * (bdx * cdy - bdy * cdx)) +
188 ((bdx * bdx + bdy * bdy) * ((cdx * adytail + ady * cdxtail) - (cdy * adxtail + adx * cdytail)) +
189 2 * (bdx * bdxtail + bdy * bdytail) * (cdx * ady - cdy * adx)) +
190 ((cdx * cdx + cdy * cdy) * ((adx * bdytail + bdy * adxtail) - (ady * bdxtail + bdx * adytail)) +
191 2 * (cdx * cdxtail + cdy * cdytail) * (adx * bdy - ady * bdx));
192
193 if (det >= errbound || -det >= errbound) {
194 return det;
195 }
196
197 if (bdxtail !== 0 || bdytail !== 0 || cdxtail !== 0 || cdytail !== 0) {
198 s1 = adx * adx;
199 c = splitter * adx;
200 ahi = c - (c - adx);
201 alo = adx - ahi;
202 s0 = alo * alo - (s1 - ahi * ahi - (ahi + ahi) * alo);
203 t1 = ady * ady;
204 c = splitter * ady;
205 ahi = c - (c - ady);
206 alo = ady - ahi;
207 t0 = alo * alo - (t1 - ahi * ahi - (ahi + ahi) * alo);
208 _i = s0 + t0;
209 bvirt = _i - s0;
210 aa[0] = s0 - (_i - bvirt) + (t0 - bvirt);
211 _j = s1 + _i;
212 bvirt = _j - s1;
213 _0 = s1 - (_j - bvirt) + (_i - bvirt);
214 _i = _0 + t1;
215 bvirt = _i - _0;
216 aa[1] = _0 - (_i - bvirt) + (t1 - bvirt);
217 u3 = _j + _i;
218 bvirt = u3 - _j;
219 aa[2] = _j - (u3 - bvirt) + (_i - bvirt);
220 aa[3] = u3;
221 }
222 if (cdxtail !== 0 || cdytail !== 0 || adxtail !== 0 || adytail !== 0) {
223 s1 = bdx * bdx;
224 c = splitter * bdx;
225 ahi = c - (c - bdx);
226 alo = bdx - ahi;
227 s0 = alo * alo - (s1 - ahi * ahi - (ahi + ahi) * alo);
228 t1 = bdy * bdy;
229 c = splitter * bdy;
230 ahi = c - (c - bdy);
231 alo = bdy - ahi;
232 t0 = alo * alo - (t1 - ahi * ahi - (ahi + ahi) * alo);
233 _i = s0 + t0;
234 bvirt = _i - s0;
235 bb[0] = s0 - (_i - bvirt) + (t0 - bvirt);
236 _j = s1 + _i;
237 bvirt = _j - s1;
238 _0 = s1 - (_j - bvirt) + (_i - bvirt);
239 _i = _0 + t1;
240 bvirt = _i - _0;
241 bb[1] = _0 - (_i - bvirt) + (t1 - bvirt);
242 u3 = _j + _i;
243 bvirt = u3 - _j;
244 bb[2] = _j - (u3 - bvirt) + (_i - bvirt);
245 bb[3] = u3;
246 }
247 if (adxtail !== 0 || adytail !== 0 || bdxtail !== 0 || bdytail !== 0) {
248 s1 = cdx * cdx;
249 c = splitter * cdx;
250 ahi = c - (c - cdx);
251 alo = cdx - ahi;
252 s0 = alo * alo - (s1 - ahi * ahi - (ahi + ahi) * alo);
253 t1 = cdy * cdy;
254 c = splitter * cdy;
255 ahi = c - (c - cdy);
256 alo = cdy - ahi;
257 t0 = alo * alo - (t1 - ahi * ahi - (ahi + ahi) * alo);
258 _i = s0 + t0;
259 bvirt = _i - s0;
260 cc[0] = s0 - (_i - bvirt) + (t0 - bvirt);
261 _j = s1 + _i;
262 bvirt = _j - s1;
263 _0 = s1 - (_j - bvirt) + (_i - bvirt);
264 _i = _0 + t1;
265 bvirt = _i - _0;
266 cc[1] = _0 - (_i - bvirt) + (t1 - bvirt);
267 u3 = _j + _i;
268 bvirt = u3 - _j;
269 cc[2] = _j - (u3 - bvirt) + (_i - bvirt);
270 cc[3] = u3;
271 }
272
273 if (adxtail !== 0) {
274 axtbclen = scale(4, bc, adxtail, axtbc);
275 finlen = finadd(finlen, sum_three(
276 scale(axtbclen, axtbc, 2 * adx, _16), _16,
277 scale(scale(4, cc, adxtail, _8), _8, bdy, _16b), _16b,
278 scale(scale(4, bb, adxtail, _8), _8, -cdy, _16c), _16c, _32, _48), _48);
279 }
280 if (adytail !== 0) {
281 aytbclen = scale(4, bc, adytail, aytbc);
282 finlen = finadd(finlen, sum_three(
283 scale(aytbclen, aytbc, 2 * ady, _16), _16,
284 scale(scale(4, bb, adytail, _8), _8, cdx, _16b), _16b,
285 scale(scale(4, cc, adytail, _8), _8, -bdx, _16c), _16c, _32, _48), _48);
286 }
287 if (bdxtail !== 0) {
288 bxtcalen = scale(4, ca, bdxtail, bxtca);
289 finlen = finadd(finlen, sum_three(
290 scale(bxtcalen, bxtca, 2 * bdx, _16), _16,
291 scale(scale(4, aa, bdxtail, _8), _8, cdy, _16b), _16b,
292 scale(scale(4, cc, bdxtail, _8), _8, -ady, _16c), _16c, _32, _48), _48);
293 }
294 if (bdytail !== 0) {
295 bytcalen = scale(4, ca, bdytail, bytca);
296 finlen = finadd(finlen, sum_three(
297 scale(bytcalen, bytca, 2 * bdy, _16), _16,
298 scale(scale(4, cc, bdytail, _8), _8, adx, _16b), _16b,
299 scale(scale(4, aa, bdytail, _8), _8, -cdx, _16c), _16c, _32, _48), _48);
300 }
301 if (cdxtail !== 0) {
302 cxtablen = scale(4, ab, cdxtail, cxtab);
303 finlen = finadd(finlen, sum_three(
304 scale(cxtablen, cxtab, 2 * cdx, _16), _16,
305 scale(scale(4, bb, cdxtail, _8), _8, ady, _16b), _16b,
306 scale(scale(4, aa, cdxtail, _8), _8, -bdy, _16c), _16c, _32, _48), _48);
307 }
308 if (cdytail !== 0) {
309 cytablen = scale(4, ab, cdytail, cytab);
310 finlen = finadd(finlen, sum_three(
311 scale(cytablen, cytab, 2 * cdy, _16), _16,
312 scale(scale(4, aa, cdytail, _8), _8, bdx, _16b), _16b,
313 scale(scale(4, bb, cdytail, _8), _8, -adx, _16c), _16c, _32, _48), _48);
314 }
315
316 if (adxtail !== 0 || adytail !== 0) {
317 if (bdxtail !== 0 || bdytail !== 0 || cdxtail !== 0 || cdytail !== 0) {
318 s1 = bdxtail * cdy;
319 c = splitter * bdxtail;
320 ahi = c - (c - bdxtail);
321 alo = bdxtail - ahi;
322 c = splitter * cdy;
323 bhi = c - (c - cdy);
324 blo = cdy - bhi;
325 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
326 t1 = bdx * cdytail;
327 c = splitter * bdx;
328 ahi = c - (c - bdx);
329 alo = bdx - ahi;
330 c = splitter * cdytail;
331 bhi = c - (c - cdytail);
332 blo = cdytail - bhi;
333 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
334 _i = s0 + t0;
335 bvirt = _i - s0;
336 u[0] = s0 - (_i - bvirt) + (t0 - bvirt);
337 _j = s1 + _i;
338 bvirt = _j - s1;
339 _0 = s1 - (_j - bvirt) + (_i - bvirt);
340 _i = _0 + t1;
341 bvirt = _i - _0;
342 u[1] = _0 - (_i - bvirt) + (t1 - bvirt);
343 u3 = _j + _i;
344 bvirt = u3 - _j;
345 u[2] = _j - (u3 - bvirt) + (_i - bvirt);
346 u[3] = u3;
347 s1 = cdxtail * -bdy;
348 c = splitter * cdxtail;
349 ahi = c - (c - cdxtail);
350 alo = cdxtail - ahi;
351 c = splitter * -bdy;
352 bhi = c - (c - -bdy);
353 blo = -bdy - bhi;
354 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
355 t1 = cdx * -bdytail;
356 c = splitter * cdx;
357 ahi = c - (c - cdx);
358 alo = cdx - ahi;
359 c = splitter * -bdytail;
360 bhi = c - (c - -bdytail);
361 blo = -bdytail - bhi;
362 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
363 _i = s0 + t0;
364 bvirt = _i - s0;
365 v[0] = s0 - (_i - bvirt) + (t0 - bvirt);
366 _j = s1 + _i;
367 bvirt = _j - s1;
368 _0 = s1 - (_j - bvirt) + (_i - bvirt);
369 _i = _0 + t1;
370 bvirt = _i - _0;
371 v[1] = _0 - (_i - bvirt) + (t1 - bvirt);
372 u3 = _j + _i;
373 bvirt = u3 - _j;
374 v[2] = _j - (u3 - bvirt) + (_i - bvirt);
375 v[3] = u3;
376 bctlen = sum(4, u, 4, v, bct);
377 s1 = bdxtail * cdytail;
378 c = splitter * bdxtail;
379 ahi = c - (c - bdxtail);
380 alo = bdxtail - ahi;
381 c = splitter * cdytail;
382 bhi = c - (c - cdytail);
383 blo = cdytail - bhi;
384 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
385 t1 = cdxtail * bdytail;
386 c = splitter * cdxtail;
387 ahi = c - (c - cdxtail);
388 alo = cdxtail - ahi;
389 c = splitter * bdytail;
390 bhi = c - (c - bdytail);
391 blo = bdytail - bhi;
392 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
393 _i = s0 - t0;
394 bvirt = s0 - _i;
395 bctt[0] = s0 - (_i + bvirt) + (bvirt - t0);
396 _j = s1 + _i;
397 bvirt = _j - s1;
398 _0 = s1 - (_j - bvirt) + (_i - bvirt);
399 _i = _0 - t1;
400 bvirt = _0 - _i;
401 bctt[1] = _0 - (_i + bvirt) + (bvirt - t1);
402 u3 = _j + _i;
403 bvirt = u3 - _j;
404 bctt[2] = _j - (u3 - bvirt) + (_i - bvirt);
405 bctt[3] = u3;
406 bcttlen = 4;
407 } else {
408 bct[0] = 0;
409 bctlen = 1;
410 bctt[0] = 0;
411 bcttlen = 1;
412 }
413 if (adxtail !== 0) {
414 const len = scale(bctlen, bct, adxtail, _16c);
415 finlen = finadd(finlen, sum(
416 scale(axtbclen, axtbc, adxtail, _16), _16,
417 scale(len, _16c, 2 * adx, _32), _32, _48), _48);
418
419 const len2 = scale(bcttlen, bctt, adxtail, _8);
420 finlen = finadd(finlen, sum_three(
421 scale(len2, _8, 2 * adx, _16), _16,
422 scale(len2, _8, adxtail, _16b), _16b,
423 scale(len, _16c, adxtail, _32), _32, _32b, _64), _64);
424
425 if (bdytail !== 0) {
426 finlen = finadd(finlen, scale(scale(4, cc, adxtail, _8), _8, bdytail, _16), _16);
427 }
428 if (cdytail !== 0) {
429 finlen = finadd(finlen, scale(scale(4, bb, -adxtail, _8), _8, cdytail, _16), _16);
430 }
431 }
432 if (adytail !== 0) {
433 const len = scale(bctlen, bct, adytail, _16c);
434 finlen = finadd(finlen, sum(
435 scale(aytbclen, aytbc, adytail, _16), _16,
436 scale(len, _16c, 2 * ady, _32), _32, _48), _48);
437
438 const len2 = scale(bcttlen, bctt, adytail, _8);
439 finlen = finadd(finlen, sum_three(
440 scale(len2, _8, 2 * ady, _16), _16,
441 scale(len2, _8, adytail, _16b), _16b,
442 scale(len, _16c, adytail, _32), _32, _32b, _64), _64);
443 }
444 }
445 if (bdxtail !== 0 || bdytail !== 0) {
446 if (cdxtail !== 0 || cdytail !== 0 || adxtail !== 0 || adytail !== 0) {
447 s1 = cdxtail * ady;
448 c = splitter * cdxtail;
449 ahi = c - (c - cdxtail);
450 alo = cdxtail - ahi;
451 c = splitter * ady;
452 bhi = c - (c - ady);
453 blo = ady - bhi;
454 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
455 t1 = cdx * adytail;
456 c = splitter * cdx;
457 ahi = c - (c - cdx);
458 alo = cdx - ahi;
459 c = splitter * adytail;
460 bhi = c - (c - adytail);
461 blo = adytail - bhi;
462 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
463 _i = s0 + t0;
464 bvirt = _i - s0;
465 u[0] = s0 - (_i - bvirt) + (t0 - bvirt);
466 _j = s1 + _i;
467 bvirt = _j - s1;
468 _0 = s1 - (_j - bvirt) + (_i - bvirt);
469 _i = _0 + t1;
470 bvirt = _i - _0;
471 u[1] = _0 - (_i - bvirt) + (t1 - bvirt);
472 u3 = _j + _i;
473 bvirt = u3 - _j;
474 u[2] = _j - (u3 - bvirt) + (_i - bvirt);
475 u[3] = u3;
476 n1 = -cdy;
477 n0 = -cdytail;
478 s1 = adxtail * n1;
479 c = splitter * adxtail;
480 ahi = c - (c - adxtail);
481 alo = adxtail - ahi;
482 c = splitter * n1;
483 bhi = c - (c - n1);
484 blo = n1 - bhi;
485 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
486 t1 = adx * n0;
487 c = splitter * adx;
488 ahi = c - (c - adx);
489 alo = adx - ahi;
490 c = splitter * n0;
491 bhi = c - (c - n0);
492 blo = n0 - bhi;
493 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
494 _i = s0 + t0;
495 bvirt = _i - s0;
496 v[0] = s0 - (_i - bvirt) + (t0 - bvirt);
497 _j = s1 + _i;
498 bvirt = _j - s1;
499 _0 = s1 - (_j - bvirt) + (_i - bvirt);
500 _i = _0 + t1;
501 bvirt = _i - _0;
502 v[1] = _0 - (_i - bvirt) + (t1 - bvirt);
503 u3 = _j + _i;
504 bvirt = u3 - _j;
505 v[2] = _j - (u3 - bvirt) + (_i - bvirt);
506 v[3] = u3;
507 catlen = sum(4, u, 4, v, cat);
508 s1 = cdxtail * adytail;
509 c = splitter * cdxtail;
510 ahi = c - (c - cdxtail);
511 alo = cdxtail - ahi;
512 c = splitter * adytail;
513 bhi = c - (c - adytail);
514 blo = adytail - bhi;
515 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
516 t1 = adxtail * cdytail;
517 c = splitter * adxtail;
518 ahi = c - (c - adxtail);
519 alo = adxtail - ahi;
520 c = splitter * cdytail;
521 bhi = c - (c - cdytail);
522 blo = cdytail - bhi;
523 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
524 _i = s0 - t0;
525 bvirt = s0 - _i;
526 catt[0] = s0 - (_i + bvirt) + (bvirt - t0);
527 _j = s1 + _i;
528 bvirt = _j - s1;
529 _0 = s1 - (_j - bvirt) + (_i - bvirt);
530 _i = _0 - t1;
531 bvirt = _0 - _i;
532 catt[1] = _0 - (_i + bvirt) + (bvirt - t1);
533 u3 = _j + _i;
534 bvirt = u3 - _j;
535 catt[2] = _j - (u3 - bvirt) + (_i - bvirt);
536 catt[3] = u3;
537 cattlen = 4;
538 } else {
539 cat[0] = 0;
540 catlen = 1;
541 catt[0] = 0;
542 cattlen = 1;
543 }
544 if (bdxtail !== 0) {
545 const len = scale(catlen, cat, bdxtail, _16c);
546 finlen = finadd(finlen, sum(
547 scale(bxtcalen, bxtca, bdxtail, _16), _16,
548 scale(len, _16c, 2 * bdx, _32), _32, _48), _48);
549
550 const len2 = scale(cattlen, catt, bdxtail, _8);
551 finlen = finadd(finlen, sum_three(
552 scale(len2, _8, 2 * bdx, _16), _16,
553 scale(len2, _8, bdxtail, _16b), _16b,
554 scale(len, _16c, bdxtail, _32), _32, _32b, _64), _64);
555
556 if (cdytail !== 0) {
557 finlen = finadd(finlen, scale(scale(4, aa, bdxtail, _8), _8, cdytail, _16), _16);
558 }
559 if (adytail !== 0) {
560 finlen = finadd(finlen, scale(scale(4, cc, -bdxtail, _8), _8, adytail, _16), _16);
561 }
562 }
563 if (bdytail !== 0) {
564 const len = scale(catlen, cat, bdytail, _16c);
565 finlen = finadd(finlen, sum(
566 scale(bytcalen, bytca, bdytail, _16), _16,
567 scale(len, _16c, 2 * bdy, _32), _32, _48), _48);
568
569 const len2 = scale(cattlen, catt, bdytail, _8);
570 finlen = finadd(finlen, sum_three(
571 scale(len2, _8, 2 * bdy, _16), _16,
572 scale(len2, _8, bdytail, _16b), _16b,
573 scale(len, _16c, bdytail, _32), _32, _32b, _64), _64);
574 }
575 }
576 if (cdxtail !== 0 || cdytail !== 0) {
577 if (adxtail !== 0 || adytail !== 0 || bdxtail !== 0 || bdytail !== 0) {
578 s1 = adxtail * bdy;
579 c = splitter * adxtail;
580 ahi = c - (c - adxtail);
581 alo = adxtail - ahi;
582 c = splitter * bdy;
583 bhi = c - (c - bdy);
584 blo = bdy - bhi;
585 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
586 t1 = adx * bdytail;
587 c = splitter * adx;
588 ahi = c - (c - adx);
589 alo = adx - ahi;
590 c = splitter * bdytail;
591 bhi = c - (c - bdytail);
592 blo = bdytail - bhi;
593 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
594 _i = s0 + t0;
595 bvirt = _i - s0;
596 u[0] = s0 - (_i - bvirt) + (t0 - bvirt);
597 _j = s1 + _i;
598 bvirt = _j - s1;
599 _0 = s1 - (_j - bvirt) + (_i - bvirt);
600 _i = _0 + t1;
601 bvirt = _i - _0;
602 u[1] = _0 - (_i - bvirt) + (t1 - bvirt);
603 u3 = _j + _i;
604 bvirt = u3 - _j;
605 u[2] = _j - (u3 - bvirt) + (_i - bvirt);
606 u[3] = u3;
607 n1 = -ady;
608 n0 = -adytail;
609 s1 = bdxtail * n1;
610 c = splitter * bdxtail;
611 ahi = c - (c - bdxtail);
612 alo = bdxtail - ahi;
613 c = splitter * n1;
614 bhi = c - (c - n1);
615 blo = n1 - bhi;
616 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
617 t1 = bdx * n0;
618 c = splitter * bdx;
619 ahi = c - (c - bdx);
620 alo = bdx - ahi;
621 c = splitter * n0;
622 bhi = c - (c - n0);
623 blo = n0 - bhi;
624 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
625 _i = s0 + t0;
626 bvirt = _i - s0;
627 v[0] = s0 - (_i - bvirt) + (t0 - bvirt);
628 _j = s1 + _i;
629 bvirt = _j - s1;
630 _0 = s1 - (_j - bvirt) + (_i - bvirt);
631 _i = _0 + t1;
632 bvirt = _i - _0;
633 v[1] = _0 - (_i - bvirt) + (t1 - bvirt);
634 u3 = _j + _i;
635 bvirt = u3 - _j;
636 v[2] = _j - (u3 - bvirt) + (_i - bvirt);
637 v[3] = u3;
638 abtlen = sum(4, u, 4, v, abt);
639 s1 = adxtail * bdytail;
640 c = splitter * adxtail;
641 ahi = c - (c - adxtail);
642 alo = adxtail - ahi;
643 c = splitter * bdytail;
644 bhi = c - (c - bdytail);
645 blo = bdytail - bhi;
646 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
647 t1 = bdxtail * adytail;
648 c = splitter * bdxtail;
649 ahi = c - (c - bdxtail);
650 alo = bdxtail - ahi;
651 c = splitter * adytail;
652 bhi = c - (c - adytail);
653 blo = adytail - bhi;
654 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
655 _i = s0 - t0;
656 bvirt = s0 - _i;
657 abtt[0] = s0 - (_i + bvirt) + (bvirt - t0);
658 _j = s1 + _i;
659 bvirt = _j - s1;
660 _0 = s1 - (_j - bvirt) + (_i - bvirt);
661 _i = _0 - t1;
662 bvirt = _0 - _i;
663 abtt[1] = _0 - (_i + bvirt) + (bvirt - t1);
664 u3 = _j + _i;
665 bvirt = u3 - _j;
666 abtt[2] = _j - (u3 - bvirt) + (_i - bvirt);
667 abtt[3] = u3;
668 abttlen = 4;
669 } else {
670 abt[0] = 0;
671 abtlen = 1;
672 abtt[0] = 0;
673 abttlen = 1;
674 }
675 if (cdxtail !== 0) {
676 const len = scale(abtlen, abt, cdxtail, _16c);
677 finlen = finadd(finlen, sum(
678 scale(cxtablen, cxtab, cdxtail, _16), _16,
679 scale(len, _16c, 2 * cdx, _32), _32, _48), _48);
680
681 const len2 = scale(abttlen, abtt, cdxtail, _8);
682 finlen = finadd(finlen, sum_three(
683 scale(len2, _8, 2 * cdx, _16), _16,
684 scale(len2, _8, cdxtail, _16b), _16b,
685 scale(len, _16c, cdxtail, _32), _32, _32b, _64), _64);
686
687 if (adytail !== 0) {
688 finlen = finadd(finlen, scale(scale(4, bb, cdxtail, _8), _8, adytail, _16), _16);
689 }
690 if (bdytail !== 0) {
691 finlen = finadd(finlen, scale(scale(4, aa, -cdxtail, _8), _8, bdytail, _16), _16);
692 }
693 }
694 if (cdytail !== 0) {
695 const len = scale(abtlen, abt, cdytail, _16c);
696 finlen = finadd(finlen, sum(
697 scale(cytablen, cytab, cdytail, _16), _16,
698 scale(len, _16c, 2 * cdy, _32), _32, _48), _48);
699
700 const len2 = scale(abttlen, abtt, cdytail, _8);
701 finlen = finadd(finlen, sum_three(
702 scale(len2, _8, 2 * cdy, _16), _16,
703 scale(len2, _8, cdytail, _16b), _16b,
704 scale(len, _16c, cdytail, _32), _32, _32b, _64), _64);
705 }
706 }
707
708 return fin[finlen - 1];
709}
710
711export function incircle(ax, ay, bx, by, cx, cy, dx, dy) {
712 const adx = ax - dx;
713 const bdx = bx - dx;
714 const cdx = cx - dx;
715 const ady = ay - dy;
716 const bdy = by - dy;
717 const cdy = cy - dy;
718
719 const bdxcdy = bdx * cdy;
720 const cdxbdy = cdx * bdy;
721 const alift = adx * adx + ady * ady;
722
723 const cdxady = cdx * ady;
724 const adxcdy = adx * cdy;
725 const blift = bdx * bdx + bdy * bdy;
726
727 const adxbdy = adx * bdy;
728 const bdxady = bdx * ady;
729 const clift = cdx * cdx + cdy * cdy;
730
731 const det =
732 alift * (bdxcdy - cdxbdy) +
733 blift * (cdxady - adxcdy) +
734 clift * (adxbdy - bdxady);
735
736 const permanent =
737 (Math.abs(bdxcdy) + Math.abs(cdxbdy)) * alift +
738 (Math.abs(cdxady) + Math.abs(adxcdy)) * blift +
739 (Math.abs(adxbdy) + Math.abs(bdxady)) * clift;
740
741 const errbound = iccerrboundA * permanent;
742
743 if (det > errbound || -det > errbound) {
744 return det;
745 }
746 return incircleadapt(ax, ay, bx, by, cx, cy, dx, dy, permanent);
747}
748
749export function incirclefast(ax, ay, bx, by, cx, cy, dx, dy) {
750 const adx = ax - dx;
751 const ady = ay - dy;
752 const bdx = bx - dx;
753 const bdy = by - dy;
754 const cdx = cx - dx;
755 const cdy = cy - dy;
756
757 const abdet = adx * bdy - bdx * ady;
758 const bcdet = bdx * cdy - cdx * bdy;
759 const cadet = cdx * ady - adx * cdy;
760 const alift = adx * adx + ady * ady;
761 const blift = bdx * bdx + bdy * bdy;
762 const clift = cdx * cdx + cdy * cdy;
763
764 return alift * bcdet + blift * cadet + clift * abdet;
765}
Note: See TracBrowser for help on using the repository browser.