Loading...
Searching...
No Matches
sourcechains.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: Apache-2.0
2#pragma once
3#include "mixed.hpp"
4#include <queue>
6{
7// Spatial index over actual constrained cell edges only, not every free grid
8// edge. Reconstruct shared source chains across CDT and fixed patch ownership.
15{
16 struct Node {
17 Box2 bounds;
18 int begin, end, left = -1, right = -1;
19 };
20 const Mesh &mesh_;
21 Work &work_;
22 std::vector<Edge> edges_;
23 std::vector<Node> nodes_;
24 Box2 bounds(Edge e) const
25 {
26 const auto &a = mesh_.vertices[e.a], &b = mesh_.vertices[e.b];
27 Point2 p[2] = {{a.x, a.y}, {b.x, b.y}};
28 return box(p, 2);
29 }
30 int build(int first, int last)
31 {
32 const int at = int(nodes_.size());
33 auto b = bounds(edges_[first]);
34 for (int i = first + 1; i < last; ++i) {
35 work_.tick();
36 b = b.united(bounds(edges_[i]));
37 }
38 nodes_.push_back({b, first, last});
39 if (last - first > 8) {
40 int middle = first + (last - first) / 2;
41 bool x = b.width() >= b.height();
42 std::nth_element(edges_.begin() + first, edges_.begin() + middle, edges_.begin() + last,
43 [&](Edge a, Edge b) {
44 work_.tick();
45 return x ? bounds(a).center().x() < bounds(b).center().x()
46 : bounds(a).center().y() < bounds(b).center().y();
47 });
48 int l = build(first, middle), r = build(middle, last);
49 nodes_[at].left = l;
50 nodes_[at].right = r;
51 }
52 return at;
53 }
54 template <class F> void query(Box2 b, F &f, int at = 0) const
55 {
56 if (nodes_.empty() || !meets(nodes_[at].bounds, b))
57 return;
58 work_.tick();
59 const auto &n = nodes_[at];
60 if (n.left < 0) {
61 for (int i = n.begin; i < n.end; ++i)
62 if (meets(bounds(edges_[i]), b))
63 f(edges_[i]);
64 } else {
65 query(b, f, n.left);
66 query(b, f, n.right);
67 }
68 }
69
70public:
79 SourceChains(const Mesh &m, std::vector<Edge> edges, Work &w) : mesh_(m), work_(w)
80 {
81 std::unordered_set<std::uint64_t> unique;
82 edges_.reserve(edges.size());
83 for (auto e : edges) {
84 work_.tick();
85 if (e.a != e.b && unique.insert(edgeKey(e.a, e.b)).second)
86 edges_.push_back(e);
87 }
88 work_.memoryFor({{edges_.size(), 128}, {m.vertices.size(), 36}, {m.cells.size(), 32}});
89 if (!edges_.empty())
90 build(0, int(edges_.size()));
91 }
92
105 std::vector<Index> chain(Index from, Index to) const
106 {
107 const auto &a = mesh_.vertices[from], &b = mesh_.vertices[to];
108 const long double dx = static_cast<long double>(b.x) - a.x,
109 dy = static_cast<long double>(b.y) - a.y, length2 = dx * dx + dy * dy;
110 const double length = std::hypot(double(dx), double(dy));
111 if (!(length > 0))
112 return {};
113 const double eps =
114 32 * std::numeric_limits<double>::epsilon() *
115 std::max({1., length, std::abs(a.x), std::abs(a.y), std::abs(b.x), std::abs(b.y)});
116 Point2 points[2] = {{a.x, a.y}, {b.x, b.y}};
117 auto bnd = box(points, 2).adjusted(-eps, -eps, eps, eps);
118 std::unordered_map<Index, std::vector<Index>> next;
119 auto visit = [&](Edge e) {
120 const auto &p = mesh_.vertices[e.a], &q = mesh_.vertices[e.b];
121 auto parameter = [&](const Point3 &p) {
122 return ((static_cast<long double>(p.x) - a.x) * dx +
123 (static_cast<long double>(p.y) - a.y) * dy) /
124 length2;
125 };
126 const auto t0 = parameter(p), t1 = parameter(q);
127 auto distance = [&](const Point3 &p, long double t) {
128 return std::hypot(static_cast<long double>(p.x) - a.x - t * dx,
129 static_cast<long double>(p.y) - a.y - t * dy);
130 };
131 if (std::min(t0, t1) < -eps / length || std::max(t0, t1) > 1 + eps / length ||
132 distance(p, t0) > eps || distance(q, t1) > eps)
133 return;
134 if (t0 <= t1)
135 next[e.a].push_back(e.b);
136 if (t1 <= t0)
137 next[e.b].push_back(e.a);
138 };
139 query(bnd, visit);
140 std::unordered_map<Index, Index> previous;
141 std::vector<Index> pending{from};
142 previous[from] = from;
143 for (std::size_t at = 0; at < pending.size() && !previous.count(to); ++at) {
144 work_.tick();
145 auto found = next.find(pending[at]);
146 if (found == next.end())
147 continue;
148 for (auto v : found->second)
149 if (previous.emplace(v, pending[at]).second)
150 pending.push_back(v);
151 }
152 if (!previous.count(to))
153 return {};
154 std::vector<Index> result{to};
155 while (result.back() != from)
156 result.push_back(previous[result.back()]);
157 std::reverse(result.begin(), result.end());
158 return result;
159 }
160};
161}
Axis-aligned rectangle in the XY plane, stored as an origin corner and a signed size.
Definition geometry.hpp:167
constexpr double left() const
X of the origin corner; the minimum x when width() >= 0.
Definition geometry.hpp:186
Box2 adjusted(double l, double t, double r, double b) const
Copy with each edge moved by an offset, in XY plane units.
Definition geometry.hpp:280
constexpr double right() const
left() + width(); the maximum x when width() >= 0.
Definition geometry.hpp:188
Point or displacement vector in the horizontal (XY) plane.
Definition geometry.hpp:21
std::vector< Index > chain(Index from, Index to) const
Shortest (fewest-edge) chain of indexed edges from one vertex to another along their straight segment...
Definition sourcechains.hpp:105
SourceChains(const Mesh &m, std::vector< Edge > edges, Work &w)
Index the distinct non-degenerate edges.
Definition sourcechains.hpp:79
Implementation helpers of the native jobs and codecs (failure signalling, work accounting,...
Box2 box(const Point2 *p, int n)
Axis-aligned bounding box of a point array.
Definition operation.hpp:131
std::uint64_t edgeKey(Index a, Index b)
Order-independent 64-bit key of an undirected edge.
Definition operation.hpp:121
bool meets(const Box2 &a, const Box2 &b)
Closed overlap test of two normalized boxes; touching edges or corners count.
Definition operation.hpp:148
std::uint32_t Index
Zero-based index into a native vertex, cell or edge array.
Definition mesh.hpp:13
Marked edge between two vertices of a Mesh.
Definition mesh.hpp:86
Index b
Second endpoint, a zero-based index into Mesh::vertices; validateMesh() requires it to differ from a.
Definition mesh.hpp:94
Index a
First endpoint, a zero-based index into Mesh::vertices.
Definition mesh.hpp:94
Neutral owned mesh: XYZ vertices, triangle/quad cells, marked edges, paths, optional external ids and...
Definition mesh.hpp:159
std::vector< Cell > cells
Triangle and quadrilateral cells.
Definition mesh.hpp:161
std::vector< Point3 > vertices
Vertex positions; every coordinate must be finite.
Definition mesh.hpp:160
Plain x, y, z coordinate triple; the vertex type of meshkit::Mesh.
Definition geometry.hpp:308
double x
Horizontal x coordinate in XY plane units; default 0.
Definition geometry.hpp:320
double y
Horizontal y coordinate in XY plane units; default 0.
Definition geometry.hpp:320
Work-unit budget, workspace-estimate gate and cancellation poll for one operation.
Definition operation.hpp:43