source: node_modules/robust-predicates/esm/orient2d.js

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

Prototype 1.1
  • Property mode set to 100644
File size: 5.2 KB
Line 
1import {epsilon, splitter, resulterrbound, estimate, vec, sum} from './util.js';
2
3const ccwerrboundA = (3 + 16 * epsilon) * epsilon;
4const ccwerrboundB = (2 + 12 * epsilon) * epsilon;
5const ccwerrboundC = (9 + 64 * epsilon) * epsilon * epsilon;
6
7const B = vec(4);
8const C1 = vec(8);
9const C2 = vec(12);
10const D = vec(16);
11const u = vec(4);
12
13function orient2dadapt(ax, ay, bx, by, cx, cy, detsum) {
14 let acxtail, acytail, bcxtail, bcytail;
15 let bvirt, c, ahi, alo, bhi, blo, _i, _j, _0, s1, s0, t1, t0, u3;
16
17 const acx = ax - cx;
18 const bcx = bx - cx;
19 const acy = ay - cy;
20 const bcy = by - cy;
21
22 s1 = acx * bcy;
23 c = splitter * acx;
24 ahi = c - (c - acx);
25 alo = acx - ahi;
26 c = splitter * bcy;
27 bhi = c - (c - bcy);
28 blo = bcy - bhi;
29 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
30 t1 = acy * bcx;
31 c = splitter * acy;
32 ahi = c - (c - acy);
33 alo = acy - ahi;
34 c = splitter * bcx;
35 bhi = c - (c - bcx);
36 blo = bcx - bhi;
37 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
38 _i = s0 - t0;
39 bvirt = s0 - _i;
40 B[0] = s0 - (_i + bvirt) + (bvirt - t0);
41 _j = s1 + _i;
42 bvirt = _j - s1;
43 _0 = s1 - (_j - bvirt) + (_i - bvirt);
44 _i = _0 - t1;
45 bvirt = _0 - _i;
46 B[1] = _0 - (_i + bvirt) + (bvirt - t1);
47 u3 = _j + _i;
48 bvirt = u3 - _j;
49 B[2] = _j - (u3 - bvirt) + (_i - bvirt);
50 B[3] = u3;
51
52 let det = estimate(4, B);
53 let errbound = ccwerrboundB * detsum;
54 if (det >= errbound || -det >= errbound) {
55 return det;
56 }
57
58 bvirt = ax - acx;
59 acxtail = ax - (acx + bvirt) + (bvirt - cx);
60 bvirt = bx - bcx;
61 bcxtail = bx - (bcx + bvirt) + (bvirt - cx);
62 bvirt = ay - acy;
63 acytail = ay - (acy + bvirt) + (bvirt - cy);
64 bvirt = by - bcy;
65 bcytail = by - (bcy + bvirt) + (bvirt - cy);
66
67 if (acxtail === 0 && acytail === 0 && bcxtail === 0 && bcytail === 0) {
68 return det;
69 }
70
71 errbound = ccwerrboundC * detsum + resulterrbound * Math.abs(det);
72 det += (acx * bcytail + bcy * acxtail) - (acy * bcxtail + bcx * acytail);
73 if (det >= errbound || -det >= errbound) return det;
74
75 s1 = acxtail * bcy;
76 c = splitter * acxtail;
77 ahi = c - (c - acxtail);
78 alo = acxtail - ahi;
79 c = splitter * bcy;
80 bhi = c - (c - bcy);
81 blo = bcy - bhi;
82 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
83 t1 = acytail * bcx;
84 c = splitter * acytail;
85 ahi = c - (c - acytail);
86 alo = acytail - ahi;
87 c = splitter * bcx;
88 bhi = c - (c - bcx);
89 blo = bcx - bhi;
90 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
91 _i = s0 - t0;
92 bvirt = s0 - _i;
93 u[0] = s0 - (_i + bvirt) + (bvirt - t0);
94 _j = s1 + _i;
95 bvirt = _j - s1;
96 _0 = s1 - (_j - bvirt) + (_i - bvirt);
97 _i = _0 - t1;
98 bvirt = _0 - _i;
99 u[1] = _0 - (_i + bvirt) + (bvirt - t1);
100 u3 = _j + _i;
101 bvirt = u3 - _j;
102 u[2] = _j - (u3 - bvirt) + (_i - bvirt);
103 u[3] = u3;
104 const C1len = sum(4, B, 4, u, C1);
105
106 s1 = acx * bcytail;
107 c = splitter * acx;
108 ahi = c - (c - acx);
109 alo = acx - ahi;
110 c = splitter * bcytail;
111 bhi = c - (c - bcytail);
112 blo = bcytail - bhi;
113 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
114 t1 = acy * bcxtail;
115 c = splitter * acy;
116 ahi = c - (c - acy);
117 alo = acy - ahi;
118 c = splitter * bcxtail;
119 bhi = c - (c - bcxtail);
120 blo = bcxtail - bhi;
121 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
122 _i = s0 - t0;
123 bvirt = s0 - _i;
124 u[0] = s0 - (_i + bvirt) + (bvirt - t0);
125 _j = s1 + _i;
126 bvirt = _j - s1;
127 _0 = s1 - (_j - bvirt) + (_i - bvirt);
128 _i = _0 - t1;
129 bvirt = _0 - _i;
130 u[1] = _0 - (_i + bvirt) + (bvirt - t1);
131 u3 = _j + _i;
132 bvirt = u3 - _j;
133 u[2] = _j - (u3 - bvirt) + (_i - bvirt);
134 u[3] = u3;
135 const C2len = sum(C1len, C1, 4, u, C2);
136
137 s1 = acxtail * bcytail;
138 c = splitter * acxtail;
139 ahi = c - (c - acxtail);
140 alo = acxtail - ahi;
141 c = splitter * bcytail;
142 bhi = c - (c - bcytail);
143 blo = bcytail - bhi;
144 s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);
145 t1 = acytail * bcxtail;
146 c = splitter * acytail;
147 ahi = c - (c - acytail);
148 alo = acytail - ahi;
149 c = splitter * bcxtail;
150 bhi = c - (c - bcxtail);
151 blo = bcxtail - bhi;
152 t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);
153 _i = s0 - t0;
154 bvirt = s0 - _i;
155 u[0] = s0 - (_i + bvirt) + (bvirt - t0);
156 _j = s1 + _i;
157 bvirt = _j - s1;
158 _0 = s1 - (_j - bvirt) + (_i - bvirt);
159 _i = _0 - t1;
160 bvirt = _0 - _i;
161 u[1] = _0 - (_i + bvirt) + (bvirt - t1);
162 u3 = _j + _i;
163 bvirt = u3 - _j;
164 u[2] = _j - (u3 - bvirt) + (_i - bvirt);
165 u[3] = u3;
166 const Dlen = sum(C2len, C2, 4, u, D);
167
168 return D[Dlen - 1];
169}
170
171export function orient2d(ax, ay, bx, by, cx, cy) {
172 const detleft = (ay - cy) * (bx - cx);
173 const detright = (ax - cx) * (by - cy);
174 const det = detleft - detright;
175
176 const detsum = Math.abs(detleft + detright);
177 if (Math.abs(det) >= ccwerrboundA * detsum) return det;
178
179 return -orient2dadapt(ax, ay, bx, by, cx, cy, detsum);
180}
181
182export function orient2dfast(ax, ay, bx, by, cx, cy) {
183 return (ay - cy) * (bx - cx) - (ax - cx) * (by - cy);
184}
Note: See TracBrowser for help on using the repository browser.