1 /*
2 Copyright (C) 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 class StrokeTool : Tool {
21
22 static bool stroke_selected = false;
23 static int iterations = 0;
24
25 public StrokeTool (string tooltip) {
26 iterations = 10;
27 select_action.connect((self) => {
28 stroke_selected = true;
29 iterations++;
30 stroke_selected_paths ();
31 stroke_selected = false;
32 });
33 }
34
35 public static void set_stroke_for_selected_paths (double width) {
36 Glyph g = MainWindow.get_current_glyph ();
37
38 foreach (Path p in g.active_paths) {
39 p.set_stroke (width);
40 }
41
42 GlyphCanvas.redraw ();
43 }
44
45 /** Create strokes for the selected outlines. */
46 void stroke_selected_paths () {
47 Glyph g = MainWindow.get_current_glyph ();
48 PathList paths = new PathList ();
49
50 foreach (Path p in g.active_paths) {
51 if (p.stroke > 0) {
52 paths.append (get_stroke (p, p.stroke));
53 }
54 }
55
56 // FIXME: delete
57 Path? last = null;
58 foreach (Path p in g.active_paths) {
59 if (p.stroke == 0) {
60 if (last != null) {
61 PathList pl;
62 if (merge_path (p, (!) last, out pl)) {
63 paths.paths.remove (p);
64 paths.paths.remove ((!) last);
65 paths.append (pl);
66 g.path_list.remove (p);
67 g.path_list.remove ((!) last);
68 } else {
69 print (@"Paths can't be merged.");
70 }
71 }
72
73 last = p;
74 }
75 }
76
77 foreach (Path np in paths.paths) {
78 g.add_path (np);
79 }
80 }
81
82 public static PathList get_stroke (Path path, double thickness) {
83 PathList n;
84 PathList o = new PathList ();
85 Path original = path.copy ();
86
87 original.remove_points_on_points ();
88
89 n = get_stroke_outline (original, thickness);
90
91 o = split_corners (n);
92 remove_self_intersecting_corners (o);
93
94 o = merge (o);
95
96 /*
97 PathList parts = new PathList ();
98 foreach (Path p in o.paths) {
99 parts.append (split (p));
100 }
101
102 return parts;
103 */
104
105 return o;
106 }
107
108 static bool is_corner_self_intersection (Path p) {
109 EditPointHandle l, r;
110 bool corner, i, remove;
111
112 remove = false;
113 i = false;
114 p.remove_points_on_points ();
115 foreach (EditPoint ep in p.points) {
116
117 corner = (ep.flags & EditPoint.NEW_CORNER) > 0;
118
119 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
120 return false;
121 }
122
123 if (corner || i) {
124 l = ep.get_left_handle ();
125 r = ep.get_right_handle ();
126
127 if (fabs (l.angle - r.angle) < 0.005) {
128 remove = true;
129 }
130 }
131
132 i = corner && p.points.size == 4;
133 }
134
135 return remove;
136 }
137
138 static void remove_self_intersecting_corners (PathList pl) {
139 PathList parts;
140 foreach (Path p in pl.paths) {
141
142 if (is_corner_self_intersection (p)) {
143 parts = get_parts (p);
144 if (parts.paths.size > 1) {
145 pl.append (parts);
146 remove_self_intersecting_corners (pl);
147 return;
148 } else {
149
150 if (has_self_intersection (p)) { // FIXME: DELETE
151 warning ("Path ha self intersection.");
152 }
153
154 pl.paths.remove (p);
155 remove_self_intersecting_corners (pl);
156 return;
157 }
158 }
159 }
160 }
161
162 public static PathList get_stroke_outline (Path path, double thickness) {
163 return get_strokes (path, thickness);
164 }
165
166 public static PathList get_strokes (Path p, double thickness) {
167 Path counter = new Path ();
168 Path outline = new Path ();
169 Path merged = new Path ();
170 PathList paths = new PathList ();
171
172 if (!p.is_open () && p.is_filled ()) {
173 outline = create_stroke (p, thickness);
174 outline.close ();
175
176 outline.update_region_boundaries ();
177 paths.add (outline);
178 } else if (!p.is_open () && !p.is_filled ()) {
179 outline = create_stroke (p, thickness);
180 counter = create_stroke (p, -1 * thickness);
181
182 if (p.is_clockwise ()) {
183 outline.force_direction (Direction.CLOCKWISE);
184 } else {
185 outline.force_direction (Direction.COUNTER_CLOCKWISE);
186 }
187
188 if (outline.is_clockwise ()) {
189 counter.force_direction (Direction.COUNTER_CLOCKWISE);
190 } else {
191 counter.force_direction (Direction.CLOCKWISE);
192 }
193
194 outline.update_region_boundaries ();
195 paths.add (outline);
196
197 counter.update_region_boundaries ();
198 paths.add (counter);
199 } else if (p.is_open ()) { // FIXME: this can create many parts
200 outline = create_stroke (p, thickness);
201 counter = create_stroke (p, -1 * thickness);
202 merged = merge_strokes (p, outline, counter, thickness);
203
204 if (p.is_clockwise ()) {
205 merged.force_direction (Direction.CLOCKWISE);
206 } else {
207 merged.force_direction (Direction.COUNTER_CLOCKWISE);
208 }
209
210 merged.update_region_boundaries ();
211 paths.add (merged);
212 } else {
213 warning ("Can not create stroke.");
214 paths.add (p);
215 }
216
217 return paths;
218 }
219
220 /** Create one stroke from the outline and counter stroke and close the
221 * open endings.
222 *
223 * @param path the path to create stroke for
224 * @param stroke for the outline of path
225 * @param stroke for the counter path
226 */
227 static Path merge_strokes (Path path, Path stroke, Path counter, double thickness) {
228 Path merged;
229
230 counter.reverse ();
231 merged = stroke.copy ();
232
233 if (path.is_open ()) {
234 merged.delete_last_point ();
235 counter.delete_first_point ();
236 merged.delete_last_point ();
237 counter.delete_first_point ();
238 }
239
240 merged.append_path (counter);
241
242 merged.close ();
243 merged.create_list ();
244 merged.recalculate_linear_handles ();
245
246 return merged;
247 }
248
249 static Path create_stroke (Path p, double thickness) {
250 Path stroked;
251 Path path;
252
253 if (p.points.size >= 2) {
254 path = p.copy ();
255 //FIXME: DELETE path.remove_points_on_points ();
256 stroked = generate_stroke (path, thickness);
257
258 if (!p.is_open ()) {
259 stroked.reverse ();
260 stroked.close ();
261 }
262 } else {
263 // TODO: create stroke for a path with one point
264 warning ("One point.");
265 stroked = new Path ();
266 }
267
268 return stroked;
269 }
270
271 static Path generate_stroke (Path p, double thickness) {
272 Path stroked = new Path ();
273 EditPoint start = new EditPoint ();
274 EditPoint end;
275 EditPoint previous;
276 int i;
277
278 previous = p.get_first_point ().copy ();
279 move_segment (start, previous, thickness);
280
281 i = 0;
282 foreach (EditPoint ep in p.points) {
283 start = ep.copy ();
284 end = ep.get_next ().copy ();
285
286 move_segment (start, end, thickness);
287
288 if (start == p.get_last_point ()) {
289 end = p.get_first_point ();
290 }
291
292 if (!p.is_open () || (i != 0 && i != p.points.size - 1)) {
293 add_corner (stroked, previous, start, ep.copy (), thickness);
294 }
295
296 stroked.add_point (start);
297
298 if (end.get_left_handle ().length > 0) {
299 stroked.add_point (end);
300 }
301
302 // open ends around corner
303 start.get_left_handle ().convert_to_line ();
304 end.get_right_handle ().convert_to_line ();
305
306 start.flags |= EditPoint.STROKE_OFFSET;
307 end.flags |= EditPoint.STROKE_OFFSET;
308
309 previous = end;
310
311 i++;
312 }
313
314 stroked.recalculate_linear_handles ();
315
316 return stroked;
317 }
318
319 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) {
320 EditPointHandle r, l;
321 double m, n;
322 double qx, qy;
323
324 stroke_start.set_tie_handle (false);
325 stroke_stop.set_tie_handle (false);
326
327 r = stroke_start.get_right_handle ();
328 l = stroke_stop.get_left_handle ();
329
330 m = cos (r.angle + PI / 2) * thickness;
331 n = sin (r.angle + PI / 2) * thickness;
332
333 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n);
334 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n);
335
336 stroke_start.independent_x += m;
337 stroke_start.independent_y += n;
338
339 qx = cos (l.angle - PI / 2) * thickness;
340 qy = sin (l.angle - PI / 2) * thickness;
341
342 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy);
343 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy);
344
345 stroke_stop.independent_x += qx;
346 stroke_stop.independent_y += qy;
347 }
348
349 static void add_corner (Path stroked, EditPoint previous, EditPoint next,
350 EditPoint original, double stroke_width) {
351
352 double ratio;
353 double distance;
354 EditPoint corner;
355 double corner_x, corner_y;
356 EditPointHandle previous_handle;
357 EditPointHandle next_handle;
358 EditPoint cutoff1, cutoff2;
359
360 previous_handle = previous.get_left_handle ();
361 next_handle = next.get_right_handle ();
362
363 previous_handle.angle += PI;
364 next_handle.angle += PI;
365
366 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y);
367 corner = new EditPoint (corner_x, corner_y, previous.type);
368 corner.convert_to_line ();
369
370 previous_handle.angle -= PI;
371 next_handle.angle -= PI;
372
373 distance = Path.distance_to_point (corner, original);
374 ratio = 1.5 * fabs (stroke_width) / distance;
375
376 if (distance < 0.1) {
377 previous.flags |= EditPoint.NEW_CORNER;
378 next.flags |= EditPoint.NEW_CORNER;
379 } else {
380 if (ratio > 1) {
381 stroked.add_point (corner);
382 } else {
383 cutoff1 = new EditPoint ();
384 cutoff1.set_point_type (previous.type);
385 cutoff1.convert_to_line ();
386
387 cutoff2 = new EditPoint ();
388 cutoff2.set_point_type (previous.type);
389 cutoff2.convert_to_line ();
390
391 cutoff1.x = previous.x + (corner.x - previous.x) * ratio;
392 cutoff1.y = previous.y + (corner.y - previous.y) * ratio;
393
394 cutoff2.x = next.x + (corner.x - next.x) * ratio;
395 cutoff2.y = next.y + (corner.y - next.y) * ratio;
396
397 cutoff1 = stroked.add_point (cutoff1);
398 cutoff2 = stroked.add_point (cutoff2);
399
400 cutoff1.recalculate_linear_handles ();
401 cutoff2.recalculate_linear_handles ();
402
403 previous.flags |= EditPoint.NEW_CORNER;
404 next.flags |= EditPoint.NEW_CORNER;
405 }
406 }
407 }
408
409 static PathList get_parts (Path path) {
410 PathList intersections;
411 PathList r;
412
413 r = get_parts_self (path);
414 intersections = new PathList ();
415
416 foreach (Path p in r.paths) {
417 intersections.add (p);
418 }
419
420 // return split_paths (intersections);
421 return intersections;
422 }
423
424 static PathList split_corners (PathList result) {
425 split_corner (result);
426 return result;
427 }
428
429 static bool split_corner (PathList pl) {
430 EditPoint p1, p2;
431 EditPoint a1, a2;
432 PathList r;
433 bool split;
434
435 foreach (Path p in pl.paths) {
436 if (p.points.size == 0) {
437 continue;
438 }
439
440 for (int index = 1; index < p.points.size + 2; index++) {
441 p1 = p.points.get ((index - 1) % p.points.size);
442 p2 = p.points.get (index % p.points.size);
443 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead
444 a2 = p.points.get ((index + 4) % p.points.size);
445
446 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0
447 || (p2.flags & EditPoint.STROKE_OFFSET) > 0
448 || (a1.flags & EditPoint.STROKE_OFFSET) > 0
449 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) { // FIXME: safe?
450
451 split = split_segment (p, a1, a2, p1, p2, out r);
452
453 if (split) {
454 pl.append (r);
455 pl.paths.remove (p);
456 split_corner (pl);
457 return true;
458 } else {
459 p1 = p.points.get ((index - 1) % p.points.size);
460 p2 = p.points.get (index % p.points.size);
461 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead
462 a2 = p.points.get ((index + 3) % p.points.size);
463
464 split = split_segment (p, a1, a2, p1, p2, out r);
465
466 if (split) {
467 pl.append (r);
468 pl.paths.remove (p);
469 split_corner (pl);
470 return true;
471 } else {
472
473 // FIXME: the special case, merge counter path with outline here
474 p1 = p.points.get ((index - 1) % p.points.size);
475 p2 = p.points.get (index % p.points.size);
476 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead
477 a2 = p.points.get ((index + 4) % p.points.size);
478
479 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0
480 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) {
481 p1.flags = EditPoint.COUNTER_TO_OUTLINE;
482 a1.flags = EditPoint.COUNTER_TO_OUTLINE;
483
484 p1.counter_to_outline = true;
485 a1.counter_to_outline = true;
486 }
487 }
488 }
489 }
490 }
491 }
492
493 return false;
494 }
495
496 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) {
497 double ix, iy;
498 bool intersection;
499 int i;
500
501 result = new PathList ();
502 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true);
503
504 if (intersection) {
505 add_intersection (p, first, next, ix, iy);
506 add_intersection (p, p1, p2, ix, iy);
507
508 i = mark_intersection_as_deleted (p);
509 return_val_if_fail (i == 2, false);
510
511 result.append (get_remaining_points (p.copy ()));
512 }
513
514 return intersection;
515 }
516
517 static bool split_path (Path path1, Path path2, PathList result) {
518 PathList pl1, pl2;
519 Path a1, a2, b1, b2;
520 Path m1, m2;
521 int i;
522
523 if (path1 == path2) {
524 return false;
525 }
526
527 if (add_intersection_points (path1, path2, 2)) {
528 i = mark_intersection_as_deleted (path1);
529 return_if_fail (i == 2);
530
531 i = mark_intersection_as_deleted (path2);
532 return_if_fail (i == 2);
533
534 pl1 = get_remaining_points (path1.copy ());
535 pl2 = get_remaining_points (path2.copy ());
536
537 return_if_fail (pl1.paths.size == 2);
538 return_if_fail (pl2.paths.size == 2);
539
540 a1 = pl1.paths.get (0);
541 a2 = pl1.paths.get (1);
542 b1 = pl2.paths.get (0);
543 b2 = pl2.paths.get (1);
544
545 m1 = PenTool.merge_open_paths (a1, b2);
546 m2 = PenTool.merge_open_paths (b1, a2);
547
548 result.add (m1);
549 result.add (m2);
550
551 return true;
552 }
553
554 return false;
555 }
556
557 static PathList split_paths (PathList pl) {
558 PathList n = new PathList ();
559
560 n.append (pl);
561
562 foreach (Path p1 in pl.paths) {
563 foreach (Path p2 in pl.paths) {
564 if (p1 != p2) {
565 if (split_path (p1, p2, n)) {
566 n.paths.remove (p1);
567 n.paths.remove (p2);
568 return split_paths (n);
569 }
570 }
571 }
572 }
573
574 return n;
575 }
576
577 static PathList get_parts_self (Path path, PathList? paths = null) {
578 PathList pl;
579 PathList r;
580
581 r = paths == null ? new PathList () : (!) paths;
582 pl = split (path);
583
584 foreach (Path part in pl.paths) {
585 if (!has_self_intersection (part)) {
586 r.add (part);
587 } else {
588 get_parts_self (part, r);
589 }
590 }
591
592 if (r.paths.size == 0) {
593 warning ("No parts in path");
594 }
595
596 return r;
597 }
598
599 static bool has_intersection_points (Path path) {
600 foreach (EditPoint p in path.points) {
601 if ((p.flags & EditPoint.INTERSECTION) > 0) {
602 return true;
603 }
604 }
605 return false;
606 }
607
608 /** Split one path at intersection points in two parts. */
609 static PathList split (Path path) {
610 PathList pl;
611 int i;
612
613 if (!has_intersection_points (path)) {
614 add_self_intersection_points (path);
615 } else {
616 warning ("points already created.");
617 }
618
619 i = mark_intersection_as_deleted (path);
620
621 if (!(i == 0 || i == 2)) {
622 warning (@"Split should only create two parts, $i points will be deleted.");
623 }
624
625 pl = get_remaining_points (path.copy ());
626
627 return pl;
628 }
629
630 static PathList process_deleted_control_points (Path path) {
631 PathList paths, nl, pl, rl;
632
633 paths = new PathList ();
634 rl = new PathList ();
635 pl = new PathList ();
636 nl = new PathList ();
637
638 if (!path.has_deleted_point ()) {
639 return pl;
640 }
641
642 pl.add (path);
643
644 foreach (Path p in pl.paths) {
645 nl = p.process_deleted_points ();
646
647 if (nl.paths.size > 0) {
648 rl.append (nl);
649 rl.paths.remove (p);
650 }
651 }
652
653 foreach (Path p in rl.paths) {
654 pl = process_deleted_control_points (p);
655
656 if (pl.paths.size > 0) {
657 paths.append (pl);
658 } else {
659 paths.add (p);
660 }
661 }
662
663 return paths;
664 }
665
666 static PathList get_remaining_points (Path old_path) {
667 PathList pl;
668
669 old_path.close ();
670 pl = process_deleted_control_points (old_path);
671
672 if (pl.paths.size == 0) {
673 pl.add (old_path);
674 }
675
676 foreach (Path pn in pl.paths) {
677 pn.close ();
678 }
679
680 return pl;
681 }
682
683 static bool has_self_intersection (Path path) {
684 bool intersection = false;
685
686 path.all_segments ((ep1, ep2) => {
687 double ix, iy;
688 EditPoint p1, p2;
689
690 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2)) {
691 intersection = true;
692 return false;
693 }
694
695 return true;
696 });
697
698 return intersection;
699 }
700
701 static bool add_self_intersection_points (Path path, bool only_offsets = false) {
702 bool intersection = false;
703
704 path.all_segments ((ep1, ep2) => {
705 double ix, iy;
706 EditPoint p1, p2;
707
708 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) {
709 add_intersection (path, ep1, ep2, ix, iy);
710 add_intersection (path, p1, p2, ix, iy);
711
712 intersection = true;
713 return false;
714 }
715
716 return true;
717 });
718
719 if (intersection) {
720 // FIXME: path.create_list ();
721 }
722
723 return intersection;
724 }
725
726 static EditPoint add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) {
727 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> ();
728 EditPoint ep1 = new EditPoint ();
729 EditPoint ep2 = new EditPoint ();
730 EditPoint ep3 = new EditPoint ();
731
732 if (next == path.get_first_point ()) { // FIXME: double check
733 ep1.prev = null;
734 } else {
735 ep1.prev = prev;
736 }
737
738 ep1.prev = prev;
739 ep1.next = ep2;
740 ep1.flags |= EditPoint.NEW_CORNER;
741 ep1.type = PointType.CUBIC;
742 ep1.x = px;
743 ep1.y = py;
744 ep1.color = c;
745 n.add (ep1);
746
747 ep2.prev = ep1;
748 ep2.next = ep3;
749 ep2.flags |= EditPoint.INTERSECTION;
750 ep2.type = PointType.QUADRATIC;
751 ep2.x = px;
752 ep2.y = py;
753 ep2.color = c;
754 n.add (ep2);
755
756 ep3.prev = ep2;
757 ep3.next = next;
758 ep3.flags |= EditPoint.NEW_CORNER;
759 ep3.type = PointType.CUBIC;
760 ep3.x = px;
761 ep3.y = py;
762 ep3.color = c;
763 n.add (ep3);
764
765 foreach (EditPoint np in n) {
766 np = path.add_point_after (np, np.prev);
767 path.create_list ();
768 }
769
770 path.recalculate_linear_handles ();
771
772 return ep2;
773 }
774
775 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next,
776 out double ix, out double iy,
777 bool skip_points_on_points = false) {
778 double cross_x, cross_y;
779
780 ix = 0;
781 iy = 0;
782
783 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y);
784
785 if (Glyph.CANVAS_MIN < cross_x < Glyph.CANVAS_MAX
786 && Glyph.CANVAS_MIN < cross_y < Glyph.CANVAS_MAX) {
787 // iterate to find intersection.
788
789 if (skip_points_on_points ||
790 !((ep.x == cross_x && ep.y == cross_y)
791 || (next.x == cross_x && next.y == cross_y)
792 || (p1.x == cross_x && p1.y == cross_y)
793 || (p2.x == cross_x && p2.y == cross_y))) {
794
795 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y)
796 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) {
797
798 ix = cross_x;
799 iy = cross_y;
800
801 return true;
802 }
803 }
804 }
805
806 return false;
807 }
808
809 static bool segment_intersects (Path path, EditPoint ep, EditPoint next,
810 out double ix, out double iy,
811 out EditPoint ia, out EditPoint ib,
812 bool skip_points_on_points = false,
813 bool only_offsets = false) {
814
815 EditPoint p1, p2;
816 bool intersection, inter;
817 double iix, iiy;
818
819 double distance, min_distance;
820
821 intersection = false;
822
823 ix = 0;
824 iy = 0;
825
826 iix = 0;
827 iiy = 0;
828
829 ia = new EditPoint ();
830 ib = new EditPoint ();
831
832 if (path.points.size == 0) {
833 return false;
834 }
835
836 min_distance = double.MAX;
837 p1 = path.points.get (path.points.size - 1);
838 for (int i = 0; i < path.points.size; i++) {
839 p2 = path.points.get (i);
840
841 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0)
842 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0)
843 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0)
844 && ((next.flags & EditPoint.STROKE_OFFSET) > 0);
845
846 if (!only_offsets || is_offset) {
847 if (p1 != ep && p2 != next) {
848 inter = segments_intersects (p1, p2, ep, next, out iix, out iiy,
849 skip_points_on_points);
850
851 if (inter) {
852 distance = Path.distance (ep.x, iix, ep.y, iiy);
853 if (distance < min_distance) {
854 ia = p1;
855 ib = p2;
856 ix = iix;
857 iy = iiy;
858 intersection = true;
859 min_distance = distance;
860 }
861 }
862 }
863 }
864
865 p1 = p2;
866 }
867
868 return intersection;
869 }
870
871 static bool same (EditPoint a, EditPoint b) {
872 return a.x == b.x && a.y == b.y;
873 }
874
875 /** @return true if p2 is on the line p1 to p3 */
876 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3) {
877 double ds = Path.distance (x1, x3, y1, y3);
878 double d1 = Path.distance (x1, x2, y1, y2);
879 double d2 = Path.distance (x2, x3, y2, y3);
880 double p = d1 / ds;
881 double x = fabs ((x3 - x1) * p - (x2 - x1));
882 double y = fabs ((y3 - y1) * p - (y2 - y1));
883 double d = fabs (ds - (d1 + d2));
884
885 // FIXME: delete print (@"$(fmin (x1, x3)) < $x2 && $x2 < $(fmax (x1, x3))\n");
886 // FIXME: delete print (@"$(fmin (y1, y3)) < $y2 && $y2 < $(fmax (y1, y3))\n");
887
888 return ds > 0.01 && d1 > 0.01 && d2 > 0.01
889 && d < 0.01 && x < 0.01 && y < 0.01
890 && fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3)
891 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3);
892 }
893
894 static Path get_outline (Path path) {
895 PathList pl = get_parts (path);
896 Path outline = new Path ();
897 int inside;
898 int min_inside = int.MAX;
899 int points = 0;
900 int i = 0;
901
902 foreach (Path p in pl.paths) {
903 inside = Path.counters (pl, p);
904
905 if (inside < min_inside) {
906 outline = p;
907 min_inside = inside;
908 }
909
910 i++;
911 }
912
913 if (min_inside == 0) {
914 foreach (Path p in pl.paths) {
915 if (p.points.size > points) {
916 outline = p;
917 points = p.points.size;
918 }
919 }
920 }
921
922 return outline;
923 }
924
925 static void remove_points_in_stroke (PathList pl) {
926 PathList result;
927 PathList r;
928 PathList parts;
929
930 foreach (Path p in pl.paths) {
931 if (remove_points_in_stroke_for_path (p, pl, out r)) {
932 pl.append (r);
933 remove_points_in_stroke (pl);
934 return;
935 }
936 }
937 }
938
939 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) {
940 bool remove = false;
941 EditPoint start_ep;
942 EditPoint start_next;
943 EditPoint start_prev;
944 EditPoint end_ep = new EditPoint ();
945 EditPoint end_next;
946 EditPoint end_prev;
947 Path path2;
948 EditPoint found = new EditPoint ();
949
950 result = new PathList ();
951
952 for (int i = 1; i < p.points.size + 1; i++) {
953 start_prev = p.points.get ((i - 1) % p.points.size);
954 start_ep = p.points.get (i % p.points.size);
955 start_next = p.points.get ((i + 1) % p.points.size);
956
957 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
958 for (int j = i; j < p.points.size + i; j++) {
959 end_prev = p.points.get ((j - 1) % p.points.size);
960 end_ep = p.points.get (j % p.points.size);
961 end_next = p.points.get ((j + 1) % p.points.size);
962
963 // FIXME: if (!is_inside_of_path
964
965 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
966 start_ep.flags = EditPoint.NONE;
967 end_ep.flags = EditPoint.NONE;
968
969 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) {
970 return true;
971 }
972 }
973 }
974 }
975
976 start_ep.flags = EditPoint.NONE;
977 end_ep.flags = EditPoint.NONE;
978 }
979
980 return false;
981 }
982
983 static bool merge_segments (PathList pl,
984 Path path1, EditPoint start1, EditPoint stop1,
985 EditPoint start2, EditPoint stop2,
986 out PathList result) {
987
988 result = new PathList ();
989
990 PathList r1;
991 PathList r2;
992
993 foreach (Path path2 in pl.paths) {
994 if (path2 != path1) {
995 reset_intersections (path1);
996 reset_intersections (path2);
997
998 if (add_merge_intersection_point (path1, path2, start1, stop1)) {
999 if (add_merge_intersection_point (path1, path2, start2, stop2)) {
1000
1001 r1 = get_remaining_points (path1.copy ());
1002 r2 = get_remaining_points (path2.copy ());
1003
1004 if (r1.paths.size != 2) {
1005 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n");
1006 reset_intersections (path1);
1007 reset_intersections (path2);
1008 return true;
1009 }
1010
1011 if (r2.paths.size != 2) {
1012 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n");
1013 reset_intersections (path1);
1014 reset_intersections (path2);
1015 return true;
1016 }
1017
1018 pl.paths.remove (path1);
1019 pl.paths.remove (path2);
1020
1021 // FIXME: find criteria
1022
1023 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (),
1024 r2.paths.get (0).get_first_point ());
1025
1026 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (),
1027 r2.paths.get (1).get_first_point ());
1028
1029 Path m1, m2;
1030
1031 if (d1 > d2) {
1032 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0));
1033 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1));
1034 } else {
1035 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0));
1036 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1));
1037 }
1038
1039 result.add (m1);
1040 result.add (m2);
1041
1042 return true;
1043 } else {
1044 reset_intersections (path1);
1045 reset_intersections (path2);
1046 }
1047 } else {
1048 reset_intersections (path1);
1049 reset_intersections (path2);
1050 }
1051 }
1052 }
1053
1054 return false;
1055 }
1056
1057 static void reset_intersections (Path p) {
1058 foreach (EditPoint ep in p.points) {
1059 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION;
1060 ep.deleted = false;
1061 }
1062 p.remove_points_on_points ();
1063 }
1064
1065 static bool has_counter_to_outline (Path p) {
1066 foreach (EditPoint ep in p.points) {
1067 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
1068 return true;
1069 }
1070 }
1071
1072 return false;
1073 }
1074
1075 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) {
1076 double ix, iy;
1077 bool intersection;
1078
1079 intersection = false;
1080 ix = 0;
1081 iy = 0;
1082 path2.all_segments ((p1, p2) => {
1083 int i;
1084
1085 intersection = segments_intersects (first, next, p1, p2, out ix, out iy);
1086
1087 if (intersection) {
1088 add_intersection (path1, first, next, ix, iy);
1089 add_intersection (path2, p1, p2, ix, iy);
1090
1091 i = mark_intersection_as_deleted (path1);
1092 i = mark_intersection_as_deleted (path2);
1093 }
1094
1095 return !intersection;
1096 });
1097
1098 return intersection;
1099 }
1100
1101 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) {
1102 outline = new Path ();
1103 foreach (Path p in pl.paths) {
1104 if (p != ps.path) {
1105 if (SvgParser.is_inside (ps.point, p)) {
1106 outline = p;
1107 return true;
1108 }
1109 }
1110 }
1111
1112 return false;
1113 }
1114
1115 static PathList merge (PathList pl) {
1116 PathList r;
1117 remove_points_in_stroke (pl);
1118 r = merge_paths (pl);
1119 //remove_merged_parts (r);
1120 return r;
1121 }
1122
1123 static void remove_merged_parts (PathList r) {
1124 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> ();
1125 foreach (Path p in r.paths) {
1126
1127 if (Path.is_counter (r, p)) {
1128 if (p.is_clockwise ()) {
1129 remove.add (p);
1130 }
1131 } else {
1132 if (!p.is_clockwise ()) {
1133 remove.add (p);
1134 }
1135 }
1136
1137 if (stroke_selected) { // FIXME: DELETE
1138 ((!) BirdFont.get_current_font ().get_glyph ("a")).add_path (p);
1139 }
1140 }
1141
1142 foreach (Path p in remove) {
1143 r.paths.remove (p);
1144 }
1145 }
1146
1147 static PathList merge_paths (PathList r) {
1148 PathList result = new PathList ();
1149 PathList m;
1150
1151 foreach (Path p1 in r.paths) {
1152 result.add (p1);
1153 }
1154
1155 foreach (Path p1 in r.paths) {
1156 foreach (Path p2 in r.paths) {
1157 if (p1 != p2) {
1158 p1.update_region_boundaries ();
1159 p2.update_region_boundaries ();
1160 if (merge_path (p1, p2, out m)) {
1161 result.append (m);
1162 result.paths.remove (p1);
1163 result.paths.remove (p2);
1164 return merge_paths (result);
1165 }
1166 }
1167 }
1168 }
1169
1170 return result;
1171
1172 }
1173
1174 public class Intersection : GLib.Object {
1175 public bool done = false;
1176 public EditPoint point;
1177 public EditPoint other_point;
1178 public Path path;
1179 public Path other_path;
1180
1181 public Intersection (EditPoint point, Path path,
1182 EditPoint other_point, Path other_path) {
1183
1184 this.point = point;
1185 this.path = path;
1186 this.other_point = other_point;
1187 this.other_path = other_path;
1188 }
1189
1190 public Intersection.empty () {
1191 this.point = new EditPoint ();
1192 this.path = new Path ();
1193 this.other_point = new EditPoint ();
1194 this.other_path = new Path ();
1195 }
1196
1197 public Path get_other_path (Path p) {
1198 if (p == path) {
1199 return other_path;
1200 }
1201
1202 if (p == other_path) {
1203 return path;
1204 }
1205
1206 warning ("Wrong intersection.");
1207 return new Path ();
1208 }
1209
1210 public EditPoint get_point (Path p) {
1211 if (p == path) {
1212 return point;
1213 }
1214
1215 if (p == other_path) {
1216 return other_point;
1217 }
1218
1219 warning ("Wrong intersection.");
1220 return new EditPoint ();
1221 }
1222 }
1223
1224 public class IntersectionList : GLib.Object {
1225 public Gee.ArrayList<Intersection> points = new Gee.ArrayList<Intersection> ();
1226
1227 public IntersectionList () {
1228 }
1229
1230 public Intersection get_point (EditPoint ep, out bool other) {
1231 other = false;
1232 foreach (Intersection i in points) {
1233 if (i.other_point == ep || i.point == ep) {
1234 other = (i.other_point == ep);
1235 return i;
1236 }
1237 }
1238
1239 warning ("No intersection found for point.");
1240 return new Intersection.empty ();
1241 }
1242 }
1243
1244 static bool merge_path (Path path1, Path path2, out PathList merged_paths) {
1245 IntersectionList intersections;
1246 EditPoint ep1, next, p1, p2, pp1, pp2;
1247 Path path, other, merged;
1248 PathList pl1, pl2, r, other_paths, result;
1249 bool intersects;
1250 int s, i;
1251 double ix, iy, iix, iiy;
1252 bool merge = false;
1253 EditPoint intersection_point, other_intersection_point;
1254 Intersection intersection;
1255
1256 merged_paths = new PathList ();
1257 intersections = new IntersectionList ();
1258
1259 iix = 0;
1260 iiy = 0;
1261
1262 result = new PathList ();
1263
1264 if (path1.points.size == 0 || path2.points.size == 0) {
1265 warning ("No points in path.");
1266 return false;
1267 }
1268
1269 if (!path1.boundaries_intersecting (path2)) {
1270 return false;
1271 }
1272
1273 Path original_path1 = path1.copy ();
1274 Path original_path2 = path2.copy ();
1275
1276 s = 0;
1277 foreach (EditPoint e in original_path1.points) {
1278 if (!SvgParser.is_inside (e, original_path2)) {
1279 break;
1280 }
1281 s++;
1282 }
1283
1284 if (s >= path1.points.size) {
1285 Path t;
1286 t = original_path1;
1287 original_path1 = original_path2;
1288 original_path2 = t;
1289 s = 0;
1290 foreach (EditPoint e in original_path1.points) {
1291 if (!SvgParser.is_inside (e, original_path2)) {
1292 break;
1293 }
1294 s++;
1295 }
1296 }
1297
1298 if (s >= original_path1.points.size) {
1299 warning ("No start point found.");
1300 return false;
1301 }
1302
1303 path = original_path1;
1304 other = original_path2;
1305
1306 other_paths = new PathList ();
1307 r = new PathList ();
1308 other_paths.add (path);
1309 other_paths.add (other);
1310 intersects = false;
1311 p1 = new EditPoint ();
1312 p2 = new EditPoint ();
1313 pp1 = new EditPoint ();
1314 pp2 = new EditPoint ();
1315
1316 ix = 0;
1317 iy = 0;
1318 i = s;
1319 merged = new Path ();
1320
1321 while (true) {
1322 ep1 = path.points.get (i % path.points.size);
1323 next = path.points.get ((i + 1) % path.points.size);
1324
1325 if ((ep1.flags & EditPoint.COPIED) > 0) {
1326 if (merge) {
1327 merged.close ();
1328 result.add (merged.copy ());
1329 }
1330
1331 merged = new Path ();
1332
1333 bool find_parts = false;
1334 Intersection new_start = new Intersection.empty ();
1335 foreach (Intersection inter in intersections.points) {
1336 if (!inter.done && !find_parts) {
1337 find_parts = true;
1338 new_start = inter;
1339 break;
1340 }
1341 }
1342
1343 if (!find_parts) {
1344 break; // done, no more parts
1345 } else {
1346 // set start point for next part
1347 path = new_start.other_path;
1348
1349 if (path.points.size == 0) {
1350 warning ("No points.");
1351 return false;
1352 }
1353
1354 i = index_of (path, new_start.get_point (path));
1355
1356 if (i < 0) {
1357 warning ("Start point not found.");
1358 return false;
1359 }
1360
1361 ep1 = path.points.get (i % path.points.size);
1362 next = path.points.get ((i + 1) % path.points.size);
1363
1364 if ((ep1.flags & EditPoint.INTERSECTION) == 0) {
1365 warning ("Not starting on an intersection point.");
1366 return false;
1367 }
1368
1369 new_start.done = true;
1370 }
1371 }
1372
1373 intersects = false;
1374
1375 double dm;
1376 double d;
1377
1378 if ((ep1.flags & EditPoint.INTERSECTION) > 0) {
1379 Intersection current_intersection;
1380 bool continue_on_other_path;
1381 current_intersection = intersections.get_point (ep1, out continue_on_other_path);
1382 current_intersection.done = true;
1383
1384 // take the other part of an intersection
1385 if ((next.flags & EditPoint.COPIED) != 0) {
1386 bool next_is_intersection = false;
1387 bool next_continue_on_other_path;
1388
1389 next_is_intersection = ((next.flags & EditPoint.INTERSECTION) > 0);
1390
1391 if (next_is_intersection) {
1392 Intersection next_intersection = intersections.get_point (next, out next_continue_on_other_path);
1393
1394 ep1.flags |= EditPoint.COPIED;
1395 merged.add_point (ep1.copy ());
1396
1397 if (!next_intersection.done) {
1398 EditPoint new_start_point;
1399
1400 path = next_continue_on_other_path
1401 ? next_intersection.other_path : next_intersection.path;
1402
1403 new_start_point = next_continue_on_other_path
1404 ? next_intersection.other_point : next_intersection.point;
1405
1406 i = index_of (path, new_start_point);
1407
1408 if (i < 0) {
1409 warning ("Point not found in path.\n");
1410 return false;
1411 }
1412
1413 ep1 = path.points.get (i % path.points.size);
1414 next = path.points.get ((i + 1) % path.points.size);
1415 } else {
1416 warning ("Part is already created.\n");
1417 return false;
1418 }
1419 } else {
1420 ep1.flags |= EditPoint.COPIED;
1421 merged.add_point (ep1.copy ());
1422
1423 EditPoint new_start_point;
1424
1425 if ((next.flags & EditPoint.COPIED) > 0) {
1426 path = current_intersection.get_other_path (path);
1427 new_start_point = current_intersection.get_point (path);
1428 i = index_of (path, new_start_point);
1429
1430 if (i < 0) {
1431 warning ("Point not found in path.");
1432 return false;
1433 }
1434
1435 ep1 = path.points.get (i % path.points.size);
1436 next = path.points.get ((i + 1) % path.points.size);
1437
1438 if ((next.flags & EditPoint.INTERSECTION) > 0) {
1439 warning ("Wrong type.");
1440 }
1441
1442 if ((next.flags & EditPoint.COPIED) > 0) {
1443 merged.add_point (ep1.copy ());
1444 continue;
1445 }
1446 } else {
1447 ep1.flags |= EditPoint.COPIED;
1448 merged.add_point (ep1.copy ());
1449 }
1450 }
1451 } else {
1452 ep1.flags |= EditPoint.COPIED;
1453 merged.add_point (ep1.copy ());
1454 }
1455
1456 current_intersection.done = true;
1457 } else {
1458 // find new intersection
1459 dm = double.MAX;
1460 foreach (Path o in other_paths.paths) {
1461 bool inter = segment_intersects (o, ep1, next, out iix, out iiy,
1462 out pp1, out pp2, true);
1463 d = Path.distance (ep1.x, iix, ep1.y, iiy);
1464 if (d < dm && inter) {
1465 other = o;
1466 dm = d;
1467 intersects = true;
1468 p1 = pp1;
1469 p2 = pp2;
1470 ix = iix;
1471 iy = iiy;
1472 }
1473 }
1474
1475 if (intersects) {
1476 merged.add_point (ep1.copy ());
1477 ep1.flags |= EditPoint.COPIED;
1478
1479 intersection_point = add_intersection (path, ep1, next, ix, iy);
1480 other_intersection_point = add_intersection (other, p1, p2, ix, iy);
1481
1482 bool g = false;
1483 bool stay = false;
1484 foreach (Intersection old_intersection in intersections.points) {
1485 if (old_intersection.point == intersection_point
1486 || old_intersection.other_point == other_intersection_point) {
1487 old_intersection.done = true;
1488 g = true;
1489 }
1490 }
1491
1492 if (!g) {
1493 Intersection ip = new Intersection (intersection_point, path, other_intersection_point, other);
1494 intersections.points.add (ip);
1495 }
1496
1497 merged.add_point (intersection_point.copy ());
1498 intersection_point.flags |= EditPoint.COPIED;
1499
1500 i = index_of (other, other_intersection_point);
1501
1502 if (i < 0) {
1503 warning (@"Point not found ($i).");
1504 break;
1505 }
1506
1507 path = other;
1508 merge = true;
1509 } else {
1510 ep1.flags |= EditPoint.COPIED;
1511 merged.add_point (ep1.copy ());
1512 }
1513 }
1514
1515 i++;
1516 }
1517
1518 int counter;
1519 foreach (Path p in result.paths) {
1520 counter = Path.counters (result, p);
1521 if (counter == 0) {
1522 merged.force_direction (Direction.CLOCKWISE);
1523 } else {
1524 if (path1.is_clockwise () != original_path2.is_clockwise ()) {
1525 merged.force_direction (Direction.COUNTER_CLOCKWISE);
1526 } else {
1527 merged.force_direction (Direction.CLOCKWISE);
1528 }
1529 }
1530
1531 reset_intersections (p);
1532 merged_paths.add (p);
1533 p.update_region_boundaries ();
1534 p.recalculate_linear_handles ();
1535 }
1536
1537 return merge;
1538 }
1539
1540 static int index_of (Path p, EditPoint ep) {
1541 int i = 0;
1542 foreach (EditPoint e in p.points) {
1543 if (e == ep) {
1544 return i;
1545 }
1546 i++;
1547 }
1548
1549 return -1;
1550 }
1551
1552 static Path get_next_part (PathList pl, EditPoint ep) {
1553 double d, m;
1554 Path r;
1555
1556 r = new Path ();
1557 m = double.MAX;
1558 foreach (Path p in pl.paths) {
1559 d = Path.distance_to_point (p.get_last_point (), ep);
1560 if (d < m) {
1561 m = d;
1562 r = p;
1563 }
1564 }
1565
1566 return r;
1567 }
1568
1569 public static int counters_in_point_in_path (Path p, EditPoint ep) {
1570 int inside_count = 0;
1571 bool inside;
1572
1573 if (p.points.size > 1) {
1574 inside = true;
1575
1576 if (!SvgParser.is_inside (ep, p)) {
1577 inside = false;
1578 }
1579
1580 if (inside) {
1581 inside_count++;
1582 }
1583 }
1584
1585 return inside_count;
1586 }
1587
1588 static int mark_intersection_as_deleted (Path path) {
1589 int i = 0;
1590
1591 foreach (EditPoint p in path.points) {
1592
1593 if ((p.flags & EditPoint.INTERSECTION) > 0) {
1594 p.deleted = true;
1595 i++;
1596 }
1597 }
1598
1599 return i;
1600 }
1601
1602 /** @param n number of interrsections to find per path. */
1603 static bool add_intersection_points (Path path1, Path path2, int n = 1) {
1604 bool intersection = false;
1605 int found = 0;
1606
1607 path1.all_segments ((ep1, ep2) => {
1608 double ix, iy;
1609 EditPoint p1, p2;
1610 bool i;
1611
1612 i = segment_intersects (path2, ep1, ep2, out ix, out iy,
1613 out p1, out p2, true);
1614
1615 if (i) {
1616 add_intersection (path1, ep1, ep2, ix, iy);
1617 add_intersection (path2, p1, p2, ix, iy);
1618 intersection = true;
1619 found++;
1620 return found < n;
1621 }
1622
1623 return true;
1624 });
1625
1626 return intersection;
1627 }
1628
1629 }
1630
1631 }
1632