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 string color_left = "Control Point Handle";
414 string color_right = "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 = "Selected Control Point Handle";
423 } else if (e.get_right_handle ().active) {
424 color_right = "Active Control Point Handle";
425 } else {
426 color_right = "Control Point Handle";
427 }
428
429 if (e.get_left_handle ().selected) {
430 color_left = "Selected Control Point Handle";
431 } else if (e.get_left_handle ().active) {
432 color_left = "Active Control Point Handle";
433 } else {
434 color_left = "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 if (e.type != PointType.HIDDEN) {
451 if (e.type == PointType.CUBIC || e.type == PointType.LINE_CUBIC) {
452 if (e.is_selected ()) {
453 if (e.active_point) {
454 draw_control_point (cr, e.x, e.y, "Selected Active Cubic Control Point");
455 } else {
456 draw_control_point (cr, e.x, e.y, "Selected Cubic Control Point");
457 }
458 } else {
459 if (e.active_point) {
460 draw_control_point (cr, e.x, e.y, "Active Cubic Control Point");
461 } else {
462 draw_control_point (cr, e.x, e.y, "Cubic Control Point");
463 }
464 }
465 } else {
466 if (e.is_selected ()) {
467 if (e.active_point) {
468 draw_control_point (cr, e.x, e.y, "Selected Active Quadratic Control Point");
469 } else {
470 draw_control_point (cr, e.x, e.y, "Selected Quadratic Control Point");
471 }
472 } else {
473 if (e.active_point) {
474 draw_control_point (cr, e.x, e.y, "Active Quadratic Control Point");
475 } else {
476 draw_control_point (cr, e.x, e.y, "Quadratic Control Point");
477 }
478 }
479 }
480 }
481 }
482
483 public static void draw_control_point (Context cr, double x, double y, string color, double size = 3.5) {
484 Glyph g = MainWindow.get_current_glyph ();
485 double ivz = 1 / g.view_zoom;
486 double width = size * Math.sqrt (stroke_width) * ivz;
487 double xc = g.allocation.width / 2.0;
488 double yc = g.allocation.height / 2.0;
489
490 cr.save ();
491
492 x = xc + x - (width / 2.0) * ivz;
493 y = yc - y - (width / 2.0) * ivz;
494
495 Theme.color (cr, color);
496
497 cr.move_to (x, y);
498 cr.arc (x, y, width, 0, 2 * Math.PI);
499 cr.close_path ();
500 cr.fill ();
501
502 cr.restore ();
503 }
504
505 public static void draw_image (Context cr, ImageSurface img, double x, double y) {
506 Glyph g = MainWindow.get_current_glyph ();
507 double r = 1.0 / 10.0;
508
509 double width = Math.sqrt (stroke_width);
510
511 double ivz = 1 / g.view_zoom;
512 double ivs = 1 / width;
513
514 double xc = g.allocation.width / 2.0;
515 double yc = g.allocation.height / 2.0;
516
517 cr.save ();
518 cr.scale (ivz * width * r, ivz * width * r);
519
520 x = xc + x - (width * r * img.get_width () / 2.0) * ivz;
521 y = yc - y - (width * r * img.get_height () / 2.0) * ivz;
522
523 cr.set_source_surface (img, x * g.view_zoom * ivs * 1/r, y * g.view_zoom * ivs * 1/r);
524 cr.paint ();
525 cr.restore ();
526 }
527
528 /** Set direction for this path to clockwise for outline and
529 * counter clockwise for inline paths.
530 */
531 public bool force_direction (Direction direction) {
532 bool c = (direction == Direction.CLOCKWISE);
533 bool d = is_clockwise ();
534 direction_is_set = true;
535
536 if (c != d) {
537 this.reverse ();
538 }
539
540 d = is_clockwise ();
541 if (unlikely (d != c)) {
542 warning ("Failed to set direction for path in force_direction.");
543 return true;
544 }
545
546 return false;
547 }
548
549 /** Switch direction from clockwise path to counter clockwise path or vise versa. */
550 public void reverse () {
551 bool direction = is_clockwise ();
552
553 if (no_derived_direction) {
554 clockwise_direction = !clockwise_direction;
555 }
556
557 reverse_points ();
558
559 if (unlikely (direction == is_clockwise ())) {
560 stderr.printf ("Error: Direction did not change after reversing path.\n");
561 stderr.printf (@"Length: $(points.size)\n");
562 stderr.printf (@"No particular direction can be derived: $no_derived_direction \n");
563 warning ("Path.reverse () failed.\n");
564 }
565 }
566
567 private void reverse_points () requires (points.size > 0) {
568 EditPointHandle t;
569 Path p = copy ();
570 EditPoint e;
571
572 create_list ();
573
574 points.clear ();
575
576 for (int i = p.points.size - 1; i >= 0 ; i--) {
577 e = p.points.get (i);
578
579 t = e.right_handle;
580 e.right_handle = e.left_handle;
581 e.left_handle = t;
582
583 add_point (e);
584 }
585
586 create_list ();
587 }
588
589 public void print_all_points () {
590 int i = 0;
591 foreach (EditPoint p in points) {
592 ++i;
593 string t = (p.type == PointType.END) ? " endpoint" : "";
594 stdout.printf (@"Point $i at ($(p.x), $(p.y)) $t \n");
595 }
596 }
597
598 private double clockwise_sum () {
599 double sum = 0;
600
601 return_val_if_fail (points.size >= 3, 0);
602
603 foreach (EditPoint e in points) {
604 sum += e.get_direction ();
605 }
606
607 return sum;
608 }
609
610 public bool is_clockwise () {
611 double s;
612
613 if (unlikely (points.size <= 2)) {
614 no_derived_direction = true;
615 return clockwise_direction;
616 }
617
618 s = clockwise_sum ();
619
620 if (s == 0) {
621 no_derived_direction = true;
622 return clockwise_direction;
623 }
624
625 return s > 0;
626 }
627
628 public bool is_editable () {
629 return edit;
630 }
631
632 /** Show control points on outline path. */
633 public void set_editable (bool e) {
634 edit = e;
635 }
636
637 public bool is_open () {
638 return open;
639 }
640
641 /** Resize path relative to bottom left coordinates. */
642 public void resize (double ratio) {
643 foreach (EditPoint p in points) {
644 p.x *= ratio;
645 p.y *= ratio;
646 p.right_handle.length *= ratio;
647 p.left_handle.length *= ratio;
648 }
649
650 xmin *= ratio;
651 xmax *= ratio;
652 ymin *= ratio;
653 ymax *= ratio;
654 }
655
656 public void scale (double scale_x, double scale_y) {
657 foreach (EditPoint p in points) {
658 p.right_handle.length *= scale_x * scale_y;
659 p.left_handle.length *= scale_x * scale_y;
660 }
661
662 foreach (EditPoint p in points) {
663 p.x *= scale_x;
664 p.y *= scale_y;
665 }
666
667 xmin *= scale_x;
668 xmax *= scale_x;
669 ymin *= scale_y;
670 ymax *= scale_y;
671 }
672
673 public Path copy () {
674 Path new_path = new Path ();
675 EditPoint p;
676
677 foreach (EditPoint ep in points) {
678 p = ep.copy ();
679 new_path.add_point (p);
680 }
681
682 new_path.edit = edit;
683 new_path.open = open;
684 new_path.stroke = stroke;
685 new_path.skew = skew;
686 new_path.fill = fill;
687 new_path.direction_is_set = direction_is_set;
688 new_path.create_list ();
689
690 new_path.hide_end_handle = hide_end_handle;
691 new_path.highlight_last_segment = highlight_last_segment;
692
693 return new_path;
694 }
695
696 public bool is_over (double x, double y) {
697 Glyph g = MainWindow.get_current_glyph ();
698
699 x = x * Glyph.ivz () + g.view_offset_x - Glyph.xc ();
700 y = y * Glyph.ivz () + g.view_offset_y - Glyph.yc ();
701
702 y *= -1;
703
704 return is_over_coordinate (x, y);
705 }
706
707 public bool is_over_coordinate (double x, double y) {
708 return is_over_coordinate_var (x, y);
709 }
710
711 public static double distance (double ax, double bx, double ay, double by) {
712 return Math.fabs (Math.sqrt (Math.pow (ax - bx, 2) + Math.pow (ay - by, 2)));
713 }
714
715 public static double distance_to_point (EditPoint a, EditPoint b) {
716 return distance (a.x, b.x, a.y, b.y);
717 }
718
719 public static double distance_pixels (double x1, double y1, double x2, double y2) {
720 return distance (Glyph.path_coordinate_x (x1),
721 Glyph.path_coordinate_x (x2),
722 Glyph.path_coordinate_x (y1),
723 Glyph.path_coordinate_x (y2));
724 }
725
726 public static double get_length_from (EditPoint a, EditPoint b) {
727 double x, y;
728
729 x = Math.fabs (a.x - a.get_right_handle ().x);
730 x += Math.fabs (a.get_right_handle ().x - b.get_left_handle ().x );
731 x += Math.fabs (b.get_left_handle ().x - b.x);
732
733 y = Math.fabs (a.y - a.get_right_handle ().y);
734 y += Math.fabs (a.get_right_handle ().y - b.get_left_handle ().y);
735 y += Math.fabs (b.get_left_handle ().y - b.y);
736
737 return Math.fabs (Math.sqrt (x * x + y * y));
738 }
739
740 /** Variable precision */
741 public bool is_over_coordinate_var (double x, double y) {
742 PathList pathlist;
743 int width;
744 ClickMap click_map;
745 int px, py;
746 int click_x, click_y;
747
748 if (points.size < 2) {
749 return false;
750 }
751
752 if (stroke > 0) {
753 pathlist = StrokeTool.get_stroke (this, stroke);
754
755 if (pathlist.paths.size > 1) {
756 if (pathlist.paths.get (1).is_over_coordinate_var (x, y)) {
757 return false;
758 }
759 }
760
761 return pathlist.get_first_path ().is_over_coordinate_var (x, y);
762 }
763
764 if (!is_over_boundry (x, y)) {
765 return false;
766 }
767
768
769 // generate a rasterized image of the object
770 width = 160;
771 click_map = new ClickMap (width);
772 px = 0;
773 py = 0;
774
775 click_map.create_click_map (this);
776
777 click_x = (int) (width * ((x - xmin) / (xmax - xmin)));
778 click_y = (int) (width * ((y - ymin) / (ymax - ymin)));
779
780 return click_map.get_value (click_x, click_y);
781 }
782
783 public bool is_over_boundry (double x, double y) {
784 if (unlikely (ymin == double.MAX || ymin == 10000)) {
785 warning ("bounding box is not calculated, run update_region_boundaries first.");
786 update_region_boundaries ();
787 }
788
789 return (ymin <= y <= ymax) && (xmin <= x <= xmax);
790 }
791
792 public bool has_overlapping_boundry (Path p) {
793 return !(xmax <= p.xmin || ymax <= p.ymin) || (xmin >= p.xmax || ymin >= p.ymax);
794 }
795
796 // FIXME: DELETE?
797 public EditPoint delete_first_point () {
798 EditPoint r;
799 int size;
800
801 size = points.size;
802 if (unlikely (size == 0)) {
803 warning ("No points in path.");
804 return new EditPoint ();
805 }
806
807 r = points.get (0);
808 points.remove_at (0);
809
810 if (size > 1) {
811 r.get_next ().prev = null;
812 }
813
814 return r;
815 }
816
817 public EditPoint delete_last_point () {
818 EditPoint r;
819 int size;
820
821 size = points.size;
822 if (unlikely (size == 0)) {
823 warning ("No points in path.");
824 return new EditPoint ();
825 }
826
827 r = points.get (size - 1);
828 points.remove_at (size - 1);
829
830 if (size > 1) {
831 r.get_prev ().next = null;
832
833 if (r.next != null) {
834 r.get_next ().prev = null;
835 }
836 }
837
838 return r;
839 }
840
841 public EditPoint add (double x, double y) {
842 if (points.size > 0) {
843 return add_after (x, y, points.get (points.size - 1));
844 }
845
846 return add_after (x, y, null);
847 }
848
849 public EditPoint add_point (EditPoint p) {
850 if (points.size > 0) {
851 return add_point_after (p, points.get (points.size - 1));
852 }
853
854 return add_point_after (p, null);
855 }
856
857 /** Insert a new point after @param previous_point and return a reference
858 * to the new item in list.
859 */
860 public EditPoint add_after (double x, double y, EditPoint? previous_point) {
861 EditPoint p = new EditPoint (x, y, PointType.NONE);
862 return add_point_after (p, previous_point);
863 }
864
865 /** @return a list item pointing to the new point */
866 public EditPoint add_point_after (EditPoint p, EditPoint? previous_point) {
867 int prev_index;
868
869 if (unlikely (previous_point == null && points.size != 0)) {
870 warning ("previous_point == null");
871 previous_point = points.get (points.size - 1).get_link_item ();
872 }
873
874 if (points.size == 0) {
875 points.add (p);
876 p.prev = points.get (0).get_link_item ();
877 p.next = points.get (0).get_link_item ();
878 } else {
879 p.prev = (!) previous_point;
880 p.next = ((!) previous_point).next;
881
882 prev_index = points.index_of ((!) previous_point);
883
884 if (unlikely (!(0 <= prev_index < points.size))) {
885 warning ("no previous point");
886 }
887
888 points.insert (prev_index + 1, p);
889 }
890
891 last_point = p;
892
893 return p;
894 }
895
896 public void recalculate_linear_handles () {
897 foreach (EditPoint e in points) {
898 e.recalculate_linear_handles ();
899 }
900 }
901
902 public void close () {
903 open = false;
904 edit = false;
905
906 create_list ();
907
908 if (points.size > 2) {
909 points.get (0).recalculate_linear_handles ();
910 points.get (points.size - 1).recalculate_linear_handles ();
911 }
912 }
913
914 public void reopen () {
915 open = true;
916 edit = true;
917 }
918
919 /** Move path. */
920 public void move (double delta_x, double delta_y) {
921 foreach (EditPoint ep in points) {
922 ep.x += delta_x;
923 ep.y += delta_y;
924 }
925
926 update_region_boundaries ();
927 }
928
929 private void update_region_boundaries_for_point (EditPoint p) {
930 EditPointHandle left_handle;
931 EditPointHandle right_handle;
932
933 left_handle = p.get_left_handle ();
934 right_handle = p.get_right_handle ();
935
936 if (p.x > xmax) {
937 xmax = p.x;
938 }
939
940 if (p.x < xmin) {
941 xmin = p.x;
942 }
943
944 if (p.y > ymax) {
945 ymax = p.y;
946 }
947
948 if (p.y < ymin) {
949 ymin = p.y;
950 }
951
952 update_region_boundaries_for_handle (left_handle);
953 update_region_boundaries_for_handle (right_handle);
954 }
955
956 private void update_region_boundaries_for_handle (EditPointHandle h) {
957 if (h.x > xmax) {
958 xmax = h.x;
959 }
960
961 if (h.x < xmin) {
962 xmin = h.x;
963 }
964
965 if (h.y > ymax) {
966 ymax = h.y;
967 }
968
969 if (h.y < ymin) {
970 ymin = h.y;
971 }
972 }
973
974 public void update_region_boundaries () {
975 xmax = -10000;
976 xmin = 10000;
977 ymax = -10000;
978 ymin = 10000;
979
980 if (points.size == 0) {
981 xmax = 0;
982 xmin = 0;
983 ymax = 0;
984 ymin = 0;
985 }
986
987 foreach (EditPoint p in points) {
988 update_region_boundaries_for_point (p);
989 }
990
991 if (stroke > 0) {
992 xmax += stroke;
993 ymax += stroke;
994 xmin -= stroke;
995 ymin -= stroke;
996 }
997 }
998
999 /** Test if @param path is a valid outline for this object. */
1000 public bool test_is_outline (Path path) {
1001 assert (false);
1002 return this.test_is_outline_of_path (path) && path.test_is_outline_of_path (this);
1003 }
1004
1005 private bool test_is_outline_of_path (Path outline)
1006 requires (outline.points.size >= 2 || points.size >= 2)
1007 {
1008 // rather slow use it for testing, only
1009 unowned EditPoint i = outline.points.get (0).get_link_item ();
1010 unowned EditPoint prev = outline.points.get (outline.points.size - 1).get_link_item ();
1011
1012 double tolerance = 1;
1013 bool g = false;
1014
1015 EditPoint ep = new EditPoint (0, 0);
1016 double min = double.MAX;
1017
1018 while (true) {
1019 min = 10000;
1020
1021 all_of (prev, i, (cx, cy) => {
1022 get_closest_point_on_path (ep, cx, cy);
1023
1024 double n = pow (ep.x - cx, 2) + pow (cy - ep.y, 2);
1025
1026 if (n < min) min = n;
1027
1028 if (n < tolerance) {
1029 g = true;
1030 return false;
1031 }
1032
1033 return true;
1034 });
1035
1036 if (!g) {
1037 critical (@"this path does not seem to be the outline. (min $min)");
1038 }
1039
1040 g = false;
1041
1042 if (i == outline.points.get (outline.points.size - 1)) {
1043 break;
1044 }
1045
1046 i = i.get_next ();
1047 }
1048
1049 return true;
1050 }
1051
1052 /** Add the extra point between line handles for double curve. */
1053 public void add_hidden_double_points () requires (points.size > 1) {
1054 EditPoint hidden;
1055 EditPoint prev;
1056 EditPoint first = points.get (points.size - 1);
1057 PointType left;
1058 PointType right;
1059 double x, y;
1060 Gee.ArrayList<EditPoint> middle_points = new Gee.ArrayList<EditPoint> ();
1061 Gee.ArrayList<EditPoint> first_points = new Gee.ArrayList<EditPoint> ();
1062
1063 foreach (EditPoint next in points) {
1064 left = first.get_right_handle ().type;
1065 right = next.get_left_handle ().type;
1066
1067 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1068 first.get_right_handle ().type = PointType.QUADRATIC;
1069
1070 // half way between handles
1071 x = first.get_right_handle ().x + (next.get_left_handle ().x - first.get_right_handle ().x) / 2;
1072 y = first.get_right_handle ().y + (next.get_left_handle ().y - first.get_right_handle ().y) / 2;
1073
1074 hidden = new EditPoint (x, y, PointType.QUADRATIC);
1075 hidden.right_handle.move_to_coordinate_internal (next.get_left_handle ().x, next.get_left_handle ().y);
1076 hidden.get_right_handle ().type = PointType.QUADRATIC;
1077
1078 hidden.get_left_handle ().type = PointType.QUADRATIC;
1079 hidden.type = PointType.QUADRATIC;
1080
1081 first.get_right_handle ().type = PointType.QUADRATIC;
1082 first.type = PointType.QUADRATIC;
1083
1084 next.get_left_handle ().type = PointType.QUADRATIC;
1085 next.type = PointType.QUADRATIC;
1086
1087 middle_points.add (hidden);
1088 first_points.add (first);
1089 }
1090 first = next;
1091 }
1092
1093 for (int i = 0; i < middle_points.size; i++) {
1094 hidden = middle_points.get (i);
1095 add_point_after (middle_points.get (i), first_points.get (i));
1096 }
1097
1098 create_list ();
1099
1100 prev= get_last_point ();
1101 foreach (EditPoint ep in points) {
1102 if (ep.type == PointType.QUADRATIC) {
1103 x = prev.get_right_handle ().x;
1104 y = prev.get_right_handle ().y;
1105 ep.get_left_handle ().move_to_coordinate (x, y);
1106 }
1107 prev = ep;
1108 }
1109 }
1110
1111 /** Convert quadratic bezier points to cubic representation of the glyph
1112 * for ttf-export.
1113 */
1114 public Path get_quadratic_points () {
1115 PointConverter converter = new PointConverter (this);
1116 return converter.get_quadratic_path ();
1117 }
1118
1119 public void insert_new_point_on_path (EditPoint ep, double t = -1, bool move_point_to_path = false) {
1120 EditPoint start, stop;
1121 double x0, x1, y0, y1;
1122 double position, min;
1123 PointType left, right;
1124 double closest_x = 0;
1125 double closest_y = 0;
1126
1127 if (ep.next == null || ep.prev == null) {
1128 warning ("missing point");
1129 return;
1130 }
1131
1132 start = ep.get_prev ();
1133 stop = ep.get_next ();
1134
1135 right = start.get_right_handle ().type;
1136 left = stop.get_left_handle ().type;
1137
1138 if (right == PointType.CUBIC || left == PointType.CUBIC) {
1139 start.get_right_handle ().type = PointType.CUBIC;
1140 stop.get_left_handle ().type = PointType.CUBIC;
1141 }
1142
1143 add_point_after (ep, ep.get_prev ());
1144
1145 min = double.MAX;
1146
1147 position = 0.5;
1148
1149 if (t < 0) {
1150 all_of (start, stop, (cx, cy, t) => {
1151 double n = pow (ep.x - cx, 2) + pow (ep.y - cy, 2);
1152
1153 if (n < min) {
1154 min = n;
1155 position = t;
1156 closest_x = cx;
1157 closest_y = cy;
1158 }
1159
1160 return true;
1161 });
1162
1163 if (move_point_to_path) {
1164 ep.x = closest_x;
1165 ep.y = closest_y;
1166 }
1167 } else {
1168 position = t;
1169 }
1170
1171 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1172 double_bezier_vector (position, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x, out x0, out x1);
1173 double_bezier_vector (position, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y, out y0, out y1);
1174
1175 ep.get_left_handle ().set_point_type (PointType.DOUBLE_CURVE);
1176 ep.get_right_handle ().set_point_type (PointType.DOUBLE_CURVE);
1177
1178 ep.get_left_handle ().move_to_coordinate (x0, y0); // FIXME: SWAPPED?
1179 ep.get_right_handle ().move_to_coordinate (x1, y1);
1180
1181 ep.type = PointType.DOUBLE_CURVE;
1182 } else if (right == PointType.QUADRATIC) {
1183 x0 = quadratic_bezier_vector (1 - position, stop.x, start.get_right_handle ().x, start.x);
1184 y0 = quadratic_bezier_vector (1 - position, stop.y, start.get_right_handle ().y, start.y);
1185 ep.get_right_handle ().move_to_coordinate (x0, y0);
1186
1187 ep.get_left_handle ().set_point_type (PointType.QUADRATIC);
1188 ep.get_right_handle ().set_point_type (PointType.QUADRATIC);
1189
1190 ep.get_left_handle ().move_to_coordinate_internal (0, 0);
1191
1192 ep.type = PointType.QUADRATIC;
1193 } else if (right == PointType.CUBIC || left == PointType.CUBIC) {
1194 bezier_vector (position, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x, out x0, out x1);
1195 bezier_vector (position, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y, out y0, out y1);
1196
1197 ep.get_left_handle ().set_point_type (PointType.CUBIC);
1198 ep.get_left_handle ().move_to_coordinate (x0, y0);
1199
1200 ep.get_right_handle ().set_point_type (PointType.CUBIC);
1201 ep.get_right_handle ().move_to_coordinate (x1, y1);
1202
1203 ep.type = PointType.LINE_CUBIC;
1204 } else if (right == PointType.LINE_QUADRATIC && left == PointType.LINE_QUADRATIC) {
1205 ep.get_right_handle ().set_point_type (PointType.LINE_QUADRATIC);
1206 ep.get_left_handle ().set_point_type (PointType.LINE_QUADRATIC);
1207 ep.type = PointType.QUADRATIC;
1208 } else if (right == PointType.LINE_CUBIC && left == PointType.LINE_CUBIC) {
1209 ep.get_right_handle ().set_point_type (PointType.LINE_CUBIC);
1210 ep.get_left_handle ().set_point_type (PointType.LINE_CUBIC);
1211 ep.type = PointType.LINE_CUBIC;
1212 } else if (right == PointType.LINE_DOUBLE_CURVE && left == PointType.LINE_DOUBLE_CURVE) {
1213 ep.get_right_handle ().set_point_type (PointType.LINE_DOUBLE_CURVE);
1214 ep.get_left_handle ().set_point_type (PointType.LINE_DOUBLE_CURVE);
1215 ep.type = PointType.DOUBLE_CURVE;
1216 } else
1217
1218 ep.get_left_handle ().parent = ep;
1219 ep.get_right_handle ().parent = ep;
1220
1221 stop.get_left_handle ().length *= 1 - position;
1222 start.get_right_handle ().length *= position;
1223
1224 if (right == PointType.QUADRATIC) { // update connected handle
1225 if (ep.prev != null) {
1226 ep.get_left_handle ().move_to_coordinate_internal (
1227 ep.get_prev ().right_handle.x,
1228 ep.get_prev ().right_handle.y);
1229
1230 } else {
1231 warning ("ep.prev is null for quadratic point");
1232 }
1233 }
1234
1235 create_list ();
1236 foreach (EditPoint p in points) {
1237 p.recalculate_linear_handles ();
1238 }
1239 }
1240
1241 /** Get a point on the this path closest to x and y coordinates. */
1242 public void get_closest_point_on_path (EditPoint edit_point, double x, double y) {
1243 return_if_fail (points.size >= 1);
1244
1245 double min = double.MAX;
1246 double n = 0;
1247 bool g = false;
1248
1249 double ox = 0;
1250 double oy = 0;
1251
1252 EditPoint prev = points.get (points.size - 1).get_link_item ();
1253 EditPoint i = points.get (0).get_link_item ();
1254
1255 bool done = false;
1256 bool exit = false;
1257 bool first = true;
1258
1259 EditPoint? previous_point = null;
1260 EditPoint? next_point = null;
1261
1262 EditPoint previous;
1263 EditPoint next;
1264 double step = 0;
1265
1266 if (points.size == 0) {
1267 warning ("Empty path.");
1268 return;
1269 }
1270
1271 if (points.size == 1) {
1272 edit_point.x = i.x;
1273 edit_point.y = i.y;
1274
1275 edit_point.prev = i;
1276 edit_point.next = i;
1277 return;
1278 }
1279
1280 edit_point.x = i.x;
1281 edit_point.y = i.y;
1282
1283 create_list ();
1284
1285 while (!exit) {
1286 if (!first && i == points.get (points.size - 1)) {
1287 done = true;
1288 }
1289
1290 if (!done) {
1291 i = i.get_next ();
1292 prev = i.get_prev ();
1293 } else if (done && !is_open ()) {
1294 i = points.get (0).get_link_item ();
1295 prev = points.get (points.size - 1).get_link_item ();
1296 exit = true;
1297 } else {
1298 break;
1299 }
1300
1301 all_of (prev, i, (cx, cy, t) => {
1302 n = pow (x - cx, 2) + pow (y - cy, 2);
1303
1304 if (n < min) {
1305 min = n;
1306
1307 ox = cx;
1308 oy = cy;
1309
1310 previous_point = i.prev;
1311 next_point = i;
1312
1313 step = t;
1314
1315 g = true;
1316 }
1317
1318 return true;
1319 });
1320
1321 first = false;
1322 }
1323
1324 if (previous_point == null && is_open ()) {
1325 previous_point = points.get (points.size - 1).get_link_item ();
1326 }
1327
1328 if (previous_point == null) {
1329 warning (@"previous_point == null, points.size: $(points.size)");
1330 return;
1331 }
1332
1333 if (next_point == null) {
1334 warning ("next_point != null");
1335 return;
1336 }
1337
1338 previous = (!) previous_point;
1339 next = (!) next_point;
1340
1341 edit_point.prev = previous_point;
1342 edit_point.next = next_point;
1343
1344 edit_point.set_position (ox, oy);
1345 }
1346
1347 public static bool all_of (EditPoint start, EditPoint stop,
1348 RasterIterator iter, int steps = -1,
1349 double min_t = 0, double max_t = 1) {
1350
1351 PointType right = PenTool.to_curve (start.get_right_handle ().type);
1352 PointType left = PenTool.to_curve (stop.get_left_handle ().type);
1353
1354 if (steps == -1) {
1355 steps = (int) (10 * get_length_from (start, stop));
1356 }
1357
1358 if (right == PointType.DOUBLE_CURVE || left == PointType.DOUBLE_CURVE) {
1359 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);
1360 } else if (right == PointType.QUADRATIC && left == PointType.QUADRATIC) {
1361 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);
1362 } else if (right == PointType.CUBIC && left == PointType.CUBIC) {
1363 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);
1364 }
1365
1366 if (start.x == stop.x && start.y == stop.y) {
1367 warning ("Zero length.");
1368 return true;
1369 }
1370
1371 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))");
1372 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);
1373 }
1374
1375 public static void get_point_for_step (EditPoint start, EditPoint stop, double step, out double x, out double y) {
1376 // FIXME: Types
1377 x = bezier_path (step, start.x, start.get_right_handle ().x, stop.get_left_handle ().x, stop.x);
1378 y = bezier_path (step, start.y, start.get_right_handle ().y, stop.get_left_handle ().y, stop.y);
1379 }
1380
1381 private static bool all_of_double (double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3,
1382 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1383
1384 double px = x1;
1385 double py = y1;
1386
1387 double t;
1388 double middle_x, middle_y;
1389 double double_step;
1390
1391 middle_x = x1 + (x2 - x1) / 2;
1392 middle_y = y1 + (y2 - y1) / 2;
1393
1394 for (int i = 0; i < steps; i++) {
1395 t = i / steps + min_t;
1396
1397 px = quadratic_bezier_path (t, x0, x1, middle_x);
1398 py = quadratic_bezier_path (t, y0, y1, middle_y);
1399
1400 double_step = t / 2;
1401
1402 if (double_step > max_t) {
1403 return false;
1404 }
1405
1406 if (!iter (px, py, double_step)) {
1407 return false;
1408 }
1409 }
1410
1411 for (int i = 0; i < steps; i++) {
1412 t = i / steps + min_t;
1413
1414 px = quadratic_bezier_path (t, middle_x, x2, x3);
1415 py = quadratic_bezier_path (t, middle_y, y2, y3);
1416
1417 double_step = 0.5 + t / 2;
1418
1419 if (double_step > max_t) {
1420 return false;
1421 }
1422
1423 if (!iter (px, py, double_step)) {
1424 return false;
1425 }
1426 }
1427
1428 return true;
1429 }
1430
1431 private static bool all_of_quadratic_curve (double x0, double y0, double x1, double y1, double x2, double y2,
1432 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1433 double px = x1;
1434 double py = y1;
1435
1436 double t;
1437
1438 for (int i = 0; i < steps; i++) {
1439 t = i / steps + min_t;
1440
1441 px = quadratic_bezier_path (t, x0, x1, x2);
1442 py = quadratic_bezier_path (t, y0, y1, y2);
1443
1444 if (t > max_t) {
1445 return false;
1446 }
1447
1448 if (!iter (px, py, t)) {
1449 return false;
1450 }
1451 }
1452
1453 return true;
1454 }
1455
1456 private static bool all_of_curve (double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3,
1457 RasterIterator iter, double steps = 400, double min_t = 0, double max_t = 1) {
1458 double px = x1;
1459 double py = y1;
1460
1461 double t;
1462
1463 for (int i = 0; i < steps; i++) {
1464 t = i / steps + min_t;
1465
1466 px = bezier_path (t, x0, x1, x2, x3);
1467 py = bezier_path (t, y0, y1, y2, y3);
1468
1469 if (t > max_t) {
1470 return false;
1471 }
1472
1473 if (!iter (px, py, t)) {
1474 return false;
1475 }
1476 }
1477
1478 return true;
1479 }
1480
1481 public bool all_segments (SegmentIterator iter) {
1482 unowned EditPoint i, next;
1483
1484 if (points.size < 2) {
1485 return false;
1486 }
1487
1488 for (int j = 0; j < points.size - 1; j++) {
1489 i = points.get (j).get_link_item ();
1490 next = i.get_next ();
1491 if (!iter (i, next)) {
1492 return false;
1493 }
1494 }
1495
1496 if (!is_open ()) {
1497 return iter (points.get (points.size - 1), points.get (0));
1498 }
1499
1500 return true;
1501 }
1502
1503 public void all_of_path (RasterIterator iter, int steps = -1) {
1504 all_segments ((start, stop) => {
1505 return all_of (start, stop, iter, steps);
1506 });
1507 }
1508
1509 public static double bezier_path (double step, double p0, double p1, double p2, double p3) {
1510 double q0, q1, q2;
1511 double r0, r1;
1512
1513 q0 = step * (p1 - p0) + p0;
1514 q1 = step * (p2 - p1) + p1;
1515 q2 = step * (p3 - p2) + p2;
1516
1517 r0 = step * (q1 - q0) + q0;
1518 r1 = step * (q2 - q1) + q1;
1519
1520 return step * (r1 - r0) + r0;
1521 }
1522
1523 public static void bezier_vector (double step, double p0, double p1, double p2, double p3, out double a0, out double a1) {
1524 double q0, q1, q2;
1525
1526 q0 = step * (p1 - p0) + p0;
1527 q1 = step * (p2 - p1) + p1;
1528 q2 = step * (p3 - p2) + p2;
1529
1530 a0 = step * (q1 - q0) + q0;
1531 a1 = step * (q2 - q1) + q1;
1532 }
1533
1534 public static double quadratic_bezier_vector (double step, double p0, double p1, double p2) {
1535 return step * (p1 - p0) + p0;
1536 }
1537
1538 public static double quadratic_bezier_path (double step, double p0, double p1, double p2) {
1539 double q0 = step * (p1 - p0) + p0;
1540 double q1 = step * (p2 - p1) + p1;
1541
1542 return step * (q1 - q0) + q0;
1543 }
1544
1545 public static double double_bezier_path (double step, double p0, double p1, double p2, double p3) {
1546 double middle = p1 + (p2 - p1) / 2;
1547
1548 if (step == 0.5) {
1549 // FIXME: return the middle point
1550 warning ("Middle");
1551 }
1552
1553 if (step < 0.5) {
1554 return quadratic_bezier_path (2 * step, p0, p1, middle);
1555 }
1556
1557 return quadratic_bezier_path (2 * (step - 0.5), middle, p2, p3);
1558 }
1559
1560 public static void double_bezier_vector (double step, double p0, double p1, double p2, double p3, out double a0, out double a1) {
1561 double b0, b1, c0, c1, d0, d1;
1562
1563 if (unlikely (step <= 0 || step >= 1)) {
1564 warning (@"Bad step: $step");
1565 step += 0.00004;
1566 }
1567
1568 // set angle
1569 b0 = double_bezier_path (step + 0.00001, p0, p1, p2, p3);
1570 c0 = double_bezier_path (step + 0.00002, p0, p1, p2, p3);
1571
1572 b1 = double_bezier_path (step - 0.00001, p0, p1, p2, p3);
1573 c1 = double_bezier_path (step - 0.00002, p0, p1, p2, p3);
1574
1575 // adjust length
1576 d0 = b0 + (b0 - c0) * 25000 * (step);
1577 d1 = b1 + (b1 - c1) * 25000 * (1 - step);
1578
1579 a0 = d0;
1580 a1 = d1;
1581 }
1582
1583 public void plot (Context cr, WidgetAllocation allocation, double view_zoom) {
1584 double px = 0, py = 0;
1585 double xc = allocation.width / 2.0;
1586 double yc = allocation.height / 2.0;
1587
1588 cr.save ();
1589
1590 all_of_path ((x, y) => {
1591 //Theme.color (cr, "Background 5");
1592 cr.move_to (px + xc, -py + yc);
1593 cr.line_to (x + xc, -y + yc);
1594
1595 px = x;
1596 py = y;
1597
1598 return true;
1599 });
1600
1601 cr.stroke ();
1602 cr.restore ();
1603 }
1604
1605 public void print_boundaries () {
1606 stderr.printf (@"xmax $xmax \n");
1607 stderr.printf (@"xmin $xmin \n");
1608 stderr.printf (@"ymax $ymax \n");
1609 stderr.printf (@"ymin $ymin \n");
1610 }
1611
1612 public bool has_region_boundaries () {
1613 return !(xmax == -10000 || xmin == 10000 || ymax == -10000 || ymin == 10000);
1614 }
1615
1616 public void create_list () {
1617 EditPoint ep;
1618
1619 if (points.size == 0) {
1620 return;
1621 }
1622
1623 if (points.size == 1) {
1624 ep = points.get (0);
1625 ep.next = null;
1626 ep.prev = null;
1627 return;
1628 }
1629
1630 ep = points.get (0);
1631 ep.next = points.get (1).get_link_item ();
1632 ep.prev = points.get (points.size - 1).get_link_item ();
1633
1634 for (int i = 1; i < points.size - 1; i++) {
1635 ep = points.get (i);
1636 ep.prev = points.get (i - 1).get_link_item ();
1637 ep.next = points.get (i + 1).get_link_item ();
1638 }
1639
1640 ep = points.get (points.size - 1);
1641 ep.next = points.get (0).get_link_item ();
1642 ep.prev = points.get (points.size - 2).get_link_item ();
1643 }
1644
1645 public bool has_point (EditPoint ep) {
1646 return points.contains (ep);
1647 }
1648
1649 public bool has_deleted_point () {
1650 foreach (EditPoint p in points) {
1651 if (p.deleted) {
1652 return true;
1653 }
1654 }
1655 return false;
1656 }
1657
1658 /** @return the remaining parts as a new path. */
1659 public PathList process_deleted_points ()
1660 requires (points.size > 0)
1661 {
1662 EditPoint p;
1663 EditPoint ep;
1664 Path current_path = new Path ();
1665 Path remaining_points = new Path ();
1666 PathList path_list = new PathList ();
1667 int i;
1668 int index = 0;
1669
1670 if (!has_deleted_point ()) {
1671 return path_list;
1672 }
1673
1674 if (points.size == 1) {
1675 points.remove_at (0);
1676 return path_list;
1677 }
1678
1679 // set start position to the point that will be removed
1680 for (i = 0; i < points.size; i++) {
1681 p = points.get (i);
1682
1683 if (p.deleted) {
1684 index = i;
1685 i++;
1686 ep = p;
1687 break;
1688 }
1689 }
1690
1691 // don't tie end points on the open path
1692 if (points.size > 1) {
1693 p = points.get (1);
1694 p.convert_to_curve ();
1695 p.set_reflective_handles (false);
1696 p.set_tie_handle (false);
1697 }
1698
1699 if (points.size > 0) {
1700 p = points.get (points.size - 1);
1701 p.convert_to_curve ();
1702 p.set_reflective_handles (false);
1703 p.set_tie_handle (false);
1704 }
1705
1706 // copy points after the deleted point
1707 while (i < points.size) {
1708 p = points.get (i);
1709 current_path.add_point (p);
1710 i++;
1711 }
1712
1713 // copy points before the deleted point
1714 for (i = 0; i < index; i++) {
1715 p = points.get (i);
1716 remaining_points.add_point (p);
1717 }
1718
1719 // merge if we still only have one path
1720 if (!is_open ()) {
1721 foreach (EditPoint point in remaining_points.points) {
1722 current_path.add_point (point.copy ());
1723 }
1724
1725 if (current_path.points.size > 0) {
1726 ep = current_path.points.get (0);
1727 ep.set_tie_handle (false);
1728 ep.set_reflective_handles (false);
1729 ep.get_left_handle ().type = PenTool.to_line (ep.type);
1730 ep.type = PenTool.to_curve (ep.type);
1731 path_list.add (current_path);
1732
1733 ep = current_path.points.get (current_path.points.size - 1);
1734 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1735 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1736 }
1737 } else {
1738 if (current_path.points.size > 0) {
1739 ep = current_path.points.get (0);
1740 ep.set_tie_handle (false);
1741 ep.set_reflective_handles (false);
1742 ep.get_left_handle ().type = PenTool.to_line (ep.type);
1743 ep.type = PenTool.to_curve (ep.type);
1744 set_new_start (current_path.points.get (0));
1745 path_list.add (current_path);
1746
1747 ep = current_path.points.get (current_path.points.size - 1);
1748 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1749 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1750 }
1751
1752 if (remaining_points.points.size > 0) {
1753 remaining_points.points.get (0).set_tie_handle (false);
1754 remaining_points.points.get (0).set_reflective_handles (false);
1755 remaining_points.points.get (0).type = remaining_points.points.get (0).type;
1756 set_new_start (remaining_points.points.get (0));
1757 path_list.add (remaining_points);
1758
1759 if (current_path.points.size > 0) {
1760 ep = current_path.points.get (current_path.points.size - 1);
1761 ep.get_right_handle ().type = PenTool.to_line (ep.type);
1762 ep.type = PenTool.to_curve (ep.get_right_handle ().type);
1763 }
1764 }
1765 }
1766
1767 foreach (Path path in path_list.paths) {
1768 path.update_region_boundaries ();
1769 }
1770
1771 return path_list;
1772 }
1773
1774 public void set_new_start (EditPoint ep) {
1775 Gee.ArrayList<EditPoint> list = new Gee.ArrayList<EditPoint> ();
1776 uint len = points.size;
1777 EditPoint iter = points.get (0);
1778 EditPoint? ni = null;
1779 bool found = false;
1780
1781 foreach (EditPoint it in points) {
1782 if (it == ep) {
1783 found = true;
1784 break;
1785 }
1786
1787 iter = iter.get_next ();
1788 ni = (!) iter;
1789 }
1790
1791 if (unlikely (!found)) {
1792 warning ("Could not find edit point.");
1793 }
1794
1795 if (ni == null) {
1796 return;
1797 }
1798
1799 iter = (!) ni;
1800
1801 for (uint i = 0; i < len; i++) {
1802 list.add (iter);
1803
1804 if (iter == points.get (points.size - 1)) {
1805 iter = points.get (0).get_link_item ();
1806 } else {
1807 iter = iter.get_next ();
1808 }
1809 }
1810
1811 points.clear ();
1812
1813 foreach (EditPoint p in list) {
1814 points.add (p);
1815 }
1816 }
1817
1818 public void append_path (Path path) {
1819 if (points.size == 0 || path.points.size == 0) {
1820 warning ("No points");
1821 return;
1822 }
1823
1824 // copy remaining points
1825 foreach (EditPoint p in path.points) {
1826 add_point (p.copy ());
1827 }
1828
1829 path.points.clear ();
1830 }
1831
1832 /** Roatate around coordinate xc, xc. */
1833 public void rotate (double theta, double xc, double yc) {
1834 double a, radius;
1835
1836 foreach (EditPoint ep in points) {
1837 radius = sqrt (pow (xc - ep.x, 2) + pow (yc + ep.y, 2));
1838
1839 if (yc + ep.y < 0) {
1840 radius = -radius;
1841 }
1842
1843 a = acos ((ep.x - xc) / radius);
1844
1845 ep.x = xc + cos (a - theta) * radius;
1846 ep.y = yc + sin (a - theta) * radius;
1847
1848 ep.get_right_handle ().angle -= theta;
1849 ep.get_left_handle ().angle -= theta;
1850
1851 while (ep.get_right_handle ().angle < 0) {
1852 ep.get_right_handle ().angle += 2 * PI;
1853 }
1854
1855 while (ep.get_left_handle ().angle < 0) {
1856 ep.get_left_handle ().angle += 2 * PI;
1857 }
1858 }
1859
1860 rotation += theta;
1861 rotation %= 2 * PI;
1862
1863 update_region_boundaries ();
1864 }
1865
1866 public void flip_vertical () {
1867 EditPointHandle hl, hr;
1868 double lx, ly, rx, ry;
1869
1870 foreach (EditPoint e in points) {
1871 hl = e.get_left_handle ();
1872 hr = e.get_right_handle ();
1873
1874 lx = hl.x;
1875 ly = hl.y;
1876 rx = hr.x;
1877 ry = hr.y;
1878
1879 e.y *= -1;
1880
1881 hr.move_to_coordinate_internal (rx, -1 * ry);
1882 hl.move_to_coordinate_internal (lx, -1 * ly);
1883 }
1884
1885 update_region_boundaries ();
1886 }
1887
1888 public void flip_horizontal () {
1889 EditPointHandle hl, hr;
1890 double lx, ly, rx, ry;
1891 foreach (EditPoint e in points) {
1892 hl = e.get_left_handle ();
1893 hr = e.get_right_handle ();
1894
1895 lx = hl.x;
1896 ly = hl.y;
1897 rx = hr.x;
1898 ry = hr.y;
1899
1900 e.x *= -1;
1901
1902 hr.move_to_coordinate_internal (-1 * rx, ry);
1903 hl.move_to_coordinate_internal (-1 * lx, ly);
1904 }
1905
1906 update_region_boundaries ();
1907 }
1908
1909 public void init_point_type () {
1910 PointType type;
1911
1912 switch (DrawingTools.point_type) {
1913 case PointType.QUADRATIC:
1914 type = PointType.LINE_QUADRATIC;
1915 break;
1916 case PointType.DOUBLE_CURVE:
1917 type = PointType.LINE_DOUBLE_CURVE;
1918 break;
1919 case PointType.CUBIC:
1920 type = PointType.LINE_CUBIC;
1921 break;
1922 default:
1923 warning ("No type is set");
1924 type = PointType.LINE_CUBIC;
1925 break;
1926 }
1927
1928 foreach (EditPoint ep in points) {
1929 ep.type = type;
1930 ep.get_right_handle ().type = type;
1931 ep.get_left_handle ().type = type;
1932 }
1933 }
1934
1935 public void convert_path_ending_to_line () {
1936 if (points.size < 2) {
1937 return;
1938 }
1939
1940 get_first_point ().get_left_handle ().convert_to_line ();
1941 get_last_point ().get_right_handle ().convert_to_line ();
1942 }
1943
1944 public void print_all_types () {
1945 print (@"Control points:\n");
1946 foreach (EditPoint ep in points) {
1947 print (@"$(ep.type) L: $(ep.get_left_handle ().type) R: L: $(ep.get_right_handle ().type)\n");
1948 }
1949 }
1950
1951 /** Find the point where two lines intersect. */
1952 public static void find_intersection (double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4,
1953 out double point_x, out double point_y) {
1954 point_x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
1955 point_y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
1956 }
1957
1958 public static void find_intersection_handle (EditPointHandle h1, EditPointHandle h2, out double point_x, out double point_y) {
1959 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);
1960 }
1961
1962 public static void find_intersection_point (EditPoint p1, EditPoint p2, EditPoint q1, EditPoint q2, out double point_x, out double point_y) {
1963 find_intersection (p1.x, p1.y, p2.x, p2.y, q1.x, q1.y, q2.x, q2.y, out point_x, out point_y);
1964 }
1965
1966 public void add_extrema () {
1967 double x0, y0, x1, y1, x2, y2, x3, y3;
1968 double minx, maxx, miny, maxy;
1969
1970 if (unlikely (points.size < 2)) {
1971 warning (@"Missing points, $(points.size) points in path.");
1972 return;
1973 }
1974
1975 minx = Glyph.CANVAS_MAX;
1976 miny = Glyph.CANVAS_MAX;
1977 maxx = Glyph.CANVAS_MIN;
1978 maxy = Glyph.CANVAS_MIN;
1979
1980 x0 = 0;
1981 y0 = 0;
1982 x1 = 0;
1983 y1 = 0;
1984 x2 = 0;
1985 y2 = 0;
1986 x3 = 0;
1987 y3 = 0;
1988
1989 all_of_path ((x, y) => {
1990 if (x < minx) {
1991 x0 = x;
1992 y0 = y;
1993 minx = x;
1994 }
1995
1996 if (x > maxx) {
1997 x1 = x;
1998 y1 = y;
1999 maxx = x;
2000 }
2001
2002 if (y < miny) {
2003 x2 = x;
2004 y2 = y;
2005 miny = y;
2006 }
2007
2008 if (y > maxy) {
2009 x3 = x;
2010 y3 = y;
2011 maxy = y;
2012 }
2013
2014 return true;
2015 });
2016
2017 insert_new_point_on_path_at (x0 - 0.001, y0);
2018 insert_new_point_on_path_at (x1 + 0.001, y1);
2019 insert_new_point_on_path_at (x2, y2 - 0.001);
2020 insert_new_point_on_path_at (x3, y3 + 0.001);
2021 }
2022
2023 public EditPoint insert_new_point_on_path_at (double x, double y) {
2024 EditPoint ep = new EditPoint ();
2025 EditPoint prev, next;
2026 bool exists;
2027
2028 if (points.size < 2) {
2029 warning ("Can't add extrema to just one point.");
2030 return ep;
2031 }
2032
2033 get_closest_point_on_path (ep, x, y);
2034
2035 next = (ep.next == null) ? points.get (0) : ep.get_next ();
2036 prev = (ep.prev == null) ? points.get (points.size - 1) : ep.get_prev ();
2037
2038 exists = prev.x == ep.x && prev.y == ep.y;
2039 exists |= next.x == ep.x && next.y == ep.y;
2040
2041 if (!exists) {
2042 insert_new_point_on_path (ep);
2043 }
2044
2045 return ep;
2046 }
2047
2048 public static bool is_counter (PathList pl, Path path) {
2049 int inside_count = 0;
2050 bool inside;
2051
2052 foreach (Path p in pl.paths) {
2053 if (p.points.size > 1 && p != path) {
2054 inside = true;
2055 foreach (EditPoint ep in path.points) {
2056 if (!SvgParser.is_inside (ep, p)) {
2057 inside = false;
2058 }
2059 }
2060
2061 if (inside) {
2062 inside_count++;
2063 }
2064 }
2065 }
2066
2067 return inside_count % 2 != 0;
2068 }
2069
2070 public void remove_points_on_points () {
2071 Gee.ArrayList<EditPoint> remove = new Gee.ArrayList<EditPoint> ();
2072 EditPoint n;
2073 EditPointHandle hr, h;
2074
2075 if (points.size == 0) {
2076 return;
2077 }
2078
2079 create_list ();
2080
2081 foreach (EditPoint ep in points) {
2082 if (ep.next != null) {
2083 n = ep.get_next ();
2084 } else {
2085 n = points.get (0);
2086 }
2087
2088 if (fabs (n.x - ep.x) < 0.00001 && fabs (n.y - ep.y) < 0.00001) {
2089 remove.add (ep);
2090 }
2091 }
2092
2093 foreach (EditPoint r in remove) {
2094 if (r.next != null) {
2095 n = r.get_next ();
2096 } else {
2097 n = points.get (0);
2098 }
2099
2100 points.remove (r);
2101 h = n.get_left_handle ();
2102 hr = r.get_left_handle ();
2103 h.length = hr.length;
2104 h.angle = hr.angle;
2105 h.type = hr.type;
2106
2107 if (h.length < 0.00001) {
2108 h.length = 0.00001;
2109 h.angle = n.get_right_handle ().angle - PI;
2110 }
2111
2112 create_list ();
2113 }
2114
2115 recalculate_linear_handles ();
2116 }
2117
2118 public void remove_deleted_points () {
2119 Gee.ArrayList<EditPoint> p = new Gee.ArrayList<EditPoint> ();
2120
2121 foreach (EditPoint ep in points) {
2122 if (ep.deleted) {
2123 p.add (ep);
2124 }
2125 }
2126
2127 foreach (EditPoint e in p) {
2128 points.remove (e);
2129 }
2130
2131 create_list ();
2132 }
2133
2134 public static void find_closes_point_in_segment (EditPoint ep0, EditPoint ep1,
2135 double px, double py,
2136 out double nx, out double ny,
2137 double max_step = 200) {
2138
2139 double min_distance = double.MAX;
2140 double npx, npy;
2141 double min_t, max_t;
2142 double rmin_t, rmax_t;
2143 bool found;
2144 int step;
2145
2146 npx = 0;
2147 npy = 0;
2148
2149 min_t = 0;
2150 max_t = 1;
2151
2152 rmin_t = 0;
2153 rmax_t = 1;
2154
2155 for (step = 3; step <= max_step; step *= 2) {
2156 found = false;
2157 min_distance = double.MAX;
2158 Path.all_of (ep0, ep1, (xa, ya, ta) => {
2159 double d = Path.distance (px, xa, py, ya);
2160
2161 if (d < min_distance) {
2162 min_distance = d;
2163 npx = xa;
2164 npy = ya;
2165 rmin_t = ta - 1.0 / step;
2166 rmax_t = ta + 1.0 / step;
2167 found = true;
2168 }
2169
2170 return true;
2171 }, step, min_t, max_t);
2172
2173 if (!found) {
2174 rmin_t = 1 - (1.0 / step);
2175 rmax_t = 1;
2176 }
2177
2178 min_t = (rmin_t > 0) ? rmin_t : 0;
2179 max_t = (rmax_t < 1) ? rmax_t : 1;
2180 }
2181
2182 nx = npx;
2183 ny = npy;
2184 }
2185 }
2186
2187 }
2188