🛰️航天仿真算法库 SpaceAST 0.0.1
载入中...
搜索中...
未找到
path_converters.h
1// 从 matplotlib src/path_converters.h 复制，去除 Python/pybind11 依赖
2// 原始版权: matplotlib project
3#pragma once
4
5#include <cmath>
6#include <cstdint>
7#include <limits>
8
9#if defined(AST_WITH_AGG)
10
11A_SUPPRESS_WARNINGS_BEGIN
12#include "agg/agg_clip_liang_barsky.h"
13#include "agg/agg_conv_segmentator.h"
14
15
16#include "mpl_utils.h"
17
18/************************************************************
19 * EmbeddedQueue — 顶点队列基类，处理一个输入顶点产生多个输出
20 ************************************************************/
21template <int QueueSize>
22class EmbeddedQueue {
23protected:
24 EmbeddedQueue() : m_queue_read(0), m_queue_write(0) {}
25
26 struct item {
27 item() = default;
28 inline void set(const unsigned cmd_, const double x_, const double y_) {
29 cmd = cmd_; x = x_; y = y_;
30 }
31 unsigned cmd;
32 double x, y;
33 };
34 int m_queue_read, m_queue_write;
35 item m_queue[QueueSize];
36
37 inline void queue_push(const unsigned cmd, const double x, const double y) {
38 m_queue[m_queue_write++].set(cmd, x, y);
39 }
40 inline bool queue_nonempty() { return m_queue_read < m_queue_write; }
41 inline bool queue_pop(unsigned *cmd, double *x, double *y) {
42 if (queue_nonempty()) {
43 const item &front = m_queue[m_queue_read++];
44 *cmd = front.cmd; *x = front.x; *y = front.y;
45 return true;
46 }
47 m_queue_read = m_queue_write = 0;
48 return false;
49 }
50 inline void queue_clear() { m_queue_read = m_queue_write = 0; }
51};
52
53/* 每种路径段类型的额外顶点数 */
54static const size_t num_extra_points_map[] = {0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
55
56/************************************************************
57 * RandomNumberGenerator — 简单 LCG 随机数 (用于 Sketch)
58 ************************************************************/
59class RandomNumberGenerator {
60 static const uint32_t a = 214013, c = 2531011;
61 uint32_t m_seed;
62public:
63 RandomNumberGenerator() : m_seed(0) {}
64 explicit RandomNumberGenerator(int seed) : m_seed(seed) {}
65 void seed(int seed) { m_seed = seed; }
66 double get_double() {
67 m_seed = a * m_seed + c;
68 return (double)m_seed / (double)(1LL << 32);
69 }
70};
71
72/************************************************************
73 * PathNanRemover — 跳过含 NaN/Inf 的线段
74 ************************************************************/
75template <class VertexSource>
76class PathNanRemover : protected EmbeddedQueue<4> {
77 VertexSource *m_source;
78 bool m_remove_nans, m_has_codes;
79 bool valid_segment_exists, m_last_segment_valid, m_was_broken;
80 double m_initX, m_initY;
81
82public:
83 PathNanRemover(VertexSource &source, bool remove_nans, bool has_codes)
84 : m_source(&source), m_remove_nans(remove_nans), m_has_codes(has_codes),
85 m_last_segment_valid(false), m_was_broken(false) {
86 m_initX = std::nan(""); m_initY = std::nan("");
87 valid_segment_exists = false;
88 }
89
90 inline void rewind(unsigned path_id) {
91 queue_clear();
92 m_source->rewind(path_id);
93 }
94
95 inline unsigned vertex(double *x, double *y) {
96 unsigned code;
97 if (!m_remove_nans) return m_source->vertex(x, y);
98
99 if (m_has_codes) {
100 if (queue_pop(&code, x, y)) return code;
101
102 bool needs_move_to = false;
103 while (true) {
104 code = m_source->vertex(x, y);
105 if (code == agg::path_cmd_stop) return code;
106 if (code == (agg::path_cmd_end_poly | agg::path_flags_close) && valid_segment_exists) {
107 if (m_was_broken) {
108 if (m_last_segment_valid && std::isfinite(m_initX) && std::isfinite(m_initY)) {
109 queue_push(agg::path_cmd_line_to, m_initX, m_initY);
110 break;
111 } else { continue; }
112 m_was_broken = false; break;
113 } else { return code; }
114 } else if (code == agg::path_cmd_move_to) {
115 m_initX = *x; m_initY = *y; m_was_broken = false;
116 }
117
118 if (needs_move_to) queue_push(agg::path_cmd_move_to, *x, *y);
119
120 size_t num_extra = num_extra_points_map[code & 0xF];
121 m_last_segment_valid = std::isfinite(*x) && std::isfinite(*y);
122 queue_push(code, *x, *y);
123 for (size_t i = 0; i < num_extra; ++i) {
124 m_source->vertex(x, y);
125 m_last_segment_valid = m_last_segment_valid && std::isfinite(*x) && std::isfinite(*y);
126 queue_push(code, *x, *y);
127 }
128 if (m_last_segment_valid) { valid_segment_exists = true; break; }
129
130 m_was_broken = true; queue_clear();
131 if (std::isfinite(*x) && std::isfinite(*y)) {
132 queue_push(agg::path_cmd_move_to, *x, *y); needs_move_to = false;
133 } else { needs_move_to = true; }
134 }
135 if (queue_pop(&code, x, y)) return code;
136 return agg::path_cmd_stop;
137 } else {
138 code = m_source->vertex(x, y);
139 if (code == agg::path_cmd_stop ||
140 (code == (agg::path_cmd_end_poly | agg::path_flags_close) && valid_segment_exists))
141 return code;
142 if (!(std::isfinite(*x) && std::isfinite(*y))) {
143 do {
144 code = m_source->vertex(x, y);
145 if (code == agg::path_cmd_stop ||
146 (code == (agg::path_cmd_end_poly | agg::path_flags_close) && valid_segment_exists))
147 return code;
148 } while (!(std::isfinite(*x) && std::isfinite(*y)));
149 return agg::path_cmd_move_to;
150 }
151 valid_segment_exists = true;
152 return code;
153 }
154 }
155};
156
157/************************************************************
158 * PathClipper — Liang-Barsky 矩形裁剪
159 ************************************************************/
160template <class VertexSource>
161class PathClipper : public EmbeddedQueue<3> {
162 VertexSource *m_source;
163 bool m_do_clipping;
164 agg::rect_base<double> m_cliprect;
165 double m_lastX, m_lastY, m_initX, m_initY;
166 bool m_moveto, m_has_init, m_was_clipped;
167
168public:
169 PathClipper(VertexSource &source, bool do_clipping, double width, double height)
170 : m_source(&source), m_do_clipping(do_clipping),
171 m_cliprect(-1.0, -1.0, width + 1.0, height + 1.0),
172 m_moveto(true), m_has_init(false), m_was_clipped(false) {
173 m_lastX = std::nan(""); m_lastY = std::nan("");
174 m_initX = std::nan(""); m_initY = std::nan("");
175 }
176
177 PathClipper(VertexSource &source, bool do_clipping, const agg::rect_base<double> &rect)
178 : m_source(&source), m_do_clipping(do_clipping), m_cliprect(rect),
179 m_moveto(true), m_has_init(false), m_was_clipped(false) {
180 m_lastX = std::nan(""); m_lastY = std::nan("");
181 m_initX = std::nan(""); m_initY = std::nan("");
182 m_cliprect.x1 -= 1.0; m_cliprect.y1 -= 1.0; m_cliprect.x2 += 1.0; m_cliprect.y2 += 1.0;
183 }
184
185 inline void rewind(unsigned path_id) {
186 m_has_init = m_was_clipped = false; m_moveto = true;
187 m_source->rewind(path_id);
188 }
189
190 int draw_clipped_line(double x0, double y0, double x1, double y1, bool closed = false) {
191 unsigned moved = agg::clip_line_segment(&x0, &y0, &x1, &y1, m_cliprect);
192 m_was_clipped = m_was_clipped || (moved != 0);
193 if (moved < 4) {
194 if (moved & 1 || m_moveto) queue_push(agg::path_cmd_move_to, x0, y0);
195 queue_push(agg::path_cmd_line_to, x1, y1);
196 if (closed && !m_was_clipped)
197 queue_push(agg::path_cmd_end_poly | agg::path_flags_close, x1, y1);
198 m_moveto = false;
199 return 1;
200 }
201 return 0;
202 }
203
204 unsigned vertex(double *x, double *y) {
205 unsigned code; bool emit_moveto = false;
206 if (!m_do_clipping) return m_source->vertex(x, y);
207 if (queue_pop(&code, x, y)) return code;
208
209 while ((code = m_source->vertex(x, y)) != agg::path_cmd_stop) {
210 emit_moveto = false;
211 switch (code) {
212 case (agg::path_cmd_end_poly | agg::path_flags_close):
213 if (m_has_init) draw_clipped_line(m_lastX, m_lastY, m_initX, m_initY, true);
214 else queue_push(agg::path_cmd_end_poly | agg::path_flags_close, m_lastX, m_lastY);
215 if (queue_nonempty()) goto exit_loop;
216 break;
217 case agg::path_cmd_move_to:
218 if (m_moveto && m_has_init && m_lastX >= m_cliprect.x1 && m_lastX <= m_cliprect.x2
219 && m_lastY >= m_cliprect.y1 && m_lastY <= m_cliprect.y2) {
220 queue_push(agg::path_cmd_move_to, m_lastX, m_lastY); emit_moveto = true;
221 }
222 m_initX = m_lastX = *x; m_initY = m_lastY = *y;
223 m_has_init = true; m_moveto = true; m_was_clipped = false;
224 if (emit_moveto) goto exit_loop;
225 break;
226 case agg::path_cmd_line_to:
227 if (draw_clipped_line(m_lastX, m_lastY, *x, *y)) { m_lastX = *x; m_lastY = *y; goto exit_loop; }
228 m_lastX = *x; m_lastY = *y;
229 break;
230 default:
231 if (m_moveto) { queue_push(agg::path_cmd_move_to, m_lastX, m_lastY); m_moveto = false; }
232 queue_push(code, *x, *y); m_lastX = *x; m_lastY = *y;
233 goto exit_loop;
234 }
235 }
236 exit_loop:
237 if (queue_pop(&code, x, y)) return code;
238 if (m_moveto && m_has_init && m_lastX >= m_cliprect.x1 && m_lastX <= m_cliprect.x2
239 && m_lastY >= m_cliprect.y1 && m_lastY <= m_cliprect.y2) {
240 *x = m_lastX; *y = m_lastY; m_moveto = false;
241 return agg::path_cmd_move_to;
242 }
243 return agg::path_cmd_stop;
244 }
245};
246
247/************************************************************
248 * e_snap_mode — 像素对齐模式
249 ************************************************************/
250enum e_snap_mode { SNAP_AUTO, SNAP_FALSE, SNAP_TRUE };
251
252/************************************************************
253 * PathSnapper — 顶点像素对齐
254 ************************************************************/
255template <class VertexSource>
256class PathSnapper {
257 VertexSource *m_source;
258 bool m_snap;
259 double m_snap_value;
260
261public:
262 static bool should_snap(VertexSource &path, e_snap_mode snap_mode, unsigned total_vertices) {
263 double x0 = 0, y0 = 0, x1 = 0, y1 = 0; unsigned code;
264 switch (snap_mode) {
265 case SNAP_AUTO:
266 if (total_vertices > 1024) return false;
267 code = path.vertex(&x0, &y0);
268 if (code == agg::path_cmd_stop) return false;
269 while ((code = path.vertex(&x1, &y1)) != agg::path_cmd_stop) {
270 switch (code) {
271 case agg::path_cmd_curve3:
272 case agg::path_cmd_curve4: return false;
273 case agg::path_cmd_line_to:
274 if (fabs(x0 - x1) >= 1e-4 && fabs(y0 - y1) >= 1e-4) return false;
275 }
276 x0 = x1; y0 = y1;
277 }
278 return true;
279 case SNAP_FALSE: return false;
280 case SNAP_TRUE: return true;
281 }
282 return false;
283 }
284
285 PathSnapper(VertexSource &source, e_snap_mode snap_mode, unsigned total_vertices = 15,
286 double stroke_width = 0.0) : m_source(&source) {
287 m_snap = should_snap(source, snap_mode, total_vertices);
288 if (m_snap) {
289 int is_odd = mpl_round_to_int(stroke_width) % 2;
290 m_snap_value = (is_odd) ? 0.5 : 0.0;
291 }
292 source.rewind(0);
293 }
294
295 inline void rewind(unsigned path_id) { m_source->rewind(path_id); }
296 inline unsigned vertex(double *x, double *y) {
297 unsigned code = m_source->vertex(x, y);
298 if (m_snap && agg::is_vertex(code)) {
299 *x = floor(*x + 0.5) + m_snap_value;
300 *y = floor(*y + 0.5) + m_snap_value;
301 }
302 return code;
303 }
304 inline bool is_snapping() { return m_snap; }
305};
306
307/************************************************************
308 * PathSimplifier — 在线路径简化 (Douglas-Peucker 变体)
309 ************************************************************/
310template <class VertexSource>
311class PathSimplifier : protected EmbeddedQueue<9> {
312public:
313 PathSimplifier(VertexSource &source, bool do_simplify, double simplify_threshold)
314 : m_source(&source), m_simplify(do_simplify),
315 m_moveto(true), m_after_moveto(false), m_clipped(false),
316 m_has_init(false), m_simplify_threshold(simplify_threshold * simplify_threshold),
317 m_initX(0), m_initY(0),
318 m_lastx(0), m_lasty(0), m_origdx(0), m_origdy(0), m_origdNorm2(0),
319 m_dnorm2ForwardMax(0), m_dnorm2BackwardMax(0),
320 m_nextX(0), m_nextY(0), m_nextBackwardX(0), m_nextBackwardY(0),
321 m_currVecStartX(0), m_currVecStartY(0),
322 m_lastForwardMax(false), m_lastBackwardMax(false) {}
323
324 inline void rewind(unsigned path_id) { queue_clear(); m_moveto = true; m_source->rewind(path_id); }
325
326 unsigned vertex(double *x, double *y) {
327 unsigned cmd;
328 if (!m_simplify) return m_source->vertex(x, y);
329 if (queue_pop(&cmd, x, y)) return cmd;
330
331 while ((cmd = m_source->vertex(x, y)) != agg::path_cmd_stop) {
332 if (m_moveto || cmd == agg::path_cmd_move_to) {
333 if (m_origdNorm2 != 0.0 && !m_after_moveto) _push(x, y);
334 m_after_moveto = true;
335 m_has_init = std::isfinite(*x) && std::isfinite(*y);
336 if (m_has_init) { m_initX = *x; m_initY = *y; }
337 m_lastx = *x; m_lasty = *y;
338 m_moveto = false; m_origdNorm2 = 0.0; m_dnorm2BackwardMax = 0.0; m_clipped = true;
339 if (queue_nonempty()) break;
340 continue;
341 }
342 m_after_moveto = false;
343
344 if (agg::is_close(cmd)) {
345 if (m_has_init) { *x = m_initX; *y = m_initY; } else continue;
346 }
347
348 if (m_origdNorm2 == 0.0) {
349 if (m_clipped) { queue_push(agg::path_cmd_move_to, m_lastx, m_lasty); m_clipped = false; }
350 m_origdx = *x - m_lastx; m_origdy = *y - m_lasty;
351 m_origdNorm2 = m_origdx * m_origdx + m_origdy * m_origdy;
352 m_dnorm2ForwardMax = m_origdNorm2; m_dnorm2BackwardMax = 0.0;
353 m_lastForwardMax = true; m_lastBackwardMax = false;
354 m_currVecStartX = m_lastx; m_currVecStartY = m_lasty;
355 m_nextX = m_lastx = *x; m_nextY = m_lasty = *y;
356 continue;
357 }
358
359 double totdx = *x - m_currVecStartX, totdy = *y - m_currVecStartY;
360 double totdot = m_origdx * totdx + m_origdy * totdy;
361 double paradx = totdot * m_origdx / m_origdNorm2, parady = totdot * m_origdy / m_origdNorm2;
362 double perpdx = totdx - paradx, perpdy = totdy - parady;
363 double perpdNorm2 = perpdx * perpdx + perpdy * perpdy;
364
365 if (perpdNorm2 < m_simplify_threshold) {
366 double paradNorm2 = paradx * paradx + parady * parady;
367 m_lastForwardMax = m_lastBackwardMax = false;
368 if (totdot > 0.0) {
369 if (paradNorm2 > m_dnorm2ForwardMax) { m_lastForwardMax = true; m_dnorm2ForwardMax = paradNorm2; m_nextX = *x; m_nextY = *y; }
370 } else {
371 if (paradNorm2 > m_dnorm2BackwardMax) { m_lastBackwardMax = true; m_dnorm2BackwardMax = paradNorm2; m_nextBackwardX = *x; m_nextBackwardY = *y; }
372 }
373 m_lastx = *x; m_lasty = *y;
374 continue;
375 }
376 _push(x, y);
377 break;
378 }
379
380 if (cmd == agg::path_cmd_stop) {
381 if (m_origdNorm2 != 0.0) {
382 queue_push((m_moveto || m_after_moveto) ? agg::path_cmd_move_to : agg::path_cmd_line_to, m_nextX, m_nextY);
383 if (m_dnorm2BackwardMax > 0.0)
384 queue_push((m_moveto || m_after_moveto) ? agg::path_cmd_move_to : agg::path_cmd_line_to, m_nextBackwardX, m_nextBackwardY);
385 m_moveto = false;
386 }
387 queue_push((m_moveto || m_after_moveto) ? agg::path_cmd_move_to : agg::path_cmd_line_to, m_lastx, m_lasty);
388 m_moveto = false;
389 queue_push(agg::path_cmd_stop, 0.0, 0.0);
390 }
391
392 if (queue_pop(&cmd, x, y)) return cmd;
393 return agg::path_cmd_stop;
394 }
395
396private:
397 VertexSource *m_source;
398 bool m_simplify, m_moveto, m_after_moveto, m_clipped, m_has_init;
399 double m_simplify_threshold;
400 double m_initX, m_initY, m_lastx, m_lasty, m_origdx, m_origdy, m_origdNorm2;
401 double m_dnorm2ForwardMax, m_dnorm2BackwardMax, m_nextX, m_nextY;
402 double m_nextBackwardX, m_nextBackwardY, m_currVecStartX, m_currVecStartY;
403 bool m_lastForwardMax, m_lastBackwardMax;
404
405 inline void _push(double *x, double *y) {
406 bool needToPushBack = (m_dnorm2BackwardMax > 0.0);
407 if (needToPushBack) {
408 if (m_lastForwardMax) { queue_push(agg::path_cmd_line_to, m_nextBackwardX, m_nextBackwardY); queue_push(agg::path_cmd_line_to, m_nextX, m_nextY); }
409 else { queue_push(agg::path_cmd_line_to, m_nextX, m_nextY); queue_push(agg::path_cmd_line_to, m_nextBackwardX, m_nextBackwardY); }
410 } else { queue_push(agg::path_cmd_line_to, m_nextX, m_nextY); }
411 if (m_clipped) queue_push(agg::path_cmd_move_to, m_lastx, m_lasty);
412 else if (!m_lastForwardMax && !m_lastBackwardMax) queue_push(agg::path_cmd_line_to, m_lastx, m_lasty);
413 m_origdx = *x - m_lastx; m_origdy = *y - m_lasty;
414 m_origdNorm2 = m_origdx * m_origdx + m_origdy * m_origdy;
415 m_dnorm2ForwardMax = m_origdNorm2; m_lastForwardMax = true;
416 m_currVecStartX = m_queue[m_queue_write - 1].x;
417 m_currVecStartY = m_queue[m_queue_write - 1].y;
418 m_lastx = m_nextX = *x; m_lasty = m_nextY = *y;
419 m_dnorm2BackwardMax = 0.0; m_lastBackwardMax = false;
420 m_clipped = false;
421 }
422};
423
424/************************************************************
425 * Sketch — 手绘风格路径扰动
426 ************************************************************/
427template <class VertexSource>
428class Sketch {
429public:
430 Sketch(VertexSource &source, double scale, double length, double randomness)
431 : m_source(&source), m_scale(scale), m_length(length), m_randomness(randomness),
432 m_segmented(source), m_last_x(0), m_last_y(0), m_p(0), m_has_last(false), m_rand(0)
433 {
434 rewind(0);
435 const double d_M_PI = 3.14159265358979323846;
436 if (m_length <= std::numeric_limits<double>::epsilon() || m_randomness <= std::numeric_limits<double>::epsilon()) {
437 m_p_scale = 0.0;
438 } else {
439 m_p_scale = (2.0 * d_M_PI) / (m_length * m_randomness);
440 }
441 m_log_randomness = (m_randomness <= std::numeric_limits<double>::epsilon()) ? 0.0 : 2.0 * log(m_randomness);
442 }
443
444 unsigned vertex(double *x, double *y) {
445 if (m_scale == 0.0) return m_source->vertex(x, y);
446 unsigned code = m_segmented.vertex(x, y);
447 if (code == agg::path_cmd_move_to) { m_has_last = false; m_p = 0.0; }
448 if (m_has_last) {
449 double d_rand = m_rand.get_double();
450 m_p += exp(d_rand * m_log_randomness);
451 double den = m_last_x - *x, num = m_last_y - *y;
452 double len = num * num + den * den;
453 m_last_x = *x; m_last_y = *y;
454 if (len != 0) {
455 len = sqrt(len);
456 double r = sin(m_p * m_p_scale) * m_scale;
457 double roverlen = r / len;
458 *x += roverlen * num;
459 *y -= roverlen * den;
460 }
461 } else { m_last_x = *x; m_last_y = *y; }
462 m_has_last = true;
463 return code;
464 }
465
466 inline void rewind(unsigned path_id) {
467 m_has_last = false; m_p = 0.0;
468 if (m_scale != 0.0) { m_rand.seed(0); m_segmented.rewind(path_id); }
469 else m_source->rewind(path_id);
470 }
471
472private:
473 VertexSource *m_source;
474 double m_scale, m_length, m_randomness;
475 agg::conv_segmentator<VertexSource> m_segmented;
476 double m_last_x, m_last_y, m_p, m_p_scale, m_log_randomness;
477 bool m_has_last;
478 RandomNumberGenerator m_rand;
479};
480
481
482A_SUPPRESS_WARNINGS_END
483#endif // AST_WITH_AGG