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