18 int begin, end, left = -1, right = -1;
22 std::vector<Edge> edges_;
23 std::vector<Node> nodes_;
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}};
30 int build(
int first,
int last)
32 const int at = int(nodes_.size());
33 auto b = bounds(edges_[first]);
34 for (
int i = first + 1; i < last; ++i) {
36 b = b.united(bounds(edges_[i]));
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,
45 return x ? bounds(a).center().x() < bounds(b).center().x()
46 : bounds(a).center().y() < bounds(b).center().y();
48 int l = build(first, middle), r = build(middle, last);
54 template <
class F>
void query(
Box2 b, F &f,
int at = 0)
const
56 if (nodes_.empty() || !
meets(nodes_[at].bounds, b))
59 const auto &n = nodes_[at];
61 for (
int i = n.begin; i < n.end; ++i)
62 if (
meets(bounds(edges_[i]), b))
81 std::unordered_set<std::uint64_t> unique;
82 edges_.reserve(edges.size());
83 for (
auto e : edges) {
85 if (e.
a != e.
b && unique.insert(
edgeKey(e.
a, e.
b)).second)
88 work_.memoryFor({{edges_.size(), 128}, {m.
vertices.size(), 36}, {m.
cells.size(), 32}});
90 build(0,
int(edges_.size()));
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));
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) /
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);
131 if (std::min(t0, t1) < -eps / length || std::max(t0, t1) > 1 + eps / length ||
132 distance(p, t0) > eps || distance(q, t1) > eps)
135 next[e.
a].push_back(e.
b);
137 next[e.
b].push_back(e.
a);
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) {
145 auto found = next.find(pending[at]);
146 if (found == next.end())
148 for (
auto v : found->second)
149 if (previous.emplace(v, pending[at]).second)
150 pending.push_back(v);
152 if (!previous.count(to))
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());
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