Loading...
Searching...
No Matches
cdt_impl.hpp
Go to the documentation of this file.
1
12
13#pragma once
14#include "meshkit/cdt.hpp"
16#include "predicates.h"
17#include <array>
18#include <algorithm>
19#include <cmath>
20#include <queue>
21#include <cstring>
22#include <limits>
23#include <mutex>
24
25namespace meshkit
26{
27
28namespace cdt_detail
29{
30
33inline std::once_flag gPredicatesInit;
34
42inline std::uint64_t mortonKey(std::uint32_t x, std::uint32_t y)
43{
44 auto spread = [](std::uint64_t v) {
45 v &= 0xffffffffull;
46 v = (v | (v << 16)) & 0x0000ffff0000ffffull;
47 v = (v | (v << 8)) & 0x00ff00ff00ff00ffull;
48 v = (v | (v << 4)) & 0x0f0f0f0f0f0f0f0full;
49 v = (v | (v << 2)) & 0x3333333333333333ull;
50 v = (v | (v << 1)) & 0x5555555555555555ull;
51 return v;
52 };
53 return spread(x) | (spread(y) << 1);
54}
55
65inline std::uint64_t edgeKey64(int a, int b)
66{
67 if (a > b)
68 std::swap(a, b);
69 return (std::uint64_t(std::uint32_t(a)) << 32) | std::uint64_t(std::uint32_t(b));
70}
71
77inline int keyLo(std::uint64_t k)
78{
79 return int(std::uint32_t(k >> 32));
80}
81
86inline int keyHi(std::uint64_t k)
87{
88 return int(std::uint32_t(k & 0xffffffffull));
89}
90
101template <class Point> double orientPts(const Point &a, const Point &b, const Point &c)
102{
103 const double pa[2] = {a.x(), a.y()}, pb[2] = {b.x(), b.y()}, pc[2] = {c.x(), c.y()};
104 return orient2d(pa, pb, pc);
105}
106
110 * @param[in] b Borrowed point in same XY frame, unchanged.
111 * @return Nonnegative squared horizontal units for ordinary finite inputs, no square root,
112 * allocation or mutation.
113 */
114template <class Point> inline double dist2(const Point &a, const Point &b)
115{
116 const double dx = a.x() - b.x(), dy = a.y() - b.y();
117 return dx * dx + dy * dy;
118}
119
120// Preserve the existing refinement coincidence rule during extraction.
121// Input build/dedup remains exact, with signed-zero normalization.
131template <class Point> bool refinementCoincident(const Point &a, const Point &b)
132{
133 auto close = [](double x, double y) {
134 return (x == 0 || y == 0) ? std::abs(x - y) <= 1e-12
135 : std::abs(x - y) * 1e12 <= std::min(std::abs(x), std::abs(y));
136 };
137 return close(a.x(), b.x()) && close(a.y(), b.y());
138}
139
140/// Area of an equilateral triangle with unit side, √3/4: a triangle of nominal size h has area
141/// kEquilateralArea * h * h.
142constexpr double kEquilateralArea = 0.4330127018922193; // √3/4
143
144} // namespace cdt_detail
145using namespace cdt_detail;
146
147// ── Predicates ───────────────────────────────────────────────────────────
148
149template <class Storage>
151 const Point &c)
152{
153 std::call_once(gPredicatesInit, [] { exactinit(); });
154 return orientPts(a, b, c);
155}
156
157template <class Storage> double BasicConstrainedDelaunay<Storage>::orient(int a, int b, int c) const
158{
159 const double pa[2] = {m_pts[a].x(), m_pts[a].y()};
160 const double pb[2] = {m_pts[b].x(), m_pts[b].y()};
161 const double pc[2] = {m_pts[c].x(), m_pts[c].y()};
162 return orient2d(pa, pb, pc);
163}
164
165template <class Storage>
166double BasicConstrainedDelaunay<Storage>::orient(int a, int b, const Point &p) const
167{
168 const double pa[2] = {m_pts[a].x(), m_pts[a].y()};
169 const double pb[2] = {m_pts[b].x(), m_pts[b].y()};
170 const double pc[2] = {p.x(), p.y()};
171 return orient2d(pa, pb, pc);
172}
173
174template <class Storage>
175bool BasicConstrainedDelaunay<Storage>::inCircle(int a, int b, int c, int d) const
176{
177 const double pa[2] = {m_pts[a].x(), m_pts[a].y()};
178 const double pb[2] = {m_pts[b].x(), m_pts[b].y()};
179 const double pc[2] = {m_pts[c].x(), m_pts[c].y()};
180 const double pd[2] = {m_pts[d].x(), m_pts[d].y()};
181 return incircle(pa, pb, pc, pd) > 0.0;
182}
183
184// ── Topology helpers ─────────────────────────────────────────────────────
185
186template <class Storage> int BasicConstrainedDelaunay<Storage>::edgeIndex(int t, int v) const
187{
188 const Triangle &T = m_tris[t];
189 for (int i = 0; i < 3; ++i)
190 if (T.v[i] == v)
191 return i;
192 return -1;
193}
194
195template <class Storage>
196void BasicConstrainedDelaunay<Storage>::trianglesAround(int v, Vector<int> *out) const
197{
198 const int start = m_vertexTri[v];
199 if (start < 0)
200 return;
201 for (int dir = 0; dir < 2; ++dir) {
202 int t = start;
203 for (int guard = 0; guard < 100000; ++guard) {
204 const int i = edgeIndex(t, v);
205 if (i < 0)
206 break;
207 if (!(dir == 1 && t == start))
208 out->append(t);
209 const int next = m_tris[t].adj[dir == 0 ? (i + 1) % 3 : (i + 2) % 3];
210 if (next < 0)
211 break;
212 if (next == start)
213 return; // closed fan: done after one direction
214 t = next;
215 }
216 }
217}
218
219template <class Storage> void BasicConstrainedDelaunay<Storage>::setAdj(int t, int e, int n)
221 if (t >= 0)
222 m_tris[t].adj[e] = n;
223}
224
227template <class Storage>
228int BasicConstrainedDelaunay<Storage>::triangleWithEdge(int a, int b, int *edgeIndexOut) const
229{
230 const int start = m_vertexTri[a];
231 if (start < 0)
232 return -1;
233 int t = start;
234 for (int guard = 0; guard < 100000; ++guard) {
235 const Triangle &T = m_tris[t];
236 const int i = edgeIndex(t, a);
237 if (i < 0)
238 return -1;
239 if (T.v[(i + 1) % 3] == b) {
240 if (edgeIndexOut)
241 *edgeIndexOut = (i + 2) % 3;
242 return t;
243 }
244 // Rotate counter-clockwise around a: next triangle across the edge
245 // (a, v[i+2]) which is opposite v[i+1].
246 const int next = T.adj[(i + 1) % 3];
247 if (next < 0 || next == start)
248 break;
249 t = next;
250 }
251 // Rotate the other way in case the fan is open on one side.
252 t = start;
253 for (int guard = 0; guard < 100000; ++guard) {
254 const Triangle &T = m_tris[t];
255 const int i = edgeIndex(t, a);
256 if (i < 0)
257 return -1;
258 if (T.v[(i + 1) % 3] == b) {
259 if (edgeIndexOut)
260 *edgeIndexOut = (i + 2) % 3;
261 return t;
262 }
263 const int next = T.adj[(i + 2) % 3];
264 if (next < 0 || next == start)
265 break;
266 t = next;
267 }
268 return -1;
269}
270
271template <class Storage> bool BasicConstrainedDelaunay<Storage>::isConstrained(int a, int b) const
272{
273 int e = -1;
274 int t = triangleWithEdge(a, b, &e);
275 if (t < 0)
276 t = triangleWithEdge(b, a, &e);
277 return t >= 0 && m_tris[t].constrained[e];
278}
279
280template <class Storage>
282{
283 // Follow constrained edges from a: first the edge to b itself, then the
284 // subsegments refinement or insertion split off (a, b) — its origin — and
285 // failing both an exactly collinear constrained edge towards b.
286 const std::uint64_t origin = edgeKey64(a, b);
287 Vector<int> chain{a};
288 int cur = a, prev = -1;
289 for (int guard = 0; guard < 1000000 && cur != b; ++guard) {
290 Vector<int> fan;
291 trianglesAround(cur, &fan);
292 bool reachesB = false;
293 int byOrigin = -1, byLine = -1;
294 double bestD2 = std::numeric_limits<double>::infinity();
295 const Point &P = m_pts[cur], &B = m_pts[b];
296 for (int t : fan) {
297 const Triangle &T = m_tris[t];
298 const int i = edgeIndex(t, cur);
299 for (int k = 1; k <= 2; ++k) {
300 const int v = T.v[(i + k) % 3];
301 const int e =
302 (i + (k == 1 ? 2 : 1)) % 3; // edge (cur, v) is opposite the third vertex
303 if (!T.constrained[e] || v == cur || v == prev)
304 continue;
305 if (v == b) {
306 reachesB = true;
307 continue;
308 }
309 const std::uint64_t ek = edgeKey64(cur, v);
310 const auto it = m_segOrigin.constFind(ek);
311 if (it != m_segOrigin.constEnd() &&
312 (it.value() == origin || m_segOriginExtra.contains(ek, origin))) {
313 byOrigin = v;
314 continue;
315 }
316 if (orient(a, b, v) != 0.0)
317 continue;
318 const Point &V = m_pts[v];
319 const double dot =
320 (V.x() - P.x()) * (B.x() - P.x()) + (V.y() - P.y()) * (B.y() - P.y());
321 if (dot <= 0.0)
322 continue;
323 const double d2 = dist2(V, P);
324 if (d2 < bestD2) {
325 bestD2 = d2;
326 byLine = v;
327 }
328 }
329 }
330 const int next = reachesB ? b : (byOrigin >= 0 ? byOrigin : byLine);
331 if (next < 0)
332 return {};
333 chain.append(next);
334 prev = cur;
335 cur = next;
336 }
337 return cur == b ? chain : Vector<int>();
338}
339
340template <class Storage> void BasicConstrainedDelaunay<Storage>::markConstrained(int a, int b)
341{
342 for (int dir = 0; dir < 2; ++dir) {
343 int e = -1;
344 const int t = dir == 0 ? triangleWithEdge(a, b, &e) : triangleWithEdge(b, a, &e);
345 if (t < 0)
346 continue;
347 m_tris[t].constrained[e] = true;
348 const int n = m_tris[t].adj[e];
349 if (n >= 0)
350 for (int i = 0; i < 3; ++i)
351 if (m_tris[n].adj[i] == t)
352 m_tris[n].constrained[i] = true;
353 }
354}
355
356template <class Storage>
357int BasicConstrainedDelaunay<Storage>::findTriangle(const Point &p, int start) const
358{
359 if (m_tris.isEmpty())
360 return -1;
361 int t = (start >= 0 && start < m_tris.size()) ? start : 0;
362 const int cap = m_tris.size() * 2 + 16;
363 for (int step = 0; step < cap; ++step) {
364 const Triangle &T = m_tris[t];
365 int next = -1;
366 for (int i = 0; i < 3; ++i) {
367 if (orient(T.v[(i + 1) % 3], T.v[(i + 2) % 3], p) < 0.0) {
368 next = T.adj[i];
369 if (next < 0)
370 return -1;
371 break;
372 }
373 }
374 if (next < 0)
375 return t;
376 t = next;
377 }
378 // Cycle guard: brute force.
379 for (int i = 0; i < m_tris.size(); ++i) {
380 const Triangle &T = m_tris[i];
381 if (orient(T.v[1], T.v[2], p) >= 0.0 && orient(T.v[2], T.v[0], p) >= 0.0 &&
382 orient(T.v[0], T.v[1], p) >= 0.0)
383 return i;
384 }
385 return -1;
386}
387
388template <class Storage> int BasicConstrainedDelaunay<Storage>::locate(const Point &p) const
389{
390 const int t = findTriangle(p, m_lastLocate);
391 return (t >= 0 && m_tris[t].alive) ? t : -1;
392}
393
395{
396 return m_liveTriangles;
397}
398
399// ── Flips and splits ─────────────────────────────────────────────────────
400
403template <class Storage> void BasicConstrainedDelaunay<Storage>::flip(int t, int e)
404{
405 Triangle &T = m_tris[t];
406 const int n = T.adj[e];
407 Triangle &N = m_tris[n];
408 const int a = T.v[e], b = T.v[(e + 1) % 3], c = T.v[(e + 2) % 3];
409 int k = 0;
410 for (int i = 0; i < 3; ++i)
411 if (N.adj[i] == t) {
412 k = i;
413 break;
414 }
415 const int d = N.v[k];
416 const int Tca = T.adj[(e + 1) % 3], Tab = T.adj[(e + 2) % 3];
417 const int Nbd = N.adj[(k + 1) % 3], Ndc = N.adj[(k + 2) % 3];
418 const bool cCA = T.constrained[(e + 1) % 3], cAB = T.constrained[(e + 2) % 3];
419 const bool cBD = N.constrained[(k + 1) % 3], cDC = N.constrained[(k + 2) % 3];
420
421 T.v[0] = a;
422 T.v[1] = b;
423 T.v[2] = d;
424 T.adj[0] = Nbd;
425 T.adj[1] = n;
426 T.adj[2] = Tab;
427 T.constrained[0] = cBD;
428 T.constrained[1] = false;
429 T.constrained[2] = cAB;
430 N.v[0] = a;
431 N.v[1] = d;
432 N.v[2] = c;
433 N.adj[0] = Ndc;
434 N.adj[1] = Tca;
435 N.adj[2] = t;
436 N.constrained[0] = cDC;
437 N.constrained[1] = cCA;
438 N.constrained[2] = false;
439 if (Nbd >= 0)
440 for (int i = 0; i < 3; ++i)
441 if (m_tris[Nbd].adj[i] == n)
442 m_tris[Nbd].adj[i] = t;
443 if (Tca >= 0)
444 for (int i = 0; i < 3; ++i)
445 if (m_tris[Tca].adj[i] == t)
446 m_tris[Tca].adj[i] = n;
447 m_vertexTri[a] = t;
448 m_vertexTri[b] = t;
449 m_vertexTri[d] = t;
450 m_vertexTri[c] = n;
451 if (m_triangleChanged) {
452 m_triangleChanged(t);
453 m_triangleChanged(n);
454 }
455}
456
457template <class Storage> void BasicConstrainedDelaunay<Storage>::legalize(int t0, int e0)
458{
459 Vector<std::pair<int, int>> stack;
460 stack.append(std::make_pair(t0, e0));
461 while (!stack.isEmpty()) {
462 const std::pair<int, int> te = stack.takeLast();
463 const int t = te.first, e = te.second;
464 const Triangle &T = m_tris[t];
465 const int n = T.adj[e];
466 if (n < 0 || T.constrained[e])
467 continue;
468 const Triangle &N = m_tris[n];
469 int k = 0;
470 for (int i = 0; i < 3; ++i)
471 if (N.adj[i] == t) {
472 k = i;
473 break;
474 }
475 const int d = N.v[k];
476 if (!inCircle(T.v[0], T.v[1], T.v[2], d))
477 continue;
478 flip(t, e);
479 // t = (a, b, d), n = (a, d, c): recheck the quad's four outer edges.
480 stack.append(std::make_pair(t, 0));
481 stack.append(std::make_pair(t, 2));
482 stack.append(std::make_pair(n, 0));
483 stack.append(std::make_pair(n, 1));
484 }
485}
486
487template <class Storage> void BasicConstrainedDelaunay<Storage>::splitTriangle(int t, int v)
488{
489 const Triangle old = m_tris[t];
490 const int a = old.v[0], b = old.v[1], c = old.v[2];
491 const int t1 = t, t2 = m_tris.size(), t3 = m_tris.size() + 1;
492 Triangle T1, T2, T3;
493 T1.v[0] = v;
494 T1.v[1] = a;
495 T1.v[2] = b;
496 T2.v[0] = v;
497 T2.v[1] = b;
498 T2.v[2] = c;
499 T3.v[0] = v;
500 T3.v[1] = c;
501 T3.v[2] = a;
502 T1.adj[0] = old.adj[2];
503 T1.adj[1] = t2;
504 T1.adj[2] = t3;
505 T2.adj[0] = old.adj[0];
506 T2.adj[1] = t3;
507 T2.adj[2] = t1;
508 T3.adj[0] = old.adj[1];
509 T3.adj[1] = t1;
510 T3.adj[2] = t2;
511 T1.constrained[0] = old.constrained[2];
512 T1.constrained[1] = T1.constrained[2] = false;
513 T2.constrained[0] = old.constrained[0];
514 T2.constrained[1] = T2.constrained[2] = false;
515 T3.constrained[0] = old.constrained[1];
516 T3.constrained[1] = T3.constrained[2] = false;
517 T1.alive = T2.alive = T3.alive = old.alive;
518 m_tris[t1] = T1;
519 m_tris.append(T2);
520 m_tris.append(T3);
521 m_liveTriangles += old.alive ? 2 : 0;
522 if (old.adj[2] >= 0)
523 for (int i = 0; i < 3; ++i)
524 if (m_tris[old.adj[2]].adj[i] == t)
525 m_tris[old.adj[2]].adj[i] = t1;
526 if (old.adj[0] >= 0)
527 for (int i = 0; i < 3; ++i)
528 if (m_tris[old.adj[0]].adj[i] == t)
529 m_tris[old.adj[0]].adj[i] = t2;
530 if (old.adj[1] >= 0)
531 for (int i = 0; i < 3; ++i)
532 if (m_tris[old.adj[1]].adj[i] == t)
533 m_tris[old.adj[1]].adj[i] = t3;
534 m_vertexTri[v] = t1;
535 m_vertexTri[a] = t1;
536 m_vertexTri[b] = t2;
537 m_vertexTri[c] = t3;
538 legalize(t1, 0);
539 legalize(t2, 0);
540 legalize(t3, 0);
541 if (m_triangleChanged) {
542 m_triangleChanged(t1);
543 m_triangleChanged(t2);
544 m_triangleChanged(t3);
545 }
546}
547
548template <class Storage> void BasicConstrainedDelaunay<Storage>::splitEdge(int t, int e, int v)
549{
550 const Triangle old = m_tris[t];
551 const int a = old.v[e], b = old.v[(e + 1) % 3], c = old.v[(e + 2) % 3];
552 const int n = old.adj[e];
553 const bool f = old.constrained[e];
554 const int t1 = t, t2 = m_tris.size();
555 Triangle T1, T2;
556 T1.v[0] = v;
557 T1.v[1] = a;
558 T1.v[2] = b;
559 T2.v[0] = v;
560 T2.v[1] = c;
561 T2.v[2] = a;
562 T1.alive = T2.alive = old.alive;
563 int n1 = -1, n2 = -1;
564 if (n >= 0) {
565 n1 = n;
566 n2 = m_tris.size() + 1;
567 }
568 // Old edges: (a, b) is opposite c = index e+2; (c, a) is opposite b = index e+1.
569 const int Tab = old.adj[(e + 2) % 3], Tca = old.adj[(e + 1) % 3];
570 T1.adj[0] = Tab;
571 T1.adj[1] = n1;
572 T1.adj[2] = t2;
573 T2.adj[0] = Tca;
574 T2.adj[1] = t1;
575 T2.adj[2] = n2;
576 T1.constrained[0] = old.constrained[(e + 2) % 3];
577 T1.constrained[1] = f;
578 T1.constrained[2] = false;
579 T2.constrained[0] = old.constrained[(e + 1) % 3];
580 T2.constrained[1] = false;
581 T2.constrained[2] = f;
582 m_tris[t1] = T1;
583 m_tris.append(T2);
584 m_liveTriangles += old.alive ? 1 : 0;
585 if (Tab >= 0)
586 for (int i = 0; i < 3; ++i)
587 if (m_tris[Tab].adj[i] == t)
588 m_tris[Tab].adj[i] = t1;
589 if (Tca >= 0)
590 for (int i = 0; i < 3; ++i)
591 if (m_tris[Tca].adj[i] == t)
592 m_tris[Tca].adj[i] = t2;
593 m_vertexTri[v] = t1;
594 m_vertexTri[a] = t1;
595 m_vertexTri[b] = t1;
596 m_vertexTri[c] = t2;
597 if (n >= 0) {
598 const Triangle oldN = m_tris[n];
599 int k = 0;
600 for (int i = 0; i < 3; ++i)
601 if (oldN.adj[i] == t) {
602 k = i;
603 break;
604 }
605 const int d = oldN.v[k];
606 Triangle N1, N2;
607 N1.v[0] = v;
608 N1.v[1] = b;
609 N1.v[2] = d;
610 N2.v[0] = v;
611 N2.v[1] = d;
612 N2.v[2] = c;
613 N1.alive = N2.alive = oldN.alive;
614 N1.adj[0] = oldN.adj[(k + 1) % 3];
615 N1.adj[1] = n2;
616 N1.adj[2] = t1;
617 N2.adj[0] = oldN.adj[(k + 2) % 3];
618 N2.adj[1] = t2;
619 N2.adj[2] = n1;
620 N1.constrained[0] = oldN.constrained[(k + 1) % 3];
621 N1.constrained[1] = false;
622 N1.constrained[2] = f;
623 N2.constrained[0] = oldN.constrained[(k + 2) % 3];
624 N2.constrained[1] = f;
625 N2.constrained[2] = false;
626 m_tris[n1] = N1;
627 m_tris.append(N2);
628 m_liveTriangles += oldN.alive ? 1 : 0;
629 if (N1.adj[0] >= 0)
630 for (int i = 0; i < 3; ++i)
631 if (m_tris[N1.adj[0]].adj[i] == n)
632 m_tris[N1.adj[0]].adj[i] = n1;
633 if (N2.adj[0] >= 0)
634 for (int i = 0; i < 3; ++i)
635 if (m_tris[N2.adj[0]].adj[i] == n)
636 m_tris[N2.adj[0]].adj[i] = n2;
637 m_vertexTri[d] = n1;
638 }
639 legalize(t1, 0);
640 legalize(t2, 0);
641 if (n >= 0) {
642 legalize(n1, 0);
643 legalize(n2, 0);
644 }
645 if (m_triangleChanged) {
646 m_triangleChanged(t1);
647 m_triangleChanged(t2);
648 if (n >= 0) {
649 m_triangleChanged(n1);
650 m_triangleChanged(n2);
651 }
652 }
653}
654
655// ── Construction ─────────────────────────────────────────────────────────
656
657template <class Storage>
659 const std::function<bool()> &cancelled,
660 const std::function<void(std::uint64_t)> &progress)
661{
662 std::call_once(gPredicatesInit, [] { exactinit(); });
663 m_origins.clear();
664 m_pts.clear();
665 m_tris.clear();
666 m_liveTriangles = 0;
667 m_vertexTri.clear();
668 m_errorMsg.clear();
669 m_terrainElevations.clear();
670 m_segOrigin.clear();
671 m_segOriginExtra.clear();
672 m_segPiece.clear();
673 m_vertexSeg.clear();
674 m_fixedSub.clear();
675 m_lastLocate = 0;
676 auto stopped = [&] {
677 if (cancelled && cancelled()) {
678 m_errorMsg = Storage::message("cdt: cancelled");
679 return true;
680 }
681 return false;
682 };
683 if (stopped())
684 return false;
685
686 // Dedup on the exact bit pattern.
688 seen.reserve(points.size());
689 if (vertexOfPoint)
690 vertexOfPoint->resize(points.size());
691 double minX = std::numeric_limits<double>::infinity(), minY = minX, maxX = -minX, maxY = -minX;
692 for (int i = 0; i < points.size(); ++i) {
693 if ((i & 4095) == 0 && stopped())
694 return false;
695 const Point &p = points[i];
696 if (!std::isfinite(p.x()) || !std::isfinite(p.y())) {
697 m_errorMsg = Storage::invalidPointMessage(i);
698 return false;
699 }
700 std::int64_t kx, ky;
701 double x = p.x(), y = p.y();
702 if (x == 0.0)
703 x = 0.0;
704 if (y == 0.0)
705 y = 0.0; // fold -0
706 std::memcpy(&kx, &x, 8);
707 std::memcpy(&ky, &y, 8);
708 const std::pair<std::int64_t, std::int64_t> key(kx, ky);
709 auto it = seen.constFind(key);
710 int id;
711 if (it == seen.constEnd()) {
712 id = m_pts.size();
713 m_pts.append(p);
714 seen.insert(key, id);
715 minX = std::min(minX, p.x());
716 maxX = std::max(maxX, p.x());
717 minY = std::min(minY, p.y());
718 maxY = std::max(maxY, p.y());
719 } else
720 id = it.value();
721 if (vertexOfPoint)
722 (*vertexOfPoint)[i] = id;
723 }
724 if (m_pts.size() < 3) {
725 m_errorMsg = Storage::message("cdt: fewer than 3 distinct points");
726 return false;
727 }
728
729 // Super triangle far outside the data.
730 const Box bbox(Point(minX, minY), Point(maxX, maxY));
731 const double ext = std::max({bbox.width(), bbox.height(), 1e-9});
732 const double cx = bbox.center().x(), cy = bbox.center().y();
733 const double R = ext * 1e5;
734 m_superBase = m_pts.size();
735 m_pts.append(Point(cx - 2.0 * R, cy - R));
736 m_pts.append(Point(cx + 2.0 * R, cy - R));
737 m_pts.append(Point(cx, cy + 2.0 * R));
738 m_vertexTri.fill(-1, m_pts.size());
739 Triangle sup;
740 sup.v[0] = m_superBase;
741 sup.v[1] = m_superBase + 1;
742 sup.v[2] = m_superBase + 2;
743 sup.adj[0] = sup.adj[1] = sup.adj[2] = -1;
744 sup.constrained[0] = sup.constrained[1] = sup.constrained[2] = false;
745 sup.alive = true;
746 m_tris.append(sup);
747 m_liveTriangles = 1;
748 m_vertexTri[m_superBase] = m_vertexTri[m_superBase + 1] = m_vertexTri[m_superBase + 2] = 0;
749
750 // Insertion order: Morton on a 2^20 quantisation (deterministic, local).
751 Vector<std::pair<std::uint64_t, int>> order(m_superBase);
752 const double sx = bbox.width() > 0 ? 1048575.0 / bbox.width() : 0.0;
753 const double sy = bbox.height() > 0 ? 1048575.0 / bbox.height() : 0.0;
754 for (int i = 0; i < m_superBase; ++i) {
755 const std::uint32_t qx = std::uint32_t((m_pts[i].x() - bbox.left()) * sx);
756 const std::uint32_t qy = std::uint32_t((m_pts[i].y() - bbox.top()) * sy);
757 order[i] = std::make_pair(mortonKey(qx, qy), i);
758 }
759 if (!cancelled)
760 std::sort(order.begin(), order.end());
761 else {
762 struct CancelBuild {
763 };
764 std::uint64_t comparisons = 0;
765 try {
766 std::sort(order.begin(), order.end(), [&](const auto &a, const auto &b) {
767 if ((++comparisons & 16383) == 0 && stopped())
768 throw CancelBuild{};
769 return a < b;
770 });
771 } catch (const CancelBuild &) {
772 return false;
773 }
774 }
775
776 m_tris.reserve(2 * m_superBase + 8);
777 std::uint64_t completed = 0;
778 for (const std::pair<std::uint64_t, int> &o : order) {
779 if ((completed++ & 4095) == 0) {
780 if (stopped())
781 return false;
782 if (progress)
783 progress(completed - 1);
784 }
785 const int v = o.second;
786 const int t = findTriangle(m_pts[v], m_lastLocate);
787 if (t < 0) {
788 m_errorMsg = Storage::message("cdt: point location failed");
789 return false;
790 }
791 const Triangle &T = m_tris[t];
792 int onEdge = -1;
793 for (int i = 0; i < 3; ++i)
794 if (orient(T.v[(i + 1) % 3], T.v[(i + 2) % 3], v) == 0.0) {
795 onEdge = i;
796 break;
797 }
798 if (onEdge >= 0)
799 splitEdge(t, onEdge, v);
800 else
801 splitTriangle(t, v);
802 m_lastLocate = m_vertexTri[v];
803 }
804 return true;
805}
806
807template <class Storage> int BasicConstrainedDelaunay<Storage>::insertPoint(const Point &p)
808{
809 const int t = findTriangle(p, m_lastLocate);
810 if (t < 0 || !m_tris[t].alive)
811 return -1;
812 const int v = m_pts.size();
813 m_pts.append(p);
814 if (!m_origins.isEmpty())
815 m_origins.append(0);
816 m_vertexTri.append(-1);
817 const Triangle &T = m_tris[t];
818 int onEdge = -1;
819 for (int i = 0; i < 3; ++i)
820 if (orient(T.v[(i + 1) % 3], T.v[(i + 2) % 3], v) == 0.0) {
821 onEdge = i;
822 break;
823 }
824 if (onEdge >= 0) {
825 // Coincident with a vertex? Then reuse it.
826 for (int i = 0; i < 3; ++i)
827 if (refinementCoincident(m_pts[T.v[i]], p)) {
828 m_pts.removeLast();
829 m_vertexTri.removeLast();
830 return T.v[i];
831 }
832 splitEdge(t, onEdge, v);
833 } else
834 splitTriangle(t, v);
835 m_lastLocate = m_vertexTri[v];
836 return v;
837}
838
839template <class Storage> bool BasicConstrainedDelaunay<Storage>::insertConstraint(int a, int b)
840{
841 return insertConstraintImpl(a, b, edgeKey64(a, b));
842}
843
844template <class Storage>
845bool BasicConstrainedDelaunay<Storage>::insertConstraintImpl(int a, int b, std::uint64_t origin)
846{
847 if (a == b)
848 return true;
849 if (a < 0 || b < 0 || a >= m_pts.size() || b >= m_pts.size() || isSuperVertex(a) ||
850 isSuperVertex(b))
851 return false;
852 int e = -1;
853 // Record the input segment and the piece an edge realises. A second
854 // constraint over the same edge (an overlap) adds its origin.
855 auto record = [&](int x, int y) {
856 const std::uint64_t k = edgeKey64(x, y);
857 const auto it = m_segOrigin.constFind(k);
858 if (it == m_segOrigin.constEnd())
859 m_segOrigin.insert(k, origin);
860 else if (it.value() != origin && !m_segOriginExtra.contains(k, origin))
861 m_segOriginExtra.insert(k, origin);
862 if (!m_segPiece.contains(k))
863 m_segPiece.insert(k, k);
864 };
865 if (triangleWithEdge(a, b, &e) >= 0 || triangleWithEdge(b, a, &e) >= 0) {
866 markConstrained(a, b);
867 record(a, b);
868 return true;
869 }
870
871 // Find the triangle at a whose opposite edge the segment a→b crosses.
872 // A vertex lying exactly on the segment splits the constraint there.
873 auto onSegment = [&](int p) {
874 if (p == a || p == b || orient(a, b, p) != 0.0)
875 return false;
876 const Point &A = m_pts[a], &B = m_pts[b], &P = m_pts[p];
877 return (P.x() - A.x()) * (B.x() - A.x()) + (P.y() - A.y()) * (B.y() - A.y()) > 0.0 &&
878 (P.x() - B.x()) * (A.x() - B.x()) + (P.y() - B.y()) * (A.y() - B.y()) > 0.0;
879 };
880 int start = -1, startEdge = -1;
881 for (int dir = 0; dir < 2 && start < 0; ++dir) {
882 const int t0 = m_vertexTri[a];
883 int t = t0;
884 for (int guard = 0; guard < 1000000 && t >= 0; ++guard) {
885 const int i = edgeIndex(t, a);
886 if (i < 0)
887 break;
888 const int p = m_tris[t].v[(i + 1) % 3], q = m_tris[t].v[(i + 2) % 3];
889 if (onSegment(p))
890 return insertConstraintImpl(a, p, origin) && insertConstraintImpl(p, b, origin);
891 if (onSegment(q))
892 return insertConstraintImpl(a, q, origin) && insertConstraintImpl(q, b, origin);
893 if (orient(a, b, p) < 0.0 && orient(a, b, q) > 0.0) {
894 start = t;
895 startEdge = i;
896 break;
897 }
898 const int next = m_tris[t].adj[dir == 0 ? (i + 1) % 3 : (i + 2) % 3];
899 if (next < 0 || next == t0)
900 break;
901 t = next;
902 }
903 }
904 if (start < 0) {
905 m_errorMsg = Storage::message("cdt: constraint start not found");
906 return false;
907 }
908
909 // Collect the crossed edges by walking from a to b.
910 Vector<std::pair<int, int>> crossed;
911 {
912 int t = start, e = startEdge;
913 for (int guard = 0; guard < 10000000; ++guard) {
914 const int p = m_tris[t].v[(e + 1) % 3], q = m_tris[t].v[(e + 2) % 3];
915 if (m_tris[t].constrained[e]) {
916 m_errorMsg = Storage::message("cdt: constraint crosses another constraint");
917 return false;
918 }
919 crossed.append(std::make_pair(p, q));
920 const int n = m_tris[t].adj[e];
921 if (n < 0) {
922 m_errorMsg = Storage::message("cdt: walked off the triangulation");
923 return false;
924 }
925 int k = 0;
926 for (int i = 0; i < 3; ++i)
927 if (m_tris[n].adj[i] == t) {
928 k = i;
929 break;
930 }
931 const int r = m_tris[n].v[k];
932 if (r == b)
933 break;
934 const double orr = orient(a, b, r);
935 if (orr == 0.0)
936 return insertConstraintImpl(a, r, origin) && insertConstraintImpl(r, b, origin);
937 // Next crossed edge: (p, r) if r is left of a→b (q side), else (r, q).
938 // In n (CCW): v[k]=r, v[k+1]=q, v[k+2]=p. Edge opposite v[k+1] is (p, r)... indices:
939 // edge opposite index j is (v[j+1], v[j+2]).
940 // r left of a→b: exit through (p, r) = (v[k+2], v[k]), opposite k+1;
941 // r right: exit through (r, q) = (v[k], v[k+1]), opposite k+2.
942 e = (orr > 0.0) ? (k + 1) % 3 : (k + 2) % 3;
943 t = n;
944 }
945 }
946
947 // Sloan: flip crossed edges until none crosses a→b.
948 Vector<std::pair<int, int>> newEdges;
949 int spins = 0;
950 while (!crossed.isEmpty()) {
951 const std::pair<int, int> pq = crossed.takeFirst();
952 int te = -1;
953 int t = triangleWithEdge(pq.first, pq.second, &te);
954 if (t < 0)
955 t = triangleWithEdge(pq.second, pq.first, &te);
956 if (t < 0) {
957 m_errorMsg = Storage::message("cdt: lost a crossed edge");
958 return false;
959 }
960 const int n = m_tris[t].adj[te];
961 const int apex = m_tris[t].v[te];
962 int k = 0;
963 for (int i = 0; i < 3; ++i)
964 if (m_tris[n].adj[i] == t) {
965 k = i;
966 break;
967 }
968 const int d = m_tris[n].v[k];
969 // Convex quad test: p and q on opposite sides of apex→d.
970 const int p = m_tris[t].v[(te + 1) % 3], q = m_tris[t].v[(te + 2) % 3];
971 const double s1 = orient(apex, d, p), s2 = orient(apex, d, q);
972 if (!((s1 > 0.0 && s2 < 0.0) || (s1 < 0.0 && s2 > 0.0))) {
973 crossed.append(pq);
974 if (++spins > 100 * (crossed.size() + 1)) {
975 m_errorMsg = Storage::message("cdt: constraint recovery stalled");
976 return false;
977 }
978 continue;
979 }
980 spins = 0;
981 flip(t, te);
982 // New edge (apex, d): does it still cross a→b?
983 const double o1 = orient(a, b, apex), o2 = orient(a, b, d);
984 const bool isTarget = (apex == a && d == b) || (apex == b && d == a);
985 if (!isTarget && ((o1 > 0.0 && o2 < 0.0) || (o1 < 0.0 && o2 > 0.0)))
986 crossed.append(std::make_pair(apex, d));
987 else if (!isTarget)
988 newEdges.append(std::make_pair(apex, d));
989 }
990 markConstrained(a, b);
991 record(a, b);
992 // Restore the Delaunay property on the edges created by the flips.
993 for (const std::pair<int, int> &ed : newEdges) {
994 int e2 = -1;
995 int t = triangleWithEdge(ed.first, ed.second, &e2);
996 if (t < 0)
997 t = triangleWithEdge(ed.second, ed.first, &e2);
998 if (t >= 0)
999 legalize(t, e2);
1000 }
1001 return true;
1002}
1003
1004// ── Regions ─────────────────────────────────────────────────────────────
1005
1007{
1008 Vector<int> stack;
1009 for (int i = 0; i < m_tris.size(); ++i) {
1010 const Triangle &T = m_tris[i];
1011 if (!T.alive)
1012 continue;
1013 if (isSuperVertex(T.v[0]) || isSuperVertex(T.v[1]) || isSuperVertex(T.v[2])) {
1014 m_tris[i].alive = false;
1015 --m_liveTriangles;
1016 stack.append(i);
1017 }
1018 }
1019 while (!stack.isEmpty()) {
1020 const int t = stack.takeLast();
1021 for (int i = 0; i < 3; ++i) {
1022 const int n = m_tris[t].adj[i];
1023 if (n < 0 || !m_tris[n].alive || m_tris[t].constrained[i])
1024 continue;
1025 m_tris[n].alive = false;
1026 --m_liveTriangles;
1027 stack.append(n);
1028 }
1029 }
1030}
1031
1033{
1034 for (Triangle &T : m_tris)
1035 if (T.alive && (isSuperVertex(T.v[0]) || isSuperVertex(T.v[1]) || isSuperVertex(T.v[2]))) {
1036 T.alive = false;
1037 --m_liveTriangles;
1038 }
1039}
1040
1041template <class Storage> int BasicConstrainedDelaunay<Storage>::removeRegionAt(const Point &p)
1042{
1043 const int t0 = locate(p);
1044 if (t0 < 0)
1045 return 0;
1046 Vector<int> stack{t0};
1047 m_tris[t0].alive = false;
1048 --m_liveTriangles;
1049 int removed = 1;
1050 while (!stack.isEmpty()) {
1051 const int t = stack.takeLast();
1052 for (int i = 0; i < 3; ++i) {
1053 const int n = m_tris[t].adj[i];
1054 if (n < 0 || !m_tris[n].alive || m_tris[t].constrained[i])
1055 continue;
1056 m_tris[n].alive = false;
1057 --m_liveTriangles;
1058 ++removed;
1059 stack.append(n);
1060 }
1061 }
1062 return removed;
1063}
1064
1065// Seed by topology, not an epsilon-offset point (which can cross a thin region).
1066template <class Storage> int BasicConstrainedDelaunay<Storage>::removeRegionLeftOf(int a, int b)
1067{
1068 if (!isConstrained(a, b))
1069 return 0;
1070 Vector<int> stack;
1071 const auto chain = constrainedChain(a, b);
1072 for (int k = 0; k + 1 < chain.size(); ++k) {
1073 Vector<int> around;
1074 trianglesAround(chain[k], &around);
1075 for (int t : around) {
1076 const auto &tri = m_tris[t];
1077 if (!tri.alive)
1078 continue;
1079 bool hasB = false;
1080 int apex = -1;
1081 for (int v : tri.v) {
1082 if (v == chain[k + 1])
1083 hasB = true;
1084 else if (v != chain[k])
1085 apex = v;
1086 }
1087 if (hasB && apex >= 0 && orient(a, b, apex) > 0)
1088 stack.append(t);
1089 }
1090 }
1091 int removed = 0;
1092 while (!stack.isEmpty()) {
1093 const int t = stack.takeLast();
1094 if (!m_tris[t].alive)
1095 continue;
1096 m_tris[t].alive = false;
1097 --m_liveTriangles;
1098 ++removed;
1099 for (int e = 0; e < 3; ++e) {
1100 const int n = m_tris[t].adj[e];
1101 if (n >= 0 && m_tris[n].alive && !m_tris[t].constrained[e])
1102 stack.append(n);
1103 }
1104 }
1105 return removed;
1106}
1107
1108// ── Quality refinement ──────────────────────────────────────────────────
1109// Ruppert's algorithm with Shewchuk's refinements, as Triangle implements
1110// them (workplans/MESH_TRIANGLE_ENGINE_PLAN_2026-09-30.md §4).
1111
1112template <class Storage> void BasicConstrainedDelaunay<Storage>::setFixedConstraint(int a, int b)
1113{
1114 const Vector<int> chain = constrainedChain(a, b);
1115 for (int i = 0; i + 1 < chain.size(); ++i)
1116 m_fixedSub.insert(edgeKey64(chain[i], chain[i + 1]));
1117}
1118
1119template <class Storage> bool BasicConstrainedDelaunay<Storage>::isFixedSub(int a, int b) const
1120{
1121 return !m_fixedSub.isEmpty() && m_fixedSub.contains(edgeKey64(a, b));
1122}
1123
1126template <class Storage>
1127bool BasicConstrainedDelaunay<Storage>::subsegmentEncroached(int a, int b) const
1128{
1129 const Point &A = m_pts[a], &B = m_pts[b];
1130 for (int dir = 0; dir < 2; ++dir) {
1131 int e = -1;
1132 const int t = dir == 0 ? triangleWithEdge(a, b, &e) : triangleWithEdge(b, a, &e);
1133 if (t < 0 || !m_tris[t].alive)
1134 continue;
1135 const int c = m_tris[t].v[e];
1136 if (isSuperVertex(c))
1137 continue;
1138 const Point &C = m_pts[c];
1139 if ((A.x() - C.x()) * (B.x() - C.x()) + (A.y() - C.y()) * (B.y() - C.y()) < 0.0)
1140 return true;
1141 }
1142 return false;
1143}
1144
1150template <class Storage> int BasicConstrainedDelaunay<Storage>::splitSubsegment(int a, int b)
1151{
1152 int e = -1;
1153 int t = triangleWithEdge(a, b, &e);
1154 if (t < 0)
1155 t = triangleWithEdge(b, a, &e);
1156 if (t < 0)
1157 return -1;
1158 const std::uint64_t key = edgeKey64(a, b);
1159 const std::uint64_t origin = m_segOrigin.value(key, key);
1160 const std::uint64_t piece = m_segPiece.value(key, key);
1161 const Vector<std::uint64_t> extra = m_segOriginExtra.values(key);
1162
1163 auto acuteAt = [&](int x, int other) {
1164 if (x >= m_superBase)
1165 return false; // refinement vertex, not an input corner
1166 const Point &X
1167 = m_pts[x], &O = m_pts[other];
1168 Vector<int> fan;
1169 trianglesAround(x, &fan);
1170 for (int ft : fan) {
1171 const Triangle &T = m_tris[ft];
1172 const int i = edgeIndex(ft, x);
1173 if (i < 0)
1174 continue;
1175 for (int k = 1; k <= 2; ++k) {
1176 const int w = T.v[(i + k) % 3];
1177 const int ei = (i + (k == 1 ? 2 : 1)) % 3;
1178 if (!T.constrained[ei] || w == other)
1179 continue;
1180 const Point &W = m_pts[w];
1181 if ((W.x() - X.x()) * (O.x() - X.x()) + (W.y() - X.y()) * (O.y() - X.y()) > 0.0)
1182 return true;
1183 }
1184 }
1185 return false;
1186 };
1187 const Point A = m_pts[a], B = m_pts[b];
1188 const double len = std::sqrt(dist2(A, B));
1189 if (!(len > 0.0) || !std::isfinite(len))
1190 return -1;
1191 const bool acA = acuteAt(a, b), acB = acuteAt(b, a);
1192 double split = 0.5;
1193 if (acA != acB) {
1194 double pw = 1.0;
1195 while (len > 3.0 * pw)
1196 pw *= 2.0;
1197 while (len < 1.5 * pw)
1198 pw *= 0.5;
1199 split = pw / len;
1200 if (acB)
1201 split = 1.0 - split;
1202 }
1203 const Point p = A + (B - A) * split;
1204 if (p == A || p == B)
1205 return -1; // below floating-point resolution
1206 const int v = m_pts.size();
1207 m_pts.append(p);
1208 if (!m_origins.isEmpty())
1209 m_origins.append(0);
1210 m_vertexTri.append(-1);
1211 if (!m_origins.isEmpty())
1212 m_origins[v] = ((m_origins[a] | m_origins[b]) & 127u) | SegmentSplit;
1213 splitEdge(t, e, v); // topological split: both halves stay constrained
1214 m_segOrigin.remove(key);
1215 m_segPiece.remove(key);
1216 m_segOriginExtra.remove(key);
1217 for (const std::uint64_t half : {edgeKey64(a, v), edgeKey64(v, b)}) {
1218 m_segOrigin.insert(half, origin);
1219 m_segPiece.insert(half, piece);
1220 for (std::uint64_t o : extra)
1221 m_segOriginExtra.insert(half, o);
1222 }
1223 m_vertexSeg.insert(v, piece);
1224 return v;
1225}
1226
1233template <class Storage>
1234bool BasicConstrainedDelaunay<Storage>::exemptShortestEdge(int u, int v) const
1235{
1236 const auto iu = m_vertexSeg.constFind(u), iv = m_vertexSeg.constFind(v);
1237 if (iu == m_vertexSeg.constEnd() || iv == m_vertexSeg.constEnd() || iu.value() == iv.value())
1238 return false;
1239 const int a1 = keyLo(iu.value()), b1 = keyHi(iu.value());
1240 const int a2 = keyLo(iv.value()), b2 = keyHi(iv.value());
1241 int j = -1;
1242 if (a1 == a2 || a1 == b2)
1243 j = a1;
1244 else if (b1 == a2 || b1 == b2)
1245 j = b1;
1246 if (j < 0)
1247 return false;
1248 const double d1 = dist2(m_pts[u], m_pts[j]), d2 = dist2(m_pts[v], m_pts[j]);
1249 return d1 < 1.001 * d2 && d1 > 0.999 * d2;
1250}
1251
1252template <class Storage> bool BasicConstrainedDelaunay<Storage>::smallAngleExempt(int t) const
1253{
1254 const Triangle &T = m_tris[t];
1255 double best = std::numeric_limits<double>::infinity();
1256 int s = 0;
1257 for (int k = 0; k < 3; ++k) {
1258 const double l = dist2(m_pts[T.v[(k + 1) % 3]], m_pts[T.v[(k + 2) % 3]]);
1259 if (l < best) {
1260 best = l;
1261 s = k;
1262 }
1263 }
1264 return exemptShortestEdge(T.v[(s + 1) % 3], T.v[(s + 2) % 3]);
1265}
1266
1267template <class Storage> bool BasicConstrainedDelaunay<Storage>::touchesFixed(int t) const
1268{
1269 if (m_fixedSub.isEmpty())
1270 return false;
1271 for (int k = 0; k < 3; ++k) {
1272 const int x = m_tris[t].v[k];
1273 Vector<int> fan;
1274 trianglesAround(x, &fan);
1275 for (int ft : fan) {
1276 const Triangle &T = m_tris[ft];
1277 const int i = edgeIndex(ft, x);
1278 if (i < 0)
1279 continue;
1280 for (int kk = 1; kk <= 2; ++kk) {
1281 const int ei = (i + (kk == 1 ? 2 : 1)) % 3;
1282 if (T.constrained[ei] && m_fixedSub.contains(edgeKey64(x, T.v[(i + kk) % 3])))
1283 return true;
1284 }
1285 }
1286 }
1287 return false;
1288}
1289
1290// Build and legalize a cavity before touching shared topology. The ring is
1291// ordered by the closed fan, so boundary edges retain their direction and flags.
1292template <class Storage>
1293bool BasicConstrainedDelaunay<Storage>::prepareRemoval(int v, Removal *out) const
1294{
1295 if (v < m_superBase + 3 || !isVertexActive(v) || m_vertexSeg.contains(v))
1296 return false;
1297 Removal r;
1298 trianglesAround(v, &r.star);
1299 if (r.star.size() < 3 || r.star.size() > 128)
1300 return false;
1301 for (int t : r.star) {
1302 const auto &T = m_tris[t];
1303 const int i = edgeIndex(t, v);
1304 if (!T.alive || i < 0 || T.constrained[(i + 1) % 3] || T.constrained[(i + 2) % 3] ||
1305 T.adj[(i + 1) % 3] < 0 || T.adj[(i + 2) % 3] < 0)
1306 return false;
1307 for (int k = 0; k < 3; ++k)
1308 if (isSuperVertex(T.v[k]))
1309 return false;
1310 r.ring.append(T.v[(i + 1) % 3]);
1311 }
1312 const int n = r.ring.size();
1313 for (int j = 0; j < n; ++j) {
1314 const auto &T = m_tris[r.star[j]];
1315 if (T.v[(edgeIndex(r.star[j], v) + 2) % 3] != r.ring[(j + 1) % n])
1316 return false;
1317 }
1318 auto triangle = [](int a, int b, int c) {
1319 return Triangle{{a, b, c}, {-1, -1, -1}, {false, false, false}, true};
1320 };
1321 Vector<int> polygon = r.ring;
1322 while (polygon.size() > 3) {
1323 bool clipped = false;
1324 for (int j = 0; j < polygon.size(); ++j) {
1325 const int a = polygon[(j + polygon.size() - 1) % polygon.size()], b = polygon[j],
1326 c = polygon[(j + 1) % polygon.size()];
1327 if (!(orient(a, b, c) > 0))
1328 continue;
1329 bool occupied = false;
1330 for (int q : polygon)
1331 if (q != a && q != b && q != c && orient(a, b, q) >= 0 && orient(b, c, q) >= 0 &&
1332 orient(c, a, q) >= 0) {
1333 occupied = true;
1334 break;
1335 }
1336 if (occupied)
1337 continue;
1338 r.replacement.append(triangle(a, b, c));
1339 polygon.removeAt(j);
1340 clipped = true;
1341 break;
1342 }
1343 if (!clipped)
1344 return false;
1345 }
1346 if (!(orient(polygon[0], polygon[1], polygon[2]) > 0))
1347 return false;
1348 r.replacement.append(triangle(polygon[0], polygon[1], polygon[2]));
1349 // Lawson flips confined to scratch triangles. Never call the global
1350 // legalizer after quality gates: it may change triangles outside the star.
1351 bool settled = false;
1352 for (int guard = 0; guard < 4 * n * n; ++guard) {
1353 bool flipped = false;
1354 for (int i = 0; i < r.replacement.size() && !flipped; ++i)
1355 for (int j = i + 1; j < r.replacement.size() && !flipped; ++j)
1356 for (int e = 0; e < 3 && !flipped; ++e)
1357 for (int f = 0; f < 3 && !flipped; ++f) {
1358 auto &T = r.replacement[i];
1359 auto &N = r.replacement[j];
1360 const int a = T.v[e], b = T.v[(e + 1) % 3], c = T.v[(e + 2) % 3],
1361 d = N.v[f];
1362 if (b != N.v[(f + 2) % 3] || c != N.v[(f + 1) % 3])
1363 continue;
1364 if (orient(a, b, d) <= 0 || orient(a, d, c) <= 0 ||
1365 !inCircle(T.v[0], T.v[1], T.v[2], d))
1366 continue;
1367 T = triangle(a, b, d);
1368 N = triangle(a, d, c);
1369 flipped = true;
1370 }
1371 if (!flipped) {
1372 settled = true;
1373 break;
1374 }
1375 }
1376 if (!settled)
1377 return false;
1378 for (int i = 0; i < r.replacement.size(); ++i)
1379 for (int e = 0; e < 3; ++e) {
1380 auto &T = r.replacement[i];
1381 const int a = T.v[(e + 1) % 3], b = T.v[(e + 2) % 3];
1382 bool found = false;
1383 for (int j = 0; j < n; ++j)
1384 if (a == r.ring[j] && b == r.ring[(j + 1) % n]) {
1385 const auto &old = m_tris[r.star[j]];
1386 const int k = edgeIndex(r.star[j], v), neighbour = old.adj[k];
1387 T.adj[e] = neighbour;
1388 T.constrained[e] = old.constrained[k];
1389 found = true;
1390 // Conservatively reject a cavity whose outer edge would need a
1391 // flip. Outside triangles are never modified by legalization.
1392 if (neighbour >= 0 && !T.constrained[e]) {
1393 const auto &N = m_tris[neighbour];
1394 if (!N.alive)
1395 return false;
1396 for (int f = 0; f < 3; ++f)
1397 if (N.adj[f] == r.star[j] && inCircle(T.v[0], T.v[1], T.v[2], N.v[f]))
1398 return false;
1399 }
1400 break;
1401 }
1402 if (found)
1403 continue;
1404 for (int j = 0; j < r.replacement.size() && !found; ++j)
1405 if (i != j)
1406 for (int f = 0; f < 3; ++f)
1407 if (r.replacement[j].v[(f + 1) % 3] == b &&
1408 r.replacement[j].v[(f + 2) % 3] == a) {
1409 T.adj[e] = r.star[j];
1410 found = true;
1411 break;
1412 }
1413 if (!found)
1414 return false;
1415 }
1416 *out = std::move(r);
1417 return true;
1418}
1419
1420template <class Storage>
1421void BasicConstrainedDelaunay<Storage>::commitRemoval(int v, const Removal &r)
1422{
1423 // Repair external backlinks before reusing any old slot.
1424 for (int j = 0; j < r.ring.size(); ++j) {
1425 const int old = r.star[j], k = edgeIndex(old, v), neighbour = m_tris[old].adj[k];
1426 if (neighbour < 0)
1427 continue;
1428 int replacement = -1;
1429 for (int i = 0; i < r.replacement.size(); ++i)
1430 for (int e = 0; e < 3; ++e)
1431 if (r.replacement[i].v[(e + 1) % 3] == r.ring[j] &&
1432 r.replacement[i].v[(e + 2) % 3] == r.ring[(j + 1) % r.ring.size()])
1433 replacement = r.star[i];
1434 for (int e = 0; e < 3; ++e)
1435 if (m_tris[neighbour].v[(e + 1) % 3] == r.ring[(j + 1) % r.ring.size()] &&
1436 m_tris[neighbour].v[(e + 2) % 3] == r.ring[j])
1437 m_tris[neighbour].adj[e] = replacement;
1438 }
1439 for (int t : r.star) {
1440 m_liveTriangles -= m_tris[t].alive ? 1 : 0;
1441 m_tris[t].alive = false;
1442 for (int &a : m_tris[t].adj)
1443 a = -1;
1444 }
1445 for (int i = 0; i < r.replacement.size(); ++i) {
1446 const int t = r.star[i];
1447 m_tris[t] = r.replacement[i];
1448 m_liveTriangles += m_tris[t].alive ? 1 : 0;
1449 for (int q : m_tris[t].v)
1450 m_vertexTri[q] = t;
1451 if (m_triangleChanged)
1452 m_triangleChanged(t);
1453 }
1454 m_vertexTri[v] = -1;
1455 m_lastLocate = r.star[0];
1456}
1457
1458template <class Storage> bool BasicConstrainedDelaunay<Storage>::removeVertex(int v)
1459{
1460 Removal r;
1461 if (!prepareRemoval(v, &r))
1462 return false;
1463 commitRemoval(v, r);
1464 return true;
1465}
1466
1467template <class Storage>
1469{
1470 QualityReport rep;
1471 const bool resolutionOrder = opt.coarseningOrder == CoarseningOrder::ResolutionAware;
1472 if ((opt.coarseningOrder != CoarseningOrder::LegacyFlatness && !resolutionOrder) ||
1473 (resolutionOrder &&
1474 (!opt.coarseningTargetSize || !(opt.coarseningReferenceSize > 0) ||
1475 !std::isfinite(opt.coarseningReferenceSize) || !(opt.normalVerticalToXY > 0) ||
1476 !std::isfinite(opt.normalVerticalToXY))) ||
1477 (opt.terrainToleranceForFootprint &&
1478 (!(opt.terrainTolerance > 0) || !opt.terrainError || !opt.terrainElevationAt))) {
1479 rep.invalidPolicy = true;
1480 return rep;
1481 }
1482 auto triangleBox = [&](const Triangle &cell) {
1483 double x0 = m_pts[cell.v[0]].x(), x1 = x0, y0 = m_pts[cell.v[0]].y(), y1 = y0;
1484 for (int k = 1; k < 3; ++k) {
1485 const auto p = m_pts[cell.v[k]];
1486 x0 = std::min(x0, p.x());
1487 x1 = std::max(x1, p.x());
1488 y0 = std::min(y0, p.y());
1489 y1 = std::max(y1, p.y());
1490 }
1491 return Box(Point(x0, y0), Point(x1, y1));
1492 };
1493 auto toleranceFor = [&](const Triangle &cell) {
1494 const double value = opt.terrainToleranceForFootprint
1495 ? opt.terrainToleranceForFootprint(triangleBox(cell))
1496 : opt.terrainTolerance;
1497 if (value > 0 && std::isfinite(value))
1498 return value;
1499 if (opt.terrainToleranceForFootprint)
1500 rep.invalidPolicy = true;
1501 return std::numeric_limits<double>::quiet_NaN();
1502 };
1503 const double theta = std::clamp(opt.minAngleDeg, 0.0, 60.0) * M_PI / 180.0;
1504 const double sinMin = std::sin(theta);
1505 // Üngör's off-centre at Triangle's 0.475 factor: the new triangle on the
1506 // shortest edge gets an apex angle just over the bound.
1507 const double offK =
1508 theta > 0.0 ? 0.475 * std::sqrt((1.0 + std::cos(theta)) / (1.0 - std::cos(theta))) : 0.0;
1509 bool stop = false;
1510 const double minEdge2 = opt.minEdge > 0.0 ? opt.minEdge * opt.minEdge : 0.0;
1511 auto tooShortToSplit = [&](int a, int b) {
1512 return minEdge2 > 0.0 && dist2(m_pts[a], m_pts[b]) < 4.0 * minEdge2;
1513 };
1514 const bool terrain = opt.terrainError && opt.terrainElevationAt && opt.terrainTolerance > 0;
1515 // Terrain insertion must respect nearby vertices beyond the source
1516 // triangle too. Quality/constraint repairs retain their separate floor.
1517 const double terrainSpacing = std::max(opt.terrainMinSpacing, opt.minEdge);
1519 auto terrainKey = [&](const Point &p) {
1520 return std::make_pair(std::int64_t(std::floor(p.x() / terrainSpacing)),
1521 std::int64_t(std::floor(p.y() / terrainSpacing)));
1522 };
1523 auto indexTerrainVertex = [&](int v) {
1524 if (terrain && terrainSpacing > 0 && !isSuperVertex(v))
1525 terrainGrid[terrainKey(m_pts[v])].append(v);
1526 };
1527 auto rebuildTerrainGrid = [&] {
1528 terrainGrid.clear();
1529 for (int v = 0; v < m_pts.size(); ++v)
1530 indexTerrainVertex(v);
1531 };
1532 auto terrainClear = [&](const Point &p) {
1533 if (!(terrainSpacing > 0))
1534 return true;
1535 const auto key = terrainKey(p);
1536 for (int dy = -1; dy <= 1; ++dy)
1537 for (int dx = -1; dx <= 1; ++dx) {
1538 const auto it =
1539 terrainGrid.constFind(std::make_pair(key.first + dx, key.second + dy));
1540 if (it != terrainGrid.cend())
1541 for (int v : *it)
1542 if (dist2(p, m_pts[v]) < terrainSpacing * terrainSpacing * (1.0 - 1e-12))
1543 return false;
1544 }
1545 return true;
1546 };
1547 if (terrain)
1548 rebuildTerrainGrid();
1549 m_terrainElevations.clear();
1550 auto &heights = m_terrainElevations;
1551 auto terrainError = [&](int t, Point *p) {
1552 const auto &T = m_tris[t];
1553 while (heights.size() < m_pts.size())
1554 heights.append(std::numeric_limits<double>::infinity());
1555 Point xy[3];
1556 double z[3];
1557 for (int k = 0; k < 3; ++k) {
1558 const int v = T.v[k];
1559 xy[k] = m_pts[v];
1560 if (std::isinf(heights[v])) {
1561 const double h = opt.terrainElevationAt(xy[k].x(), xy[k].y());
1562 heights[v] = std::isfinite(h) ? h : std::numeric_limits<double>::quiet_NaN();
1563 }
1564 z[k] = heights[v];
1565 }
1566 return opt.terrainError(xy, z, p);
1567 };
1568 // The terrain error is a pure function of a triangle's ordered vertices
1569 // (heights never change once set), so the final pass may reuse the last
1570 // finite value measured for the same triple in the same slot.
1571 struct Measured {
1572 int v[3] = {-1, -1, -1};
1573 double e = 0;
1574 };
1575 Vector<Measured> measured;
1576 auto measure = [&](int t, Point *p) {
1577 const double e = terrainError(t, p);
1578 if (std::isfinite(e)) {
1579 if (measured.size() <= t)
1580 measured.resize(std::max<std::ptrdiff_t>(t + 1, measured.size() * 3 / 2));
1581 Measured &m = measured[t];
1582 for (int k = 0; k < 3; ++k)
1583 m.v[k] = m_tris[t].v[k];
1584 m.e = e;
1585 }
1586 return e;
1587 };
1588 int reason = 0; // 1 size, 2 angle, 3 terrain; count successful inserts only.
1589 bool repairing = false;
1590 int repairBegin = 0;
1591 auto footprintCap = [&](const Triangle &t) {
1592 if (!opt.maximumAreaForTriangle)
1593 return 0.;
1594 const Point xy[3] = {m_pts[t.v[0]], m_pts[t.v[1]], m_pts[t.v[2]]};
1595 return opt.maximumAreaForTriangle(xy);
1596 };
1597
1598 // Point for a bad triangle; false when it meets both bounds.
1599 auto badPoint = [&](int t, Point *out) {
1600 reason = 0;
1601 const Triangle &T = m_tris[t];
1602 if (!T.alive || isSuperVertex(T.v[0]) || isSuperVertex(T.v[1]) || isSuperVertex(T.v[2]))
1603 return false;
1604 const Point &A = m_pts[T.v[0]], &B = m_pts[T.v[1]], &C = m_pts[T.v[2]];
1605 const double cross = (B.x() - A.x()) * (C.y() - A.y()) - (B.y() - A.y()) * (C.x() - A.x());
1606 if (!(cross > 0.0))
1607 return false;
1608 const double l[3] = {dist2(B, C), dist2(C, A), dist2(A, B)}; // edge opposite v[i]
1609 const int s = (l[0] <= l[1] && l[0] <= l[2]) ? 0 : (l[1] <= l[2] ? 1 : 2);
1610 bool bad = false;
1611 if (opt.hAt) {
1612 const Point g = (A + B + C) / 3.0;
1613 const double h = opt.hAt(g.x(), g.y());
1614 if (h > 0.0 && 0.5 * cross > kEquilateralArea * h * h) {
1615 bad = true;
1616 reason = 1;
1617 }
1618 }
1619 if (!bad && opt.maximumAreaForTriangle) {
1620 const double cap = footprintCap(T);
1621 if (cap > 0 && .5 * cross > cap * (1 + 1e-10)) {
1622 bad = true;
1623 reason = 1;
1624 }
1625 }
1626 if (!bad && repairing && opt.maximumAdjacentRatio >= 1) {
1627 for (int neighbour : T.adj) {
1628 if (neighbour < 0 || !m_tris[neighbour].alive)
1629 continue;
1630 const auto &other = m_tris[neighbour];
1631 if (isSuperVertex(other.v[0]) || isSuperVertex(other.v[1]) ||
1632 isSuperVertex(other.v[2]))
1633 continue;
1634 const double otherArea =
1635 std::abs(orientPts(m_pts[other.v[0]], m_pts[other.v[1]], m_pts[other.v[2]])) *
1636 .5;
1637 if (std::sqrt(.5 * cross / otherArea) > opt.maximumAdjacentRatio * (1 + 1e-10)) {
1638 bad = true;
1639 reason = 1;
1640 break;
1641 }
1642 }
1643 if (!bad && opt.fixedNeighbourSize)
1644 for (int k = 0; k < 3; ++k) {
1645 const double neighbour =
1646 opt.fixedNeighbourSize(T.v[(k + 1) % 3], T.v[(k + 2) % 3]);
1647 if (neighbour > 0 && std::sqrt(.5 * cross / kEquilateralArea) / neighbour >
1648 opt.maximumAdjacentRatio * (1 + 1e-10)) {
1649 bad = true;
1650 reason = 1;
1651 break;
1652 }
1653 }
1654 }
1655 if (!bad && sinMin > 0.0 && l[s] >= minEdge2) {
1656 const double sinA =
1657 cross /
1658 std::sqrt(l[(s + 1) % 3] * l[(s + 2) % 3]); // angle opposite the shortest edge
1659 if (sinA < sinMin && !exemptShortestEdge(T.v[(s + 1) % 3], T.v[(s + 2) % 3])) {
1660 bad = true;
1661 reason = 2;
1662 }
1663 }
1664 if (!bad && terrain && (!opt.terrainWorstFirst || repairing)) {
1665 const double e = measure(t, out);
1666 if (std::isfinite(e) && e > toleranceFor(T)) {
1667 const double clearance = std::max(opt.terrainMinSpacing, opt.minEdge);
1668 // A protected elevation or minimum spacing may make the
1669 // tolerance impossible. Leave it for the explicit final report.
1670 if (std::min({dist2(*out, A), dist2(*out, B), dist2(*out, C)}) <=
1671 clearance * clearance)
1672 return false;
1673 reason = 3;
1674 return true;
1675 }
1676 }
1677 if (!bad)
1678 return false;
1679 // Shortest edge P→Q with R on its left (counter-clockwise order).
1680 const Point &P = m_pts[T.v[(s + 1) % 3]], &Q = m_pts[T.v[(s + 2) % 3]], &R = m_pts[T.v[s]];
1681 const double bx = Q.x() - P.x(), by = Q.y() - P.y(), cx = R.x() - P.x(), cy = R.y() - P.y();
1682 const double d = 2.0 * (bx * cy - by * cx);
1683 if (!(d > 0.0))
1684 return false;
1685 const double b2 = bx * bx + by * by, c2 = cx * cx + cy * cy;
1686 double ux = (cy * b2 - by * c2) / d, uy = (bx * c2 - cx * b2) / d;
1687 if (offK > 0.0) {
1688 const double mx = 0.5 * bx, my = 0.5 * by;
1689 const double ox = mx - offK * by, oy = my + offK * bx;
1690 if ((ox - mx) * (ox - mx) + (oy - my) * (oy - my) <
1691 (ux - mx) * (ux - mx) + (uy - my) * (uy - my)) {
1692 ux = ox;
1693 uy = oy;
1694 }
1695 }
1696 *out = Point(P.x() + ux, P.y() + uy);
1697 return std::isfinite(out->x()) && std::isfinite(out->y());
1698 };
1699
1700 // Straight walk from triangle t's centroid to p. Returns the live
1701 // triangle containing p, or -1 with *blockT/*blockE set to the first
1702 // constrained edge the walk would cross (-1 when lost).
1703 auto walkTo = [&](int t, const Point &p, int *blockT, int *blockE) {
1704 *blockT = *blockE = -1;
1705 const Triangle &T0 = m_tris[t];
1706 const Point g = (m_pts[T0.v[0]] + m_pts[T0.v[1]] + m_pts[T0.v[2]]) / 3.0;
1707 const int cap = 4 * m_tris.size() + 16;
1708 for (int step = 0; step < cap; ++step) {
1709 const Triangle &T = m_tris[t];
1710 double o[3];
1711 for (int i = 0; i < 3; ++i)
1712 o[i] = orient(T.v[(i + 1) % 3], T.v[(i + 2) % 3], p);
1713 if (o[0] >= 0.0 && o[1] >= 0.0 && o[2] >= 0.0)
1714 return t;
1715 int exit = -1;
1716 for (int i = 0; i < 3 && exit < 0; ++i) {
1717 if (!(o[i] < 0.0))
1718 continue;
1719 const double s1 = orientPts(g, p, m_pts[T.v[(i + 1) % 3]]);
1720 const double s2 = orientPts(g, p, m_pts[T.v[(i + 2) % 3]]);
1721 if ((s1 <= 0.0 && s2 >= 0.0) || (s1 >= 0.0 && s2 <= 0.0))
1722 exit = i;
1723 }
1724 if (exit < 0)
1725 for (int i = 0; i < 3 && exit < 0; ++i)
1726 if (o[i] < 0.0)
1727 exit = i;
1728 if (T.constrained[exit]) {
1729 *blockT = t;
1730 *blockE = exit;
1731 return -1;
1732 }
1733 const int n = T.adj[exit];
1734 if (n < 0 || !m_tris[n].alive)
1735 return -1;
1736 t = n;
1737 }
1738 return -1;
1739 };
1740
1741 // Constrained edges of the insertion cavity of p (triangles whose
1742 // circumcircle holds p, reached without crossing a constraint) whose
1743 // diametral circle holds p.
1744 auto cavityEncroached = [&](int t0, const Point &p, Vector<std::uint64_t> *enc) {
1745 const double pd[2] = {p.x(), p.y()};
1746 Vector<int> stack{t0}, seen{t0};
1747 while (!stack.isEmpty()) {
1748 const int t = stack.takeLast();
1749 const Triangle &T = m_tris[t];
1750 for (int k = 0; k < 3; ++k) {
1751 const int a = T.v[(k + 1) % 3], b = T.v[(k + 2) % 3];
1752 if (T.constrained[k]) {
1753 const Point &A = m_pts[a], &B = m_pts[b];
1754 if ((A.x() - p.x()) * (B.x() - p.x()) + (A.y() - p.y()) * (B.y() - p.y()) < 0.0)
1755 enc->append(edgeKey64(a, b));
1756 continue;
1757 }
1758 const int n = T.adj[k];
1759 if (n < 0 || !m_tris[n].alive || seen.contains(n))
1760 continue;
1761 const Triangle &N = m_tris[n];
1762 if (isSuperVertex(N.v[0]) || isSuperVertex(N.v[1]) || isSuperVertex(N.v[2]))
1763 continue;
1764 const double pa[2] = {m_pts[N.v[0]].x(), m_pts[N.v[0]].y()};
1765 const double pb[2] = {m_pts[N.v[1]].x(), m_pts[N.v[1]].y()};
1766 const double pc[2] = {m_pts[N.v[2]].x(), m_pts[N.v[2]].y()};
1767 if (!(incircle(pa, pb, pc, pd) > 0.0))
1768 continue;
1769 seen.append(n);
1770 stack.append(n);
1771 }
1772 }
1773 };
1774
1775 Vector<std::uint64_t> segQueue;
1776 // Intrusive FIFO angle buckets: one pending entry per triangle, no stale
1777 // history proportional to all insertions, and no O(log N) heap operations.
1778 std::array<int, 32> heads, tails;
1779 heads.fill(-1);
1780 tails.fill(-1);
1781 Vector<int> next(m_tris.size(), -2); // -2 means not queued, -1 end of list
1782 auto enqueue = [&](int t) {
1783 while (next.size() < m_tris.size())
1784 next.append(-2);
1785 const auto &T = m_tris[t];
1786 if (!T.alive || next[t] != -2)
1787 return;
1788 int bucket = 31;
1789 if (opt.prioritizeQuality && sinMin > 0) {
1790 const auto &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
1791 const double cross =
1792 std::abs((b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()));
1793 const double l0 = dist2(a, b), l1 = dist2(b, c), l2 = dist2(c, a);
1794 const double denom = std::sqrt(std::max({l0 * l1, l1 * l2, l2 * l0}));
1795 if (denom > 0)
1796 bucket = std::clamp(int(31 * cross / (denom * sinMin)), 0, 31);
1797 }
1798 next[t] = -1;
1799 if (tails[bucket] >= 0)
1800 next[tails[bucket]] = t;
1801 else
1802 heads[bucket] = t;
1803 tails[bucket] = t;
1804 };
1805 auto dequeue = [&]() {
1806 for (int k = 0; k < 32; ++k)
1807 if (heads[k] >= 0) {
1808 const int t = heads[k];
1809 heads[k] = next[t];
1810 if (heads[k] < 0)
1811 tails[k] = -1;
1812 next[t] = -2;
1813 return t;
1814 }
1815 return -1;
1816 };
1817 m_triangleChanged = enqueue;
1818 // The cell budget counts live triangles: removed regions (exterior,
1819 // holes, patch interiors) leave dead slots that are never refilled.
1821 auto publishProgress = [&] {
1822 if (opt.onProgress) {
1823 GenerationProgress state;
1824 state.stage = progressStage;
1825 state.workingVertices = std::max<std::ptrdiff_t>(0, m_pts.size() - 3);
1826 state.triangles = liveTriangleCount();
1827 state.inserted = rep.inserted;
1828 state.removed = rep.coarsenRemoved;
1829 opt.onProgress(state);
1830 }
1831 };
1832 publishProgress();
1833 const auto clearObserver = detail::scopeExit([&] { m_triangleChanged = {}; });
1834 auto queueEncroachedOf = [&](int t) {
1835 const Triangle &T = m_tris[t];
1836 for (int k = 0; k < 3; ++k) {
1837 if (!T.constrained[k])
1838 continue;
1839 const int a = T.v[(k + 1) % 3], b = T.v[(k + 2) % 3];
1840 if (isSuperVertex(a) || isSuperVertex(b) || isFixedSub(a, b))
1841 continue;
1842 if (subsegmentEncroached(a, b))
1843 segQueue.append(edgeKey64(a, b));
1844 }
1845 };
1846 auto afterInsert = [&](int v) {
1847 indexTerrainVertex(v);
1848 ++rep.inserted;
1849 Vector<int> star;
1850 trianglesAround(v, &star);
1851 for (int t : std::as_const(star))
1852 if (m_tris[t].alive) {
1853 enqueue(t);
1854 queueEncroachedOf(t);
1855 }
1856 if (rep.inserted >= opt.maxInsertions || liveTriangleCount() >= opt.maxTriangles) {
1857 rep.capped = true;
1858 stop = true;
1859 }
1860 if (repairing && rep.inserted - repairBegin >= opt.maximumSizingRepairInsertions)
1861 rep.sizingRepairLimited = true;
1862 if ((rep.inserted & 4095) == 0) {
1863 publishProgress();
1864 if (opt.cancelled && opt.cancelled()) {
1865 rep.cancelled = true;
1866 stop = true;
1867 }
1868 }
1869 };
1870 auto drainSegments = [&]() {
1871 while (!segQueue.isEmpty() && !stop && !(repairing && rep.sizingRepairLimited)) {
1872 const std::uint64_t k = segQueue.takeLast();
1873 const int a = keyLo(k), b = keyHi(k);
1874 if (isFixedSub(a, b) || tooShortToSplit(a, b) || !isConstrained(a, b) ||
1875 !subsegmentEncroached(a, b))
1876 continue;
1877 const int v = splitSubsegment(a, b);
1878 if (v < 0)
1879 continue;
1880 ++rep.segmentSplits;
1881 afterInsert(v);
1882 }
1883 };
1884
1885 for (int i = 0; i < m_tris.size(); ++i)
1886 if (m_tris[i].alive) {
1887 enqueue(i);
1888 queueEncroachedOf(i);
1889 }
1890 if (liveTriangleCount() >= opt.maxTriangles) {
1891 rep.capped = true;
1892 stop = true;
1893 }
1894 drainSegments();
1895
1897 // Insert p for bad triangle t (reason already set), or split the
1898 // subsegments p would encroach. Returns false when nothing changed.
1899 auto tryInsert = [&](int t, Point p) {
1900 if (reason == 3 && !terrainClear(p))
1901 return false;
1902 enc.clear();
1903 int blockT = -1, blockE = -1;
1904 int c = walkTo(t, p, &blockT, &blockE);
1905 if (c < 0) {
1906 if (blockT < 0)
1907 return false; // lost the point: leave the triangle
1908 enc.append(
1909 edgeKey64(m_tris[blockT].v[(blockE + 1) % 3], m_tris[blockT].v[(blockE + 2) % 3]));
1910 } else
1911 cavityEncroached(c, p, &enc);
1912 if (!enc.isEmpty()) {
1913 // Split what the point would encroach instead of inserting it
1914 // (the subsegments need not be encroached by an existing vertex).
1915 bool split = false;
1916 for (std::uint64_t k : std::as_const(enc)) {
1917 const int a = keyLo(k), b = keyHi(k);
1918 if (stop || isFixedSub(a, b) || tooShortToSplit(a, b) || !isConstrained(a, b))
1919 continue;
1920 if (reason == 3 && !terrainClear((m_pts[a] + m_pts[b]) * 0.5))
1921 continue;
1922 const int v = splitSubsegment(a, b);
1923 if (v < 0)
1924 continue;
1925 ++rep.segmentSplits;
1926 split = true;
1927 afterInsert(v);
1928 }
1929 if (!split) {
1930 ++rep.blockedByFixed;
1931 // Size repair may need a skinny triangle against an immutable
1932 // quad edge. An interior insertion preserves that edge exactly;
1933 // ordinary constrained edges must still use segment recovery.
1934 if (!repairing || reason != 1 || !opt.maximumAreaForTriangle)
1935 return false;
1936 const auto &cell = m_tris[t];
1937 const auto a = m_pts[cell.v[0]], b = m_pts[cell.v[1]], cxy = m_pts[cell.v[2]];
1938 const double cap = footprintCap(cell);
1939 if (!(cap > 0) || orientPts(a, b, cxy) * .5 <= cap * (1 + 1e-10))
1940 return false;
1941 const Point center = a + ((b - a) + (cxy - a)) / 3.;
1942 if (!std::isfinite(center.x()) || !std::isfinite(center.y()) ||
1943 std::min({dist2(center, a), dist2(center, b), dist2(center, cxy)}) < minEdge2 ||
1944 orientPts(a, b, center) <= 0 || orientPts(b, cxy, center) <= 0 ||
1945 orientPts(cxy, a, center) <= 0)
1946 return false;
1947 enc.clear();
1948 cavityEncroached(t, center, &enc);
1949 for (std::uint64_t key : enc)
1950 if (!isFixedSub(keyLo(key), keyHi(key)))
1951 return false;
1952 p = center;
1953 c = t;
1954 } else {
1955 enqueue(t); // retried with the subsegments split
1956 drainSegments();
1957 return true;
1958 }
1959 }
1960 m_lastLocate = c;
1961 const int before = m_pts.size();
1962 const int v = insertPoint(p);
1963 if (v < 0 || v < before)
1964 return false; // outside or coincident
1965 addVertexOrigin(v, reason == 1 ? Size : reason == 2 ? Angle : Terrain);
1966 if (reason == 1)
1967 ++rep.sizeInsertions;
1968 else if (reason == 2)
1969 ++rep.qualityInsertions;
1970 else if (reason == 3)
1971 ++rep.terrainInsertions;
1972 afterInsert(v);
1973 drainSegments();
1974 return true;
1975 };
1976 int examined = 0;
1977 auto drainQueue = [&]() {
1978 while (!stop && !rep.invalidPolicy && !(repairing && rep.sizingRepairLimited)) {
1979 const int t = dequeue();
1980 if (t < 0)
1981 break;
1982 if ((++examined & 4095) == 0) {
1983 publishProgress();
1984 if (opt.cancelled && opt.cancelled()) {
1985 rep.cancelled = true;
1986 break;
1987 }
1988 }
1989 Point p;
1990 if (!badPoint(t, &p))
1991 continue;
1992 tryInsert(t, p);
1993 }
1994 };
1995 drainQueue();
1996
1997 // Non-degrading smoothing (MESH_REGIONAL_TRIQUAD_PLAN D-R6): before any
1998 // terrain point is placed, so no sampled height is moved off its spot.
1999 if (opt.smoothingPasses > 0 && (!terrain || opt.terrainWorstFirst) && !stop && !rep.cancelled) {
2001 publishProgress();
2002 auto minAngleOf = [&](int t) {
2003 const auto &T = m_tris[t];
2004 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2005 const double l[3] = {dist2(b, c), dist2(c, a), dist2(a, b)};
2006 const double cross =
2007 std::abs((b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()));
2008 // sin of the angle opposite the shortest edge
2009 const int s = (l[0] <= l[1] && l[0] <= l[2]) ? 0 : (l[1] <= l[2] ? 1 : 2);
2010 return cross / std::sqrt(l[(s + 1) % 3] * l[(s + 2) % 3]);
2011 };
2012 auto positive = [&](int t) {
2013 const auto &T = m_tris[t];
2014 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2015 return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()) > 0.0;
2016 };
2017 const int firstFree = m_superBase + 3;
2018 Vector<int> star;
2019 for (int pass = 0; pass < opt.smoothingPasses; ++pass) {
2020 for (int v = firstFree; v < m_pts.size(); ++v) {
2021 star.clear();
2022 trianglesAround(v, &star);
2023 if (star.size() < 3)
2024 continue;
2025 bool fixed = false;
2026 double wsum = 0, cx = 0, cy = 0, before = 1e300;
2027 for (int t : std::as_const(star)) {
2028 const auto &T = m_tris[t];
2029 const int i = edgeIndex(t, v);
2030 if (!T.alive || i < 0 || isSuperVertex(T.v[0]) || isSuperVertex(T.v[1]) ||
2031 isSuperVertex(T.v[2]) || T.constrained[(i + 1) % 3] ||
2032 T.constrained[(i + 2) % 3] || T.adj[(i + 1) % 3] < 0 ||
2033 T.adj[(i + 2) % 3] < 0) {
2034 fixed = true;
2035 break;
2036 }
2037 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2038 const double area = 0.5 * std::abs((b.x() - a.x()) * (c.y() - a.y()) -
2039 (b.y() - a.y()) * (c.x() - a.x()));
2040 cx += area * (a.x() + b.x() + c.x()) / 3.0;
2041 cy += area * (a.y() + b.y() + c.y()) / 3.0;
2042 wsum += area;
2043 before = std::min(before, minAngleOf(t));
2044 }
2045 if (fixed || !(wsum > 0.0))
2046 continue;
2047 const Point old = m_pts[v];
2048 m_pts[v] = Point(cx / wsum, cy / wsum);
2049 double after = 1e300;
2050 bool valid = true;
2051 for (int t : std::as_const(star)) {
2052 if (!positive(t)) {
2053 valid = false;
2054 break;
2055 }
2056 after = std::min(after, minAngleOf(t));
2057 }
2058 if (!valid || !(after > before * (1.0 + 1e-9))) {
2059 m_pts[v] = old;
2060 continue;
2061 }
2062 for (int t : std::as_const(star))
2063 if (m_tris[t].alive) {
2064 const int i = edgeIndex(t, v);
2065 if (i >= 0)
2066 legalize(t, i);
2067 }
2068 }
2069 }
2070 }
2071
2072 // Worst-first terrain refinement: with size and angle met, spend the
2073 // remaining cell budget where the surface error is largest, so a capped
2074 // run still has even fidelity. Each insertion restores quality locally,
2075 // then only the triangles it changed are measured again.
2076 if (terrain && opt.terrainWorstFirst && !stop && !rep.cancelled) {
2077 progressStage = GenerationProgress::Stage::Terrain;
2078 publishProgress();
2079 // Smoothing may have moved vertices since the initial grid build.
2080 rebuildTerrainGrid();
2081 struct Candidate {
2082 double e;
2083 int t;
2084 int v[3];
2085 Point p;
2086 };
2087 auto worse = [](const Candidate &a, const Candidate &b) { return a.e < b.e; };
2088 std::priority_queue<Candidate, std::vector<Candidate>, decltype(worse)> heap(worse);
2089 auto consider = [&](int t) {
2090 const Triangle &T = m_tris[t];
2091 if (!T.alive || isSuperVertex(T.v[0]) || isSuperVertex(T.v[1]) || isSuperVertex(T.v[2]))
2092 return;
2093 const Point &A = m_pts[T.v[0]], &B = m_pts[T.v[1]], &C = m_pts[T.v[2]];
2094 if (!((B.x() - A.x()) * (C.y() - A.y()) - (B.y() - A.y()) * (C.x() - A.x()) > 0.0))
2095 return;
2096 Point p;
2097 const double e = measure(t, &p);
2098 const double localTolerance = toleranceFor(T);
2099 if (!std::isfinite(e) || !std::isfinite(localTolerance) || e <= localTolerance)
2100 return;
2101 const double clearance = std::max(opt.terrainMinSpacing, opt.minEdge);
2102 if (std::min({dist2(p, A), dist2(p, B), dist2(p, C)}) <= clearance * clearance)
2103 return;
2104 heap.push({opt.terrainToleranceForFootprint ? e / localTolerance : e,
2105 t,
2106 {T.v[0], T.v[1], T.v[2]},
2107 p});
2108 };
2109 for (int t = 0; t < m_tris.size(); ++t)
2110 consider(t);
2111 Vector<int> changed;
2112 m_triangleChanged = [&](int t) {
2113 enqueue(t);
2114 changed.append(t);
2115 };
2116 while (!heap.empty() && !stop) {
2117 const Candidate c = heap.top();
2118 heap.pop();
2119 const Triangle &T = m_tris[c.t];
2120 if (!T.alive || T.v[0] != c.v[0] || T.v[1] != c.v[1] || T.v[2] != c.v[2])
2121 continue;
2122 if ((++examined & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2123 rep.cancelled = true;
2124 break;
2125 }
2126 changed.clear();
2127 reason = 3;
2128 if (!tryInsert(c.t, c.p))
2129 continue;
2130 drainQueue();
2131 for (int t : std::as_const(changed))
2132 consider(t);
2133 }
2134 m_triangleChanged = enqueue;
2135 }
2136 // Coarsening cannot use refinement witnesses as upper bounds. Only the
2137 // explicit coverage-aware callback (and bounds derived from it) certifies
2138 // replacement triangles. Removed slots and vertex ids remain stable.
2139 m_triangleChanged = {};
2140 if (opt.coarsenPasses > 0 && !rep.cancelled) {
2142 publishProgress();
2143 detail::Timer clock;
2144 clock.start();
2145 rep.coarsenSkippedTerrain = terrain && !opt.terrainErrorBound;
2146 if (!rep.coarsenSkippedTerrain) {
2147 const double unknown = std::numeric_limits<double>::quiet_NaN();
2148 Vector<double> bounds(terrain ? m_tris.size() : 0, unknown);
2149 Vector<unsigned char> attempts(m_pts.size(), 0);
2150 Vector<unsigned> versions(resolutionOrder ? 0 : m_pts.size(), 0);
2151 const auto freeSlots = std::max<std::ptrdiff_t>(0, m_pts.size() - m_superBase - 3);
2152 CoarseningQueue resolutionHeap(resolutionOrder && freeSlots ? m_pts.size() : 0,
2153 resolutionOrder ? freeSlots : 0);
2154 // Serial Morton tiles improve DEM locality; boundary stars are
2155 // allowed because no concurrent topology mutation takes place.
2156 double x0 = std::numeric_limits<double>::infinity(), y0 = x0, x1 = -x0, y1 = -x0;
2157 Vector<char> used(m_pts.size(), 0);
2158 for (const auto &T : m_tris)
2159 if (T.alive)
2160 for (int v : T.v)
2161 if (!isSuperVertex(v)) {
2162 used[v] = 1;
2163 x0 = std::min(x0, m_pts[v].x());
2164 y0 = std::min(y0, m_pts[v].y());
2165 x1 = std::max(x1, m_pts[v].x());
2166 y1 = std::max(y1, m_pts[v].y());
2167 }
2168 auto key = [&](int v, unsigned scale) {
2169 const unsigned x =
2170 x1 > x0
2171 ? unsigned(std::clamp((m_pts[v].x() - x0) / (x1 - x0), 0.0, 1.0) * scale)
2172 : 0;
2173 const unsigned y =
2174 y1 > y0
2175 ? unsigned(std::clamp((m_pts[v].y() - y0) / (y1 - y0), 0.0, 1.0) * scale)
2176 : 0;
2177 return mortonKey(x, y);
2178 };
2179 if (terrain) {
2180 // Capped refinement may not have reached terrain at all.
2181 // Sample each needed elevation once, spatially ordered; the
2182 // assembly stage reuses these same values afterwards.
2183 while (heights.size() < m_pts.size())
2184 heights.append(std::numeric_limits<double>::infinity());
2186 for (int v = 0; v < m_pts.size(); ++v)
2187 if (used[v] && std::isinf(heights[v]))
2188 pending.append({key(v, 65535), v});
2189 std::sort(pending.begin(), pending.end());
2190 for (int i = 0; i < pending.size(); ++i) {
2191 if ((i & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2192 rep.cancelled = true;
2193 break;
2194 }
2195 const int v = pending[i].second;
2196 heights[v] = opt.terrainElevationAt(m_pts[v].x(), m_pts[v].y());
2197 }
2198 }
2199 struct Candidate {
2200 float score;
2201 int v;
2202 unsigned version, tile;
2203 };
2204 auto less = [](const Candidate &a, const Candidate &b) {
2205 if (a.tile != b.tile)
2206 return a.tile > b.tile;
2207 return a.score != b.score ? a.score < b.score : a.v > b.v;
2208 };
2209 std::priority_queue<Candidate, std::vector<Candidate>, decltype(less)> heap(less);
2210 auto height = [&](int v) {
2211 while (heights.size() < m_pts.size())
2212 heights.append(std::numeric_limits<double>::infinity());
2213 if (std::isinf(heights[v]))
2214 heights[v] = opt.terrainElevationAt(m_pts[v].x(), m_pts[v].y());
2215 return heights[v];
2216 };
2217 auto score = [&](int v, const Vector<int> &star) {
2218 if (!terrain)
2219 return 1.0;
2220 std::array<double, 3> sum{0, 0, 0};
2222 for (int t : star) {
2223 const auto &T = m_tris[t];
2224 const Point b = m_pts[T.v[1]] - m_pts[T.v[0]],
2225 c = m_pts[T.v[2]] - m_pts[T.v[0]];
2226 const double scale = resolutionOrder ? opt.normalVerticalToXY : 1.;
2227 const double z = height(T.v[0]), bz = (height(T.v[1]) - z) * scale,
2228 cz = (height(T.v[2]) - z) * scale;
2229 if (!std::isfinite(z) || !std::isfinite(bz) || !std::isfinite(cz))
2230 return -1.0;
2231 std::array<double, 3> normal{b.y() * cz - bz * c.y(), bz * c.x() - b.x() * cz,
2232 b.x() * c.y() - b.y() * c.x()};
2233 const double length = std::hypot(normal[0], normal[1], normal[2]);
2234 if (!(length > 0))
2235 return -1.0;
2236 for (int k = 0; k < 3; ++k) {
2237 sum[k] += normal[k];
2238 normal[k] /= length;
2239 }
2240 normals.append(normal);
2241 }
2242 const double length = std::hypot(sum[0], sum[1], sum[2]);
2243 if (!(length > 0))
2244 return -1.0;
2245 double result = 1;
2246 for (const auto &n : normals)
2247 result =
2248 std::min(result, (n[0] * sum[0] + n[1] * sum[1] + n[2] * sum[2]) / length);
2249 return result;
2250 };
2251 const int limit = std::clamp(opt.coarsenPasses, 1, 10);
2252 auto queue = [&](int v) {
2253 if (v < m_superBase + 3 || !isVertexActive(v) || m_vertexSeg.contains(v) ||
2254 opt.protectedVertices.contains(v) ||
2255 (opt.protectedLocation && opt.protectedLocation(m_pts[v])) ||
2256 attempts[v] >= limit)
2257 return;
2258 Vector<int> star;
2259 if (terrain || resolutionOrder)
2260 trianglesAround(v, &star);
2261 const double flatness = score(v, star);
2262 if (!resolutionOrder) {
2263 heap.push({float(flatness), v, ++versions[v], unsigned(key(v, 31))});
2264 rep.coarsenQueuePeak =
2265 std::max<std::uint64_t>(rep.coarsenQueuePeak, heap.size());
2266 return;
2267 }
2268 Box box;
2269 double totalArea = 0;
2270 bool first = true;
2271 for (int t : star) {
2272 const auto &cell = m_tris[t];
2273 const auto bound = triangleBox(cell);
2274 box = first ? bound : box.united(bound);
2275 first = false;
2276 totalArea +=
2277 .5 * orientPts(m_pts[cell.v[0]], m_pts[cell.v[1]], m_pts[cell.v[2]]);
2278 }
2280 double target = opt.coarseningTargetSize(box);
2281 if (!std::isfinite(target) || target < 0) {
2282 rep.invalidPolicy = true;
2283 return;
2284 }
2285 if (target == 0)
2286 target = opt.coarseningReferenceSize;
2287 const double actual =
2288 star.isEmpty() ? 0 : std::sqrt(totalArea / (star.size() * kEquilateralArea));
2289 const double density = actual / target;
2290 const double importance =
2291 flatness >= -1 ? resolutionRemovalImportance(flatness, actual, target)
2292 : std::numeric_limits<double>::infinity();
2293 const auto compact = [](double value) {
2294 return float(std::min(value, double(std::numeric_limits<float>::max())));
2295 };
2296 resolutionHeap.update(
2297 {compact(importance), compact(density), v, unsigned(key(v, 31))});
2298 rep.coarsenQueuePeak =
2299 std::max<std::uint64_t>(rep.coarsenQueuePeak, resolutionHeap.size());
2300 };
2301 for (int v = m_superBase + 3; v < m_pts.size() && !rep.cancelled && !rep.invalidPolicy;
2302 ++v) {
2303 if ((v & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2304 rep.cancelled = true;
2305 break;
2306 }
2307 queue(v);
2308 }
2309 auto plane = [&](const Triangle &T, const Point &p) {
2310 const auto &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2311 const double z = height(T.v[0]);
2312 const double cross = orientPts(a, b, c);
2313 const double u =
2314 ((p.x() - a.x()) * (c.y() - a.y()) - (p.y() - a.y()) * (c.x() - a.x())) / cross;
2315 const double w =
2316 ((b.x() - a.x()) * (p.y() - a.y()) - (b.y() - a.y()) * (p.x() - a.x())) / cross;
2317 return z + u * (height(T.v[1]) - z) + w * (height(T.v[2]) - z);
2318 };
2319 while (!(resolutionOrder ? resolutionHeap.empty() : heap.empty()) && !rep.cancelled &&
2320 !rep.invalidPolicy) {
2321 Candidate c{};
2322 if (resolutionOrder) {
2323 const auto next = resolutionHeap.pop();
2324 c.v = next.vertex;
2325 } else {
2326 c = heap.top();
2327 heap.pop();
2328 }
2329 const int v = c.v;
2330 if ((!resolutionOrder && c.version != versions[v]) || !isVertexActive(v))
2331 continue;
2332 if ((rep.coarsenAttempts & 255) == 0) {
2333 publishProgress();
2334 if (opt.cancelled && opt.cancelled()) {
2335 rep.cancelled = true;
2336 break;
2337 }
2338 }
2339 ++attempts[v];
2340 ++rep.coarsenAttempts;
2341 Removal r;
2342 if (!prepareRemoval(v, &r))
2343 continue;
2344 double shortest = std::numeric_limits<double>::infinity();
2345 for (int t : r.star)
2346 for (int k = 0; k < 3; ++k)
2347 shortest = std::min(shortest, dist2(m_pts[m_tris[t].v[k]],
2348 m_pts[m_tris[t].v[(k + 1) % 3]]));
2349 bool accepted = true;
2350 for (const auto &T : r.replacement) {
2351 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2352 const double cross = orientPts(a, b, c);
2353 const double l[3] = {dist2(b, c), dist2(c, a), dist2(a, b)};
2354 const int k = l[0] <= l[1] && l[0] <= l[2] ? 0 : l[1] <= l[2] ? 1 : 2;
2355 if (l[k] < shortest * (1 - 1e-12)) {
2356 ++rep.coarsenRejectedEdge;
2357 accepted = false;
2358 break;
2359 }
2360 if (l[k] >= minEdge2 &&
2361 cross / std::sqrt(l[(k + 1) % 3] * l[(k + 2) % 3]) < sinMin &&
2362 !exemptShortestEdge(T.v[(k + 1) % 3], T.v[(k + 2) % 3])) {
2364 accepted = false;
2365 break;
2366 }
2367 const Point g = (a + b + c) / 3;
2368 const double h = opt.hAt ? opt.hAt(g.x(), g.y()) : 0;
2369 if (h > 0 && cross * .5 > kEquilateralArea * h * h) {
2370 ++rep.coarsenRejectedSize;
2371 accepted = false;
2372 break;
2373 }
2374 if (resolutionOrder) {
2375 const double target = opt.coarseningTargetSize(triangleBox(T));
2376 if (!std::isfinite(target) || target < 0) {
2377 rep.invalidPolicy = true;
2378 accepted = false;
2379 break;
2380 }
2381 if (target > 0 && static_cast<long double>(cross) * .5 >
2382 kEquilateralArea * static_cast<long double>(target) *
2383 target * (1 + 1e-10)) {
2384 ++rep.coarsenRejectedSize;
2385 accepted = false;
2386 break;
2387 }
2388 }
2389 const double cap = footprintCap(T);
2390 if (cap > 0 && cross * .5 > cap * (1 + 1e-10)) {
2391 ++rep.coarsenRejectedSize;
2392 accepted = false;
2393 break;
2394 }
2395 }
2396 if (!accepted)
2397 continue;
2398 Vector<double> newBounds;
2399 if (terrain) {
2400 // A necessary condition only: the removed reference height
2401 // must still fit the new plane covering its location.
2402 for (const auto &T : r.replacement)
2403 if (orient(T.v[0], T.v[1], m_pts[v]) >= 0 &&
2404 orient(T.v[1], T.v[2], m_pts[v]) >= 0 &&
2405 orient(T.v[2], T.v[0], m_pts[v]) >= 0) {
2406 const double error = std::abs(plane(T, m_pts[v]) - height(v));
2407 if (!std::isfinite(error) || !std::isfinite(toleranceFor(T)) ||
2408 error > toleranceFor(T)) {
2410 accepted = false;
2411 }
2412 break;
2413 }
2414 for (const auto &T : r.replacement) {
2415 if (!accepted)
2416 break;
2417 double bound = 0;
2418 // The plane difference is affine. Bounding it at all
2419 // three vertices of EVERY old triangle covers every
2420 // overlap, without assuming the polygons are convex.
2421 for (int t : r.star) {
2422 if (!std::isfinite(bounds[t])) {
2423 bound = unknown;
2424 break;
2425 }
2426 double difference = 0;
2427 for (int q : m_tris[t].v) {
2428 const double d = std::abs(plane(T, m_pts[q]) - height(q));
2429 if (!std::isfinite(d)) {
2430 difference = unknown;
2431 break;
2432 }
2433 difference = std::max(difference, d);
2434 }
2435 if (!std::isfinite(difference)) {
2436 bound = unknown;
2437 break;
2438 }
2439 bound = std::max(bound, bounds[t] + difference);
2440 }
2441 if (std::isfinite(bound) && bound <= toleranceFor(T) * (1 - 1e-10))
2442 ++rep.coarsenBoundAccepts;
2443 else {
2444 Point xy[3];
2445 double z[3];
2446 for (int k = 0; k < 3; ++k) {
2447 xy[k] = m_pts[T.v[k]];
2448 z[k] = height(T.v[k]);
2449 }
2450 bound = opt.terrainErrorBound(xy, z);
2451 ++rep.coarsenExactQueries;
2452 }
2453 if (!std::isfinite(bound) || bound < 0 || !std::isfinite(toleranceFor(T)) ||
2454 bound > toleranceFor(T))
2455 accepted = false;
2456 newBounds.append(bound);
2457 }
2458 if (!accepted) {
2460 continue;
2461 }
2462 }
2463 commitRemoval(v, r);
2464 ++rep.coarsenRemoved;
2465 for (int i = 0; i < r.star.size(); ++i) {
2466 const int t = r.star[i];
2467 if (t < measured.size())
2468 measured[t] = Measured{};
2469 if (terrain)
2470 bounds[t] = i < newBounds.size() ? newBounds[i] : unknown;
2471 }
2472 for (int q : r.ring)
2473 queue(q);
2474 }
2475 }
2476 rep.coarsenSeconds = clock.nsecsElapsed() / 1e9;
2477 }
2478 // Bounded repair after smoothing, terrain insertion and coarsening. Ordinary
2479 // constraints may be subdivided but never moved/deleted; fixed patch edges
2480 // retain their stations. Terrain is rechecked inline for every changed cell.
2481 if (opt.sizingRepairPasses > 0 && !stop && !rep.cancelled) {
2482 repairing = true;
2483 repairBegin = rep.inserted;
2484 if (opt.maximumSizingRepairInsertions <= 0)
2485 rep.sizingRepairLimited = true;
2487 m_triangleChanged = [&](int t) {
2488 enqueue(t);
2489 for (int n : m_tris[t].adj)
2490 if (n >= 0)
2491 enqueue(n);
2492 };
2493 for (int pass = 0; pass < std::clamp(opt.sizingRepairPasses, 0, 3) && !stop &&
2494 !rep.cancelled && !rep.sizingRepairLimited;
2495 ++pass) {
2496 heads.fill(-1);
2497 tails.fill(-1);
2498 next.fill(-2, m_tris.size());
2499 const int before = rep.inserted;
2500 ++rep.sizingRepairPasses;
2501 for (int t = 0; t < m_tris.size(); ++t) {
2502 if ((t & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2503 rep.cancelled = true;
2504 break;
2505 }
2506 if (m_tris[t].alive)
2507 enqueue(t);
2508 }
2509 if (rep.cancelled)
2510 break;
2511 drainQueue();
2512 if (rep.inserted == before)
2513 break;
2514 }
2515 rep.sizingRepairInserted = rep.inserted - repairBegin;
2516 m_triangleChanged = {};
2517 }
2518 // Independent pass over the final geometry: every live triangle is checked,
2519 // so a missed edge flip or a blocked terrain candidate cannot go unnoticed.
2520 // A value is reused only for the identical ordered vertex triple.
2521 if (terrain && opt.terrainFinalCheck && !rep.cancelled) {
2523 publishProgress();
2524 for (int t = 0; t < m_tris.size(); ++t) {
2525 const auto &T = m_tris[t];
2526 if (!T.alive || isSuperVertex(T.v[0]) || isSuperVertex(T.v[1]) || isSuperVertex(T.v[2]))
2527 continue;
2528 if ((t & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2529 rep.cancelled = true;
2530 break;
2531 }
2532 double e;
2533 if (t < measured.size() && measured[t].v[0] == T.v[0] && measured[t].v[1] == T.v[1] &&
2534 measured[t].v[2] == T.v[2])
2535 e = measured[t].e;
2536 else {
2537 Point p;
2538 e = terrainError(t, &p);
2539 }
2540 if (!std::isfinite(e) || !std::isfinite(toleranceFor(T)))
2541 ++rep.terrainUnknown;
2542 else {
2543 rep.maxTerrainError = std::max(rep.maxTerrainError, e);
2544 if (e > toleranceFor(T))
2545 ++rep.terrainUnresolved;
2546 }
2547 }
2548 }
2549 publishProgress();
2550 return rep;
2551}
2552
2553} // namespace mesh
Constrained Delaunay triangulation kernel (workplans/MESH_OVERHAUL_PLAN_2026-09-29....
typename Storage::PointInput PointInput
Point container accepted by build() (std::vector<Point2> or QVector<QPointF>).
Definition cdt.hpp:74
typename meshkit::detail::QtStorage::template Vector< T > Vector
Definition cdt.hpp:76
int insertPoint(const Point &p)
Insert one finite point in a live triangle, splitting a triangle/edge and restoring Delaunay edges.
Definition cdt_impl.hpp:807
int liveTriangleCount() const
Count slots whose alive flag is true, including super faces if still alive.
Definition cdt_impl.hpp:394
bool isVertexActive(int v) const
Test whether an in-range vertex has a nonnegative incident-triangle hint.
Definition cdt.hpp:204
static double orientExact(const Point &a, const Point &b, const Point &c)
Return adaptive-exact orientation sign after thread-safe one-time predicate initialization.
Definition cdt_impl.hpp:150
bool smallAngleExempt(int t) const
Test the shortest edge of a triangle for equal-radius input-corner shell exemption.
Definition cdt_impl.hpp:1252
void addVertexOrigin(int v, std::uint32_t origin)
OR diagnostic provenance flags into an enabled in-range origin slot.
Definition cdt.hpp:599
bool build(const PointInput &points, Vector< int > *vertexOfPoint=nullptr, const std::function< bool()> &cancelled={}, const std::function< void(std::uint64_t)> &progress={})
Reset and incrementally triangulate distinct finite points inside a constructed super triangle.
Definition cdt_impl.hpp:658
int locate(const Point &p) const
Locate a finite point and require its found triangle to be alive.
Definition cdt_impl.hpp:388
int removeRegionLeftOf(int a, int b)
Delete live constraint-bounded faces topologically seeded to a directed edge's left.
Definition cdt_impl.hpp:1066
bool touchesFixed(int t) const
Test whether any triangle vertex participates in a marked fixed constrained edge.
Definition cdt_impl.hpp:1267
void setFixedConstraint(int a, int b)
Mark every recovered subedge of a requested constraint chain unsplittable for refinement.
Definition cdt_impl.hpp:1112
bool insertConstraint(int a, int b)
Recover/mark a straight constraint, recursively splitting at exactly collinear existing vertices.
Definition cdt_impl.hpp:839
@ Size
refineQuality() insertion for a size target.
Definition cdt.hpp:580
@ Angle
refineQuality() insertion for the minimum-angle bound.
Definition cdt.hpp:581
@ Terrain
refineQuality() insertion for terrain error.
Definition cdt.hpp:582
int removeRegionAt(const Point &p)
Mark the live constraint-bounded component containing a finite seed point dead.
Definition cdt_impl.hpp:1041
QualityReport refineQuality(const QualityOptions &opt)
Mutate live constrained triangulation by bounded size/angle/terrain refinement and optional coarsenin...
Definition cdt_impl.hpp:1468
typename meshkit::detail::QtStorage::template Hash< K, V > Hash
Definition cdt.hpp:78
void removeSuperTriangles()
Mark only live faces touching one of the three super vertices dead.
Definition cdt_impl.hpp:1032
bool isSuperVertex(int v) const
Test whether an integer falls in the recorded three-super-vertex interval.
Definition cdt.hpp:691
bool isConstrained(int a, int b) const
Check whether a direct edge between two stored vertices is marked constrained.
Definition cdt_impl.hpp:271
bool removeVertex(int v)
Transactionally remove a free post-build interior vertex and retriangulate its local cavity.
Definition cdt_impl.hpp:1458
Vector< int > constrainedChain(int a, int b) const
Follow direct, origin-associated or collinear constrained edges from one endpoint to another.
Definition cdt_impl.hpp:281
typename Storage::Box Box
Axis-aligned XY rectangle type of the storage; passed to footprint callbacks.
Definition cdt.hpp:70
void removeExterior()
Mark super-touching faces and every unconstrained reachable neighbor dead.
Definition cdt_impl.hpp:1006
typename Storage::Point Point
2D point type of the storage (meshkit::Point2 or QPointF), in XY plane units.
Definition cdt.hpp:68
Indexed binary min-heap holding at most one entry per vertex for resolution-aware coarsening.
Definition coarseningqueue.hpp:19
Entry pop()
Remove and return the first entry in queue order.
Definition coarseningqueue.hpp:74
void update(Entry entry)
Insert the vertex's entry, or replace its existing entry, and restore heap order.
Definition coarseningqueue.hpp:56
bool empty() const
True when no entry is queued.
Definition coarseningqueue.hpp:44
std::size_t size() const
Number of queued entries (at most one per vertex).
Definition coarseningqueue.hpp:46
Minimal std::chrono::steady_clock stopwatch with QElapsedTimer-style names.
Definition storage.hpp:499
std::int64_t nsecsElapsed() const
Time since the last start().
Definition storage.hpp:510
void start()
Record the current steady_clock time as the reference; call again to restart.
Definition storage.hpp:504
Internals of the constrained Delaunay kernel implementation; not part of the supported API.
std::uint64_t mortonKey(std::uint32_t x, std::uint32_t y)
Interleave two unsigned 32-bit coordinates into a Morton ordering key.
Definition cdt_impl.hpp:42
constexpr double kEquilateralArea
Area of an equilateral triangle with unit side, √3/4: a triangle of nominal size h has area kEquilate...
Definition cdt_impl.hpp:142
std::once_flag gPredicatesInit
Once-flag for the thread-safe, one-time initialization of the robust predicates (exactinit()) before ...
Definition cdt_impl.hpp:33
double dist2(const Point &a, const Point &b)
Compute ordinary squared Cartesian distance without overflow/finite checking.
Definition cdt_impl.hpp:114
int keyHi(std::uint64_t k)
Recover the larger endpoint word from an edgeKey64 key.
Definition cdt_impl.hpp:86
std::uint64_t edgeKey64(int a, int b)
Pack a normalized integer vertex pair into a 64-bit undirected edge identity.
Definition cdt_impl.hpp:65
bool refinementCoincident(const Point &a, const Point &b)
Whether a refinement point coincides with an existing vertex.
Definition cdt_impl.hpp:131
int keyLo(std::uint64_t k)
Recover the smaller endpoint word from an edgeKey64 key.
Definition cdt_impl.hpp:77
double orientPts(const Point &a, const Point &b, const Point &c)
Evaluate adaptive orientation on three borrowed Cartesian points after predicate initialization.
Definition cdt_impl.hpp:101
ScopeExit< F > scopeExit(F f)
Make a ScopeExit guard for f.
Definition storage.hpp:489
Box2 box(const Point2 *p, int n)
Axis-aligned bounding box of a point array.
Definition operation.hpp:131
The Qt-free MeshKit library: job events and progress (meshkit::runtime), the neutral mesh model,...
double resolutionRemovalImportance(double flatness, double actualSize, double targetSize)
Rank a vertex for resolution-aware coarsening; lower values are tried first.
Definition terrainpolicy.hpp:101
@ LegacyFlatness
Flattest vertex star first (smallest facet-normal spread), tile by tile in spatial (Morton) order.
Definition terrainpolicy.hpp:10
@ ResolutionAware
Lowest resolutionRemovalImportance() first, then lowest actual/target size ratio, tile by tile; the r...
Definition terrainpolicy.hpp:10
Options for refineQuality().
Definition cdt.hpp:268
Counters and diagnostics of one refineQuality() call.
Definition cdt.hpp:400
bool coarsenSkippedTerrain
Terrain is active but terrainErrorBound is absent, so coarsening was skipped.
Definition cdt.hpp:473
int segmentSplits
Constrained subsegments split; also counted in inserted.
Definition cdt.hpp:411
bool capped
Stopped at maxInsertions or maxTriangles.
Definition cdt.hpp:439
std::uint64_t coarsenQueuePeak
Largest size reached by the coarsening priority queue.
Definition cdt.hpp:481
int inserted
Vertices added, segment splits included.
Definition cdt.hpp:410
int terrainInsertions
Terrain witness points inserted, excluding segment splits.
Definition cdt.hpp:427
int terrainUnresolved
Final check: live triangles whose terrain error still exceeds the tolerance.
Definition cdt.hpp:436
int terrainUnknown
Final check: live triangles whose error or tolerance is not finite.
Definition cdt.hpp:436
int sizingRepairInserted
Vertices (segment splits included) inserted by the sizing-repair stage.
Definition cdt.hpp:407
int coarsenAttempts
Removal attempts, including stars that could not be retriangulated.
Definition cdt.hpp:460
int coarsenExactQueries
Calls to QualityOptions::terrainErrorBound.
Definition cdt.hpp:471
int coarsenBoundAccepts
Replacement triangles certified by the cached bound without calling terrainErrorBound.
Definition cdt.hpp:471
int sizeInsertions
Point insertions, excluding segment splits, for a size target (hAt, maximumAreaForTriangle or sizing-...
Definition cdt.hpp:427
int coarsenRejectedSize
Removals refused because a replacement triangle exceeds hAt, coarseningTargetSize (ResolutionAware) o...
Definition cdt.hpp:450
int coarsenRejectedEdge
Removals refused because a replacement edge is shorter than the star's shortest edge.
Definition cdt.hpp:460
bool sizingRepairLimited
Sizing repair reached maximumSizingRepairInsertions (at once when that is <= 0).
Definition cdt.hpp:409
int coarsenRejectedTerrain
Removals refused by the terrain checks; includes coarsenHeightRejects.
Definition cdt.hpp:460
double maxTerrainError
Final check: largest finite terrain error found, in Z units; 0 when not checked.
Definition cdt.hpp:438
int coarsenRejectedAngle
Removals refused because a replacement triangle breaks the angle bound.
Definition cdt.hpp:450
int coarsenRemoved
Free vertices removed by coarsening.
Definition cdt.hpp:450
bool cancelled
QualityOptions::cancelled returned true; edits are kept.
Definition cdt.hpp:440
int qualityInsertions
Point insertions, excluding segment splits, for the minimum-angle bound.
Definition cdt.hpp:427
int coarsenHeightRejects
Removals refused because the removed vertex's own height misses the replacement plane by more than th...
Definition cdt.hpp:471
bool invalidPolicy
Options or a callback result were invalid (coarseningOrder requirements, terrainToleranceForFootprint...
Definition cdt.hpp:487
std::uint64_t coarsenPriorityQueries
ResolutionAware only: coarseningTargetSize calls made for queue priorities.
Definition cdt.hpp:481
int sizingRepairPasses
Sizing-repair passes started (at most 3).
Definition cdt.hpp:407
int blockedByFixed
Bad triangles whose point would encroach constrained subsegments of which none could be split: fixed,...
Definition cdt.hpp:416
double coarsenSeconds
Wall-clock seconds spent in the coarsening stage.
Definition cdt.hpp:474
One triangle slot of triangles().
Definition cdt.hpp:87
int adj[3]
Neighbour across the edge opposite v[i] (v[i+1], v[i+2]); -1 = none.
Definition cdt.hpp:89
bool alive
False once the slot is removed (removeExterior(), removeSuperTriangles(), region removal,...
Definition cdt.hpp:93
int v[3]
Counter-clockwise.
Definition cdt.hpp:88
bool constrained[3]
Edge opposite v[i] is a constraint.
Definition cdt.hpp:90
int vertex
Vertex id in [0, vertices) given to the constructor; not range-checked.
Definition coarseningqueue.hpp:29
Counter snapshot passed to ConstrainedDelaunay::QualityOptions::onProgress during refineQuality().
Definition progress.hpp:14
Stage stage
Phase being run.
Definition progress.hpp:27
std::int64_t triangles
Live triangle count.
Definition progress.hpp:32
std::int64_t inserted
Vertices inserted so far, segment splits included.
Definition progress.hpp:41
std::int64_t removed
Vertices removed by coarsening so far.
Definition progress.hpp:41
Stage
Refinement phase being run.
Definition progress.hpp:16
@ Refining
Size and angle refinement, and later the sizing-repair passes.
Definition progress.hpp:16
@ Coarsening
Removal of free vertices.
Definition progress.hpp:16
@ Terrain
Worst-first insertion of terrain points.
Definition progress.hpp:16
@ Verifying
Final terrain check of every live triangle.
Definition progress.hpp:16
@ Smoothing
Non-degrading smoothing of free vertices.
Definition progress.hpp:16
std::int64_t workingVertices
Working vertex slots, excluding the three super-triangle vertices.
Definition progress.hpp:30