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 point_distance (EditPoint p1, EditPoint p2) {
748 return distance (p1.x, p2.x, p1.y, p2.y);
749 }
750
751 public static double distance (double ax, double bx, double ay, double by) {
752 return Math.fabs (Math.sqrt (Math.pow (ax - bx, 2) + Math.pow (ay - by, 2)));
753 }
754
755 public static double distance_to_point (EditPoint a, EditPoint b) {
756 return distance (a.x, b.x, a.y, b.y);
757 }
758
759 public static double distance_pixels (double x1, double y1, double x2, double y2) {
760 return distance (Glyph.path_coordinate_x (x1),
761 Glyph.path_coordinate_x (x2),
762 Glyph.path_coordinate_x (y1),
763 Glyph.path_coordinate_x (y2));
764 }
765
766 public static double get_length_from (EditPoint a, EditPoint b) {
767 double x, y;
768
769 x = Math.fabs (a.x - a.get_right_handle ().x);
770 x += Math.fabs (a.get_right_handle ().x - b.get_left_handle ().x );
771 x += Math.fabs (b.get_left_handle ().x - b.x);
772
773 y = Math.fabs (a.y - a.get_right_handle ().y);
774 y += Math.fabs (a.get_right_handle ().y - b.get_left_handle ().y);
775 y += Math.fabs (b.get_left_handle ().y - b.y);
776
777 return Math.fabs (Math.sqrt (x * x + y * y));
778 }
779
780 /** Variable precision */
781 public bool is_over_coordinate_var (double x, double y) {
782 PathList pathlist;
783 int width;
784 ClickMap click_map;
785 int px, py;
786 int click_x, click_y;
787
788 if (points.size < 2) {
789 return false;
790 }
791
792 if (stroke > 0) {
793 pathlist = StrokeTool.get_stroke (this, stroke);
794
795 if (pathlist.paths.size > 1) {
796 if (pathlist.paths.get (1).is_over_coordinate_var (x, y)) {
797 return false;
798 }
799 }
800
801 return pathlist.get_first_path ().is_over_coordinate_var (x, y);
802 }
803
804 if (!is_over_boundry (x, y)) {
805 return false;
806 }
807
808 // generate a rasterized image of the object
809 width = 160;
810 click_map = new ClickMap (width);
811 px = 0;
812 py = 0;
813
814 click_map.create_click_map (this);
815
816 click_x = (int) (width * ((x - xmin) / (xmax - xmin)));
817 click_y = (int) (width * ((y - ymin) / (ymax - ymin)));
818
819 return click_map.get_value (click_x, click_y);
820 }
821
822 public bool is_over_boundry (double x, double y) {
823 if (unlikely (ymin == double.MAX || ymin == 10000)) {
824 warning ("bounding box is not calculated, run update_region_boundaries first.");
825 update_region_boundaries ();
826 }
827
828 return (ymin <= y <= ymax) && (xmin <= x <= xmax);
829 }
830
831 public bool has_overlapping_boundry (Path p) {
832 return !(xmax <= p.xmin || ymax <= p.ymin) || (xmin >= p.xmax || ymin >= p.ymax);
833 }
834
835 // FIXME: DELETE?
836 public EditPoint delete_first_point () {
837 EditPoint r;
838 int size;
839
840 size = points.size;
841 if (unlikely (size == 0)) {
842 warning ("No points in path.");
843 return new EditPoint ();
844 }
845
846 r = points.get (0);
847 points.remove_at (0);
848
849 if (size > 1) {
850 r.get_next ().prev = null;
851 }
852
853 return r;
854 }
855
856 public EditPoint delete_last_point () {
857 EditPoint r;
858 int size;
859
860 size = points.size;
861 if (unlikely (size == 0)) {
862 warning ("No points in path.");
863 return new EditPoint ();
864 }
865
866 r = points.get (size - 1);
867 points.remove_at (size - 1);
868
869 if (size > 1) {
870 r.get_prev ().next = null;
871
872 if (r.next != null) {
873 r.get_next ().prev = null;
874 }
875 }
876
877 return r;
878 }
879
880 public EditPoint add (double x, double y) {
881 if (points.size > 0) {
882 return add_after (x, y, points.get (points.size - 1));
883 }
884
885 return add_after (x, y, null);
886 }
887
888 public EditPoint add_point (EditPoint p) {
889 if (points.size > 0) {
890 return add_point_after (p, points.get (points.size - 1));
891 }
892
893 return add_point_after (p, null);
894 }
895
896 /** Insert a new point after @param previous_point and return a reference
897 * to the new item in list.
898 */
899 public EditPoint add_after (double x, double y, EditPoint? previous_point) {
900 EditPoint p = new EditPoint (x, y, PointType.NONE);
901 return add_point_after (p, previous_point);
902 }
903
904 /** @return a list item pointing to the new point */
905 public EditPoint add_point_after (EditPoint p, EditPoint? previous_point) {
906 int prev_index;
907
908 if (unlikely (previous_point == null && points.size != 0)) {
909 warning ("previous_point == null");
910 previous_point = points.get (points.size - 1).get_link_item ();
911 }
912
913 if (points.size == 0) {
914 points.add (p);
915 p.prev = points.get (0).get_link_item ();
916 p.next = points.get (0).get_link_item ();
917 } else {
918 p.prev = (!) previous_point;
919 p.next = ((!) previous_point).next;
920
921 prev_index = points.index_of ((!) previous_point);
922
923 if (unlikely (!(0 <= prev_index < points.size))) {
924 warning ("no previous point");
925 }
926
927 points.insert (prev_index + 1, p);
928 }
929
930 last_point = p;
931
932 return p;
933 }
934
935 public void recalculate_linear_handles () {
936 foreach (EditPoint e in points) {
937 e.recalculate_linear_handles ();
938 }
939 }
940
941 public void close () {
942 open = false;
943 edit = false;
944
945 create_list ();
946
947 if (points.size > 2) {
948 points.get (0).recalculate_linear_handles ();
949 points.get (points.size - 1).recalculate_linear_handles ();
950 }
951 }
952
953 public void reopen () {
954 open = true;
955 edit = true;
956 }
957
958 /** Move path. */
959 public void move (double delta_x, double delta_y) {
960 foreach (EditPoint ep in points) {
961 ep.x += delta_x;
962 ep.y += delta_y;
963 }
964
965 update_region_boundaries ();
966 }
967
968 private void update_region_boundaries_for_point (EditPoint p) {
969 EditPointHandle left_handle;
970 EditPointHandle right_handle;
971
972 left_handle = p.get_left_handle ();
973 right_handle = p.get_right_handle ();
974
975 if (p.x > xmax) {
976 xmax = p.x;
977 }
978
979 if (p.x < xmin) {
980 xmin = p.x;
981 }
982
983 if (p.y > ymax) {
984 ymax = p.y;
985 }
986
987 if (p.y < ymin) {
988 ymin = p.y;
989 }
990
991 update_region_boundaries_for_handle (left_handle);
992 update_region_boundaries_for_handle (right_handle);
993 }
994
995 private void update_region_boundaries_for_handle (EditPointHandle h) {
996 if (h.x > xmax) {
997 xmax = h.x;
998 }
999
1000 if (h.x < xmin) {
1001 xmin = h.x;
1002 }
1003
1004 if (h.y > ymax) {
1005 ymax = h.y;
1006 }
1007
1008 if (h.y < ymin) {
1009 ymin = h.y;
1010 }
1011 }
1012
1013 public void update_region_boundaries () {
1014 xmax = -10000;
1015 xmin = 10000;
1016 ymax = -10000;
1017 ymin = 10000;
1018
1019 if (points.size == 0) {
1020 xmax = 0;
1021 xmin = 0;
1022 ymax = 0;
1023 ymin = 0;
1024 }
1025
1026 foreach (EditPoint p in points) {
1027 update_region_boundaries_for_point (p);
1028 }
1029
1030 if (stroke > 0) {
1031 xmax += stroke;
1032 ymax += stroke;
1033 xmin -= stroke;
1034 ymin -= stroke;
1035 }
1036 }
1037
1038 /** Test if @param path is a valid outline for this object. */
1039 public bool test_is_outline (Path path) {
1040 assert (false);
1041 return this.test_is_outline_of_path (path) && path.test_is_outline_of_path (this);
1042 }
1043
1044 private bool test_is_outline_of_path (Path outline)
1045 requires (outline.points.size >= 2 || points.size >= 2)
1046 {
1047 // rather slow use it for testing, only
1048 unowned EditPoint i = outline.points.get (0).get_link_item ();
1049 unowned EditPoint prev = outline.points.get (outline.points.size - 1).get_link_item ();
1050
1051 double tolerance = 1;
1052 bool g = false;
1053
1054 EditPoint ep = new EditPoint (0, 0);
1055 double min = double.MAX;
1056
1057 while (true) {
1058 min = 10000;
1059
1060 all_of (prev, i, (cx, cy) => {
1061 get_closest_point_on_path (ep, cx, cy);
1062
1063 double n = pow (ep.x - cx, 2) + pow (cy - ep.y, 2);
1064
1065 if (n < min) min = n;
1066
1067 if (n < tolerance) {
1068 g = true;
1069 return false;
1070 }
1071
1072 return true;
1073 });
1074
1075 if (!g) {
1076 critical (@"this path does not seem to be the outline. (min $min)");
1077 }
1078
1079 g = false;
1080
1081 if (i == outline.points.get (outline.points.size - 1)) {
1082 break;
1083 }
1084
1085 i = i.get_next ();
1086 }
1087
1088 return true;
1089 }
1090
1091 /** Add the extra point between line handles for double curve. */
1092 public void add_hidden_double_points () requires (points.size > 1) {
1093 EditPoint hidden;
1094 EditPoint prev;
1095 EditPoint first = points.get (points.size - 1);
1096 PointType left;
1097 PointType right;
1098 double x, y;
1099 Gee.ArrayList<EditPoint> middle_points = new Gee.ArrayList<EditPoint> ();
1100 Gee.ArrayList<EditPoint> first_points = new Gee.ArrayList<EditPoint> ();
1101
1102 foreach (EditPoint next in points) {
1103 left = first.get_right_handle ().type;
1104 right = next.get_left_handle ().type;
1105
1106 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1107 first.get_right_handle ().type = PointType.QUADRATIC;
1108
1109 // half way between handles
1110 x = first.get_right_handle ().x + (next.get_left_handle ().x - first.get_right_handle ().x) / 2;
1111 y = first.get_right_handle ().y + (next.get_left_handle ().y - first.get_right_handle ().y) / 2;
1112
1113 hidden = new EditPoint (x, y, PointType.QUADRATIC);
1114 hidden.right_handle.move_to_coordinate_internal (next.get_left_handle ().x, next.get_left_handle ().y);
1115 hidden.get_right_handle ().type = PointType.QUADRATIC;
1116
1117 hidden.get_left_handle ().type = PointType.QUADRATIC;
1118 hidden.type = PointType.QUADRATIC;
1119
1120 first.get_right_handle ().type = PointType.QUADRATIC;
1121 first.type = PointType.QUADRATIC;
1122
1123 next.get_left_handle ().type = PointType.QUADRATIC;
1124 next.type = PointType.QUADRATIC;
1125
1126 middle_points.add (hidden);
1127 first_points.add (first);
1128 }
1129 first = next;
1130 }
1131
1132 for (int i = 0; i < middle_points.size; i++) {
1133 hidden = middle_points.get (i);
1134 add_point_after (middle_points.get (i), first_points.get (i));
1135 }
1136
1137 create_list ();
1138
1139 prev= get_last_point ();
1140 foreach (EditPoint ep in points) {
1141 if (ep.type == PointType.QUADRATIC) {
1142 x = prev.get_right_handle ().x;
1143 y = prev.get_right_handle ().y;
1144 ep.get_left_handle ().move_to_coordinate (x, y);
1145 }
1146 prev = ep;
1147 }
1148 }
1149
1150 /** Convert quadratic bezier points to cubic representation of the glyph
1151 * for ttf-export.
1152 */
1153 public Path get_quadratic_points () {
1154 PointConverter converter = new PointConverter (this);
1155 return converter.get_quadratic_path ();
1156 }
1157
1158 public void insert_new_point_on_path (EditPoint ep, double t = -1, bool move_point_to_path = false) {
1159 EditPoint start, stop;
1160 double x0, x1, y0, y1;
1161 double position, min;
1162 PointType left, right;
1163 double closest_x = 0;
1164 double closest_y = 0;
1165
1166 if (ep.next == null || ep.prev == null) {
1167 warning ("missing point");
1168 return;
1169 }
1170
1171 start = ep.get_prev ();
1172 stop = ep.get_next ();
1173
1174 right = start.get_right_handle ().type;
1175 left = stop.get_left_handle ().type;
1176
1177 if (right == PointType.CUBIC || left == PointType.CUBIC) {
1178 start.get_right_handle ().type = PointType.CUBIC;
1179 stop.get_left_handle ().type = PointType.CUBIC;
1180 }
1181
1182 add_point_after (ep, ep.get_prev ());
1183
1184 min = double.MAX;
1185
1186 position = 0.5;
1187
1188 if (t < 0) {
1189 all_of (start, stop, (cx, cy, t) => {
1190 double n = pow (ep.x - cx, 2) + pow (ep.y - cy, 2);
1191
1192 if (n < min) {
1193 min = n;
1194 position = t;
1195 closest_x = cx;
1196 closest_y = cy;
1197 }
1198
1199 return true;
1200 });
1201
1202 if (move_point_to_path) {
1203 ep.x = closest_x;
1204 ep.y = closest_y;
1205 }
1206 } else {
1207 position = t;
1208 }
1209
1210 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1211 double_bezier_vector (position, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x, out x0, out x1);
1212 double_bezier_vector (position, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y, out y0, out y1);
1213
1214 ep.get_left_handle ().set_point_type (PointType.DOUBLE_CURVE);
1215 ep.get_right_handle ().set_point_type (PointType.DOUBLE_CURVE);
1216
1217 ep.get_left_handle ().move_to_coordinate (x0, y0); // FIXME: SWAPPED?
1218 ep.get_right_handle ().move_to_coordinate (x1, y1);
1219
1220 ep.type = PointType.DOUBLE_CURVE;
1221 } else if (right == PointType.QUADRATIC) {
1222 x0 = quadratic_bezier_vector (1 - position, stop.x, start.get_right_handle ().x, start.x);
1223 y0 = quadratic_bezier_vector (1 - position, stop.y, start.get_right_handle ().y, start.y);
1224 ep.get_right_handle ().move_to_coordinate (x0, y0);
1225
1226 ep.get_left_handle ().set_point_type (PointType.QUADRATIC);
1227 ep.get_right_handle ().set_point_type (PointType.QUADRATIC);
1228
1229 ep.get_left_handle ().move_to_coordinate_internal (0, 0);
1230
1231 ep.type = PointType.QUADRATIC;
1232 } else if (right == PointType.CUBIC || left == PointType.CUBIC) {
1233 bezier_vector (position, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x, out x0, out x1);
1234 bezier_vector (position, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y, out y0, out y1);
1235
1236 ep.get_left_handle ().set_point_type (PointType.CUBIC);
1237 ep.get_left_handle ().move_to_coordinate (x0, y0);
1238
1239 ep.get_right_handle ().set_point_type (PointType.CUBIC);
1240 ep.get_right_handle ().move_to_coordinate (x1, y1);
1241
1242 ep.type = PointType.LINE_CUBIC;
1243 } else if (right == PointType.LINE_QUADRATIC && left == PointType.LINE_QUADRATIC) {
1244 ep.get_right_handle ().set_point_type (PointType.LINE_QUADRATIC);
1245 ep.get_left_handle ().set_point_type (PointType.LINE_QUADRATIC);
1246 ep.type = PointType.QUADRATIC;
1247 } else if (right == PointType.LINE_CUBIC && left == PointType.LINE_CUBIC) {
1248 ep.get_right_handle ().set_point_type (PointType.LINE_CUBIC);
1249 ep.get_left_handle ().set_point_type (PointType.LINE_CUBIC);
1250 ep.type = PointType.LINE_CUBIC;
1251 } else if (right == PointType.LINE_DOUBLE_CURVE && left == PointType.LINE_DOUBLE_CURVE) {
1252 ep.get_right_handle ().set_point_type (PointType.LINE_DOUBLE_CURVE);
1253 ep.get_left_handle ().set_point_type (PointType.LINE_DOUBLE_CURVE);
1254 ep.type = PointType.DOUBLE_CURVE;
1255 } else
1256
1257 ep.get_left_handle ().parent = ep;
1258 ep.get_right_handle ().parent = ep;
1259
1260 stop.get_left_handle ().length *= 1 - position;
1261 start.get_right_handle ().length *= position;
1262
1263 if (right == PointType.QUADRATIC) { // update connected handle
1264 if (ep.prev != null) {
1265 ep.get_left_handle ().move_to_coordinate_internal (
1266 ep.get_prev ().right_handle.x,
1267 ep.get_prev ().right_handle.y);
1268
1269 } else {
1270 warning ("ep.prev is null for quadratic point");
1271 }
1272 }
1273
1274 create_list ();
1275 foreach (EditPoint p in points) {
1276 p.recalculate_linear_handles ();
1277 }
1278 }
1279
1280 /** Get a point on the this path closest to x and y coordinates. */
1281 public void get_closest_point_on_path (EditPoint edit_point, double x, double y) {
1282 return_if_fail (points.size >= 1);
1283
1284 double min = double.MAX;
1285 double n = 0;
1286 bool g = false;
1287
1288 double ox = 0;
1289 double oy = 0;
1290
1291 EditPoint prev = points.get (points.size - 1).get_link_item ();
1292 EditPoint i = points.get (0).get_link_item ();
1293
1294 bool done = false;
1295 bool exit = false;
1296 bool first = true;
1297
1298 EditPoint? previous_point = null;
1299 EditPoint? next_point = null;
1300
1301 EditPoint previous;
1302 EditPoint next;
1303 double step = 0;
1304
1305 if (points.size == 0) {
1306 warning ("Empty path.");
1307 return;
1308 }
1309
1310 if (points.size == 1) {
1311 edit_point.x = i.x;
1312 edit_point.y = i.y;
1313
1314 edit_point.prev = i;
1315 edit_point.next = i;
1316 return;
1317 }
1318
1319 edit_point.x = i.x;
1320 edit_point.y = i.y;
1321
1322 create_list ();
1323
1324 while (!exit) {
1325 if (!first && i == points.get (points.size - 1)) {
1326 done = true;
1327 }
1328
1329 if (!done) {
1330 i = i.get_next ();
1331 prev = i.get_prev ();
1332 } else if (done && !is_open ()) {
1333 i = points.get (0).get_link_item ();
1334 prev = points.get (points.size - 1).get_link_item ();
1335 exit = true;
1336 } else {
1337 break;
1338 }
1339
1340 all_of (prev, i, (cx, cy, t) => {
1341 n = pow (x - cx, 2) + pow (y - cy, 2);
1342
1343 if (n < min) {
1344 min = n;
1345
1346 ox = cx;
1347 oy = cy;
1348
1349 previous_point = i.prev;
1350 next_point = i;
1351
1352 step = t;
1353
1354 g = true;
1355 }
1356
1357 return true;
1358 });
1359
1360 first = false;
1361 }
1362
1363 if (previous_point == null && is_open ()) {
1364 previous_point = points.get (points.size - 1).get_link_item ();
1365 }
1366
1367 if (previous_point == null) {
1368 warning (@"previous_point == null, points.size: $(points.size)");
1369 return;
1370 }
1371
1372 if (next_point == null) {
1373 warning ("next_point != null");
1374 return;
1375 }
1376
1377 previous = (!) previous_point;
1378 next = (!) next_point;
1379
1380 edit_point.prev = previous_point;
1381 edit_point.next = next_point;
1382
1383 edit_point.set_position (ox, oy);
1384 }
1385
1386 public static bool all_of (EditPoint start, EditPoint stop,
1387 RasterIterator iter, int steps = -1,
1388 double min_t = 0, double max_t = 1) {
1389
1390 PointType right = PenTool.to_curve (start.get_right_handle ().type);
1391 PointType left = PenTool.to_curve (stop.get_left_handle ().type);
1392
1393 if (steps == -1) {
1394 steps = (int) (10 * get_length_from (start, stop));
1395 }
1396
1397 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1398 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);
1399 } else if (right == PointType.QUADRATIC && left == PointType.QUADRATIC) {
1400 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);
1401 } else if (right == PointType.CUBIC && left == PointType.CUBIC) {
1402 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);
1403 }
1404
1405 if (start.x == stop.x && start.y == stop.y) {
1406 warning ("Zero length.");
1407 return true;
1408 }
1409
1410 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))");
1411 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);
1412 }
1413
1414 public static void get_point_for_step (EditPoint start, EditPoint stop, double step, out double x, out double y) {
1415 // FIXME: Types
1416 x = bezier_path (step, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x);
1417 y = bezier_path (step, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y);
1418 }
1419
1420 private static bool all_of_double (double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3,
1421 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1422
1423 double px = x1;
1424 double py = y1;
1425
1426 double t;
1427 double middle_x, middle_y;
1428 double double_step;
1429
1430 middle_x = x1 + (x2 - x1) / 2;
1431 middle_y = y1 + (y2 - y1) / 2;
1432
1433 for (int i = 0; i < steps; i++) {
1434 t = i / steps + min_t;
1435
1436 px = quadratic_bezier_path (t, x0, x1, middle_x);
1437 py = quadratic_bezier_path (t, y0, y1, middle_y);
1438
1439 double_step = t / 2;
1440
1441 if (double_step > max_t) {
1442 return false;
1443 }
1444
1445 if (!iter (px, py, double_step)) {
1446 return false;
1447 }
1448 }
1449
1450 for (int i = 0; i < steps; i++) {
1451 t = i / steps + min_t;
1452
1453 px = quadratic_bezier_path (t, middle_x, x2, x3);
1454 py = quadratic_bezier_path (t, middle_y, y2, y3);
1455
1456 double_step = 0.5 + t / 2;
1457
1458 if (double_step > max_t) {
1459 return false;
1460 }
1461
1462 if (!iter (px, py, double_step)) {
1463 return false;
1464 }
1465 }
1466
1467 return true;
1468 }
1469
1470 private static bool all_of_quadratic_curve (double x0, double y0, double x1, double y1, double x2, double y2,
1471 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1472 double px = x1;
1473 double py = y1;
1474
1475 double t;
1476
1477 for (int i = 0; i < steps; i++) {
1478 t = i / steps + min_t;
1479
1480 px = quadratic_bezier_path (t, x0, x1, x2);
1481 py = quadratic_bezier_path (t, y0, y1, y2);
1482
1483 if (t > max_t) {
1484 return false;
1485 }
1486
1487 if (!iter (px, py, t)) {
1488 return false;
1489 }
1490 }
1491
1492 return true;
1493 }
1494
1495 private static bool all_of_curve (double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3,
1496 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1497 double px = x1;
1498 double py = y1;
1499
1500 double t;
1501
1502 for (int i = 0; i < steps; i++) {
1503 t = i / steps + min_t;
1504
1505 px = bezier_path (t, x0, x1, x2, x3);
1506 py = bezier_path (t, y0, y1, y2, y3);
1507
1508 if (t > max_t) {
1509 return false;
1510 }
1511
1512 if (!iter (px, py, t)) {
1513 return false;
1514 }
1515 }
1516
1517 return true;
1518 }
1519
1520 public bool all_segments (SegmentIterator iter) {
1521 unowned EditPoint i, next;
1522
1523 if (points.size < 2) {
1524 return false;
1525 }
1526
1527 for (int j = 0; j < points.size - 1; j++) {
1528 i = points.get (j).get_link_item ();
1529 next = i.get_next ();
1530 if (!iter (i, next)) {
1531 return false;
1532 }
1533 }
1534
1535 if (!is_open ()) {
1536 return iter (points.get (points.size - 1), points.get (0));
1537 }
1538
1539 return true;
1540 }
1541
1542 public void all_of_path (RasterIterator iter, int steps = -1) {
1543 all_segments ((start, stop) => {
1544 return all_of (start, stop, iter, steps);
1545 });
1546 }
1547
1548 public static double bezier_path (double step, double p0, double p1, double p2, double p3) {
1549 double q0, q1, q2;
1550 double r0, r1;
1551
1552 q0 = step * (p1 - p0) + p0;
1553 q1 = step * (p2 - p1) + p1;
1554 q2 = step * (p3 - p2) + p2;
1555
1556 r0 = step * (q1 - q0) + q0;
1557 r1 = step * (q2 - q1) + q1;
1558
1559 return step * (r1 - r0) + r0;
1560 }
1561
1562 public static void bezier_vector (double step, double p0, double p1, double p2, double p3, out double a0, out double a1) {
1563 double q0, q1, q2;
1564
1565 q0 = step * (p1 - p0) + p0;
1566 q1 = step * (p2 - p1) + p1;
1567 q2 = step * (p3 - p2) + p2;
1568
1569 a0 = step * (q1 - q0) + q0;
1570 a1 = step * (q2 - q1) + q1;
1571 }
1572
1573 public static double quadratic_bezier_vector (double step, double p0, double p1, double p2) {
1574 return step * (p1 - p0) + p0;
1575 }
1576
1577 public static double quadratic_bezier_path (double step, double p0, double p1, double p2) {
1578 double q0 = step * (p1 - p0) + p0;
1579 double q1 = step * (p2 - p1) + p1;
1580
1581 return step * (q1 - q0) + q0;
1582 }
1583
1584 public static double double_bezier_path (double step, double p0, double p1, double p2, double p3) {
1585 double middle = p1 + (p2 - p1) / 2;
1586
1587 if (step == 0.5) {
1588 // FIXME: return the middle point
1589 warning ("Middle");
1590 }
1591
1592 if (step < 0.5) {
1593 return quadratic_bezier_path (2 * step, p0, p1, middle);
1594 }
1595
1596 return quadratic_bezier_path (2 * (step - 0.5), middle, p2, p3);
1597 }
1598
1599 public static void double_bezier_vector (double step, double p0, double p1, double p2, double p3, out double a0, out double a1) {
1600 double b0, b1, c0, c1, d0, d1;
1601
1602 if (unlikely (step <= 0 || step >= 1)) {
1603 warning (@"Bad step: $step");
1604 step += 0.00004;
1605 }
1606
1607 // set angle
1608 b0 = double_bezier_path (step + 0.00001, p0, p1, p2, p3);
1609 c0 = double_bezier_path (step + 0.00002, p0, p1, p2, p3);
1610
1611 b1 = double_bezier_path (step - 0.00001, p0, p1, p2, p3);
1612 c1 = double_bezier_path (step - 0.00002, p0, p1, p2, p3);
1613
1614 // adjust length
1615 d0 = b0 + (b0 - c0) * 25000 * (step);
1616 d1 = b1 + (b1 - c1) * 25000 * (1 - step);
1617
1618 a0 = d0;
1619 a1 = d1;
1620 }
1621
1622 public void plot (Context cr, WidgetAllocation allocation, double view_zoom) {
1623 double px = 0, py = 0;
1624 double xc = allocation.width / 2.0;
1625 double yc = allocation.height / 2.0;
1626
1627 cr.save ();
1628
1629 all_of_path ((x, y) => {
1630 //Theme.color (cr, "Background 5");
1631 cr.move_to (px + xc, -py + yc);
1632 cr.line_to (x + xc, -y + yc);
1633
1634 px = x;
1635 py = y;
1636
1637 return true;
1638 });
1639
1640 cr.stroke ();
1641 cr.restore ();
1642 }
1643
1644 public void print_boundaries () {
1645 stderr.printf (@"xmax $xmax \n");
1646 stderr.printf (@"xmin $xmin \n");
1647 stderr.printf (@"ymax $ymax \n");
1648 stderr.printf (@"ymin $ymin \n");
1649 }
1650
1651 public bool has_region_boundaries () {
1652 return !(xmax == -10000 || xmin == 10000 || ymax == -10000 || ymin == 10000);
1653 }
1654
1655 public void create_list () {
1656 EditPoint ep;
1657
1658 if (points.size == 0) {
1659 return;
1660 }
1661
1662 if (points.size == 1) {
1663 ep = points.get (0);
1664 ep.next = null;
1665 ep.prev = null;
1666 return;
1667 }
1668
1669 ep = points.get (0);
1670 ep.next = points.get (1).get_link_item ();
1671 ep.prev = points.get (points.size - 1).get_link_item ();
1672
1673 for (int i = 1; i < points.size - 1; i++) {
1674 ep = points.get (i);
1675 ep.prev = points.get (i - 1).get_link_item ();
1676 ep.next = points.get (i + 1).get_link_item ();
1677 }
1678
1679 ep = points.get (points.size - 1);
1680 ep.next = points.get (0).get_link_item ();
1681 ep.prev = points.get (points.size - 2).get_link_item ();
1682 }
1683
1684 public bool has_point (EditPoint ep) {
1685 return points.contains (ep);
1686 }
1687
1688 public bool has_deleted_point () {
1689 foreach (EditPoint p in points) {
1690 if (p.deleted) {
1691 return true;
1692 }
1693 }
1694 return false;
1695 }
1696
1697 /** @return the remaining parts as a new path. */
1698 public PathList process_deleted_points ()
1699 requires (points.size > 0)
1700 {
1701 EditPoint p;
1702 EditPoint ep;
1703 Path current_path = new Path ();
1704 Path remaining_points = new Path ();
1705 PathList path_list = new PathList ();
1706 int i;
1707 int index = 0;
1708
1709 if (!has_deleted_point ()) {
1710 return path_list;
1711 }
1712
1713 if (points.size == 1) {
1714 points.remove_at (0);
1715 return path_list;
1716 }
1717
1718 // set start position to a point that will be removed
1719 for (i = 0; i < points.size; i++) {
1720 p = points.get (i);
1721
1722 if (p.deleted) {
1723 index = i;
1724 i++;
1725 ep = p;
1726 break;
1727 }
1728 }
1729
1730 // don't tie end points on the open path
1731 if (points.size > 1) {
1732 p = points.get (1);
1733 p.convert_to_curve ();
1734 p.set_reflective_handles (false);
1735 p.set_tie_handle (false);
1736 }
1737
1738 if (points.size > 0) {
1739 p = points.get (points.size - 1);
1740 p.convert_to_curve ();
1741 p.set_reflective_handles (false);
1742 p.set_tie_handle (false);
1743 }
1744
1745 // copy points after the deleted point
1746 while (i < points.size) {
1747 p = points.get (i);
1748 current_path.add_point (p);
1749 i++;
1750 }
1751
1752 // copy points before the deleted point
1753 for (i = 0; i < index; i++) {
1754 p = points.get (i);
1755 remaining_points.add_point (p);
1756 }
1757
1758 // merge if we still only have one path
1759 if (!is_open ()) {
1760 foreach (EditPoint point in remaining_points.points) {
1761 current_path.add_point (point.copy ());
1762 }
1763
1764 if (current_path.points.size > 0) {
1765 ep = current_path.points.get (0);
1766 ep.set_tie_handle (false);
1767 ep.set_reflective_handles (false);
1768 ep.get_left_handle ().type = PenTool.to_line (ep.type);
1769 ep.type = PenTool.to_curve (ep.type);
1770 path_list.add (current_path);
1771
1772 ep = current_path.points.get (current_path.points.size - 1);
1773 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1774 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1775 }
1776 } else {
1777 if (current_path.points.size > 0) {
1778 ep = current_path.points.get (0);
1779 ep.set_tie_handle (false);
1780 ep.set_reflective_handles (false);
1781 ep.get_left_handle ().type = PenTool.to_line (ep.type);
1782 ep.type = PenTool.to_curve (ep.type);
1783 set_new_start (current_path.points.get (0));
1784 path_list.add (current_path);
1785
1786 ep = current_path.points.get (current_path.points.size - 1);
1787 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1788 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1789 }
1790
1791 if (remaining_points.points.size > 0) {
1792 remaining_points.points.get (0).set_tie_handle (false);
1793 remaining_points.points.get (0).set_reflective_handles (false);
1794 remaining_points.points.get (0).type = remaining_points.points.get (0).type;
1795 set_new_start (remaining_points.points.get (0));
1796 path_list.add (remaining_points);
1797
1798 if (current_path.points.size > 0) {
1799 ep = current_path.points.get (current_path.points.size - 1);
1800 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1801 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1802 }
1803 }
1804 }
1805
1806 foreach (Path path in path_list.paths) {
1807 path.update_region_boundaries ();
1808 }
1809
1810 return path_list;
1811 }
1812
1813 public void set_new_start (EditPoint ep) {
1814 Gee.ArrayList<EditPoint> list = new Gee.ArrayList<EditPoint> ();
1815 uint len = points.size;
1816 EditPoint iter = points.get (0);
1817 EditPoint? ni = null;
1818 bool found = false;
1819
1820 foreach (EditPoint it in points) {
1821 if (it == ep) {
1822 found = true;
1823 break;
1824 }
1825
1826 iter = iter.get_next ();
1827 ni = (!) iter;
1828 }
1829
1830 if (unlikely (!found)) {
1831 warning ("Could not find edit point.");
1832 }
1833
1834 if (ni == null) {
1835 return;
1836 }
1837
1838 iter = (!) ni;
1839
1840 for (uint i = 0; i < len; i++) {
1841 list.add (iter);
1842
1843 if (iter == points.get (points.size - 1)) {
1844 iter = points.get (0).get_link_item ();
1845 } else {
1846 iter = iter.get_next ();
1847 }
1848 }
1849
1850 points.clear ();
1851
1852 foreach (EditPoint p in list) {
1853 points.add (p);
1854 }
1855 }
1856
1857 public void append_path (Path path) {
1858 if (points.size == 0 || path.points.size == 0) {
1859 warning ("No points");
1860 return;
1861 }
1862
1863 // copy remaining points
1864 foreach (EditPoint p in path.points) {
1865 add_point (p.copy ());
1866 }
1867
1868 path.points.clear ();
1869 }
1870
1871 /** Roatate around coordinate xc, xc. */
1872 public void rotate (double theta, double xc, double yc) {
1873 double a, radius;
1874
1875 foreach (EditPoint ep in points) {
1876 radius = sqrt (pow (xc - ep.x, 2) + pow (yc + ep.y, 2));
1877
1878 if (yc + ep.y < 0) {
1879 radius = -radius;
1880 }
1881
1882 a = acos ((ep.x - xc) / radius);
1883
1884 ep.x = xc + cos (a - theta) * radius;
1885 ep.y = yc + sin (a - theta) * radius;
1886
1887 ep.get_right_handle ().angle -= theta;
1888 ep.get_left_handle ().angle -= theta;
1889
1890 while (ep.get_right_handle ().angle < 0) {
1891 ep.get_right_handle ().angle += 2 * PI;
1892 }
1893
1894 while (ep.get_left_handle ().angle < 0) {
1895 ep.get_left_handle ().angle += 2 * PI;
1896 }
1897 }
1898
1899 rotation += theta;
1900 rotation %= 2 * PI;
1901
1902 update_region_boundaries ();
1903 }
1904
1905 public void flip_vertical () {
1906 EditPointHandle hl, hr;
1907 double lx, ly, rx, ry;
1908
1909 foreach (EditPoint e in points) {
1910 hl = e.get_left_handle ();
1911 hr = e.get_right_handle ();
1912
1913 lx = hl.x;
1914 ly = hl.y;
1915 rx = hr.x;
1916 ry = hr.y;
1917
1918 e.y *= -1;
1919
1920 hr.move_to_coordinate_internal (rx, -1 * ry);
1921 hl.move_to_coordinate_internal (lx, -1 * ly);
1922 }
1923
1924 update_region_boundaries ();
1925 }
1926
1927 public void flip_horizontal () {
1928 EditPointHandle hl, hr;
1929 double lx, ly, rx, ry;
1930 foreach (EditPoint e in points) {
1931 hl = e.get_left_handle ();
1932 hr = e.get_right_handle ();
1933
1934 lx = hl.x;
1935 ly = hl.y;
1936 rx = hr.x;
1937 ry = hr.y;
1938
1939 e.x *= -1;
1940
1941 hr.move_to_coordinate_internal (-1 * rx, ry);
1942 hl.move_to_coordinate_internal (-1 * lx, ly);
1943 }
1944
1945 update_region_boundaries ();
1946 }
1947
1948 public void init_point_type () {
1949 PointType type;
1950
1951 switch (DrawingTools.point_type) {
1952 case PointType.QUADRATIC:
1953 type = PointType.LINE_QUADRATIC;
1954 break;
1955 case PointType.DOUBLE_CURVE:
1956 type = PointType.LINE_DOUBLE_CURVE;
1957 break;
1958 case PointType.CUBIC:
1959 type = PointType.LINE_CUBIC;
1960 break;
1961 default:
1962 warning ("No type is set");
1963 type = PointType.LINE_CUBIC;
1964 break;
1965 }
1966
1967 foreach (EditPoint ep in points) {
1968 ep.type = type;
1969 ep.get_right_handle ().type = type;
1970 ep.get_left_handle ().type = type;
1971 }
1972 }
1973
1974 public void convert_path_ending_to_line () {
1975 if (points.size < 2) {
1976 return;
1977 }
1978
1979 get_first_point ().get_left_handle ().convert_to_line ();
1980 get_last_point ().get_right_handle ().convert_to_line ();
1981 }
1982
1983 public void print_all_types () {
1984 print (@"Control points:\n");
1985 foreach (EditPoint ep in points) {
1986 print (@"$(ep.type) L: $(ep.get_left_handle ().type) R: L: $(ep.get_right_handle ().type)\n");
1987 }
1988 }
1989
1990 /** Find the point where two lines intersect. */
1991 public static void find_intersection (double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4,
1992 out double point_x, out double point_y) {
1993 point_x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
1994 point_y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
1995 }
1996
1997 public static void find_intersection_handle (EditPointHandle h1, EditPointHandle h2, out double point_x, out double point_y) {
1998 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);
1999 }
2000
2001 /** Finx intersection point for two straight lines. */
2002 public static void find_intersection_point (EditPoint p1, EditPoint p2, EditPoint q1, EditPoint q2, out double point_x, out double point_y) {
2003 find_intersection (p1.x, p1.y, p2.x, p2.y, q1.x, q1.y, q2.x, q2.y, out point_x, out point_y);
2004 }
2005
2006 public void add_extrema () {
2007 double x0, y0, x1, y1, x2, y2, x3, y3;
2008 double minx, maxx, miny, maxy;
2009
2010 if (unlikely (points.size < 2)) {
2011 warning (@"Missing points, $(points.size) points in path.");
2012 return;
2013 }
2014
2015 minx = Glyph.CANVAS_MAX;
2016 miny = Glyph.CANVAS_MAX;
2017 maxx = Glyph.CANVAS_MIN;
2018 maxy = Glyph.CANVAS_MIN;
2019
2020 x0 = 0;
2021 y0 = 0;
2022 x1 = 0;
2023 y1 = 0;
2024 x2 = 0;
2025 y2 = 0;
2026 x3 = 0;
2027 y3 = 0;
2028
2029 all_of_path ((x, y) => {
2030 if (x < minx) {
2031 x0 = x;
2032 y0 = y;
2033 minx = x;
2034 }
2035
2036 if (x > maxx) {
2037 x1 = x;
2038 y1 = y;
2039 maxx = x;
2040 }
2041
2042 if (y < miny) {
2043 x2 = x;
2044 y2 = y;
2045 miny = y;
2046 }
2047
2048 if (y > maxy) {
2049 x3 = x;
2050 y3 = y;
2051 maxy = y;
2052 }
2053
2054 return true;
2055 });
2056
2057 insert_new_point_on_path_at (x0 - 0.001, y0);
2058 insert_new_point_on_path_at (x1 + 0.001, y1);
2059 insert_new_point_on_path_at (x2, y2 - 0.001);
2060 insert_new_point_on_path_at (x3, y3 + 0.001);
2061 }
2062
2063 public EditPoint insert_new_point_on_path_at (double x, double y) {
2064 EditPoint ep = new EditPoint ();
2065 EditPoint prev, next;
2066 bool exists;
2067
2068 if (points.size < 2) {
2069 warning ("Can't add extrema to just one point.");
2070 return ep;
2071 }
2072
2073 get_closest_point_on_path (ep, x, y);
2074
2075 next = (ep.next == null) ? points.get (0) : ep.get_next ();
2076 prev = (ep.prev == null) ? points.get (points.size - 1) : ep.get_prev ();
2077
2078 exists = prev.x == ep.x && prev.y == ep.y;
2079 exists |= next.x == ep.x && next.y == ep.y;
2080
2081 if (!exists) {
2082 insert_new_point_on_path (ep);
2083 }
2084
2085 return ep;
2086 }
2087
2088 public static bool is_counter (PathList pl, Path path) {
2089 return counters (pl, path) % 2 != 0;
2090 }
2091
2092 public static int counters (PathList pl, Path path) {
2093 int inside_count = 0;
2094 bool inside;
2095
2096 foreach (Path p in pl.paths) {
2097 if (p.points.size > 1 && p != path
2098 && path.boundaries_intersecting (p)) {
2099
2100 inside = true;
2101 foreach (EditPoint ep in path.points) {
2102 if (!SvgParser.is_inside (ep, p)) {
2103 inside = false;
2104 }
2105 }
2106
2107 if (inside) {
2108 inside_count++;
2109 }
2110 }
2111 }
2112
2113 return inside_count;
2114 }
2115
2116 public bool boundaries_intersecting (Path p) {
2117 bool xm1 = in_boundaries (p.xmin, p.ymin);
2118 bool xm2 = in_boundaries (p.xmax, p.ymax);
2119 bool xm3 = in_boundaries (p.xmin, p.ymax);
2120 bool xm4 = in_boundaries (p.xmax, p.ymin);
2121
2122 if (xm1 || xm2 || xm3 || xm3) {
2123 return true;
2124 }
2125
2126 xm1 = p.in_boundaries (xmin, ymin);
2127 xm2 = p.in_boundaries (xmax, ymax);
2128 xm3 = p.in_boundaries (xmin, ymax);
2129 xm4 = p.in_boundaries (xmax, ymin);
2130
2131 if (xm1 || xm2 || xm3 || xm3) {
2132 return true;
2133 }
2134
2135 return false;
2136 }
2137
2138 public bool in_boundaries (double x, double y) {
2139 return xmin <= x <= xmax && ymin <= y <= ymax;
2140 }
2141
2142 /** @param t smallest distance to other points. */
2143 public void remove_points_on_points (double t = 0.00001) {
2144 Gee.ArrayList<EditPoint> remove = new Gee.ArrayList<EditPoint> ();
2145 EditPoint n;
2146 EditPointHandle hr, h;
2147
2148 if (points.size == 0) {
2149 return;
2150 }
2151
2152 create_list ();
2153
2154 foreach (EditPoint ep in points) {
2155 if (ep.next != null) {
2156 n = ep.get_next ();
2157 } else {
2158 n = points.get (0);
2159 }
2160
2161 if (fabs (n.x - ep.x) < t && fabs (n.y - ep.y) < t) {
2162 remove.add (ep);
2163 }
2164 }
2165
2166 foreach (EditPoint r in remove) {
2167 if (r.next != null) {
2168 n = r.get_next ();
2169 } else {
2170 n = points.get (0);
2171 }
2172
2173 points.remove (r);
2174 h = n.get_left_handle ();
2175 hr = r.get_left_handle ();
2176 h.length = hr.length;
2177 h.angle = hr.angle;
2178 h.type = hr.type;
2179
2180 if (h.length < t) {
2181 h.length = t;
2182 h.angle = n.get_right_handle ().angle - PI;
2183 }
2184
2185 create_list ();
2186 }
2187
2188 recalculate_linear_handles ();
2189 }
2190
2191 public void remove_deleted_points () {
2192 Gee.ArrayList<EditPoint> p = new Gee.ArrayList<EditPoint> ();
2193
2194 foreach (EditPoint ep in points) {
2195 if (ep.deleted) {
2196 p.add (ep);
2197 }
2198 }
2199
2200 foreach (EditPoint e in p) {
2201 points.remove (e);
2202 }
2203
2204 create_list ();
2205 }
2206
2207 public static void find_closes_point_in_segment (EditPoint ep0, EditPoint ep1,
2208 double px, double py,
2209 out double nx, out double ny,
2210 double max_step = 200) {
2211
2212 double min_distance = double.MAX;
2213 double npx, npy;
2214 double min_t, max_t;
2215 double rmin_t, rmax_t;
2216 bool found;
2217 int step;
2218
2219 npx = 0;
2220 npy = 0;
2221
2222 min_t = 0;
2223 max_t = 1;
2224
2225 rmin_t = 0;
2226 rmax_t = 1;
2227
2228 for (step = 3; step <= max_step; step *= 2) {
2229 found = false;
2230 min_distance = double.MAX;
2231 Path.all_of (ep0, ep1, (xa, ya, ta) => {
2232 double d = Path.distance (px, xa, py, ya);
2233
2234 if (d < min_distance) {
2235 min_distance = d;
2236 npx = xa;
2237 npy = ya;
2238 rmin_t = ta - 1.0 / step;
2239 rmax_t = ta + 1.0 / step;
2240 found = true;
2241 }
2242
2243 return true;
2244 }, step, min_t, max_t);
2245
2246 if (!found) {
2247 rmin_t = 1 - (1.0 / step);
2248 rmax_t = 1;
2249 }
2250
2251 min_t = (rmin_t > 0) ? rmin_t : 0;
2252 max_t = (rmax_t < 1) ? rmax_t : 1;
2253 }
2254
2255 nx = npx;
2256 ny = npy;
2257 }
2258 }
2259
2260 }
2261