1 /*
2 Copyright (C) 2012, 2013, 2014, 2015 Johan Mattsson
3
4 This library is free software; you can redistribute it and/or modify
5 it under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 3 of the
7 License, or (at your option) any later version.
8
9 This library is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13 */
14
15 using Cairo;
16 using Math;
17
18 namespace BirdFont {
19
20 public enum Direction {
21 CLOCKWISE,
22 COUNTER_CLOCKWISE
23 }
24
25 public class Path {
26
27 public Gee.ArrayList<EditPoint> points {
28 get {
29 if (control_points == null) {
30 control_points = new Gee.ArrayList<EditPoint> ();
31 BirdFontFile.parse_path_data (point_data, this);
32 point_data = "";
33 }
34
35 return (!) control_points;
36 }
37 }
38
39 public Gee.ArrayList<EditPoint>? control_points = null;
40
41 EditPoint? last_point = null;
42
43 /** Path boundaries */
44 public double xmax = double.MIN;
45 public double xmin = double.MAX;
46 public double ymax = double.MIN;
47 public double ymin = double.MAX;
48
49 /** Stroke width */
50 public double stroke = 0;
51
52 /** Fill property for closed paths with stroke. */
53 public bool fill = false;
54
55 bool edit = true;
56 bool open = true;
57
58 public bool direction_is_set = false;
59 bool no_derived_direction = false;
60 bool clockwise_direction = true;
61
62 // Iterate over each pixel in a path
63 public delegate bool RasterIterator (double x, double y, double step);
64
65 public delegate bool SegmentIterator (EditPoint start, EditPoint stop);
66
67 /** The stroke of an outline when the path is not filled. */
68 public static double stroke_width = 0;
69 public static bool show_all_line_handles = true;
70 public static bool fill_open_path = false;
71
72 public double rotation = 0;
73 public double skew = 0;
74
75 public bool hide_end_handle = true;
76 public bool highlight_last_segment = false;
77
78 public string point_data = "";
79
80 public Path () {
81 string width;
82
83 if (unlikely (stroke_width < 1)) {
84 width = Preferences.get ("stroke_width");
85 if (width != "") {
86 stroke_width = double.parse (width);
87 }
88 }
89
90 if (stroke_width < 1) {
91 stroke_width = 1;
92 }
93 }
94
95 public bool is_filled () {
96 return fill;
97 }
98
99 public void set_fill (bool f) {
100 fill = f;
101 }
102
103 public EditPoint get_first_point () {
104 if (unlikely (points.size == 0)) {
105 warning ("No point");
106 return new EditPoint ();
107 }
108
109 return points.get (0);
110 }
111
112 public EditPoint get_last_visible_point () {
113 EditPoint e;
114
115 if (unlikely (points.size == 0)) {
116 warning ("No point");
117 return new EditPoint ();
118 }
119
120 for (int i = points.size - 1; i >= 0; i--) {
121 e = points.get (i);
122 if (e.type != PointType.HIDDEN) {
123 return e;
124 }
125 }
126
127 warning ("Only hidden points");
128 return new EditPoint ();
129 }
130
131 public EditPoint get_last_point () {
132 if (unlikely (points.size == 0)) {
133 warning ("No point");
134 return new EditPoint ();
135 }
136
137 return points.get (points.size - 1);
138 }
139
140 public bool has_direction () {
141 return direction_is_set;
142 }
143
144 public bool empty () {
145 return points.size == 0;
146 }
147
148 public void set_stroke (double width) {
149 stroke = width;
150 }
151
152 public void draw_boundaries (Context cr) {
153 double x = Glyph.reverse_path_coordinate_x (xmin);
154 double y = Glyph.reverse_path_coordinate_y (ymin);
155 double x2 = Glyph.reverse_path_coordinate_x (xmax);
156 double y2 = Glyph.reverse_path_coordinate_y (ymax);
157
158 cr.save ();
159
160 Theme.color (cr, "Background 4");
161 cr.set_line_width (2);
162 cr.rectangle (x, y, x2 - x, y2 - y);
163 cr.stroke ();
164
165 cr.restore ();
166 }
167
168 public void draw_outline (Context cr) {
169 unowned EditPoint? n = null;
170 unowned EditPoint en;
171 unowned EditPoint em;
172 int i;
173
174 if (points.size < 2) {
175 return;
176 }
177
178 cr.new_path ();
179
180 // draw lines
181 i = 0;
182 foreach (EditPoint e in points) {
183 if (n != null) {
184 en = (!) n;
185 if (!highlight_last_segment || i != points.size - 1) {
186 draw_next (en, e, cr);
187 }
188 }
189
190 n = e;
191 i++;
192 }
193
194 // close path
195 if (!is_open () && n != null) {
196 if (highlight_last_segment) {
197 cr.stroke ();
198 en = points.get (points.size - 1).get_link_item ();
199 em = points.get (0).get_link_item ();
200 draw_next (en, em, cr);
201 cr.stroke ();
202 } else {
203 en = (!) n;
204 em = points.get (0).get_link_item ();
205 draw_next (en, em, cr);
206 cr.stroke ();
207 }
208 } else {
209 cr.stroke ();
210 }
211
212 // draw highlighted segment
213 if (highlight_last_segment && points.size >= 2) {
214 draw_next (points.get (points.size - 2), points.get (points.size - 1), cr, true);
215 cr.stroke ();
216 }
217 }
218
219 public void draw_edit_points (Context cr) {
220 if (is_editable ()) {
221 // control points for curvature
222 foreach (EditPoint e in points) {
223 if (show_all_line_handles || e.selected_point || e.selected_handle > 0) {
224 draw_edit_point_handles (e, cr);
225 }
226 }
227
228 // control points
229 foreach (EditPoint e in points) {
230 draw_edit_point (e, cr);
231 }
232 }
233 }
234
235 /** Add all control points for a path to the cairo context.
236 * Call Context.new_path (); before this method and Context.fill ()
237 * to show the path.
238 */
239 public void draw_path (Context cr, Glyph glyph, Color? color = null) {
240 unowned EditPoint? n = null;
241 unowned EditPoint en;
242 unowned EditPoint em;
243 Color c;
244 double center_x, center_y;
245 double ex, ey;
246
247 if (points.size == 0){
248 return;
249 }
250
251 center_x = glyph.allocation.width / 2.0;
252 center_y = glyph.allocation.height / 2.0;
253
254 ex = center_x + points.get (0).x;
255 ey = center_y - points.get (0).y;
256
257 cr.move_to (ex, ey);
258
259 // draw lines
260 foreach (EditPoint e in points) {
261 if (n != null) {
262 en = (!) n;
263 draw_next (en, e, cr);
264 }
265
266 n = e;
267 }
268
269 // close path
270 if (!is_open () && points.size >= 2 && n != null) {
271 en = (!) n;
272 em = points.get (0).get_link_item ();
273 draw_next (en, em, cr);
274 }
275
276 // fill path
277 cr.close_path ();
278
279 if (color != null) {
280 c = (!) color;
281 cr.set_source_rgba (c.r, c.g, c.b, c.a);
282 } else {
283 if (is_clockwise ()) {
284 cr.set_source_rgba (80/255.0, 95/255.0, 137/255.0, 0.5);
285 } else {
286 cr.set_source_rgba (144/255.0, 145/255.0, 236/255.0, 0.5);
287 }
288 }
289 }
290
291 private void draw_next (EditPoint e, EditPoint en, Context cr, bool highlighted = false) {
292 PointType r = e.get_right_handle ().type;
293 PointType l = en.get_left_handle ().type;
294
295 if (r == PointType.DOUBLE_CURVE || l == PointType.DOUBLE_CURVE) {
296 draw_double_curve (e, en, cr, highlighted);
297 } else {
298 draw_curve (e, en, cr, highlighted);
299 }
300 }
301
302 private static void draw_double_curve (EditPoint e, EditPoint en, Context cr, bool highlighted) {
303 EditPoint middle;
304 double x, y;
305
306 x = e.get_right_handle ().x + (en.get_left_handle ().x - e.get_right_handle ().x) / 2;
307 y = e.get_right_handle ().y + (en.get_left_handle ().y - e.get_right_handle ().y) / 2;
308
309 middle = new EditPoint (x, y, PointType.DOUBLE_CURVE);
310 middle.right_handle = en.get_left_handle ().copy ();
311
312 middle.right_handle.type = PointType.DOUBLE_CURVE;
313 middle.left_handle.type = PointType.DOUBLE_CURVE;
314
315 draw_curve (e, middle, cr, highlighted);
316 draw_curve (middle, en, cr, highlighted);
317 }
318
319 private static void draw_curve (EditPoint e, EditPoint en, Context cr, bool highlighted = false, double alpha = 1) {
320 Glyph g = MainWindow.get_current_glyph ();
321 double xa, ya, xb, yb, xc, yc, xd, yd;
322 PointType t = e.get_right_handle ().type;
323 PointType u = en.get_left_handle ().type;
324
325 get_bezier_points (e, en, out xa, out ya, out xb, out yb, out xc, out yc, out xd, out yd);
326
327 if (!highlighted) {
328 Theme.color (cr, "Stroke Color");
329 } else {
330 Theme.color (cr, "Highlighted Guide");
331 }
332
333 cr.set_line_width (stroke_width / g.view_zoom);
334
335 cr.line_to (xa, ya); // this point makes sense only if it is in the first or last position
336
337 if (t == PointType.QUADRATIC || t == PointType.LINE_QUADRATIC || t == PointType.DOUBLE_CURVE || u == PointType.QUADRATIC || u == PointType.LINE_QUADRATIC || u == PointType.DOUBLE_CURVE) {
338 cr.curve_to ((xa + 2 * xb) / 3, (ya + 2 * yb) / 3, (xd + 2 * xb) / 3, (yd + 2 * yb) / 3, xd, yd);
339 } else {
340 cr.curve_to (xb, yb, xc, yc, xd, yd);
341 }
342 }
343
344 /** Curve relative to window center. */
345 public static void get_bezier_points (EditPoint e, EditPoint en, out double xa, out double ya, out double xb, out double yb, out double xc, out double yc, out double xd, out double yd) {
346 Glyph g = MainWindow.get_current_glyph ();
347
348 double center_x, center_y;
349
350 center_x = g.allocation.width / 2.0;
351 center_y = g.allocation.height / 2.0;
352
353 xa = center_x + e.x;
354 ya = center_y - e.y;
355
356 xb = center_x + e.get_right_handle ().x;
357 yb = center_y - e.get_right_handle ().y;
358
359 xc = center_x + en.get_left_handle ().x;
360 yc = center_y - en.get_left_handle ().y;
361
362 xd = center_x + en.x;
363 yd = center_y - en.y;
364 }
365
366 /** Curve absolute glyph data. */
367 public static void get_abs_bezier_points (EditPoint e, EditPoint en, out double xa, out double ya, out double xb, out double yb, out double xc, out double yc, out double xd, out double yd) {
368 xa = + e.x;
369 ya = - e.y;
370
371 xb = + e.get_right_handle ().x;
372 yb = - e.get_right_handle ().y;
373
374 xc = + en.get_left_handle ().x;
375 yc = - en.get_left_handle ().y;
376
377 xd = + en.x;
378 yd = - en.y;
379 }
380
381 /** Line points relative to centrum. */
382 public static void get_line_points (EditPoint e, EditPoint en, out double xa, out double ya, out double xb, out double yb) {
383 double xc = Glyph.xc ();
384 double yc = Glyph.yc ();
385
386 xa = xc + e.x;
387 ya = yc - e.y;
388
389 xb = xc + en.x;
390 yb = yc - en.y;
391 }
392
393 public void draw_line (EditPoint e, EditPoint en, Context cr, double alpha = 1) {
394 Glyph g = MainWindow.get_current_glyph ();
395 double ax, ay, bx, by;
396
397 get_line_points (e, en, out ax, out ay, out bx, out by);
398
399 Theme.color (cr, "Handle Color");
400 cr.set_line_width (1.7 * (stroke_width / g.view_zoom));
401
402 cr.line_to (ax, ay);
403 cr.line_to (bx, by);
404
405 cr.stroke ();
406 }
407
408 public void draw_edit_point (EditPoint e, Context cr) {
409 draw_edit_point_center (e, cr);
410 }
411
412 public void draw_edit_point_handles (EditPoint e, Context cr) {
413 Color color_left = Theme.get_color ("Control Point Handle");
414 Color color_right = Theme.get_color ("Control Point Handle");
415 EditPoint handle_right = e.get_right_handle ().get_point ();
416 EditPoint handle_left = e.get_left_handle ().get_point ();
417
418 cr.stroke ();
419
420 if (e.type != PointType.HIDDEN) {
421 if (e.get_right_handle ().selected) {
422 color_right = Theme.get_color ("Selected Control Point Handle");
423 } else if (e.get_right_handle ().active) {
424 color_right = Theme.get_color ("Active Control Point Handle");
425 } else {
426 color_right = Theme.get_color ("Control Point Handle");
427 }
428
429 if (e.get_left_handle ().selected) {
430 color_left = Theme.get_color ("Selected Control Point Handle");
431 } else if (e.get_left_handle ().active) {
432 color_left = Theme.get_color ("Active Control Point Handle");
433 } else {
434 color_left = Theme.get_color ("Control Point Handle");
435 }
436
437 if (!hide_end_handle || !(is_open () && e == points.get (points.size - 1))) {
438 draw_line (handle_right, e, cr, 0.15);
439 draw_control_point (cr, e.get_right_handle ().x, e.get_right_handle ().y, color_right);
440 }
441
442 if (!(is_open () && e == points.get (0))) {
443 draw_line (handle_left, e, cr, 0.15);
444 draw_control_point (cr, e.get_left_handle ().x, e.get_left_handle ().y, color_left);
445 }
446 }
447 }
448
449 public static void draw_edit_point_center (EditPoint e, Context cr) {
450 Color c;
451
452 if (e.type != PointType.HIDDEN) {
453 if (e.type == PointType.CUBIC || e.type == PointType.LINE_CUBIC) {
454 if (e.is_selected ()) {
455 if (e.active_point) {
456 if (e.color != null) {
457 c = (!) e.color;
458 } else {
459 c = Theme.get_color ("Selected Active Cubic Control Point");
460 }
461 } else {
462 if (e.color != null) {
463 c = (!) e.color;
464 } else {
465 c = Theme.get_color ("Selected Cubic Control Point");
466 }
467 }
468 } else {
469 if (e.active_point) {
470 if (e.color != null) {
471 c = (!) e.color;
472 } else {
473 c = Theme.get_color ("Active Cubic Control Point");
474 }
475 } else {
476 if (e.color != null) {
477 c = (!) e.color;
478 } else {
479 c = Theme.get_color ("Cubic Control Point");
480 }
481 }
482 }
483 } else {
484 if (e.is_selected ()) {
485 if (e.active_point) {
486 if (e.color != null) {
487 c = (!) e.color;
488 } else {
489 c = Theme.get_color ("Selected Active Quadratic Control Point");
490 }
491 } else {
492 if (e.color != null) {
493 c = (!) e.color;
494 } else {
495 c = Theme.get_color ("Selected Quadratic Control Point");
496 }
497 }
498 } else {
499 if (e.active_point) {
500 if (e.color != null) {
501 c = (!) e.color;
502 } else {
503 c = Theme.get_color ("Active Quadratic Control Point");
504 }
505 } else {
506 if (e.color != null) {
507 c = (!) e.color;
508 } else {
509 c = Theme.get_color ("Quadratic Control Point");
510 }
511 }
512 }
513 }
514
515 draw_control_point (cr, e.x, e.y, c);
516 }
517 }
518
519 public static void draw_control_point (Context cr, double x, double y, Color color, double size = 3.5) {
520 Glyph g = MainWindow.get_current_glyph ();
521 double ivz = 1 / g.view_zoom;
522 double width = size * Math.sqrt (stroke_width) * ivz;
523 double xc = g.allocation.width / 2.0;
524 double yc = g.allocation.height / 2.0;
525
526 cr.save ();
527
528 x = xc + x - (width / 2.0) * ivz;
529 y = yc - y - (width / 2.0) * ivz;
530
531 cr.set_source_rgba (color.r, color.g, color.b, color.a);
532
533 cr.move_to (x, y);
534 cr.arc (x, y, width, 0, 2 * Math.PI);
535 cr.close_path ();
536 cr.fill ();
537
538 cr.restore ();
539 }
540
541 public static void draw_image (Context cr, ImageSurface img, double x, double y) {
542 Glyph g = MainWindow.get_current_glyph ();
543 double r = 1.0 / 10.0;
544
545 double width = Math.sqrt (stroke_width);
546
547 double ivz = 1 / g.view_zoom;
548 double ivs = 1 / width;
549
550 double xc = g.allocation.width / 2.0;
551 double yc = g.allocation.height / 2.0;
552
553 cr.save ();
554 cr.scale (ivz * width * r, ivz * width * r);
555
556 x = xc + x - (width * r * img.get_width () / 2.0) * ivz;
557 y = yc - y - (width * r * img.get_height () / 2.0) * ivz;
558
559 cr.set_source_surface (img, x * g.view_zoom * ivs * 1/r, y * g.view_zoom * ivs * 1/r);
560 cr.paint ();
561 cr.restore ();
562 }
563
564 /** Set direction for this path to clockwise for outline and
565 * counter clockwise for inline paths.
566 */
567 public bool force_direction (Direction direction) {
568 bool c = (direction == Direction.CLOCKWISE);
569 bool d = is_clockwise ();
570 direction_is_set = true;
571
572 if (c != d) {
573 this.reverse ();
574 }
575
576 d = is_clockwise ();
577 if (unlikely (d != c)) {
578 warning ("Failed to set direction for path in force_direction.");
579 return true;
580 }
581
582 return false;
583 }
584
585 /** Switch direction from clockwise path to counter clockwise path or vise versa. */
586 public void reverse () {
587 bool direction = is_clockwise ();
588
589 if (no_derived_direction) {
590 clockwise_direction = !clockwise_direction;
591 }
592
593 reverse_points ();
594
595 if (unlikely (direction == is_clockwise ())) {
596 stderr.printf ("Error: Direction did not change after reversing path.\n");
597 stderr.printf (@"Length: $(points.size)\n");
598 stderr.printf (@"No particular direction can be derived: $no_derived_direction \n");
599 warning ("Path.reverse () failed.\n");
600 }
601 }
602
603 private void reverse_points () requires (points.size > 0) {
604 EditPointHandle t;
605 Path p = copy ();
606 EditPoint e;
607
608 create_list ();
609
610 points.clear ();
611
612 for (int i = p.points.size - 1; i >= 0 ; i--) {
613 e = p.points.get (i);
614
615 t = e.right_handle;
616 e.right_handle = e.left_handle;
617 e.left_handle = t;
618
619 add_point (e);
620 }
621
622 create_list ();
623 }
624
625 public void print_all_points () {
626 int i = 0;
627 foreach (EditPoint p in points) {
628 ++i;
629 string t = (p.type == PointType.END) ? " endpoint" : "";
630 stdout.printf (@"Point $i at ($(p.x), $(p.y)) $t \n");
631 }
632 }
633
634 private double clockwise_sum () {
635 double sum = 0;
636
637 return_val_if_fail (points.size >= 3, 0);
638
639 foreach (EditPoint e in points) {
640 sum += e.get_direction ();
641 }
642
643 return sum;
644 }
645
646 public bool is_clockwise () {
647 double s;
648
649 if (unlikely (points.size <= 2)) {
650 no_derived_direction = true;
651 return clockwise_direction;
652 }
653
654 s = clockwise_sum ();
655
656 if (s == 0) {
657 no_derived_direction = true;
658 return clockwise_direction;
659 }
660
661 return s > 0;
662 }
663
664 public bool is_editable () {
665 return edit;
666 }
667
668 /** Show control points on outline path. */
669 public void set_editable (bool e) {
670 edit = e;
671 }
672
673 public bool is_open () {
674 return open;
675 }
676
677 /** Resize path relative to bottom left coordinates. */
678 public void resize (double ratio) {
679 foreach (EditPoint p in points) {
680 p.x *= ratio;
681 p.y *= ratio;
682 p.right_handle.length *= ratio;
683 p.left_handle.length *= ratio;
684 }
685
686 xmin *= ratio;
687 xmax *= ratio;
688 ymin *= ratio;
689 ymax *= ratio;
690 }
691
692 public void scale (double scale_x, double scale_y) {
693 foreach (EditPoint p in points) {
694 p.right_handle.length *= scale_x * scale_y;
695 p.left_handle.length *= scale_x * scale_y;
696 }
697
698 foreach (EditPoint p in points) {
699 p.x *= scale_x;
700 p.y *= scale_y;
701 }
702
703 xmin *= scale_x;
704 xmax *= scale_x;
705 ymin *= scale_y;
706 ymax *= scale_y;
707 }
708
709 public Path copy () {
710 Path new_path = new Path ();
711 EditPoint p;
712
713 foreach (EditPoint ep in points) {
714 p = ep.copy ();
715 new_path.add_point (p);
716 }
717
718 new_path.edit = edit;
719 new_path.open = open;
720 new_path.stroke = stroke;
721 new_path.skew = skew;
722 new_path.fill = fill;
723 new_path.direction_is_set = direction_is_set;
724 new_path.create_list ();
725
726 new_path.hide_end_handle = hide_end_handle;
727 new_path.highlight_last_segment = highlight_last_segment;
728
729 return new_path;
730 }
731
732 public bool is_over (double x, double y) {
733 Glyph g = MainWindow.get_current_glyph ();
734
735 x = x * Glyph.ivz () + g.view_offset_x - Glyph.xc ();
736 y = y * Glyph.ivz () + g.view_offset_y - Glyph.yc ();
737
738 y *= -1;
739
740 return is_over_coordinate (x, y);
741 }
742
743 public bool is_over_coordinate (double x, double y) {
744 return is_over_coordinate_var (x, y);
745 }
746
747 public static double distance (double ax, double bx, double ay, double by) {
748 return Math.fabs (Math.sqrt (Math.pow (ax - bx, 2) + Math.pow (ay - by, 2)));
749 }
750
751 public static double distance_to_point (EditPoint a, EditPoint b) {
752 return distance (a.x, b.x, a.y, b.y);
753 }
754
755 public static double distance_pixels (double x1, double y1, double x2, double y2) {
756 return distance (Glyph.path_coordinate_x (x1),
757 Glyph.path_coordinate_x (x2),
758 Glyph.path_coordinate_x (y1),
759 Glyph.path_coordinate_x (y2));
760 }
761
762 public static double get_length_from (EditPoint a, EditPoint b) {
763 double x, y;
764
765 x = Math.fabs (a.x - a.get_right_handle ().x);
766 x += Math.fabs (a.get_right_handle ().x - b.get_left_handle ().x );
767 x += Math.fabs (b.get_left_handle ().x - b.x);
768
769 y = Math.fabs (a.y - a.get_right_handle ().y);
770 y += Math.fabs (a.get_right_handle ().y - b.get_left_handle ().y);
771 y += Math.fabs (b.get_left_handle ().y - b.y);
772
773 return Math.fabs (Math.sqrt (x * x + y * y));
774 }
775
776 /** Variable precision */
777 public bool is_over_coordinate_var (double x, double y) {
778 PathList pathlist;
779 int width;
780 ClickMap click_map;
781 int px, py;
782 int click_x, click_y;
783
784 if (points.size < 2) {
785 return false;
786 }
787
788 if (stroke > 0) {
789 pathlist = StrokeTool.get_stroke (this, stroke);
790
791 if (pathlist.paths.size > 1) {
792 if (pathlist.paths.get (1).is_over_coordinate_var (x, y)) {
793 return false;
794 }
795 }
796
797 return pathlist.get_first_path ().is_over_coordinate_var (x, y);
798 }
799
800 if (!is_over_boundry (x, y)) {
801 return false;
802 }
803
804 // generate a rasterized image of the object
805 width = 160;
806 click_map = new ClickMap (width);
807 px = 0;
808 py = 0;
809
810 click_map.create_click_map (this);
811
812 click_x = (int) (width * ((x - xmin) / (xmax - xmin)));
813 click_y = (int) (width * ((y - ymin) / (ymax - ymin)));
814
815 return click_map.get_value (click_x, click_y);
816 }
817
818 public bool is_over_boundry (double x, double y) {
819 if (unlikely (ymin == double.MAX || ymin == 10000)) {
820 warning ("bounding box is not calculated, run update_region_boundaries first.");
821 update_region_boundaries ();
822 }
823
824 return (ymin <= y <= ymax) && (xmin <= x <= xmax);
825 }
826
827 public bool has_overlapping_boundry (Path p) {
828 return !(xmax <= p.xmin || ymax <= p.ymin) || (xmin >= p.xmax || ymin >= p.ymax);
829 }
830
831 // FIXME: DELETE?
832 public EditPoint delete_first_point () {
833 EditPoint r;
834 int size;
835
836 size = points.size;
837 if (unlikely (size == 0)) {
838 warning ("No points in path.");
839 return new EditPoint ();
840 }
841
842 r = points.get (0);
843 points.remove_at (0);
844
845 if (size > 1) {
846 r.get_next ().prev = null;
847 }
848
849 return r;
850 }
851
852 public EditPoint delete_last_point () {
853 EditPoint r;
854 int size;
855
856 size = points.size;
857 if (unlikely (size == 0)) {
858 warning ("No points in path.");
859 return new EditPoint ();
860 }
861
862 r = points.get (size - 1);
863 points.remove_at (size - 1);
864
865 if (size > 1) {
866 r.get_prev ().next = null;
867
868 if (r.next != null) {
869 r.get_next ().prev = null;
870 }
871 }
872
873 return r;
874 }
875
876 public EditPoint add (double x, double y) {
877 if (points.size > 0) {
878 return add_after (x, y, points.get (points.size - 1));
879 }
880
881 return add_after (x, y, null);
882 }
883
884 public EditPoint add_point (EditPoint p) {
885 if (points.size > 0) {
886 return add_point_after (p, points.get (points.size - 1));
887 }
888
889 return add_point_after (p, null);
890 }
891
892 /** Insert a new point after @param previous_point and return a reference
893 * to the new item in list.
894 */
895 public EditPoint add_after (double x, double y, EditPoint? previous_point) {
896 EditPoint p = new EditPoint (x, y, PointType.NONE);
897 return add_point_after (p, previous_point);
898 }
899
900 /** @return a list item pointing to the new point */
901 public EditPoint add_point_after (EditPoint p, EditPoint? previous_point) {
902 int prev_index;
903
904 if (unlikely (previous_point == null && points.size != 0)) {
905 warning ("previous_point == null");
906 previous_point = points.get (points.size - 1).get_link_item ();
907 }
908
909 if (points.size == 0) {
910 points.add (p);
911 p.prev = points.get (0).get_link_item ();
912 p.next = points.get (0).get_link_item ();
913 } else {
914 p.prev = (!) previous_point;
915 p.next = ((!) previous_point).next;
916
917 prev_index = points.index_of ((!) previous_point);
918
919 if (unlikely (!(0 <= prev_index < points.size))) {
920 warning ("no previous point");
921 }
922
923 points.insert (prev_index + 1, p);
924 }
925
926 last_point = p;
927
928 return p;
929 }
930
931 public void recalculate_linear_handles () {
932 foreach (EditPoint e in points) {
933 e.recalculate_linear_handles ();
934 }
935 }
936
937 public void close () {
938 open = false;
939 edit = false;
940
941 create_list ();
942
943 if (points.size > 2) {
944 points.get (0).recalculate_linear_handles ();
945 points.get (points.size - 1).recalculate_linear_handles ();
946 }
947 }
948
949 public void reopen () {
950 open = true;
951 edit = true;
952 }
953
954 /** Move path. */
955 public void move (double delta_x, double delta_y) {
956 foreach (EditPoint ep in points) {
957 ep.x += delta_x;
958 ep.y += delta_y;
959 }
960
961 update_region_boundaries ();
962 }
963
964 private void update_region_boundaries_for_point (EditPoint p) {
965 EditPointHandle left_handle;
966 EditPointHandle right_handle;
967
968 left_handle = p.get_left_handle ();
969 right_handle = p.get_right_handle ();
970
971 if (p.x > xmax) {
972 xmax = p.x;
973 }
974
975 if (p.x < xmin) {
976 xmin = p.x;
977 }
978
979 if (p.y > ymax) {
980 ymax = p.y;
981 }
982
983 if (p.y < ymin) {
984 ymin = p.y;
985 }
986
987 update_region_boundaries_for_handle (left_handle);
988 update_region_boundaries_for_handle (right_handle);
989 }
990
991 private void update_region_boundaries_for_handle (EditPointHandle h) {
992 if (h.x > xmax) {
993 xmax = h.x;
994 }
995
996 if (h.x < xmin) {
997 xmin = h.x;
998 }
999
1000 if (h.y > ymax) {
1001 ymax = h.y;
1002 }
1003
1004 if (h.y < ymin) {
1005 ymin = h.y;
1006 }
1007 }
1008
1009 public void update_region_boundaries () {
1010 xmax = -10000;
1011 xmin = 10000;
1012 ymax = -10000;
1013 ymin = 10000;
1014
1015 if (points.size == 0) {
1016 xmax = 0;
1017 xmin = 0;
1018 ymax = 0;
1019 ymin = 0;
1020 }
1021
1022 foreach (EditPoint p in points) {
1023 update_region_boundaries_for_point (p);
1024 }
1025
1026 if (stroke > 0) {
1027 xmax += stroke;
1028 ymax += stroke;
1029 xmin -= stroke;
1030 ymin -= stroke;
1031 }
1032 }
1033
1034 /** Test if @param path is a valid outline for this object. */
1035 public bool test_is_outline (Path path) {
1036 assert (false);
1037 return this.test_is_outline_of_path (path) && path.test_is_outline_of_path (this);
1038 }
1039
1040 private bool test_is_outline_of_path (Path outline)
1041 requires (outline.points.size >= 2 || points.size >= 2)
1042 {
1043 // rather slow use it for testing, only
1044 unowned EditPoint i = outline.points.get (0).get_link_item ();
1045 unowned EditPoint prev = outline.points.get (outline.points.size - 1).get_link_item ();
1046
1047 double tolerance = 1;
1048 bool g = false;
1049
1050 EditPoint ep = new EditPoint (0, 0);
1051 double min = double.MAX;
1052
1053 while (true) {
1054 min = 10000;
1055
1056 all_of (prev, i, (cx, cy) => {
1057 get_closest_point_on_path (ep, cx, cy);
1058
1059 double n = pow (ep.x - cx, 2) + pow (cy - ep.y, 2);
1060
1061 if (n < min) min = n;
1062
1063 if (n < tolerance) {
1064 g = true;
1065 return false;
1066 }
1067
1068 return true;
1069 });
1070
1071 if (!g) {
1072 critical (@"this path does not seem to be the outline. (min $min)");
1073 }
1074
1075 g = false;
1076
1077 if (i == outline.points.get (outline.points.size - 1)) {
1078 break;
1079 }
1080
1081 i = i.get_next ();
1082 }
1083
1084 return true;
1085 }
1086
1087 /** Add the extra point between line handles for double curve. */
1088 public void add_hidden_double_points () requires (points.size > 1) {
1089 EditPoint hidden;
1090 EditPoint prev;
1091 EditPoint first = points.get (points.size - 1);
1092 PointType left;
1093 PointType right;
1094 double x, y;
1095 Gee.ArrayList<EditPoint> middle_points = new Gee.ArrayList<EditPoint> ();
1096 Gee.ArrayList<EditPoint> first_points = new Gee.ArrayList<EditPoint> ();
1097
1098 foreach (EditPoint next in points) {
1099 left = first.get_right_handle ().type;
1100 right = next.get_left_handle ().type;
1101
1102 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1103 first.get_right_handle ().type = PointType.QUADRATIC;
1104
1105 // half way between handles
1106 x = first.get_right_handle ().x + (next.get_left_handle ().x - first.get_right_handle ().x) / 2;
1107 y = first.get_right_handle ().y + (next.get_left_handle ().y - first.get_right_handle ().y) / 2;
1108
1109 hidden = new EditPoint (x, y, PointType.QUADRATIC);
1110 hidden.right_handle.move_to_coordinate_internal (next.get_left_handle ().x, next.get_left_handle ().y);
1111 hidden.get_right_handle ().type = PointType.QUADRATIC;
1112
1113 hidden.get_left_handle ().type = PointType.QUADRATIC;
1114 hidden.type = PointType.QUADRATIC;
1115
1116 first.get_right_handle ().type = PointType.QUADRATIC;
1117 first.type = PointType.QUADRATIC;
1118
1119 next.get_left_handle ().type = PointType.QUADRATIC;
1120 next.type = PointType.QUADRATIC;
1121
1122 middle_points.add (hidden);
1123 first_points.add (first);
1124 }
1125 first = next;
1126 }
1127
1128 for (int i = 0; i < middle_points.size; i++) {
1129 hidden = middle_points.get (i);
1130 add_point_after (middle_points.get (i), first_points.get (i));
1131 }
1132
1133 create_list ();
1134
1135 prev= get_last_point ();
1136 foreach (EditPoint ep in points) {
1137 if (ep.type == PointType.QUADRATIC) {
1138 x = prev.get_right_handle ().x;
1139 y = prev.get_right_handle ().y;
1140 ep.get_left_handle ().move_to_coordinate (x, y);
1141 }
1142 prev = ep;
1143 }
1144 }
1145
1146 /** Convert quadratic bezier points to cubic representation of the glyph
1147 * for ttf-export.
1148 */
1149 public Path get_quadratic_points () {
1150 PointConverter converter = new PointConverter (this);
1151 return converter.get_quadratic_path ();
1152 }
1153
1154 public void insert_new_point_on_path (EditPoint ep, double t = -1, bool move_point_to_path = false) {
1155 EditPoint start, stop;
1156 double x0, x1, y0, y1;
1157 double position, min;
1158 PointType left, right;
1159 double closest_x = 0;
1160 double closest_y = 0;
1161
1162 if (ep.next == null || ep.prev == null) {
1163 warning ("missing point");
1164 return;
1165 }
1166
1167 start = ep.get_prev ();
1168 stop = ep.get_next ();
1169
1170 right = start.get_right_handle ().type;
1171 left = stop.get_left_handle ().type;
1172
1173 if (right == PointType.CUBIC || left == PointType.CUBIC) {
1174 start.get_right_handle ().type = PointType.CUBIC;
1175 stop.get_left_handle ().type = PointType.CUBIC;
1176 }
1177
1178 add_point_after (ep, ep.get_prev ());
1179
1180 min = double.MAX;
1181
1182 position = 0.5;
1183
1184 if (t < 0) {
1185 all_of (start, stop, (cx, cy, t) => {
1186 double n = pow (ep.x - cx, 2) + pow (ep.y - cy, 2);
1187
1188 if (n < min) {
1189 min = n;
1190 position = t;
1191 closest_x = cx;
1192 closest_y = cy;
1193 }
1194
1195 return true;
1196 });
1197
1198 if (move_point_to_path) {
1199 ep.x = closest_x;
1200 ep.y = closest_y;
1201 }
1202 } else {
1203 position = t;
1204 }
1205
1206 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1207 double_bezier_vector (position, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x, out x0, out x1);
1208 double_bezier_vector (position, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y, out y0, out y1);
1209
1210 ep.get_left_handle ().set_point_type (PointType.DOUBLE_CURVE);
1211 ep.get_right_handle ().set_point_type (PointType.DOUBLE_CURVE);
1212
1213 ep.get_left_handle ().move_to_coordinate (x0, y0); // FIXME: SWAPPED?
1214 ep.get_right_handle ().move_to_coordinate (x1, y1);
1215
1216 ep.type = PointType.DOUBLE_CURVE;
1217 } else if (right == PointType.QUADRATIC) {
1218 x0 = quadratic_bezier_vector (1 - position, stop.x, start.get_right_handle ().x, start.x);
1219 y0 = quadratic_bezier_vector (1 - position, stop.y, start.get_right_handle ().y, start.y);
1220 ep.get_right_handle ().move_to_coordinate (x0, y0);
1221
1222 ep.get_left_handle ().set_point_type (PointType.QUADRATIC);
1223 ep.get_right_handle ().set_point_type (PointType.QUADRATIC);
1224
1225 ep.get_left_handle ().move_to_coordinate_internal (0, 0);
1226
1227 ep.type = PointType.QUADRATIC;
1228 } else if (right == PointType.CUBIC || left == PointType.CUBIC) {
1229 bezier_vector (position, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x, out x0, out x1);
1230 bezier_vector (position, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y, out y0, out y1);
1231
1232 ep.get_left_handle ().set_point_type (PointType.CUBIC);
1233 ep.get_left_handle ().move_to_coordinate (x0, y0);
1234
1235 ep.get_right_handle ().set_point_type (PointType.CUBIC);
1236 ep.get_right_handle ().move_to_coordinate (x1, y1);
1237
1238 ep.type = PointType.LINE_CUBIC;
1239 } else if (right == PointType.LINE_QUADRATIC && left == PointType.LINE_QUADRATIC) {
1240 ep.get_right_handle ().set_point_type (PointType.LINE_QUADRATIC);
1241 ep.get_left_handle ().set_point_type (PointType.LINE_QUADRATIC);
1242 ep.type = PointType.QUADRATIC;
1243 } else if (right == PointType.LINE_CUBIC && left == PointType.LINE_CUBIC) {
1244 ep.get_right_handle ().set_point_type (PointType.LINE_CUBIC);
1245 ep.get_left_handle ().set_point_type (PointType.LINE_CUBIC);
1246 ep.type = PointType.LINE_CUBIC;
1247 } else if (right == PointType.LINE_DOUBLE_CURVE && left == PointType.LINE_DOUBLE_CURVE) {
1248 ep.get_right_handle ().set_point_type (PointType.LINE_DOUBLE_CURVE);
1249 ep.get_left_handle ().set_point_type (PointType.LINE_DOUBLE_CURVE);
1250 ep.type = PointType.DOUBLE_CURVE;
1251 } else
1252
1253 ep.get_left_handle ().parent = ep;
1254 ep.get_right_handle ().parent = ep;
1255
1256 stop.get_left_handle ().length *= 1 - position;
1257 start.get_right_handle ().length *= position;
1258
1259 if (right == PointType.QUADRATIC) { // update connected handle
1260 if (ep.prev != null) {
1261 ep.get_left_handle ().move_to_coordinate_internal (
1262 ep.get_prev ().right_handle.x,
1263 ep.get_prev ().right_handle.y);
1264
1265 } else {
1266 warning ("ep.prev is null for quadratic point");
1267 }
1268 }
1269
1270 create_list ();
1271 foreach (EditPoint p in points) {
1272 p.recalculate_linear_handles ();
1273 }
1274 }
1275
1276 /** Get a point on the this path closest to x and y coordinates. */
1277 public void get_closest_point_on_path (EditPoint edit_point, double x, double y) {
1278 return_if_fail (points.size >= 1);
1279
1280 double min = double.MAX;
1281 double n = 0;
1282 bool g = false;
1283
1284 double ox = 0;
1285 double oy = 0;
1286
1287 EditPoint prev = points.get (points.size - 1).get_link_item ();
1288 EditPoint i = points.get (0).get_link_item ();
1289
1290 bool done = false;
1291 bool exit = false;
1292 bool first = true;
1293
1294 EditPoint? previous_point = null;
1295 EditPoint? next_point = null;
1296
1297 EditPoint previous;
1298 EditPoint next;
1299 double step = 0;
1300
1301 if (points.size == 0) {
1302 warning ("Empty path.");
1303 return;
1304 }
1305
1306 if (points.size == 1) {
1307 edit_point.x = i.x;
1308 edit_point.y = i.y;
1309
1310 edit_point.prev = i;
1311 edit_point.next = i;
1312 return;
1313 }
1314
1315 edit_point.x = i.x;
1316 edit_point.y = i.y;
1317
1318 create_list ();
1319
1320 while (!exit) {
1321 if (!first && i == points.get (points.size - 1)) {
1322 done = true;
1323 }
1324
1325 if (!done) {
1326 i = i.get_next ();
1327 prev = i.get_prev ();
1328 } else if (done && !is_open ()) {
1329 i = points.get (0).get_link_item ();
1330 prev = points.get (points.size - 1).get_link_item ();
1331 exit = true;
1332 } else {
1333 break;
1334 }
1335
1336 all_of (prev, i, (cx, cy, t) => {
1337 n = pow (x - cx, 2) + pow (y - cy, 2);
1338
1339 if (n < min) {
1340 min = n;
1341
1342 ox = cx;
1343 oy = cy;
1344
1345 previous_point = i.prev;
1346 next_point = i;
1347
1348 step = t;
1349
1350 g = true;
1351 }
1352
1353 return true;
1354 });
1355
1356 first = false;
1357 }
1358
1359 if (previous_point == null && is_open ()) {
1360 previous_point = points.get (points.size - 1).get_link_item ();
1361 }
1362
1363 if (previous_point == null) {
1364 warning (@"previous_point == null, points.size: $(points.size)");
1365 return;
1366 }
1367
1368 if (next_point == null) {
1369 warning ("next_point != null");
1370 return;
1371 }
1372
1373 previous = (!) previous_point;
1374 next = (!) next_point;
1375
1376 edit_point.prev = previous_point;
1377 edit_point.next = next_point;
1378
1379 edit_point.set_position (ox, oy);
1380 }
1381
1382 public static bool all_of (EditPoint start, EditPoint stop,
1383 RasterIterator iter, int steps = -1,
1384 double min_t = 0, double max_t = 1) {
1385
1386 PointType right = PenTool.to_curve (start.get_right_handle ().type);
1387 PointType left = PenTool.to_curve (stop.get_left_handle ().type);
1388
1389 if (steps == -1) {
1390 steps = (int) (10 * get_length_from (start, stop));
1391 }
1392
1393 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1394 return all_of_double (start.x, start.y, start.get_right_handle ().x, start.get_right_handle ().y, stop.get_left_handle ().x, stop.get_left_handle ().y, stop.x, stop.y, iter, steps, min_t, max_t);
1395 } else if (right == PointType.QUADRATIC && left == PointType.QUADRATIC) {
1396 return all_of_quadratic_curve (start.x, start.y, start.get_right_handle ().x, start.get_right_handle ().y, stop.x, stop.y, iter, steps, min_t, max_t);
1397 } else if (right == PointType.CUBIC && left == PointType.CUBIC) {
1398 return all_of_curve (start.x, start.y, start.get_right_handle ().x, start.get_right_handle ().y, stop.get_left_handle ().x, stop.get_left_handle ().y, stop.x, stop.y, iter, steps, min_t, max_t);
1399 }
1400
1401 if (start.x == stop.x && start.y == stop.y) {
1402 warning ("Zero length.");
1403 return true;
1404 }
1405
1406 warning (@"Mixed point types in segment $(start.x),$(start.y) to $(stop.x),$(stop.y) right: $(right), left: $(left) (start: $(start.type), stop: $(stop.type))");
1407 return all_of_quadratic_curve (start.x, start.y, start.get_right_handle ().x, start.get_right_handle ().x, stop.x, stop.y, iter, steps);
1408 }
1409
1410 public static void get_point_for_step (EditPoint start, EditPoint stop, double step, out double x, out double y) {
1411 // FIXME: Types
1412 x = bezier_path (step, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x);
1413 y = bezier_path (step, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y);
1414 }
1415
1416 private static bool all_of_double (double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3,
1417 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1418
1419 double px = x1;
1420 double py = y1;
1421
1422 double t;
1423 double middle_x, middle_y;
1424 double double_step;
1425
1426 middle_x = x1 + (x2 - x1) / 2;
1427 middle_y = y1 + (y2 - y1) / 2;
1428
1429 for (int i = 0; i < steps; i++) {
1430 t = i / steps + min_t;
1431
1432 px = quadratic_bezier_path (t, x0, x1, middle_x);
1433 py = quadratic_bezier_path (t, y0, y1, middle_y);
1434
1435 double_step = t / 2;
1436
1437 if (double_step > max_t) {
1438 return false;
1439 }
1440
1441 if (!iter (px, py, double_step)) {
1442 return false;
1443 }
1444 }
1445
1446 for (int i = 0; i < steps; i++) {
1447 t = i / steps + min_t;
1448
1449 px = quadratic_bezier_path (t, middle_x, x2, x3);
1450 py = quadratic_bezier_path (t, middle_y, y2, y3);
1451
1452 double_step = 0.5 + t / 2;
1453
1454 if (double_step > max_t) {
1455 return false;
1456 }
1457
1458 if (!iter (px, py, double_step)) {
1459 return false;
1460 }
1461 }
1462
1463 return true;
1464 }
1465
1466 private static bool all_of_quadratic_curve (double x0, double y0, double x1, double y1, double x2, double y2,
1467 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1468 double px = x1;
1469 double py = y1;
1470
1471 double t;
1472
1473 for (int i = 0; i < steps; i++) {
1474 t = i / steps + min_t;
1475
1476 px = quadratic_bezier_path (t, x0, x1, x2);
1477 py = quadratic_bezier_path (t, y0, y1, y2);
1478
1479 if (t > max_t) {
1480 return false;
1481 }
1482
1483 if (!iter (px, py, t)) {
1484 return false;
1485 }
1486 }
1487
1488 return true;
1489 }
1490
1491 private static bool all_of_curve (double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3,
1492 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1493 double px = x1;
1494 double py = y1;
1495
1496 double t;
1497
1498 for (int i = 0; i < steps; i++) {
1499 t = i / steps + min_t;
1500
1501 px = bezier_path (t, x0, x1, x2, x3);
1502 py = bezier_path (t, y0, y1, y2, y3);
1503
1504 if (t > max_t) {
1505 return false;
1506 }
1507
1508 if (!iter (px, py, t)) {
1509 return false;
1510 }
1511 }
1512
1513 return true;
1514 }
1515
1516 public bool all_segments (SegmentIterator iter) {
1517 unowned EditPoint i, next;
1518
1519 if (points.size < 2) {
1520 return false;
1521 }
1522
1523 for (int j = 0; j < points.size - 1; j++) {
1524 i = points.get (j).get_link_item ();
1525 next = i.get_next ();
1526 if (!iter (i, next)) {
1527 return false;
1528 }
1529 }
1530
1531 if (!is_open ()) {
1532 return iter (points.get (points.size - 1), points.get (0));
1533 }
1534
1535 return true;
1536 }
1537
1538 public void all_of_path (RasterIterator iter, int steps = -1) {
1539 all_segments ((start, stop) => {
1540 return all_of (start, stop, iter, steps);
1541 });
1542 }
1543
1544 public static double bezier_path (double step, double p0, double p1, double p2, double p3) {
1545 double q0, q1, q2;
1546 double r0, r1;
1547
1548 q0 = step * (p1 - p0) + p0;
1549 q1 = step * (p2 - p1) + p1;
1550 q2 = step * (p3 - p2) + p2;
1551
1552 r0 = step * (q1 - q0) + q0;
1553 r1 = step * (q2 - q1) + q1;
1554
1555 return step * (r1 - r0) + r0;
1556 }
1557
1558 public static void bezier_vector (double step, double p0, double p1, double p2, double p3, out double a0, out double a1) {
1559 double q0, q1, q2;
1560
1561 q0 = step * (p1 - p0) + p0;
1562 q1 = step * (p2 - p1) + p1;
1563 q2 = step * (p3 - p2) + p2;
1564
1565 a0 = step * (q1 - q0) + q0;
1566 a1 = step * (q2 - q1) + q1;
1567 }
1568
1569 public static double quadratic_bezier_vector (double step, double p0, double p1, double p2) {
1570 return step * (p1 - p0) + p0;
1571 }
1572
1573 public static double quadratic_bezier_path (double step, double p0, double p1, double p2) {
1574 double q0 = step * (p1 - p0) + p0;
1575 double q1 = step * (p2 - p1) + p1;
1576
1577 return step * (q1 - q0) + q0;
1578 }
1579
1580 public static double double_bezier_path (double step, double p0, double p1, double p2, double p3) {
1581 double middle = p1 + (p2 - p1) / 2;
1582
1583 if (step == 0.5) {
1584 // FIXME: return the middle point
1585 warning ("Middle");
1586 }
1587
1588 if (step < 0.5) {
1589 return quadratic_bezier_path (2 * step, p0, p1, middle);
1590 }
1591
1592 return quadratic_bezier_path (2 * (step - 0.5), middle, p2, p3);
1593 }
1594
1595 public static void double_bezier_vector (double step, double p0, double p1, double p2, double p3, out double a0, out double a1) {
1596 double b0, b1, c0, c1, d0, d1;
1597
1598 if (unlikely (step <= 0 || step >= 1)) {
1599 warning (@"Bad step: $step");
1600 step += 0.00004;
1601 }
1602
1603 // set angle
1604 b0 = double_bezier_path (step + 0.00001, p0, p1, p2, p3);
1605 c0 = double_bezier_path (step + 0.00002, p0, p1, p2, p3);
1606
1607 b1 = double_bezier_path (step - 0.00001, p0, p1, p2, p3);
1608 c1 = double_bezier_path (step - 0.00002, p0, p1, p2, p3);
1609
1610 // adjust length
1611 d0 = b0 + (b0 - c0) * 25000 * (step);
1612 d1 = b1 + (b1 - c1) * 25000 * (1 - step);
1613
1614 a0 = d0;
1615 a1 = d1;
1616 }
1617
1618 public void plot (Context cr, WidgetAllocation allocation, double view_zoom) {
1619 double px = 0, py = 0;
1620 double xc = allocation.width / 2.0;
1621 double yc = allocation.height / 2.0;
1622
1623 cr.save ();
1624
1625 all_of_path ((x, y) => {
1626 //Theme.color (cr, "Background 5");
1627 cr.move_to (px + xc, -py + yc);
1628 cr.line_to (x + xc, -y + yc);
1629
1630 px = x;
1631 py = y;
1632
1633 return true;
1634 });
1635
1636 cr.stroke ();
1637 cr.restore ();
1638 }
1639
1640 public void print_boundaries () {
1641 stderr.printf (@"xmax $xmax \n");
1642 stderr.printf (@"xmin $xmin \n");
1643 stderr.printf (@"ymax $ymax \n");
1644 stderr.printf (@"ymin $ymin \n");
1645 }
1646
1647 public bool has_region_boundaries () {
1648 return !(xmax == -10000 || xmin == 10000 || ymax == -10000 || ymin == 10000);
1649 }
1650
1651 public void create_list () {
1652 EditPoint ep;
1653
1654 if (points.size == 0) {
1655 return;
1656 }
1657
1658 if (points.size == 1) {
1659 ep = points.get (0);
1660 ep.next = null;
1661 ep.prev = null;
1662 return;
1663 }
1664
1665 ep = points.get (0);
1666 ep.next = points.get (1).get_link_item ();
1667 ep.prev = points.get (points.size - 1).get_link_item ();
1668
1669 for (int i = 1; i < points.size - 1; i++) {
1670 ep = points.get (i);
1671 ep.prev = points.get (i - 1).get_link_item ();
1672 ep.next = points.get (i + 1).get_link_item ();
1673 }
1674
1675 ep = points.get (points.size - 1);
1676 ep.next = points.get (0).get_link_item ();
1677 ep.prev = points.get (points.size - 2).get_link_item ();
1678 }
1679
1680 public bool has_point (EditPoint ep) {
1681 return points.contains (ep);
1682 }
1683
1684 public bool has_deleted_point () {
1685 foreach (EditPoint p in points) {
1686 if (p.deleted) {
1687 return true;
1688 }
1689 }
1690 return false;
1691 }
1692
1693 /** @return the remaining parts as a new path. */
1694 public PathList process_deleted_points ()
1695 requires (points.size > 0)
1696 {
1697 EditPoint p;
1698 EditPoint ep;
1699 Path current_path = new Path ();
1700 Path remaining_points = new Path ();
1701 PathList path_list = new PathList ();
1702 int i;
1703 int index = 0;
1704
1705 if (!has_deleted_point ()) {
1706 return path_list;
1707 }
1708
1709 if (points.size == 1) {
1710 points.remove_at (0);
1711 return path_list;
1712 }
1713
1714 // set start position to a point that will be removed
1715 for (i = 0; i < points.size; i++) {
1716 p = points.get (i);
1717
1718 if (p.deleted) {
1719 index = i;
1720 i++;
1721 ep = p;
1722 break;
1723 }
1724 }
1725
1726 // don't tie end points on the open path
1727 if (points.size > 1) {
1728 p = points.get (1);
1729 p.convert_to_curve ();
1730 p.set_reflective_handles (false);
1731 p.set_tie_handle (false);
1732 }
1733
1734 if (points.size > 0) {
1735 p = points.get (points.size - 1);
1736 p.convert_to_curve ();
1737 p.set_reflective_handles (false);
1738 p.set_tie_handle (false);
1739 }
1740
1741 // copy points after the deleted point
1742 while (i < points.size) {
1743 p = points.get (i);
1744 current_path.add_point (p);
1745 i++;
1746 }
1747
1748 // copy points before the deleted point
1749 for (i = 0; i < index; i++) {
1750 p = points.get (i);
1751 remaining_points.add_point (p);
1752 }
1753
1754 // merge if we still only have one path
1755 if (!is_open ()) {
1756 foreach (EditPoint point in remaining_points.points) {
1757 current_path.add_point (point.copy ());
1758 }
1759
1760 if (current_path.points.size > 0) {
1761 ep = current_path.points.get (0);
1762 ep.set_tie_handle (false);
1763 ep.set_reflective_handles (false);
1764 ep.get_left_handle ().type = PenTool.to_line (ep.type);
1765 ep.type = PenTool.to_curve (ep.type);
1766 path_list.add (current_path);
1767
1768 ep = current_path.points.get (current_path.points.size - 1);
1769 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1770 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1771 }
1772 } else {
1773 if (current_path.points.size > 0) {
1774 ep = current_path.points.get (0);
1775 ep.set_tie_handle (false);
1776 ep.set_reflective_handles (false);
1777 ep.get_left_handle ().type = PenTool.to_line (ep.type);
1778 ep.type = PenTool.to_curve (ep.type);
1779 set_new_start (current_path.points.get (0));
1780 path_list.add (current_path);
1781
1782 ep = current_path.points.get (current_path.points.size - 1);
1783 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1784 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1785 }
1786
1787 if (remaining_points.points.size > 0) {
1788 remaining_points.points.get (0).set_tie_handle (false);
1789 remaining_points.points.get (0).set_reflective_handles (false);
1790 remaining_points.points.get (0).type = remaining_points.points.get (0).type;
1791 set_new_start (remaining_points.points.get (0));
1792 path_list.add (remaining_points);
1793
1794 if (current_path.points.size > 0) {
1795 ep = current_path.points.get (current_path.points.size - 1);
1796 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1797 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1798 }
1799 }
1800 }
1801
1802 foreach (Path path in path_list.paths) {
1803 path.update_region_boundaries ();
1804 }
1805
1806 return path_list;
1807 }
1808
1809 public void set_new_start (EditPoint ep) {
1810 Gee.ArrayList<EditPoint> list = new Gee.ArrayList<EditPoint> ();
1811 uint len = points.size;
1812 EditPoint iter = points.get (0);
1813 EditPoint? ni = null;
1814 bool found = false;
1815
1816 foreach (EditPoint it in points) {
1817 if (it == ep) {
1818 found = true;
1819 break;
1820 }
1821
1822 iter = iter.get_next ();
1823 ni = (!) iter;
1824 }
1825
1826 if (unlikely (!found)) {
1827 warning ("Could not find edit point.");
1828 }
1829
1830 if (ni == null) {
1831 return;
1832 }
1833
1834 iter = (!) ni;
1835
1836 for (uint i = 0; i < len; i++) {
1837 list.add (iter);
1838
1839 if (iter == points.get (points.size - 1)) {
1840 iter = points.get (0).get_link_item ();
1841 } else {
1842 iter = iter.get_next ();
1843 }
1844 }
1845
1846 points.clear ();
1847
1848 foreach (EditPoint p in list) {
1849 points.add (p);
1850 }
1851 }
1852
1853 public void append_path (Path path) {
1854 if (points.size == 0 || path.points.size == 0) {
1855 warning ("No points");
1856 return;
1857 }
1858
1859 // copy remaining points
1860 foreach (EditPoint p in path.points) {
1861 add_point (p.copy ());
1862 }
1863
1864 path.points.clear ();
1865 }
1866
1867 /** Roatate around coordinate xc, xc. */
1868 public void rotate (double theta, double xc, double yc) {
1869 double a, radius;
1870
1871 foreach (EditPoint ep in points) {
1872 radius = sqrt (pow (xc - ep.x, 2) + pow (yc + ep.y, 2));
1873
1874 if (yc + ep.y < 0) {
1875 radius = -radius;
1876 }
1877
1878 a = acos ((ep.x - xc) / radius);
1879
1880 ep.x = xc + cos (a - theta) * radius;
1881 ep.y = yc + sin (a - theta) * radius;
1882
1883 ep.get_right_handle ().angle -= theta;
1884 ep.get_left_handle ().angle -= theta;
1885
1886 while (ep.get_right_handle ().angle < 0) {
1887 ep.get_right_handle ().angle += 2 * PI;
1888 }
1889
1890 while (ep.get_left_handle ().angle < 0) {
1891 ep.get_left_handle ().angle += 2 * PI;
1892 }
1893 }
1894
1895 rotation += theta;
1896 rotation %= 2 * PI;
1897
1898 update_region_boundaries ();
1899 }
1900
1901 public void flip_vertical () {
1902 EditPointHandle hl, hr;
1903 double lx, ly, rx, ry;
1904
1905 foreach (EditPoint e in points) {
1906 hl = e.get_left_handle ();
1907 hr = e.get_right_handle ();
1908
1909 lx = hl.x;
1910 ly = hl.y;
1911 rx = hr.x;
1912 ry = hr.y;
1913
1914 e.y *= -1;
1915
1916 hr.move_to_coordinate_internal (rx, -1 * ry);
1917 hl.move_to_coordinate_internal (lx, -1 * ly);
1918 }
1919
1920 update_region_boundaries ();
1921 }
1922
1923 public void flip_horizontal () {
1924 EditPointHandle hl, hr;
1925 double lx, ly, rx, ry;
1926 foreach (EditPoint e in points) {
1927 hl = e.get_left_handle ();
1928 hr = e.get_right_handle ();
1929
1930 lx = hl.x;
1931 ly = hl.y;
1932 rx = hr.x;
1933 ry = hr.y;
1934
1935 e.x *= -1;
1936
1937 hr.move_to_coordinate_internal (-1 * rx, ry);
1938 hl.move_to_coordinate_internal (-1 * lx, ly);
1939 }
1940
1941 update_region_boundaries ();
1942 }
1943
1944 public void init_point_type () {
1945 PointType type;
1946
1947 switch (DrawingTools.point_type) {
1948 case PointType.QUADRATIC:
1949 type = PointType.LINE_QUADRATIC;
1950 break;
1951 case PointType.DOUBLE_CURVE:
1952 type = PointType.LINE_DOUBLE_CURVE;
1953 break;
1954 case PointType.CUBIC:
1955 type = PointType.LINE_CUBIC;
1956 break;
1957 default:
1958 warning ("No type is set");
1959 type = PointType.LINE_CUBIC;
1960 break;
1961 }
1962
1963 foreach (EditPoint ep in points) {
1964 ep.type = type;
1965 ep.get_right_handle ().type = type;
1966 ep.get_left_handle ().type = type;
1967 }
1968 }
1969
1970 public void convert_path_ending_to_line () {
1971 if (points.size < 2) {
1972 return;
1973 }
1974
1975 get_first_point ().get_left_handle ().convert_to_line ();
1976 get_last_point ().get_right_handle ().convert_to_line ();
1977 }
1978
1979 public void print_all_types () {
1980 print (@"Control points:\n");
1981 foreach (EditPoint ep in points) {
1982 print (@"$(ep.type) L: $(ep.get_left_handle ().type) R: L: $(ep.get_right_handle ().type)\n");
1983 }
1984 }
1985
1986 /** Find the point where two lines intersect. */
1987 public static void find_intersection (double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4,
1988 out double point_x, out double point_y) {
1989 point_x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
1990 point_y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
1991 }
1992
1993 public static void find_intersection_handle (EditPointHandle h1, EditPointHandle h2, out double point_x, out double point_y) {
1994 find_intersection (h1.parent.x, h1.parent.y, h1.x, h1.y, h2.parent.x, h2.parent.y, h2.x, h2.y, out point_x, out point_y);
1995 }
1996
1997 /** Finx intersection point for two straight lines. */
1998 public static void find_intersection_point (EditPoint p1, EditPoint p2, EditPoint q1, EditPoint q2, out double point_x, out double point_y) {
1999 find_intersection (p1.x, p1.y, p2.x, p2.y, q1.x, q1.y, q2.x, q2.y, out point_x, out point_y);
2000 }
2001
2002 public void add_extrema () {
2003 double x0, y0, x1, y1, x2, y2, x3, y3;
2004 double minx, maxx, miny, maxy;
2005
2006 if (unlikely (points.size < 2)) {
2007 warning (@"Missing points, $(points.size) points in path.");
2008 return;
2009 }
2010
2011 minx = Glyph.CANVAS_MAX;
2012 miny = Glyph.CANVAS_MAX;
2013 maxx = Glyph.CANVAS_MIN;
2014 maxy = Glyph.CANVAS_MIN;
2015
2016 x0 = 0;
2017 y0 = 0;
2018 x1 = 0;
2019 y1 = 0;
2020 x2 = 0;
2021 y2 = 0;
2022 x3 = 0;
2023 y3 = 0;
2024
2025 all_of_path ((x, y) => {
2026 if (x < minx) {
2027 x0 = x;
2028 y0 = y;
2029 minx = x;
2030 }
2031
2032 if (x > maxx) {
2033 x1 = x;
2034 y1 = y;
2035 maxx = x;
2036 }
2037
2038 if (y < miny) {
2039 x2 = x;
2040 y2 = y;
2041 miny = y;
2042 }
2043
2044 if (y > maxy) {
2045 x3 = x;
2046 y3 = y;
2047 maxy = y;
2048 }
2049
2050 return true;
2051 });
2052
2053 insert_new_point_on_path_at (x0 - 0.001, y0);
2054 insert_new_point_on_path_at (x1 + 0.001, y1);
2055 insert_new_point_on_path_at (x2, y2 - 0.001);
2056 insert_new_point_on_path_at (x3, y3 + 0.001);
2057 }
2058
2059 public EditPoint insert_new_point_on_path_at (double x, double y) {
2060 EditPoint ep = new EditPoint ();
2061 EditPoint prev, next;
2062 bool exists;
2063
2064 if (points.size < 2) {
2065 warning ("Can't add extrema to just one point.");
2066 return ep;
2067 }
2068
2069 get_closest_point_on_path (ep, x, y);
2070
2071 next = (ep.next == null) ? points.get (0) : ep.get_next ();
2072 prev = (ep.prev == null) ? points.get (points.size - 1) : ep.get_prev ();
2073
2074 exists = prev.x == ep.x && prev.y == ep.y;
2075 exists |= next.x == ep.x && next.y == ep.y;
2076
2077 if (!exists) {
2078 insert_new_point_on_path (ep);
2079 }
2080
2081 return ep;
2082 }
2083
2084 public static bool is_counter (PathList pl, Path path) {
2085 return counters (pl, path) % 2 != 0;
2086 }
2087
2088 public static int counters (PathList pl, Path path) {
2089 int inside_count = 0;
2090 bool inside;
2091
2092 foreach (Path p in pl.paths) {
2093 if (p.points.size > 1 && p != path) {
2094 inside = true;
2095 foreach (EditPoint ep in path.points) {
2096 if (!SvgParser.is_inside (ep, p)) {
2097 inside = false;
2098 }
2099 }
2100
2101 if (inside) {
2102 inside_count++;
2103 }
2104 }
2105 }
2106
2107 return inside_count;
2108 }
2109
2110 /** @param t smallest distance to other points. */
2111 public void remove_points_on_points (double t = 0.00001) {
2112 Gee.ArrayList<EditPoint> remove = new Gee.ArrayList<EditPoint> ();
2113 EditPoint n;
2114 EditPointHandle hr, h;
2115
2116 if (points.size == 0) {
2117 return;
2118 }
2119
2120 create_list ();
2121
2122 foreach (EditPoint ep in points) {
2123 if (ep.next != null) {
2124 n = ep.get_next ();
2125 } else {
2126 n = points.get (0);
2127 }
2128
2129 if (fabs (n.x - ep.x) < t && fabs (n.y - ep.y) < t) {
2130 remove.add (ep);
2131 }
2132 }
2133
2134 foreach (EditPoint r in remove) {
2135 if (r.next != null) {
2136 n = r.get_next ();
2137 } else {
2138 n = points.get (0);
2139 }
2140
2141 points.remove (r);
2142 h = n.get_left_handle ();
2143 hr = r.get_left_handle ();
2144 h.length = hr.length;
2145 h.angle = hr.angle;
2146 h.type = hr.type;
2147
2148 if (h.length < t) {
2149 h.length = t;
2150 h.angle = n.get_right_handle ().angle - PI;
2151 }
2152
2153 create_list ();
2154 }
2155
2156 recalculate_linear_handles ();
2157 }
2158
2159 public void remove_deleted_points () {
2160 Gee.ArrayList<EditPoint> p = new Gee.ArrayList<EditPoint> ();
2161
2162 foreach (EditPoint ep in points) {
2163 if (ep.deleted) {
2164 p.add (ep);
2165 }
2166 }
2167
2168 foreach (EditPoint e in p) {
2169 points.remove (e);
2170 }
2171
2172 create_list ();
2173 }
2174
2175 public static void find_closes_point_in_segment (EditPoint ep0, EditPoint ep1,
2176 double px, double py,
2177 out double nx, out double ny,
2178 double max_step = 200) {
2179
2180 double min_distance = double.MAX;
2181 double npx, npy;
2182 double min_t, max_t;
2183 double rmin_t, rmax_t;
2184 bool found;
2185 int step;
2186
2187 npx = 0;
2188 npy = 0;
2189
2190 min_t = 0;
2191 max_t = 1;
2192
2193 rmin_t = 0;
2194 rmax_t = 1;
2195
2196 for (step = 3; step <= max_step; step *= 2) {
2197 found = false;
2198 min_distance = double.MAX;
2199 Path.all_of (ep0, ep1, (xa, ya, ta) => {
2200 double d = Path.distance (px, xa, py, ya);
2201
2202 if (d < min_distance) {
2203 min_distance = d;
2204 npx = xa;
2205 npy = ya;
2206 rmin_t = ta - 1.0 / step;
2207 rmax_t = ta + 1.0 / step;
2208 found = true;
2209 }
2210
2211 return true;
2212 }, step, min_t, max_t);
2213
2214 if (!found) {
2215 rmin_t = 1 - (1.0 / step);
2216 rmax_t = 1;
2217 }
2218
2219 min_t = (rmin_t > 0) ? rmin_t : 0;
2220 max_t = (rmax_t < 1) ? rmax_t : 1;
2221 }
2222
2223 nx = npx;
2224 ny = npy;
2225 }
2226 }
2227
2228 }
2229