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 paths.append (get_stroke (p, p.stroke));
52 }
53
54 foreach (Path np in paths.paths) {
55 g.add_path (np);
56 }
57 }
58
59 public static PathList get_stroke (Path path, double thickness) {
60 PathList n;
61 PathList o = new PathList ();
62 Path original = path.copy ();
63
64 original.remove_points_on_points ();
65
66 n = get_stroke_outline (original, thickness);
67
68 o = split_corners (n);
69 remove_self_intersecting_corners (o);
70
71 o = merge (o);
72
73 PathList parts = new PathList ();
74 foreach (Path p in o.paths) {
75 parts.append (split (p));
76 }
77
78 return parts;
79 }
80
81 static bool is_corner_self_intersection (Path p) {
82 EditPointHandle l, r;
83 bool corner, i, remove;
84
85 remove = false;
86 i = false;
87 p.remove_points_on_points ();
88 foreach (EditPoint ep in p.points) {
89
90 corner = (ep.flags & EditPoint.NEW_CORNER) > 0;
91
92 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
93 return false;
94 }
95
96 if (corner || i) {
97 l = ep.get_left_handle ();
98 r = ep.get_right_handle ();
99
100 if (fabs (l.angle - r.angle) < 0.005) {
101 ep.color = new Color (1,0,0,1);
102 remove = true;
103 } else ep.color = new Color (0,0,1,1);
104 }
105
106 i = corner && p.points.size == 4;
107 }
108
109 return remove;
110 }
111
112 static void remove_self_intersecting_corners (PathList pl) {
113 PathList parts;
114 foreach (Path p in pl.paths) {
115
116 if (is_corner_self_intersection (p)) {
117 parts = get_parts (p);
118 if (parts.paths.size > 1) {
119 pl.append (parts);
120 remove_self_intersecting_corners (pl);
121 return;
122 } else {
123
124 if (has_self_intersection (p)) { // FIXME: DELETE
125 warning ("Path ha self intersection.");
126 }
127
128 pl.paths.remove (p);
129 remove_self_intersecting_corners (pl);
130 return;
131 }
132 }
133 }
134 }
135
136 public static PathList get_stroke_outline (Path path, double thickness) {
137 return get_strokes (path, thickness);
138 }
139
140 public static PathList get_strokes (Path p, double thickness) {
141 Path counter = new Path ();
142 Path outline = new Path ();
143 Path merged = new Path ();
144 PathList paths = new PathList ();
145
146 if (!p.is_open () && p.is_filled ()) {
147 outline = create_stroke (p, thickness);
148 outline.close ();
149
150 outline.update_region_boundaries ();
151 paths.add (outline);
152 } else if (!p.is_open () && !p.is_filled ()) {
153 outline = create_stroke (p, thickness);
154 counter = create_stroke (p, -1 * thickness);
155
156 if (p.is_clockwise ()) {
157 outline.force_direction (Direction.CLOCKWISE);
158 } else {
159 outline.force_direction (Direction.COUNTER_CLOCKWISE);
160 }
161
162 if (outline.is_clockwise ()) {
163 counter.force_direction (Direction.COUNTER_CLOCKWISE);
164 } else {
165 counter.force_direction (Direction.CLOCKWISE);
166 }
167
168 outline.update_region_boundaries ();
169 paths.add (outline);
170
171 counter.update_region_boundaries ();
172 paths.add (counter);
173 } else if (p.is_open ()) { // FIXME: this can create many parts
174 outline = create_stroke (p, thickness);
175 counter = create_stroke (p, -1 * thickness);
176 merged = merge_strokes (p, outline, counter, thickness);
177
178 if (p.is_clockwise ()) {
179 merged.force_direction (Direction.CLOCKWISE);
180 } else {
181 merged.force_direction (Direction.COUNTER_CLOCKWISE);
182 }
183
184 merged.update_region_boundaries ();
185 paths.add (merged);
186 } else {
187 warning ("Can not create stroke.");
188 paths.add (p);
189 }
190
191 return paths;
192 }
193
194 /** Create one stroke from the outline and counter stroke and close the
195 * open endings.
196 *
197 * @param path the path to create stroke for
198 * @param stroke for the outline of path
199 * @param stroke for the counter path
200 */
201 static Path merge_strokes (Path path, Path stroke, Path counter, double thickness) {
202 Path merged;
203
204 counter.reverse ();
205 merged = stroke.copy ();
206
207 if (path.is_open ()) {
208 merged.delete_last_point ();
209 counter.delete_first_point ();
210 merged.delete_last_point ();
211 counter.delete_first_point ();
212 }
213
214 merged.append_path (counter);
215
216 merged.close ();
217 merged.create_list ();
218 merged.recalculate_linear_handles ();
219
220 return merged;
221 }
222
223 static Path create_stroke (Path p, double thickness) {
224 Path stroked;
225 Path path;
226
227 if (p.points.size >= 2) {
228 path = p.copy ();
229 //FIXME: DELETE path.remove_points_on_points ();
230 stroked = generate_stroke (path, thickness);
231
232 if (!p.is_open ()) {
233 stroked.reverse ();
234 stroked.close ();
235 }
236 } else {
237 // TODO: create stroke for a path with one point
238 warning ("One point.");
239 stroked = new Path ();
240 }
241
242 return stroked;
243 }
244
245 static Path generate_stroke (Path p, double thickness) {
246 Path stroked = new Path ();
247 EditPoint start = new EditPoint ();
248 EditPoint end;
249 EditPoint previous;
250 int i;
251
252 previous = p.get_first_point ().copy ();
253 move_segment (start, previous, thickness);
254
255 i = 0;
256 foreach (EditPoint ep in p.points) {
257 start = ep.copy ();
258 end = ep.get_next ().copy ();
259
260 move_segment (start, end, thickness);
261
262 if (start == p.get_last_point ()) {
263 end = p.get_first_point ();
264 }
265
266 if (!p.is_open () || (i != 0 && i != p.points.size - 1)) {
267 add_corner (stroked, previous, start, ep.copy (), thickness);
268 }
269
270 stroked.add_point (start);
271
272 if (end.get_left_handle ().length > 0) {
273 stroked.add_point (end);
274 }
275
276 // open ends around corner
277 start.get_left_handle ().convert_to_line ();
278 end.get_right_handle ().convert_to_line ();
279
280 start.flags |= EditPoint.STROKE_OFFSET;
281 end.flags |= EditPoint.STROKE_OFFSET;
282
283 previous = end;
284
285 i++;
286 }
287
288 stroked.recalculate_linear_handles ();
289
290 return stroked;
291 }
292
293 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) {
294 EditPointHandle r, l;
295 double m, n;
296 double qx, qy;
297
298 stroke_start.set_tie_handle (false);
299 stroke_stop.set_tie_handle (false);
300
301 r = stroke_start.get_right_handle ();
302 l = stroke_stop.get_left_handle ();
303
304 m = cos (r.angle + PI / 2) * thickness;
305 n = sin (r.angle + PI / 2) * thickness;
306
307 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n);
308 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n);
309
310 stroke_start.independent_x += m;
311 stroke_start.independent_y += n;
312
313 qx = cos (l.angle - PI / 2) * thickness;
314 qy = sin (l.angle - PI / 2) * thickness;
315
316 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy);
317 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy);
318
319 stroke_stop.independent_x += qx;
320 stroke_stop.independent_y += qy;
321 }
322
323 static void add_corner (Path stroked, EditPoint previous, EditPoint next,
324 EditPoint original, double stroke_width) {
325
326 double ratio;
327 double distance;
328 EditPoint corner;
329 double corner_x, corner_y;
330 EditPointHandle previous_handle;
331 EditPointHandle next_handle;
332 EditPoint cutoff1, cutoff2;
333
334 previous_handle = previous.get_left_handle ();
335 next_handle = next.get_right_handle ();
336
337 previous_handle.angle += PI;
338 next_handle.angle += PI;
339
340 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y);
341 corner = new EditPoint (corner_x, corner_y, previous.type);
342 corner.convert_to_line ();
343
344 previous_handle.angle -= PI;
345 next_handle.angle -= PI;
346
347 distance = Path.distance_to_point (corner, original);
348 ratio = 1.5 * fabs (stroke_width) / distance;
349
350 if (distance < 0.1) {
351 previous.flags |= EditPoint.NEW_CORNER;
352 next.flags |= EditPoint.NEW_CORNER;
353 } else {
354 if (ratio > 1) {
355 stroked.add_point (corner);
356 } else {
357 cutoff1 = new EditPoint ();
358 cutoff1.set_point_type (previous.type);
359 cutoff1.convert_to_line ();
360
361 cutoff2 = new EditPoint ();
362 cutoff2.set_point_type (previous.type);
363 cutoff2.convert_to_line ();
364
365 cutoff1.x = previous.x + (corner.x - previous.x) * ratio;
366 cutoff1.y = previous.y + (corner.y - previous.y) * ratio;
367
368 cutoff2.x = next.x + (corner.x - next.x) * ratio;
369 cutoff2.y = next.y + (corner.y - next.y) * ratio;
370
371 cutoff1 = stroked.add_point (cutoff1);
372 cutoff2 = stroked.add_point (cutoff2);
373
374 cutoff1.recalculate_linear_handles ();
375 cutoff2.recalculate_linear_handles ();
376
377 previous.flags |= EditPoint.NEW_CORNER;
378 next.flags |= EditPoint.NEW_CORNER;
379 }
380 }
381 }
382
383 static PathList get_parts (Path path) {
384 PathList intersections;
385 PathList r;
386
387 r = get_parts_self (path);
388 intersections = new PathList ();
389
390 foreach (Path p in r.paths) {
391 intersections.add (p);
392 }
393
394 // return split_paths (intersections);
395 return intersections;
396 }
397
398 static PathList split_corners (PathList result) {
399 split_corner (result);
400 return result;
401 }
402
403 static bool split_corner (PathList pl) {
404 EditPoint p1, p2;
405 EditPoint a1, a2;
406 PathList r;
407 bool split;
408
409 foreach (Path p in pl.paths) {
410 if (p.points.size == 0) {
411 continue;
412 }
413
414 for (int index = 1; index < p.points.size + 2; index++) {
415 p1 = p.points.get ((index - 1) % p.points.size);
416 p2 = p.points.get (index % p.points.size);
417 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead
418 a2 = p.points.get ((index + 4) % p.points.size);
419
420 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0
421 || (p2.flags & EditPoint.STROKE_OFFSET) > 0
422 || (a1.flags & EditPoint.STROKE_OFFSET) > 0
423 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) { // FIXME: safe?
424
425 split = split_segment (p, a1, a2, p1, p2, out r);
426
427 if (split) {
428 pl.append (r);
429 pl.paths.remove (p);
430 split_corner (pl);
431 return true;
432 } else {
433 p1 = p.points.get ((index - 1) % p.points.size);
434 p2 = p.points.get (index % p.points.size);
435 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead
436 a2 = p.points.get ((index + 3) % p.points.size);
437
438 split = split_segment (p, a1, a2, p1, p2, out r);
439
440 if (split) {
441 pl.append (r);
442 pl.paths.remove (p);
443 split_corner (pl);
444 return true;
445 } else {
446
447 // FIXME: the special case, merge counter path with outline here
448 p1 = p.points.get ((index - 1) % p.points.size);
449 p2 = p.points.get (index % p.points.size);
450 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead
451 a2 = p.points.get ((index + 4) % p.points.size);
452
453 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0
454 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) {
455 p1.color = new Color (1,0,1,0.7);
456 a1.color = new Color (1,0,1,0.7);
457 p1.flags = EditPoint.COUNTER_TO_OUTLINE;
458 a1.flags = EditPoint.COUNTER_TO_OUTLINE;
459
460 p1.counter_to_outline = true;
461 a1.counter_to_outline = true;
462 }
463 }
464 }
465 }
466 }
467 }
468
469 return false;
470 }
471
472 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) {
473 double ix, iy;
474 bool intersection;
475 int i;
476
477 result = new PathList ();
478 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true);
479
480 if (intersection) {
481 add_intersection (p, first, next, ix, iy);
482 add_intersection (p, p1, p2, ix, iy);
483
484 i = mark_intersection_as_deleted (p);
485 return_val_if_fail (i == 2, false);
486
487 result.append (get_remaining_points (p.copy ()));
488 }
489
490 return intersection;
491 }
492
493 static bool split_path (Path path1, Path path2, PathList result) {
494 PathList pl1, pl2;
495 Path a1, a2, b1, b2;
496 Path m1, m2;
497 int i;
498
499 if (path1 == path2) {
500 return false;
501 }
502
503 if (add_intersection_points (path1, path2, 2)) {
504 i = mark_intersection_as_deleted (path1);
505 return_if_fail (i == 2);
506
507 i = mark_intersection_as_deleted (path2);
508 return_if_fail (i == 2);
509
510 pl1 = get_remaining_points (path1.copy ());
511 pl2 = get_remaining_points (path2.copy ());
512
513 return_if_fail (pl1.paths.size == 2);
514 return_if_fail (pl2.paths.size == 2);
515
516 a1 = pl1.paths.get (0);
517 a2 = pl1.paths.get (1);
518 b1 = pl2.paths.get (0);
519 b2 = pl2.paths.get (1);
520
521 m1 = PenTool.merge_open_paths (a1, b2);
522 m2 = PenTool.merge_open_paths (b1, a2);
523
524 result.add (m1);
525 result.add (m2);
526
527 return true;
528 }
529
530 return false;
531 }
532
533 static PathList split_paths (PathList pl) {
534 PathList n = new PathList ();
535
536 n.append (pl);
537
538 foreach (Path p1 in pl.paths) {
539 foreach (Path p2 in pl.paths) {
540 if (p1 != p2) {
541 if (split_path (p1, p2, n)) {
542 n.paths.remove (p1);
543 n.paths.remove (p2);
544 return split_paths (n);
545 }
546 }
547 }
548 }
549
550 return n;
551 }
552
553 static PathList get_parts_self (Path path, PathList? paths = null) {
554 PathList pl;
555 PathList r;
556
557 r = paths == null ? new PathList () : (!) paths;
558 pl = split (path);
559
560 foreach (Path part in pl.paths) {
561 if (!has_self_intersection (part)) {
562 r.add (part);
563 } else {
564 get_parts_self (part, r);
565 }
566 }
567
568 if (r.paths.size == 0) {
569 warning ("No parts in path");
570 }
571
572 return r;
573 }
574
575 static bool has_intersection_points (Path path) {
576 foreach (EditPoint p in path.points) {
577 if ((p.flags & EditPoint.INTERSECTION) > 0) {
578 return true;
579 }
580 }
581 return false;
582 }
583
584 /** Split one path at intersection points in two parts. */
585 static PathList split (Path path) {
586 PathList pl;
587 int i;
588
589 if (!has_intersection_points (path)) {
590 add_self_intersection_points (path);
591 } else {
592 warning ("points already created.");
593 }
594
595 i = mark_intersection_as_deleted (path);
596
597 if (!(i == 0 || i == 2)) {
598 warning (@"Split should only create two parts, $i points will be deleted.");
599 }
600
601 pl = get_remaining_points (path.copy ());
602
603 return pl;
604 }
605
606 static PathList process_deleted_control_points (Path path) {
607 PathList paths, nl, pl, rl;
608
609 paths = new PathList ();
610 rl = new PathList ();
611 pl = new PathList ();
612 nl = new PathList ();
613
614 if (!path.has_deleted_point ()) {
615 return pl;
616 }
617
618 pl.add (path);
619
620 foreach (Path p in pl.paths) {
621 nl = p.process_deleted_points ();
622
623 if (nl.paths.size > 0) {
624 rl.append (nl);
625 rl.paths.remove (p);
626 }
627 }
628
629 foreach (Path p in rl.paths) {
630 pl = process_deleted_control_points (p);
631
632 if (pl.paths.size > 0) {
633 paths.append (pl);
634 } else {
635 paths.add (p);
636 }
637 }
638
639 return paths;
640 }
641
642 static PathList get_remaining_points (Path old_path) {
643 PathList pl;
644
645 old_path.close ();
646 pl = process_deleted_control_points (old_path);
647
648 if (pl.paths.size == 0) {
649 pl.add (old_path);
650 }
651
652 foreach (Path pn in pl.paths) {
653 pn.close ();
654 }
655
656 return pl;
657 }
658
659 static bool has_self_intersection (Path path) {
660 bool intersection = false;
661
662 path.all_segments ((ep1, ep2) => {
663 double ix, iy;
664 EditPoint p1, p2;
665
666 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2)) {
667 intersection = true;
668 return false;
669 }
670
671 return true;
672 });
673
674 return intersection;
675 }
676
677 static bool add_self_intersection_points (Path path, bool only_offsets = false) {
678 bool intersection = false;
679
680 path.all_segments ((ep1, ep2) => {
681 double ix, iy;
682 EditPoint p1, p2;
683
684 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) {
685 add_intersection (path, ep1, ep2, ix, iy);
686 add_intersection (path, p1, p2, ix, iy);
687
688 intersection = true;
689 return false;
690 }
691
692 return true;
693 });
694
695 if (intersection) {
696 // FIXME: path.create_list ();
697 }
698
699 return intersection;
700 }
701
702 static void add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) {
703 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> ();
704 EditPoint ep1 = new EditPoint ();
705 EditPoint ep2 = new EditPoint ();
706 EditPoint ep3 = new EditPoint ();
707
708 if (next == path.get_first_point ()) { // FIXME: double check
709 ep1.prev = null;
710 } else {
711 ep1.prev = prev;
712 }
713
714 ep1.prev = prev;
715 ep1.next = ep2;
716 ep1.flags |= EditPoint.NEW_CORNER;
717 ep1.type = PointType.CUBIC;
718 ep1.x = px;
719 ep1.y = py;
720 ep1.color = c;
721 n.add (ep1);
722
723 ep2.prev = ep1;
724 ep2.next = ep3;
725 ep2.flags |= EditPoint.INTERSECTION;
726 ep2.type = PointType.QUADRATIC;
727 ep2.x = px;
728 ep2.y = py;
729 ep2.color = c;
730 n.add (ep2);
731
732 ep3.prev = ep2;
733 ep3.next = next;
734 ep3.flags |= EditPoint.NEW_CORNER;
735 ep3.type = PointType.CUBIC;
736 ep3.x = px;
737 ep3.y = py;
738 ep3.color = c;
739 n.add (ep3);
740
741 foreach (EditPoint np in n) {
742 np = path.add_point_after (np, np.prev);
743 path.create_list ();
744 }
745
746 path.recalculate_linear_handles ();
747 }
748
749 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next,
750 out double ix, out double iy,
751 bool skip_points_on_points = false) {
752 double cross_x, cross_y;
753
754 ix = 0;
755 iy = 0;
756
757 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y);
758
759 if (Glyph.CANVAS_MIN < cross_x < Glyph.CANVAS_MAX
760 && Glyph.CANVAS_MIN < cross_y < Glyph.CANVAS_MAX) {
761 // iterate to find intersection.
762
763 if (skip_points_on_points ||
764 !((ep.x == cross_x && ep.y == cross_y)
765 || (next.x == cross_x && next.y == cross_y)
766 || (p1.x == cross_x && p1.y == cross_y)
767 || (p2.x == cross_x && p2.y == cross_y))) {
768
769 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y)
770 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) {
771
772 ix = cross_x;
773 iy = cross_y;
774
775 return true;
776 }
777 }
778 }
779
780 return false;
781 }
782
783 static bool segment_intersects (Path path, EditPoint ep, EditPoint next,
784 out double ix, out double iy,
785 out EditPoint ia, out EditPoint ib,
786 bool skip_points_on_points = false,
787 bool only_offsets = false) {
788
789 EditPoint p1, p2;
790 bool intersection;
791
792 ix = 0;
793 iy = 0;
794
795 ia = new EditPoint ();
796 ib = new EditPoint ();
797
798 if (path.points.size == 0) {
799 return false;
800 }
801
802 p1 = path.points.get (path.points.size - 1);
803 for (int i = 0; i < path.points.size; i++) {
804 p2 = path.points.get (i);
805
806 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0)
807 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0)
808 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0)
809 && ((next.flags & EditPoint.STROKE_OFFSET) > 0);
810
811 if (!only_offsets || is_offset) {
812 intersection = segments_intersects (p1, p2, ep, next, out ix, out iy,
813 skip_points_on_points);
814
815 if (intersection) {
816 ia = p1;
817 ib = p2;
818 return true;
819 }
820 }
821
822 p1 = p2;
823 }
824
825 return false;
826 }
827
828 /** @return true if p2 is on the line p1 to p3 */
829 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3) {
830 double ds = Path.distance (x1, x3, y1, y3);
831 double d1 = Path.distance (x1, x2, y1, y2);
832 double d2 = Path.distance (x2, x3, y2, y3);
833 double p = d1 / ds;
834 double x = fabs ((x3 - x1) * p - (x2 - x1));
835 double y = fabs ((y3 - y1) * p - (y2 - y1));
836 double d = fabs (ds - (d1 + d2));
837
838 // FIXME: delete print (@"$(fmin (x1, x3)) < $x2 && $x2 < $(fmax (x1, x3))\n");
839 // FIXME: delete print (@"$(fmin (y1, y3)) < $y2 && $y2 < $(fmax (y1, y3))\n");
840
841 return ds > 0.01 && d1 > 0.01 && d2 > 0.01
842 && d < 0.01 && x < 0.01 && y < 0.01
843 && fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3)
844 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3);
845 }
846
847 static Path get_outline (Path path) {
848 PathList pl = get_parts (path);
849 Path outline = new Path ();
850 int inside;
851 int min_inside = int.MAX;
852 int points = 0;
853 int i = 0;
854
855 foreach (Path p in pl.paths) {
856 inside = Path.counters (pl, p);
857
858 if (inside < min_inside) {
859 outline = p;
860 min_inside = inside;
861 }
862
863 i++;
864 }
865
866 if (min_inside == 0) {
867 foreach (Path p in pl.paths) {
868 if (p.points.size > points) {
869 outline = p;
870 points = p.points.size;
871 }
872 }
873 }
874
875 return outline;
876 }
877
878 static void remove_points_in_stroke (PathList pl) {
879 PathList result;
880 PathList r;
881 PathList parts;
882
883 foreach (Path p in pl.paths) {
884 if (remove_points_in_stroke_for_path (p, pl, out r)) {
885 pl.append (r);
886 remove_points_in_stroke (pl);
887 return;
888 }
889 }
890 }
891
892 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) {
893 bool remove = false;
894 EditPoint start_ep;
895 EditPoint start_next;
896 EditPoint start_prev;
897 EditPoint end_ep = new EditPoint ();
898 EditPoint end_next;
899 EditPoint end_prev;
900 Path path2;
901 EditPoint found = new EditPoint ();
902
903 result = new PathList ();
904
905 for (int i = 1; i < p.points.size + 1; i++) {
906 start_prev = p.points.get ((i - 1) % p.points.size);
907 start_ep = p.points.get (i % p.points.size);
908 start_next = p.points.get ((i + 1) % p.points.size);
909
910 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
911 for (int j = i; j < p.points.size + i; j++) {
912 end_prev = p.points.get ((j - 1) % p.points.size);
913 end_ep = p.points.get (j % p.points.size);
914 end_next = p.points.get ((j + 1) % p.points.size);
915
916 // FIXME: if (!is_inside_of_path
917
918 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
919 start_ep.flags = EditPoint.NONE;
920 end_ep.flags = EditPoint.NONE;
921
922 //start_ep.color = new Color (0,0,1,1);
923 //end_ep.color = new Color (0,0,1,1);
924
925 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) {
926 return true;
927 }
928 }
929 }
930 }
931
932 start_ep.flags = EditPoint.NONE;
933 end_ep.flags = EditPoint.NONE;
934 }
935
936 return false;
937 }
938
939 static bool merge_segments (PathList pl,
940 Path path1, EditPoint start1, EditPoint stop1,
941 EditPoint start2, EditPoint stop2,
942 out PathList result) {
943
944 result = new PathList ();
945
946 PathList r1;
947 PathList r2;
948
949 foreach (Path path2 in pl.paths) {
950 if (path2 != path1) {
951 reset_intersections (path1);
952 reset_intersections (path2);
953
954 if (add_merge_intersection_point (path1, path2, start1, stop1)) {
955 if (add_merge_intersection_point (path1, path2, start2, stop2)) {
956
957 r1 = get_remaining_points (path1.copy ());
958 r2 = get_remaining_points (path2.copy ());
959
960 if (r1.paths.size != 2) {
961 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n");
962 reset_intersections (path1);
963 reset_intersections (path2);
964 return true;
965 }
966
967 if (r2.paths.size != 2) {
968 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n");
969 reset_intersections (path1);
970 reset_intersections (path2);
971 return true;
972 }
973
974 pl.paths.remove (path1);
975 pl.paths.remove (path2);
976
977 // FIXME: find criteria
978
979 start1.color = new Color (1,0,0,1);
980 stop1.color = new Color (1,0,0,1);
981 start2.color = new Color (1,0,0,1);
982 stop2.color = new Color (1,0,0,1);
983
984 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (),
985 r2.paths.get (0).get_first_point ());
986
987 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (),
988 r2.paths.get (1).get_first_point ());
989
990 Path m1, m2;
991
992 if (d1 > d2) {
993 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0));
994 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1));
995 } else {
996 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0));
997 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1));
998 }
999
1000 result.add (m1);
1001 result.add (m2);
1002
1003 return true;
1004 } else {
1005 reset_intersections (path1);
1006 reset_intersections (path2);
1007 }
1008 } else {
1009 reset_intersections (path1);
1010 reset_intersections (path2);
1011 }
1012 }
1013 }
1014
1015 return false;
1016 }
1017
1018 static void reset_intersections (Path p) {
1019 foreach (EditPoint ep in p.points) {
1020 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION;
1021 ep.deleted = false;
1022 }
1023 p.remove_points_on_points ();
1024 }
1025
1026 static bool has_counter_to_outline (Path p) {
1027 foreach (EditPoint ep in p.points) {
1028 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
1029 return true;
1030 }
1031 }
1032
1033 return false;
1034 }
1035
1036 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) {
1037 double ix, iy;
1038 bool intersection;
1039
1040 intersection = false;
1041 ix = 0;
1042 iy = 0;
1043 path2.all_segments ((p1, p2) => {
1044 int i;
1045
1046 intersection = segments_intersects (first, next, p1, p2, out ix, out iy);
1047
1048 if (intersection) {
1049 add_intersection (path1, first, next, ix, iy);
1050 add_intersection (path2, p1, p2, ix, iy);
1051
1052 i = mark_intersection_as_deleted (path1);
1053 i = mark_intersection_as_deleted (path2);
1054 }
1055
1056 return !intersection;
1057 });
1058
1059 return intersection;
1060 }
1061
1062 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) {
1063 outline = new Path ();
1064 foreach (Path p in pl.paths) {
1065 if (p != ps.path) {
1066 if (SvgParser.is_inside (ps.point, p)) {
1067 outline = p;
1068 return true;
1069 }
1070 }
1071 }
1072
1073 return false;
1074 }
1075
1076 static PathList merge (PathList pl) {
1077 remove_points_in_stroke (pl);
1078
1079 PathList r = pl;
1080 foreach (Path p in pl.paths) {
1081 if (stroke_selected) { // FIXME: DELETE
1082 ((!) BirdFont.get_current_font ().get_glyph ("a")).add_path (p);
1083 }
1084 }
1085
1086 PathList result = new PathList ();
1087 PathList m;
1088
1089 foreach (Path p1 in r.paths) {
1090 foreach (Path p2 in r.paths) {
1091 if (p1 != p2) {
1092 if (p1.is_clockwise ()) { // FIXME
1093 m = merge_path (p1, p2);
1094 if (m.paths.size > 1) {
1095 result.append (m);
1096 }
1097 }
1098 }
1099 }
1100 result.add (p1);
1101 }
1102
1103 return result;
1104 }
1105
1106 static PathList merge_path (Path path1, Path path2) {
1107 EditPoint ep1, next, p1, p2, start_point;
1108 Path path, other;
1109 PathList pl1, pl2, r, other_paths;
1110 bool intersects;
1111 int s = 0;
1112 int i;
1113 double ix, iy;
1114
1115 foreach (EditPoint e in path1.points) {
1116 if (SvgParser.is_inside (e, path2)) {
1117 break;
1118 }
1119 s++;
1120 }
1121
1122 other_paths = new PathList ();
1123 r = new PathList ();
1124 path = path1;
1125 other = path2;
1126 other_paths.add (other);
1127 intersects = false;
1128 p1 = new EditPoint ();
1129 p2 = new EditPoint ();
1130 ix = 0;
1131 iy = 0;
1132 i = s;
1133 path.points.get (i % path.points.size).color = new Color (0,1,0,1);
1134 while (i < path.points.size + s) {
1135 ep1 = path.points.get (i % path.points.size);
1136 next = path.points.get ((i + 1) % path.points.size);
1137
1138 foreach (Path o in other_paths.paths) {
1139 other = o;
1140 intersects = segment_intersects (other, ep1, next, out ix, out iy,
1141 out p1, out p2, true);
1142 }
1143
1144 if (intersects) {
1145 add_intersection (path, ep1, next, ix, iy);
1146 add_intersection (other, p1, p2, ix, iy);
1147
1148 pl1 = get_remaining_points (path.copy ());
1149 pl2 = get_remaining_points (other.copy ());
1150
1151 return_val_if_fail (0 < pl1.paths.size < 3, r);
1152 return_val_if_fail (0 < pl2.paths.size < 3, r);
1153
1154 r.paths.remove (path);
1155 r.paths.remove (other);
1156
1157 path = get_next_part (pl2, path.get_last_point ());
1158 other_paths = pl1;
1159 other_paths.append (pl2);
1160 other_paths.paths.remove (path);
1161
1162 r.append (pl1);
1163 r.append (pl2);
1164
1165 i = 0;
1166 }
1167
1168 i++;
1169 }
1170
1171 return r;
1172 }
1173
1174 static Path get_next_part (PathList pl, EditPoint ep) {
1175 double d, m;
1176 Path r;
1177
1178 r = new Path ();
1179 m = double.MAX;
1180 foreach (Path p in pl.paths) {
1181 d = Path.distance_to_point (p.get_last_point (), ep);
1182 if (d < m) {
1183 m = d;
1184 r = p;
1185 }
1186 }
1187
1188 return r;
1189 }
1190
1191 public static int counters_in_point_in_path (Path p, EditPoint ep) {
1192 int inside_count = 0;
1193 bool inside;
1194
1195 if (p.points.size > 1) {
1196 inside = true;
1197
1198 if (!SvgParser.is_inside (ep, p)) {
1199 inside = false;
1200 }
1201
1202 if (inside) {
1203 inside_count++;
1204 }
1205 }
1206
1207 return inside_count;
1208 }
1209
1210 static int mark_intersection_as_deleted (Path path) {
1211 int i = 0;
1212
1213 foreach (EditPoint p in path.points) {
1214
1215 if ((p.flags & EditPoint.INTERSECTION) > 0) {
1216 p.deleted = true;
1217 i++;
1218 }
1219 }
1220
1221 return i;
1222 }
1223
1224 /** @return true if the two paths can be merged. */
1225 static bool merge_path_delete (Path path1, Path path2, out Path merged) {
1226 PathList pl1, pl2;
1227 Path p1, p2;
1228 int i;
1229
1230 merged = new Path ();
1231
1232 if (path1 == path2) {
1233 return false;
1234 }
1235
1236 if (add_intersection_points (path1, path2)) {
1237 i = mark_intersection_as_deleted (path1);
1238 return_if_fail (i == 1);
1239
1240 i = mark_intersection_as_deleted (path2);
1241 return_if_fail (i == 1);
1242
1243 pl1 = get_remaining_points (path1.copy ());
1244 pl2 = get_remaining_points (path2.copy ());
1245
1246 return_if_fail (pl1.paths.size == 1);
1247 return_if_fail (pl2.paths.size == 1);
1248
1249 p1 = pl1.paths.get (0);
1250 p2 = pl2.paths.get (0);
1251
1252 merged = PenTool.merge_open_paths (p1, p2);
1253
1254 return true;
1255 }
1256
1257 return false;
1258 }
1259
1260 /** @param n number of interrsections to find per path. */
1261 static bool add_intersection_points (Path path1, Path path2, int n = 1) {
1262 bool intersection = false;
1263 int found = 0;
1264
1265 path1.all_segments ((ep1, ep2) => {
1266 double ix, iy;
1267 EditPoint p1, p2;
1268 bool i;
1269
1270 i = segment_intersects (path2, ep1, ep2, out ix, out iy,
1271 out p1, out p2, true);
1272
1273 if (i) {
1274 add_intersection (path1, ep1, ep2, ix, iy);
1275 add_intersection (path2, p1, p2, ix, iy);
1276 intersection = true;
1277 found++;
1278 return found < n;
1279 }
1280
1281 return true;
1282 });
1283
1284 return intersection;
1285 }
1286
1287 }
1288
1289 }
1290