75 static std::vector<Rectf>
generateRects(
float radius,
float maxRectRatio = 0.5, std::pair<float, float> radiusRatios = {0.1f, 1.f} , uint64_t seed = 0) {
76 std::vector<Rectf> result;
79 float denominator = 1 / maxRectRatio;
82 float diagMin = radius * radiusRatios.first;
83 float diagMax = radius * radiusRatios.second;
87 for (
int i = 0; i < nbRects; ++i) {
90 float ratio = maxRectRatio +
random0D(next) * (denominator - maxRectRatio);
93 float diagonal = diagMin +
random0D(next) * (diagMax - diagMin);
97 float w = diagonal * ratio / std::sqrt(1.0f + ratio * ratio);
98 float h = diagonal / std::sqrt(1.0f + ratio * ratio);
101 float reducedRadius = radius - diagonal / 2.0f;
104 float theta =
random0D(next) * 2.0f * M_PI;
106 float r = reducedRadius * std::sqrt(
random0D(next));
109 float x = r * std::cos(theta);
110 float y = r * std::sin(theta);
117 result.push_back({x, y, w, h});
127 for (
int i = 0; i < its; ++i) {
128 for (
size_t i = 0; i < rects.size(); ++i) {
129 for (
size_t j = i + 1; j < rects.size(); ++j) {
131 if (isCollidingOrClose(rects[i], rects[j])) {
132 float dx = rects[j].x - rects[i].x;
133 float dy = rects[j].y - rects[i].y;
134 float dist = sqrtf(dx*dx + dy*dy) + 0.001f;
135 float nx = dx / dist;
136 float ny = dy / dist;
138 float overlapX = (rects[i].w + rects[j].w)/2 - fabs(dx);
139 float overlapY = (rects[i].h + rects[j].h)/2 - fabs(dy);
140 float overlap = fminf(overlapX, overlapY);
142 float attractionRange = 50.0f;
145 rects[i].x -= nx * overlap * 0.5f;
146 rects[i].y -= ny * overlap * 0.5f;
147 rects[j].x += nx * overlap * 0.5f;
148 rects[j].y += ny * overlap * 0.5f;
149 }
else if (dist < attractionRange) {
151 float attractionStrength = (attractionRange - dist) * 0.05f;
152 rects[i].x += nx * attractionStrength;
153 rects[i].y += ny * attractionStrength;
154 rects[j].x -= nx * attractionStrength;
155 rects[j].y -= ny * attractionStrength;
166 static std::vector<Linef>
bowyerWatson(
const std::vector<Rectf>& rects) {
168 std::vector<Vector2f> points(rects.size());
169 points.reserve(rects.size());
172 double minX = rects[0].x, maxX = rects[0].x;
173 double minY = rects[0].y, maxY = rects[0].y;
174 for (
auto& r : rects) {
175 minX = std::min(minX, r.x);
176 maxX = std::max(maxX, r.x);
177 minY = std::min(minY, r.y);
178 maxY = std::max(maxY, r.y);
181 double dx = maxX - minX;
182 double dy = maxY - minY;
183 double deltaMax = std::max(dx, dy) * 10.0f;
185 Vector2f p1 = {minX - deltaMax, minY - deltaMax};
186 Vector2f p2 = {minX + 0.5f * dx, maxY + deltaMax};
187 Vector2f p3 = {maxX + deltaMax, minY - deltaMax};
189 std::vector<Trianglef> triangles;
190 triangles.push_back({p1, p2, p3});
194 for (
auto &p: rects) {
195 std::vector<Trianglef> badTriangles;
196 std::vector<Linef> polygonEdges;
198 points.push_back({p.
x, p.
y});
203 for (
auto t: triangles) {
204 if (circumcircleContains(t, {p.
x, p.
y})) {
205 badTriangles.push_back(t);
214 for (
auto bt: badTriangles) {
215 std::vector<Linef> btedges = {
221 for (
const Linef& e : btedges) {
225 for (
const Trianglef other : badTriangles) {
226 if (bt.same(other))
continue;
227 std::vector<Linef> otherEdges = {
228 { other.p1, other.p2 },
229 { other.p2, other.p3 },
230 { other.p3, other.p1 }
233 for (
const Linef& oe : otherEdges) {
244 polygonEdges.push_back(e);
251 for (
const Trianglef& bad : badTriangles) {
252 auto it = std::remove_if(triangles.begin(), triangles.end(),
254 return (t.same(bad));
256 triangles.erase(it, triangles.end());
263 for (
auto& e : polygonEdges) {
264 triangles.push_back({e.p1, e.p2, {p.
x, p.
y}});
270 triangles.erase(std::remove_if(triangles.begin(), triangles.end(),
272 auto usesSuperVertex = [&](const Vector2f& v) {
273 return (fabs(v.x - p1.x) < 1e-12 && fabs(v.y - p1.y) < 1e-12) ||
274 (fabs(v.x - p2.x) < 1e-12 && fabs(v.y - p2.y) < 1e-12) ||
275 (fabs(v.x - p3.x) < 1e-12 && fabs(v.y - p3.y) < 1e-12);
277 return usesSuperVertex(t.
p1) || usesSuperVertex(t.
p2) || usesSuperVertex(t.
p3);
286 std::vector<Linef> edges;
287 for (
auto& t : triangles) {
288 edges.push_back({t.p1, t.p2});
289 edges.push_back({t.p2, t.p3});
290 edges.push_back({t.p3, t.p1});
312 static std::vector<Linef>
shortenLine(
const std::vector<Rectf>& rects,
313 const std::vector<Linef>& edges) {
315 for (
const auto& r : rects) {
317 if (c.
same(p))
return &r;
323 double dx = other.x - r.
x;
324 double dy = other.y - r.
y;
325 constexpr double INF = std::numeric_limits<double>::infinity();
326 double tx = (std::abs(dx) >
epsilond) ? (r.
w * 0.5) / std::abs(dx) : INF;
327 double ty = (std::abs(dy) >
epsilond) ? (r.
h * 0.5) / std::abs(dy) : INF;
328 double t = std::min(tx, ty);
329 return {r.
x + t * dx, r.
y + t * dy};
332 std::vector<Linef> result;
333 result.reserve(edges.size());
335 for (
const auto& e : edges) {
336 const Rectf* ra = findRect(e.p1);
337 const Rectf* rb = findRect(e.p2);
338 if (!ra || !rb) { result.push_back(e);
continue; }
342 result.push_back({a, b});