Loading...
Searching...
No Matches
regionlimits.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: Apache-2.0
2#pragma once
3#include "meshkit/job.hpp"
4#include "operation.hpp"
5#include <algorithm>
7{
8// AABB bounds intentionally over-refine concave/holed regions. Every footprint
9// touching a prescribed region receives its cap, even after a quad fallback.
17{
18 struct Entry {
19 Box2 bounds;
20 double h;
21 };
22 struct Node {
23 Box2 bounds;
24 int begin, end, left = -1, right = -1;
25 };
26 std::vector<Entry> entries;
27 std::vector<Node> nodes;
28 int build(int begin, int end, Work &work)
29 {
30 Box2 bounds = entries[begin].bounds;
31 for (int i = begin + 1; i < end; ++i) {
32 work.tick();
33 bounds = bounds.united(entries[i].bounds);
34 }
35 int at = int(nodes.size());
36 nodes.push_back({bounds, begin, end});
37 if (end - begin > 8) {
38 int middle = begin + (end - begin) / 2;
39 bool x = bounds.width() >= bounds.height();
40 std::nth_element(entries.begin() + begin, entries.begin() + middle,
41 entries.begin() + end, [&](const Entry &a, const Entry &b) {
42 work.tick();
43 return x ? a.bounds.center().x() < b.bounds.center().x()
44 : a.bounds.center().y() < b.bounds.center().y();
45 });
46 nodes[at].left = build(begin, middle, work);
47 nodes[at].right = build(middle, end, work);
48 }
49 return at;
50 }
51
52public:
60 RegionLimits(const std::vector<plan::QuadRegion> &regions, Work &work)
61 {
62 for (const auto &r : regions) {
63 work.tick();
64 if (!std::isfinite(r.spacing) || r.spacing < 0)
65 fail("region_size", "Region spacing must be finite and nonnegative.");
66 if (r.spacing > 0 && !r.ring.empty())
67 entries.push_back({r.ring.boundingRect(), r.spacing});
68 }
69 if (!entries.empty())
70 build(0, int(entries.size()), work);
71 }
72
79 double minimum(const Box2 &bounds, Work &work) const
80 {
81 double h = 0;
82 auto visit = [&](auto &&self, int at) -> void {
83 work.tick();
84 const auto &n = nodes[at];
85 if (!meets(bounds, n.bounds))
86 return;
87 if (n.left >= 0) {
88 self(self, n.left);
89 self(self, n.right);
90 return;
91 }
92 for (int i = n.begin; i < n.end; ++i)
93 if (meets(bounds, entries[i].bounds))
94 h = h > 0 ? std::min(h, entries[i].h) : entries[i].h;
95 };
96 if (!nodes.empty())
97 visit(visit, 0);
98 return h;
99 }
100};
101}
Axis-aligned rectangle in the XY plane, stored as an origin corner and a signed size.
Definition geometry.hpp:167
constexpr double width() const
Signed extent along x in XY plane units; negative when not normalized.
Definition geometry.hpp:194
Box2 united(Box2 b) const
Bounding box of this box and b.
Definition geometry.hpp:294
constexpr double height() const
Signed extent along y in XY plane units; negative when not normalized.
Definition geometry.hpp:196
double minimum(const Box2 &bounds, Work &work) const
Smallest spacing among indexed regions whose box meets a footprint.
Definition regionlimits.hpp:79
RegionLimits(const std::vector< plan::QuadRegion > &regions, Work &work)
Index every region that has a positive spacing and a non-empty ring.
Definition regionlimits.hpp:60
Implementation helpers of the native jobs and codecs (failure signalling, work accounting,...
void fail(std::string code, std::string message, RunStatus status=RunStatus::Infeasible)
Abort the current native operation by throwing a Stop.
Definition operation.hpp:32
bool meets(const Box2 &a, const Box2 &b)
Closed overlap test of two normalized boxes; touching edges or corners count.
Definition operation.hpp:148
Work-unit budget, workspace-estimate gate and cancellation poll for one operation.
Definition operation.hpp:43
void tick(std::uint64_t count=1)
Charge work units; cancellation is polled whenever the updated total is an exact multiple of 4096.
Definition operation.hpp:77