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 public static double stroke_width = 0;
23 public static bool add_stroke = false;
24
25 public static bool show_stroke_tools = false;
26 public static bool stroke_selected = false;
27
28 public StrokeTool (string tooltip) {
29 }
30
31 /** Create strokes for the selected outlines. */
32 public static void stroke_selected_paths () {
33 Glyph g = MainWindow.get_current_glyph ();
34 PathList paths = new PathList ();
35
36 // FIXME: use background thread
37
38 stroke_selected = true; // FIXME: delete
39
40 g.store_undo_state ();
41
42 foreach (Path p in g.active_paths) {
43 if (p.stroke > 0) {
44 paths.append (p.get_stroke ());
45 }
46 }
47
48 // FIXME: delete
49 bool h = false;
50 foreach (Path p in g.active_paths) {
51 if (p.stroke == 0) {
52 h = true;
53 }
54 }
55
56 if (h) {
57 PathList n = new PathList ();
58
59 foreach (Path p in g.active_paths) {
60 if (p.stroke == 0) {
61 n.add (p);
62 }
63 }
64
65 n = merge (n);
66 paths.append (n);
67 }
68
69 if (paths.paths.size > 0) {
70 foreach (Path p in g.active_paths) {
71 g.path_list.remove (p);
72 }
73
74 g.active_paths.clear ();
75
76 foreach (Path np in paths.paths) {
77 g.add_path (np);
78 g.active_paths.add (np);
79 }
80
81 PenTool.update_orientation ();
82
83 GlyphCanvas.redraw ();
84 }
85
86 PenTool.update_orientation ();
87 stroke_selected = false; // FIXME: delete
88 }
89
90 public static PathList get_stroke_fast (Path path, double thickness) {
91 PathList o;
92 Path stroke;
93
94 stroke = path.copy ();
95 stroke.remove_points_on_points (0.3);
96 o = create_stroke (stroke, thickness, true);
97
98 return o;
99 }
100
101 public static PathList get_stroke (Path path, double thickness) {
102 PathList o, m;
103 Path stroke;
104
105 stroke = path.copy ();
106 stroke.remove_points_on_points (0.3);
107 o = create_stroke (stroke, thickness, false);
108 o = get_all_parts (o);
109 o = merge (o);
110
111 m = new PathList ();
112 foreach (Path p in o.paths) {
113 m.add (simplify_stroke (p));
114 }
115
116 return m;
117 }
118
119 static Path simplify_stroke (Path p) {
120 Path simplified = new Path ();
121 Path segment, added_segment;
122 EditPoint ep, ep_start, last, first, segment_last;
123 int start, stop;
124 int j;
125 EditPointHandle rh;
126
127 segment_last = new EditPoint ();
128 last = new EditPoint ();
129
130 foreach (EditPoint e in p.points) {
131 PenTool.convert_point_type (e, PointType.CUBIC);
132 }
133
134 foreach (EditPoint e in p.points) {
135 if ((e.flags & EditPoint.CURVE) == 0) {
136 p.set_new_start (e);
137 break;
138 }
139 }
140
141 for (int i = 0; i < p.points.size; i++) {
142 ep = p.points.get (i);
143
144 if ((ep.flags & EditPoint.CURVE) > 0) {
145 start = i;
146 for (j = start + 1; j < p.points.size; j++) {
147 ep = p.points.get (j);
148 if ((ep.flags & EditPoint.CURVE) == 0) {
149 break;
150 }
151 }
152
153 stop = j;
154 start -= 1;
155
156 if (start < 0) {
157 warning ("start < 0");
158 start = 0;
159 }
160
161 if (stop >= p.points.size) {
162 warning ("stop >= p.points.size");
163 stop = p.points.size - 1;
164 }
165
166 ep_start = p.points.get (start);
167 ep = p.points.get (stop);
168
169 segment = fit_bezier_path (p, start, stop, 0.0007);
170
171 if (stroke_selected) { // FIXME: DELETE
172 ((!) BirdFont.get_current_font ().get_glyph ("l")).add_path (segment.copy ());
173 }
174
175 added_segment = segment.copy ();
176
177 if (simplified.points.size > 0) {
178 last = simplified.get_last_point ();
179 segment_last = added_segment.get_last_point ();
180 }
181
182 first = added_segment.get_first_point ();
183
184 segment_last.get_right_handle ().convert_to_line ();
185
186 if (simplified.points.size > 1) {
187 simplified.delete_last_point ();
188 }
189
190 last.get_right_handle ().x = first.get_right_handle ().x;
191 last.get_right_handle ().y = first.get_right_handle ().y;
192
193 first.get_left_handle ().convert_to_curve ();
194 first.get_left_handle ().x = last.get_left_handle ().x;
195 first.get_left_handle ().y = last.get_left_handle ().y;
196
197 simplified.append_path (added_segment);
198
199 last = added_segment.get_last_point ();
200 last.get_right_handle ().convert_to_line ();
201 last.recalculate_linear_handles ();
202
203 if (ep_start.get_right_handle ().is_line ()) {
204 first = added_segment.get_first_point ();
205 first.get_right_handle ().convert_to_line ();
206 first.recalculate_linear_handles ();
207 }
208
209 i = stop;
210 } else {
211 simplified.add_point (ep.copy ());
212 }
213 }
214
215 simplified.remove_points_on_points ();
216 simplified.recalculate_linear_handles ();
217 simplified.close ();
218
219 /*
220 if (p.get_first_point ().tie_handles) {
221 first = simplified.get_first_point ();
222 first.convert_to_curve ();
223 first.tie_handles = true;
224 first.process_tied_handle ();
225 }
226 */
227
228 //simplified.remove_points_on_points ();
229
230 simplified.get_last_point ().color = Color.pink ();
231 simplified.get_first_point ().color = Color.green ();
232
233 return simplified;
234 }
235
236 static Path fit_bezier_path (Path p, int start, int stop, double error) {
237 int index, size;
238 Path simplified;
239 double[] lines;
240 double[] result;
241 EditPoint ep;
242
243 simplified = new Path ();
244
245 return_val_if_fail (0 <= start < p.points.size, simplified);
246 return_val_if_fail (0 <= stop < p.points.size, simplified);
247
248 size = stop - start + 1;
249 lines = new double[2 * size];
250
251 index = 0;
252
253 for (int i = start; i <= stop; i++) {
254 ep = p.points.get (i);
255 lines[index] = ep.x;
256 index++;
257
258 lines[index] = ep.y;
259 index++;
260 }
261
262 return_val_if_fail (2 * size == index, new Path ());
263
264 Gems.fit_bezier_curve_to_line (lines, error, out result);
265
266 return_val_if_fail (!is_null (result), simplified);
267
268 for (int i = 0; i + 7 < result.length; i += 8) {
269 simplified.add_cubic_bezier_points (
270 result[i], result[i + 1],
271 result[i + 2], result[i + 3],
272 result[i + 4], result[i + 5],
273 result[i + 6], result[i + 7]);
274 }
275
276 return simplified;
277 }
278
279 static bool segment_is_line (Path p, int start, int stop) {
280 EditPoint p0, p1, p2;
281
282 if (stop - start < 2) {
283 warning ("Too small segment.");
284 return true;
285 }
286
287 for (int i = start; i <= stop - 2; i++) {
288 p0 = p.points.get (i);
289 p1 = p.points.get (i + 1);
290 p2 = p.points.get (i + 2);
291
292 if (!is_line (p0.x, p0.y, p1.x, p1.y, p2.x, p2.y)) {
293 return false;
294 }
295 }
296
297 return true;
298 }
299
300 /** Create one stroke from the outline and counter stroke and close the
301 * open endings.
302 *
303 * @param path the path to create stroke for
304 * @param stroke for the outline of path
305 * @param stroke for the counter path
306 */
307 static Path merge_strokes (Path path, Path stroke, Path counter) {
308 Path merged;
309 EditPoint last_counter, first;
310
311 merged = stroke.copy ();
312 counter.reverse ();
313
314 counter.reverse ();
315 merged.reverse ();
316
317 last_counter = new EditPoint ();
318 first = new EditPoint ();
319
320 merged.append_path (counter);
321
322 merged.close ();
323 merged.create_list ();
324 merged.recalculate_linear_handles ();
325
326 if (path.is_open ()) {
327 first = merged.get_first_point ();
328 last_counter = merged.get_last_point ();
329
330 first.get_left_handle ().convert_to_line ();
331 first.recalculate_linear_handles ();
332
333 last_counter.get_right_handle ().convert_to_line ();
334 last_counter.recalculate_linear_handles ();
335 }
336
337 return merged;
338 }
339
340 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) {
341 EditPointHandle r, l;
342 double m, n;
343 double qx, qy;
344
345 stroke_start.set_tie_handle (false);
346 stroke_stop.set_tie_handle (false);
347
348 r = stroke_start.get_right_handle ();
349 l = stroke_stop.get_left_handle ();
350
351 m = cos (r.angle + PI / 2) * thickness;
352 n = sin (r.angle + PI / 2) * thickness;
353
354 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n);
355 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n);
356
357 stroke_start.independent_x += m;
358 stroke_start.independent_y += n;
359
360 qx = cos (l.angle - PI / 2) * thickness;
361 qy = sin (l.angle - PI / 2) * thickness;
362
363 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy);
364 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy);
365
366 stroke_stop.independent_x += qx;
367 stroke_stop.independent_y += qy;
368 }
369
370 static void add_corner (Path stroked, EditPoint previous, EditPoint next,
371 EditPoint original, double stroke_width) {
372
373 double ratio;
374 double distance;
375 EditPoint corner;
376 double corner_x, corner_y;
377 EditPointHandle previous_handle;
378 EditPointHandle next_handle;
379 EditPoint cutoff1, cutoff2;
380 double adjusted_stroke = (stroke_width * 0.999999) / 2.0;
381
382 previous_handle = previous.get_left_handle ();
383 next_handle = next.get_right_handle ();
384
385 previous_handle.angle += PI;
386 next_handle.angle += PI;
387
388 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y);
389 corner = new EditPoint (corner_x, corner_y, previous.type);
390 corner.convert_to_line ();
391
392 previous_handle.angle -= PI;
393 next_handle.angle -= PI;
394
395 distance = Path.distance_to_point (corner, original);
396 ratio = 1.5 * fabs (adjusted_stroke) / distance;
397
398 if (ratio > 1) {
399 stroked.add_point (corner);
400 } else {
401
402 cutoff1 = new EditPoint ();
403 cutoff1.set_point_type (previous.type);
404 cutoff1.convert_to_line ();
405
406 cutoff2 = new EditPoint ();
407 cutoff2.set_point_type (previous.type);
408 cutoff2.convert_to_line ();
409
410 cutoff1.x = previous.x + (corner.x - previous.x) * ratio;
411 cutoff1.y = previous.y + (corner.y - previous.y) * ratio;
412
413 cutoff2.x = next.x + (corner.x - next.x) * ratio;
414 cutoff2.y = next.y + (corner.y - next.y) * ratio;
415
416 if (!cutoff1.is_valid () || cutoff2.is_valid ()) {
417 cutoff1 = stroked.add_point (cutoff1);
418 cutoff2 = stroked.add_point (cutoff2);
419 }
420
421 cutoff1.recalculate_linear_handles ();
422 cutoff2.recalculate_linear_handles ();
423
424 return_if_fail (previous.prev != null);
425
426 bool d1 = corner.x - previous.x > 0 == previous.x - previous.get_prev ().x > 0;
427 bool d2 = corner.y - previous.y > 0 == previous.y - previous.get_prev ().y > 0;
428
429 if (!d1 && !d2) {
430 cutoff1.deleted = true;
431 cutoff2.deleted = true;
432
433 stroked.remove_deleted_points ();
434 return;
435 }
436
437 if (distance > 4 * stroke_width) {
438 previous.flags = EditPoint.NONE;
439 next.flags = EditPoint.NONE;
440 } else {
441 previous.flags |= EditPoint.NEW_CORNER;
442 next.flags |= EditPoint.NEW_CORNER;
443 }
444 }
445 }
446
447 static PathList get_parts (Path path) {
448 PathList intersections;
449 PathList r;
450
451 r = get_parts_self (path);
452 intersections = new PathList ();
453
454 foreach (Path p in r.paths) {
455 intersections.add (p);
456 }
457
458 return intersections;
459 }
460
461 static bool split_corner (PathList pl) {
462 EditPoint p1, p2;
463 EditPoint a1, a2;
464 PathList result;
465 bool split;
466
467 foreach (Path p in pl.paths) {
468 if (p.points.size == 0) {
469 continue;
470 }
471
472 for (int index = 1; index < p.points.size + 2; index++) {
473 p1 = p.points.get ((index - 1) % p.points.size);
474 p2 = p.points.get (index % p.points.size);
475 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead
476 a2 = p.points.get ((index + 4) % p.points.size);
477
478 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0
479 || (p2.flags & EditPoint.STROKE_OFFSET) > 0
480 || (a1.flags & EditPoint.STROKE_OFFSET) > 0
481 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) {
482
483 split = split_segment (p, a1, a2, p1, p2, out result);
484
485 if (split) {
486 pl.append (result);
487 pl.paths.remove (p);
488 split_corner (pl);
489 return true;
490 } else {
491 p1 = p.points.get ((index - 1) % p.points.size);
492 p2 = p.points.get (index % p.points.size);
493 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead
494 a2 = p.points.get ((index + 3) % p.points.size);
495
496 split = split_segment (p, a1, a2, p1, p2, out result);
497
498 if (split) {
499 pl.append (result);
500 pl.paths.remove (p);
501 split_corner (pl);
502 return true;
503 } else {
504 p1 = p.points.get ((index - 1) % p.points.size);
505 p2 = p.points.get (index % p.points.size);
506 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead
507 a2 = p.points.get ((index + 4) % p.points.size);
508
509 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0
510 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) {
511 p1.flags = EditPoint.COUNTER_TO_OUTLINE;
512 a1.flags = EditPoint.COUNTER_TO_OUTLINE;
513 }
514 }
515 }
516 }
517 }
518 }
519
520 return false;
521 }
522
523 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) {
524 double ix, iy;
525 bool intersection;
526 int i;
527
528 result = new PathList ();
529 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true);
530
531 if (intersection) {
532 add_intersection (p, first, next, ix, iy);
533 add_intersection (p, p1, p2, ix, iy);
534
535 i = mark_intersection_as_deleted (p);
536 return_val_if_fail (i == 2, false);
537
538 result.append (get_remaining_points (p.copy ()));
539 }
540
541 return intersection;
542 }
543
544 static bool split_path (Path path1, Path path2, PathList result) {
545 PathList pl1, pl2;
546 Path a1, a2, b1, b2;
547 Path m1, m2;
548 int i;
549
550 if (path1 == path2) {
551 return false;
552 }
553
554 if (add_intersection_points (path1, path2, 2)) {
555 i = mark_intersection_as_deleted (path1);
556 return_if_fail (i == 2);
557
558 i = mark_intersection_as_deleted (path2);
559 return_if_fail (i == 2);
560
561 pl1 = get_remaining_points (path1.copy ());
562 pl2 = get_remaining_points (path2.copy ());
563
564 return_if_fail (pl1.paths.size == 2);
565 return_if_fail (pl2.paths.size == 2);
566
567 a1 = pl1.paths.get (0);
568 a2 = pl1.paths.get (1);
569 b1 = pl2.paths.get (0);
570 b2 = pl2.paths.get (1);
571
572 m1 = PenTool.merge_open_paths (a1, b2);
573 m2 = PenTool.merge_open_paths (b1, a2);
574
575 result.add (m1);
576 result.add (m2);
577
578 return true;
579 }
580
581 return false;
582 }
583
584 static PathList split_paths (PathList pl) {
585 PathList n = new PathList ();
586
587 n.append (pl);
588
589 foreach (Path p1 in pl.paths) {
590 foreach (Path p2 in pl.paths) {
591 if (p1 != p2) {
592 if (split_path (p1, p2, n)) {
593 n.paths.remove (p1);
594 n.paths.remove (p2);
595 return split_paths (n);
596 }
597 }
598 }
599 }
600
601 return n;
602 }
603
604 static PathList get_parts_self (Path path, PathList? paths = null) {
605 PathList pl;
606 PathList r;
607
608 r = paths == null ? new PathList () : (!) paths;
609 pl = split (path);
610
611 foreach (Path part in pl.paths) {
612 if (!has_self_intersection (part)) {
613 r.add (part);
614 } else {
615 get_parts_self (part, r);
616 }
617 }
618
619 if (r.paths.size == 0) {
620 warning ("No parts in path");
621 }
622
623 return r;
624 }
625
626
627 static bool has_intersection_points (Path path) {
628 foreach (EditPoint p in path.points) {
629 if ((p.flags & EditPoint.INTERSECTION) > 0) {
630 return true;
631 }
632 }
633 return false;
634 }
635
636 /** Split one path at intersection points in two parts. */
637 static PathList split (Path path) {
638 Path new_path;
639 PathList pl;
640 int i;
641
642 if (!has_intersection_points (path)) {
643 add_self_intersection_points (path);
644 } else {
645 warning ("points already created.");
646 }
647
648 foreach (EditPoint p in path.points) {
649 if (insides (p, path) == 1) {
650 path.set_new_start (p);
651 path.close ();
652 break;
653 }
654 }
655
656 i = mark_intersection_as_deleted (path);
657
658 if (!(i == 0 || i == 2)) {
659 warning (@"Split should only create two parts, $i points will be deleted.");
660 }
661
662 new_path = path.copy ();
663 pl = get_remaining_points (new_path);
664
665 return pl;
666 }
667
668 static PathList process_deleted_control_points (Path path) {
669 PathList paths, nl, pl, rl, result;
670
671 paths = new PathList ();
672 rl = new PathList ();
673 pl = new PathList ();
674 nl = new PathList ();
675
676 if (!path.has_deleted_point ()) {
677 return pl;
678 }
679
680 pl.add (path);
681
682 foreach (Path p in pl.paths) {
683 nl = p.process_deleted_points ();
684
685 if (nl.paths.size > 0) {
686 rl.append (nl);
687 rl.paths.remove (p);
688 }
689 }
690
691 result = new PathList ();
692 foreach (Path p in rl.paths) {
693 pl = process_deleted_control_points (p);
694
695 if (pl.paths.size > 0) {
696 result.append (pl);
697 } else {
698 result.add (p);
699 }
700 }
701
702 for (int i = 1; i < result.paths.size; i++) {
703 result.paths.get (i).reverse ();
704 }
705
706 paths.append (result);
707
708 return paths;
709 }
710
711 static PathList get_remaining_points (Path old_path) {
712 PathList pl;
713
714 old_path.close ();
715 pl = process_deleted_control_points (old_path);
716
717 if (pl.paths.size == 0) {
718 pl.add (old_path);
719 }
720
721 foreach (Path pn in pl.paths) {
722 pn.close ();
723 }
724
725 return pl;
726 }
727
728 static bool has_self_intersection (Path path) {
729 bool intersection = false;
730
731 path.all_segments ((ep1, ep2) => {
732 double ix, iy;
733 EditPoint p1, p2;
734
735 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true)) {
736 intersection = true;
737 return false;
738 }
739
740 return true;
741 });
742
743 return intersection;
744 }
745
746 static bool add_self_intersection_points (Path path, bool only_offsets = false) {
747 bool intersection = false;
748
749 path.all_segments ((ep1, ep2) => {
750 double ix, iy;
751 EditPoint p1, p2;
752
753 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) {
754 add_intersection (path, ep1, ep2, ix, iy);
755 add_intersection (path, p1, p2, ix, iy);
756
757 intersection = true;
758 return false;
759 }
760
761 return true;
762 });
763
764 return intersection;
765 }
766
767 static EditPoint add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) {
768 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> ();
769 EditPoint ep1 = new EditPoint ();
770 EditPoint ep2 = new EditPoint ();
771 EditPoint ep3 = new EditPoint ();
772 double d;
773
774 if (next == path.get_first_point ()) {
775 ep1.prev = null;
776 } else {
777 ep1.prev = prev;
778 }
779
780 ep1.prev = prev;
781 ep1.next = ep2;
782 ep1.flags |= EditPoint.NEW_CORNER;
783 ep1.type = prev.type;
784 ep1.x = px;
785 ep1.y = py;
786 ep1.color = c;
787 n.add (ep1);
788
789 ep2.prev = ep1;
790 ep2.next = ep3;
791 ep2.flags |= EditPoint.INTERSECTION;
792 ep2.type = prev.type;
793 ep2.x = px;
794 ep2.y = py;
795 ep2.color = c;
796 n.add (ep2);
797
798 ep3.prev = ep2;
799 ep3.next = next;
800 ep3.flags |= EditPoint.NEW_CORNER;
801 ep3.type = prev.type;
802 ep3.x = px;
803 ep3.y = py;
804 ep3.color = c;
805 n.add (ep3);
806
807 next.get_left_handle ().convert_to_line ();
808
809 foreach (EditPoint np in n) {
810 np = path.add_point_after (np, np.prev);
811 path.create_list ();
812 }
813
814 PenTool.convert_point_to_line (ep1, true);
815 PenTool.convert_point_to_line (ep2, true);
816 PenTool.convert_point_to_line (ep3, true);
817
818 ep1.recalculate_linear_handles ();
819 ep2.recalculate_linear_handles ();
820 ep3.recalculate_linear_handles ();
821
822 d = Path.distance_to_point (prev, next);
823 prev.get_right_handle ().length *= Path.distance_to_point (prev, ep1) / d;
824 next.get_left_handle ().length *= Path.distance_to_point (ep3, next) / d;
825
826 prev.color = Color.green ();
827 next.color = Color.blue ();
828
829 next.recalculate_linear_handles ();
830
831 return ep2;
832 }
833
834 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next,
835 out double ix, out double iy,
836 bool skip_points_on_points = false) {
837 double cross_x, cross_y;
838
839 ix = 0;
840 iy = 0;
841
842 if (is_line (ep.x, ep.y, p1.x, p1.y, next.x, next.y)) {
843 ix = p1.x;
844 iy = p1.y;
845 return true;
846 }
847
848 if (is_line (ep.x, ep.y, p2.x, p2.y, next.x, next.y)) {
849 ix = p2.x;
850 iy = p2.y;
851 return true;
852 }
853
854 if (is_line (p1.x, p1.y, ep.x, ep.y, p2.x, p2.y)) {
855 ix = ep.x;
856 iy = ep.y;
857 return true;
858 }
859
860 if (is_line (p1.x, p1.y, next.x, next.y, p2.x, p2.y)) {
861 ix = next.x;
862 iy = next.y;
863 return true;
864 }
865
866 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y);
867
868 if (Glyph.CANVAS_MIN < cross_x < Glyph.CANVAS_MAX
869 && Glyph.CANVAS_MIN < cross_y < Glyph.CANVAS_MAX) {
870 // iterate to find intersection.
871 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y)
872 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) {
873
874 ix = cross_x;
875 iy = cross_y;
876
877 return true;
878 }
879 }
880
881 return false;
882 }
883
884 static bool segment_intersects (Path path, EditPoint ep, EditPoint next,
885 out double ix, out double iy,
886 out EditPoint ia, out EditPoint ib,
887 bool skip_points_on_points = false,
888 bool only_offsets = false) {
889
890 EditPoint p1, p2;
891 bool intersection, inter;
892 double iix, iiy;
893
894 double distance, min_distance;
895
896 intersection = false;
897
898 ix = 0;
899 iy = 0;
900
901 iix = 0;
902 iiy = 0;
903
904 ia = new EditPoint ();
905 ib = new EditPoint ();
906
907 if (path.points.size == 0) {
908 return false;
909 }
910
911 min_distance = double.MAX;
912 p1 = path.points.get (path.points.size - 1);
913 for (int i = 0; i < path.points.size; i++) {
914 p2 = path.points.get (i);
915
916 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0)
917 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0)
918 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0)
919 && ((next.flags & EditPoint.STROKE_OFFSET) > 0);
920
921 if (!only_offsets || is_offset) {
922 if (p1 != ep && p2 != next) {
923 inter = segments_intersects (p1, p2, ep, next, out iix, out iiy,
924 skip_points_on_points);
925
926 if (inter) {
927 distance = Path.distance (ep.x, iix, ep.y, iiy);
928 if (distance < min_distance) {
929 ia = p1;
930 ib = p2;
931 ix = iix;
932 iy = iiy;
933 intersection = true;
934 min_distance = distance;
935 }
936 }
937 }
938 }
939
940 p1 = p2;
941 }
942
943 return intersection;
944 }
945
946 /** @return true if p2 is on the line p1 to p3 */
947 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.01) {
948 return fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3)
949 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3)
950 && is_flat (x1, y1, x2, y2, x3, y3, tolerance);
951 }
952
953 public static bool is_flat (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.001) {
954 double ds = Path.distance (x1, x3, y1, y3);
955 double d1 = Path.distance (x1, x2, y1, y2);
956 double d2 = Path.distance (x2, x3, y2, y3);
957 double p = d1 / ds;
958 double x = fabs ((x3 - x1) * p - (x2 - x1));
959 double y = fabs ((y3 - y1) * p - (y2 - y1));
960 double d = fabs (ds - (d1 + d2));
961
962 return ds > 0.001 && d1 > 0.001 && d2 > 0.001
963 && d < tolerance && x < tolerance && y < tolerance;
964 }
965
966 // indside becomes outside in some paths
967 static void remove_points_in_stroke (PathList pl) {
968 PathList r;
969
970 foreach (Path p in pl.paths) {
971 if (remove_points_in_stroke_for_path (p, pl, out r)) {
972 pl.append (r);
973 remove_points_in_stroke (pl);
974 return;
975 }
976 }
977 }
978
979 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) {
980 EditPoint start_ep;
981 EditPoint start_next;
982 EditPoint start_prev;
983 EditPoint end_ep = new EditPoint ();
984 EditPoint end_next;
985 EditPoint end_prev;
986
987 result = new PathList ();
988
989 for (int i = 1; i < p.points.size + 1; i++) {
990 start_prev = p.points.get ((i - 1) % p.points.size);
991 start_ep = p.points.get (i % p.points.size);
992 start_next = p.points.get ((i + 1) % p.points.size);
993
994 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
995 for (int j = i; j < p.points.size + i; j++) {
996 end_prev = p.points.get ((j - 1) % p.points.size);
997 end_ep = p.points.get (j % p.points.size);
998 end_next = p.points.get ((j + 1) % p.points.size);
999
1000
1001 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) {
1002 start_ep.flags = EditPoint.NONE;
1003 end_ep.flags = EditPoint.NONE;
1004
1005 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) {
1006 return true;
1007 }
1008 }
1009 }
1010 }
1011
1012 start_ep.flags = EditPoint.NONE;
1013 end_ep.flags = EditPoint.NONE;
1014 }
1015
1016 return false;
1017 }
1018
1019 static bool merge_segments (PathList pl,
1020 Path path1, EditPoint start1, EditPoint stop1,
1021 EditPoint start2, EditPoint stop2,
1022 out PathList result) {
1023
1024 result = new PathList ();
1025
1026 PathList r1;
1027 PathList r2;
1028
1029 foreach (Path path2 in pl.paths) {
1030 if (path2 != path1) {
1031 reset_intersections (path1);
1032 reset_intersections (path2);
1033
1034 if (add_merge_intersection_point (path1, path2, start1, stop1)) {
1035 if (add_merge_intersection_point (path1, path2, start2, stop2)) {
1036
1037 r1 = get_remaining_points (path1.copy ());
1038 r2 = get_remaining_points (path2.copy ());
1039
1040 if (r1.paths.size != 2) {
1041 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n");
1042 reset_intersections (path1);
1043 reset_intersections (path2);
1044 return true;
1045 }
1046
1047 if (r2.paths.size != 2) {
1048 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n");
1049 reset_intersections (path1);
1050 reset_intersections (path2);
1051 return true;
1052 }
1053
1054 pl.paths.remove (path1);
1055 pl.paths.remove (path2);
1056
1057 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (),
1058 r2.paths.get (0).get_first_point ());
1059
1060 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (),
1061 r2.paths.get (1).get_first_point ());
1062
1063 Path m1, m2;
1064
1065 if (d1 > d2) {
1066 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0));
1067 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1));
1068 } else {
1069 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0));
1070 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1));
1071 }
1072
1073 result.add (m1);
1074 result.add (m2);
1075
1076 return true;
1077 } else {
1078 reset_intersections (path1);
1079 reset_intersections (path2);
1080 }
1081 } else {
1082 reset_intersections (path1);
1083 reset_intersections (path2);
1084 }
1085 }
1086 }
1087
1088 return false;
1089 }
1090
1091 static void reset_intersections (Path p) {
1092 foreach (EditPoint ep in p.points) {
1093 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION;
1094 ep.flags &= uint.MAX ^ EditPoint.COPIED;
1095 ep.deleted = false;
1096 }
1097 p.remove_points_on_points ();
1098 }
1099
1100 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) {
1101 double ix, iy;
1102 bool intersection;
1103
1104 intersection = false;
1105 ix = 0;
1106 iy = 0;
1107 path2.all_segments ((p1, p2) => {
1108 int i;
1109
1110 intersection = segments_intersects (first, next, p1, p2, out ix, out iy);
1111
1112 if (intersection) {
1113 add_intersection (path1, first, next, ix, iy);
1114 add_intersection (path2, p1, p2, ix, iy);
1115
1116 i = mark_intersection_as_deleted (path1);
1117 i = mark_intersection_as_deleted (path2);
1118 }
1119
1120 return !intersection;
1121 });
1122
1123 return intersection;
1124 }
1125
1126 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) {
1127 outline = new Path ();
1128 foreach (Path p in pl.paths) {
1129 if (p != ps.path) {
1130 if (is_inside (ps.point, p)) {
1131 outline = p;
1132 return true;
1133 }
1134 }
1135 }
1136
1137 return false;
1138 }
1139
1140 static PathList get_all_parts (PathList pl) {
1141 PathList m;
1142 bool intersects = false;
1143 PathList r = new PathList ();
1144
1145 foreach (Path p in pl.paths) {
1146 if (has_self_intersection (p)) {
1147 m = get_parts (p);
1148 r.append (m);
1149 intersects = true;
1150 } else {
1151 r.add (p);
1152 }
1153 }
1154
1155 foreach (Path p in r.paths) {
1156 p.close ();
1157 p.update_region_boundaries ();
1158 }
1159
1160 if (intersects) {
1161 return get_all_parts (r);
1162 }
1163
1164 return r;
1165 }
1166
1167 static PathList merge (PathList pl) {
1168 bool error = false;
1169 PathList m;
1170 PathList r = pl;
1171 Path p1, p2;
1172
1173 r = get_all_parts (r);
1174
1175 while (paths_has_intersection (r, out p1, out p2)) {
1176 if (merge_path (p1, p2, out m, out error)) {
1177 r.paths.remove (p1);
1178 r.paths.remove (p2);
1179
1180 foreach (Path np in m.paths) {
1181 np.remove_points_on_points ();
1182 r.add (np);
1183 }
1184
1185 r = get_all_parts (r);
1186 } else {
1187 warning ("Not merged.");
1188 }
1189
1190 if (error) {
1191 warning ("Merge error");
1192 break;
1193 }
1194 }
1195
1196 if (!error) {
1197 remove_merged_parts (r);
1198 }
1199
1200 foreach (Path p in r.paths) {
1201 p.close ();
1202 p.recalculate_linear_handles ();
1203 }
1204
1205 return r;
1206 }
1207
1208 static bool has_zero_area_segment (Path p) {
1209 EditPointHandle l, r;
1210
1211 p.recalculate_linear_handles ();
1212
1213 foreach (EditPoint ep in p.points) {
1214 l = ep.get_left_handle ();
1215 r = ep.get_right_handle ();
1216
1217 if (l.length < 0.01 || r.length < 0.01) {
1218 continue;
1219 }
1220
1221 if (!(fabs ((l.angle - r.angle + PI) % 2 * PI) < 0.0001)
1222 && !(fabs (l.angle - r.angle) < 0.0001)) {
1223 return false;
1224 }
1225 }
1226 return true;
1227 }
1228
1229 static void remove_merged_parts (PathList r) {
1230 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> ();
1231 int c;
1232
1233 foreach (Path p in r.paths) {
1234 p.update_region_boundaries ();
1235 }
1236
1237 foreach (Path p in r.paths) {
1238 c = counters (r, p);
1239
1240 if (has_zero_area_segment (p)) {
1241 //FIXME: remove.add (p);
1242 }
1243
1244 if (c % 2 == 0) {
1245
1246 if (!p.is_clockwise ()) {
1247 remove.add (p);
1248 }
1249
1250 if (stroke_selected)
1251 ((!) BirdFont.get_current_font ().get_glyph ("m")).add_path (p);
1252
1253 } else {
1254 if (stroke_selected)
1255 ((!) BirdFont.get_current_font ().get_glyph ("n")).add_path (p);
1256
1257 if (p.is_clockwise ()) {
1258 remove.add (p);
1259 }
1260 }
1261 }
1262
1263 if (stroke_selected) { // FIXME: DELETE
1264 foreach (Path mm in r.paths)
1265 ((!) BirdFont.get_current_font ().get_glyph ("i")).add_path (mm);
1266 }
1267
1268 foreach (Path p in remove) {
1269 r.paths.remove (p);
1270 }
1271
1272 if (stroke_selected) { // FIXME: DELETE
1273 foreach (Path mm in r.paths)
1274 ((!) BirdFont.get_current_font ().get_glyph ("j")).add_path (mm);
1275 }
1276 }
1277
1278 public static int counters (PathList pl, Path path) {
1279 int inside_count = 0;
1280 bool inside;
1281
1282 foreach (Path p in pl.paths) {
1283 inside = true;
1284
1285 if (p.points.size > 1
1286 && p != path
1287 && path.boundaries_intersecting (p)) {
1288
1289 // FIXME: all points can be corners in counter paths
1290 foreach (EditPoint ep in path.points) {
1291 if (!is_inside (ep, p)) {
1292 inside = false;
1293 }
1294 }
1295
1296 if (inside) {
1297 inside_count++;
1298 }
1299 }
1300 }
1301
1302 return inside_count;
1303 }
1304
1305 public static bool is_inside (EditPoint point, Path path) {
1306 EditPoint prev;
1307 bool inside = false;
1308
1309 if (path.points.size <= 1) {
1310 return false;
1311 }
1312
1313 prev = path.points.get (path.points.size - 1);
1314
1315 foreach (EditPoint p in path.points) {
1316 if ((p.x == point.x && p.y == point.y) || (prev.x == point.x && prev.y == point.y)) {
1317 return true;
1318 } else if ((p.y > point.y) != (prev.y > point.y)
1319 && point.x < (prev.x - p.x) * (point.y - p.y) / (prev.y - p.y) + p.x) {
1320 inside = !inside;
1321 }
1322
1323 prev = p;
1324 }
1325
1326 return inside;
1327 }
1328
1329 public static int insides (EditPoint point, Path path) {
1330 EditPoint prev;
1331 int inside = 0;
1332
1333 if (path.points.size <= 1) {
1334 return 0;
1335 }
1336
1337 prev = path.get_last_point ();
1338
1339 foreach (EditPoint start in path.points) {
1340 if (start.x == point.x && point.y == start.y) {
1341 inside++;
1342 } else if ((start.y > point.y) != (prev.y > point.y)
1343 && point.x < (prev.x - start.x) * (point.y - start.y) / (prev.y - start.y) + start.x) {
1344 inside++;
1345 }
1346
1347 prev = start;
1348 }
1349
1350 return inside;
1351 }
1352
1353 static bool merge_path (Path path1, Path path2, out PathList merged_paths, out bool error) {
1354 IntersectionList intersections;
1355 EditPoint ep1, next, p1, p2, pp1, pp2;
1356 Path path, other, merged;
1357 PathList r, other_paths, result;
1358 bool intersects;
1359 int s, i;
1360 double ix, iy, iix, iiy;
1361 bool merge = false;
1362 EditPoint intersection_point, other_intersection_point;
1363 bool path1_direction, path2_direction;
1364
1365 error = false;
1366 merged_paths = new PathList ();
1367 intersections = new IntersectionList ();
1368
1369 reset_intersections (path1);
1370 reset_intersections (path2);
1371
1372 iix = 0;
1373 iiy = 0;
1374
1375 result = new PathList ();
1376
1377 if (path1.points.size == 0 || path2.points.size == 0) {
1378 warning ("No points in path.");
1379 error = true;
1380 return false;
1381 }
1382
1383 if (!path1.boundaries_intersecting (path2)) {
1384 return false;
1385 }
1386
1387 Path original_path1 = path1.copy ();
1388 Path original_path2 = path2.copy ();
1389
1390 s = 0;
1391 foreach (EditPoint e in original_path1.points) {
1392 if (!is_inside (e, original_path2)
1393 && insides (e, original_path1) == 1) { // FIXME: later as well
1394 break;
1395 }
1396 s++;
1397 }
1398
1399 if (s >= path1.points.size) {
1400 Path t;
1401 t = original_path1;
1402 original_path1 = original_path2;
1403 original_path2 = t;
1404 s = 0;
1405 foreach (EditPoint e in original_path1.points) {
1406 if (!is_inside (e, original_path2)) {
1407 break;
1408 }
1409 s++;
1410 }
1411 }
1412
1413 if (s >= original_path1.points.size) {
1414 warning ("No start point found.");
1415 error = true;
1416 return false;
1417 }
1418
1419 path = original_path1;
1420 other = original_path2;
1421
1422 other_paths = new PathList ();
1423 r = new PathList ();
1424 other_paths.add (path);
1425 other_paths.add (other);
1426 intersects = false;
1427 p1 = new EditPoint ();
1428 p2 = new EditPoint ();
1429 pp1 = new EditPoint ();
1430 pp2 = new EditPoint ();
1431
1432 ix = 0;
1433 iy = 0;
1434 i = s;
1435 merged = new Path ();
1436
1437 path1_direction = is_clockwise (original_path1);
1438 path2_direction = is_clockwise (original_path1);
1439
1440 while (true) {
1441 ep1 = path.points.get (i % path.points.size);
1442 next = path.points.get ((i + 1) % path.points.size);
1443
1444 if ((ep1.flags & EditPoint.COPIED) > 0) {
1445 if (merge) {
1446 merged.close ();
1447 result.add (merged.copy ());
1448 }
1449
1450 merged = new Path ();
1451
1452 bool find_parts = false;
1453 Intersection new_start = new Intersection.empty ();
1454 foreach (Intersection inter in intersections.points) {
1455 if (!inter.done && !find_parts) {
1456 find_parts = true;
1457 new_start = inter;
1458 break;
1459 }
1460 }
1461
1462 if (!find_parts) {
1463 break; // done, no more parts to merge
1464 } else {
1465 // set start point for next part
1466 path = new_start.other_path;
1467
1468 if (path.points.size == 0) {
1469 warning ("No points.");
1470 error = true;
1471 return false;
1472 }
1473
1474 i = index_of (path, new_start.get_point (path));
1475
1476 if (i < 0) {
1477 warning ("Start point not found.");
1478 error = true;
1479 return false;
1480 }
1481
1482 ep1 = path.points.get (i % path.points.size);
1483 next = path.points.get ((i + 1) % path.points.size);
1484
1485 if ((ep1.flags & EditPoint.INTERSECTION) == 0) {
1486 warning ("Not starting on an intersection point.");
1487 error = true;
1488 return false;
1489 }
1490
1491 new_start.done = true;
1492 }
1493 }
1494
1495 intersects = false;
1496
1497 double dm;
1498 double d;
1499
1500 if ((ep1.flags & EditPoint.INTERSECTION) > 0) {
1501 Intersection current_intersection;
1502 bool continue_on_other_path;
1503 current_intersection = intersections.get_point (ep1, out continue_on_other_path);
1504 current_intersection.done = true;
1505
1506 // take the other part of an intersection
1507 if ((next.flags & EditPoint.COPIED) != 0) {
1508 bool next_is_intersection = false;
1509 bool next_continue_on_other_path;
1510
1511 next_is_intersection = ((next.flags & EditPoint.INTERSECTION) > 0);
1512
1513 if (next_is_intersection) {
1514 Intersection next_intersection = intersections.get_point (next, out next_continue_on_other_path);
1515
1516 ep1.flags |= EditPoint.COPIED;
1517 merged.add_point (ep1.copy ());
1518
1519 if (!next_intersection.done) {
1520 EditPoint new_start_point;
1521
1522 path = next_continue_on_other_path
1523 ? next_intersection.other_path : next_intersection.path;
1524
1525 new_start_point = next_continue_on_other_path
1526 ? next_intersection.other_point : next_intersection.point;
1527
1528 i = index_of (path, new_start_point);
1529
1530 if (i < 0) {
1531 warning ("Point not found in path.\n");
1532 error = true;
1533 return false;
1534 }
1535
1536 ep1 = path.points.get (i % path.points.size);
1537 next = path.points.get ((i + 1) % path.points.size);
1538 } else {
1539 warning ("Part is already created.\n");
1540 error = true;
1541 return false;
1542 }
1543 } else {
1544 ep1.flags |= EditPoint.COPIED;
1545 merged.add_point (ep1.copy ());
1546
1547 EditPoint new_start_point;
1548
1549 if ((next.flags & EditPoint.COPIED) > 0) {
1550 path = current_intersection.get_other_path (path);
1551 new_start_point = current_intersection.get_point (path);
1552 i = index_of (path, new_start_point);
1553
1554 if (i < 0) {
1555 warning ("Point not found in path.");
1556 error = true;
1557 return false;
1558 }
1559
1560 ep1 = path.points.get (i % path.points.size);
1561 next = path.points.get ((i + 1) % path.points.size);
1562
1563 if ((next.flags & EditPoint.INTERSECTION) > 0) {
1564 warning ("Wrong type.");
1565 error = true;
1566 return false;
1567 }
1568
1569 if ((next.flags & EditPoint.COPIED) > 0) {
1570 merged.add_point (ep1.copy ());
1571 continue;
1572 }
1573 } else {
1574 ep1.flags |= EditPoint.COPIED;
1575 merged.add_point (ep1.copy ());
1576 }
1577 }
1578 } else {
1579 ep1.flags |= EditPoint.COPIED;
1580
1581 if (path1_direction == path2_direction) {
1582 if (!is_inside (ep1, original_path1)) {
1583 merged.add_point (ep1.copy ());
1584 }
1585 } else {
1586 merged.add_point (ep1.copy ());
1587 }
1588 }
1589
1590 current_intersection.done = true;
1591 } else {
1592 // find new intersection
1593 dm = double.MAX;
1594 foreach (Path o in other_paths.paths) {
1595 bool inter = segment_intersects (o, ep1, next, out iix, out iiy,
1596 out pp1, out pp2);
1597 d = Path.distance (ep1.x, iix, ep1.y, iiy);
1598 if (d < dm && inter) {
1599 other = o;
1600 dm = d;
1601 intersects = true;
1602 p1 = pp1;
1603 p2 = pp2;
1604 ix = iix;
1605 iy = iiy;
1606 }
1607
1608 if (d < 0.0001) {
1609 intersects = false;
1610 }
1611 }
1612
1613 if (intersects) {
1614 merged.add_point (ep1.copy ());
1615 ep1.flags |= EditPoint.COPIED;
1616
1617 intersection_point = add_intersection (path, ep1, next, ix, iy);
1618 other_intersection_point = add_intersection (other, p1, p2, ix, iy);
1619
1620 bool g = false;
1621 foreach (Intersection old_intersection in intersections.points) {
1622 if (old_intersection.point == intersection_point
1623 || old_intersection.other_point == other_intersection_point) {
1624 old_intersection.done = true;
1625 g = true;
1626 }
1627 }
1628
1629 if (!g) {
1630 Intersection ip = new Intersection (intersection_point, path, other_intersection_point, other);
1631 intersections.points.add (ip);
1632 }
1633
1634 merged.add_point (intersection_point.copy ());
1635 intersection_point.flags |= EditPoint.COPIED;
1636
1637 i = index_of (other, other_intersection_point);
1638
1639 if (i < 0) {
1640 warning (@"Point not found ($i).");
1641 break;
1642 }
1643
1644 path = other;
1645 merge = true;
1646 } else {
1647 ep1.flags |= EditPoint.COPIED;
1648 merged.add_point (ep1.copy ());
1649
1650 PointSelection ps;
1651 Path outline;
1652
1653 // remove points inside of path
1654 if (is_clockwise (original_path2)) {
1655 ps = new PointSelection (ep1, merged);
1656 if (is_inside_of_path (ps, result, out outline)) {
1657 ep1.deleted = true;
1658 ep1.color = Color.red ();
1659 }
1660 }
1661 }
1662 }
1663
1664 i++;
1665 }
1666
1667 if (merge) {
1668 original_path1.remove_points_on_points ();
1669 original_path2.remove_points_on_points ();
1670 original_path1.remove_deleted_points ();
1671 original_path2.remove_deleted_points ();
1672
1673 foreach (Path np in result.paths) {
1674 Path p = np.copy ();
1675 bool has_direction = true;
1676
1677 p.remove_points_on_points ();
1678
1679 if (has_direction) {
1680 p.close ();
1681 reset_intersections (p);
1682 merged_paths.append (get_parts (p));
1683 p.update_region_boundaries ();
1684 p.recalculate_linear_handles ();
1685 }
1686 }
1687 }
1688
1689 return merge && !error;
1690 }
1691
1692 static int index_of (Path p, EditPoint ep) {
1693 int i = 0;
1694 foreach (EditPoint e in p.points) {
1695 if (e == ep) {
1696 return i;
1697 }
1698 i++;
1699 }
1700
1701 return -1;
1702 }
1703
1704 public static int counters_in_point_in_path (Path p, EditPoint ep) {
1705 int inside_count = 0;
1706 bool inside;
1707
1708 if (p.points.size > 1) {
1709 inside = true;
1710
1711 if (!is_inside (ep, p)) {
1712 inside = false;
1713 }
1714
1715 if (inside) {
1716 inside_count++;
1717 }
1718 }
1719
1720 return inside_count;
1721 }
1722
1723 static int mark_intersection_as_deleted (Path path) {
1724 int i = 0;
1725
1726 foreach (EditPoint p in path.points) {
1727 if ((p.flags & EditPoint.INTERSECTION) > 0) {
1728 p.deleted = true;
1729 i++;
1730 }
1731 }
1732
1733 return i;
1734 }
1735
1736 /** @param n number of interrsections to find per path. */
1737 static bool add_intersection_points (Path path1, Path path2, int n = 1) {
1738 bool intersection = false;
1739 int found = 0;
1740
1741 path1.all_segments ((ep1, ep2) => {
1742 double ix, iy;
1743 EditPoint p1, p2;
1744 bool i;
1745
1746 i = segment_intersects (path2, ep1, ep2, out ix, out iy,
1747 out p1, out p2, true);
1748
1749 if (i) {
1750 add_intersection (path1, ep1, ep2, ix, iy);
1751 add_intersection (path2, p1, p2, ix, iy);
1752 intersection = true;
1753 found++;
1754 return found < n;
1755 }
1756
1757 return true;
1758 });
1759
1760 return intersection;
1761 }
1762
1763 /** @param n number of interrsections to find per path. */
1764 static bool has_intersection (Path path1, Path path2) {
1765 bool intersection = false;
1766
1767 if (!path1.boundaries_intersecting (path2)) {
1768 return false;
1769 }
1770
1771 path1.all_segments ((ep1, ep2) => {
1772 double ix, iy;
1773 EditPoint p1, p2;
1774 bool i;
1775
1776 i = segment_intersects (path2, ep1, ep2, out ix, out iy,
1777 out p1, out p2, true);
1778
1779 if (i) {
1780 intersection = true;
1781 }
1782
1783 return !intersection;
1784 });
1785
1786 return intersection;
1787 }
1788
1789 static bool paths_has_intersection (PathList r, out Path path1, out Path path2) {
1790 int i, j;
1791 path1 = new Path ();
1792 path2 = new Path ();
1793
1794 i = 0;
1795 foreach (Path p1 in r.paths) {
1796
1797 j = 0;
1798 foreach (Path p2 in r.paths) {
1799 if (p1 != p2) {
1800 if (has_intersection (p1, p2)) {
1801 path1 = p1;
1802 path2 = p2;
1803 return true;
1804 }
1805 }
1806 j++;
1807 }
1808 i++;
1809 }
1810 return false;
1811 }
1812
1813 public static bool has_points_outside (PathList pl, Path p) {
1814 if (pl.paths.size != 2) {
1815 warning ("Stroke should only create two parts.");
1816 return false;
1817 }
1818
1819 foreach (Path path in pl.paths) {
1820 if (path != p) {
1821 foreach (EditPoint ep in p.points) {
1822 if (!is_inside (ep, path)) {
1823 return true;
1824 }
1825 }
1826 }
1827 }
1828
1829 return false;
1830 }
1831
1832 static bool is_clockwise (Path p) {
1833 double sum = 0;
1834 EditPoint p1, p2;
1835
1836 EditPointHandle l, r;
1837
1838 p.recalculate_linear_handles ();
1839
1840 if (p.points.size < 3) {
1841 return true;
1842 }
1843
1844 for (int i = 0; i < p.points.size; i++) {
1845 p1 = p.points.get (i);
1846 p2 = p.points.get ((i + 1) % p.points.size);
1847
1848 l = p1.get_left_handle ();
1849 r = p1.get_right_handle ();
1850 if (!(fabs (l.angle - r.angle) < 0.0001 && l.length > 0.01 && r.length > 0.01)) {
1851 sum += (p2.x - p1.x) * (p2.y + p1.y);
1852 }
1853 }
1854
1855 return sum > 0;
1856 }
1857
1858 public static PathList create_stroke (Path original_path,
1859 double thickness, bool fast) {
1860
1861 PathList pl;
1862 EditPoint p1, p2, p3;
1863 EditPoint previous, previous_inside, start, start_inside;
1864
1865 Path side1, side2;
1866
1867 double x, y, x2, y2, x3, y3;
1868 int size;
1869 bool flat, f_next, f_bigger;
1870 int i;
1871
1872 double tolerance;
1873 double step_increment;
1874 double step_size;
1875 EditPoint corner1, corner1_inside;
1876 double step;
1877 double min_increment;
1878
1879 EditPointHandle l, r;
1880
1881 Path path = original_path.copy ();
1882
1883 int keep;
1884 bool on_curve;
1885
1886 pl = new PathList ();
1887 size = path.is_open () ? path.points.size - 1 : path.points.size;
1888
1889 side1 = new Path ();
1890 side2 = new Path ();
1891
1892 if (path.points.size < 2) {
1893 return pl;
1894 }
1895
1896 previous = new EditPoint ();
1897 previous_inside = new EditPoint ();
1898 corner1 = new EditPoint ();
1899 corner1_inside = new EditPoint ();
1900
1901 if (path.is_open () || fast) {
1902 p1 = path.points.get (0);
1903 p2 = path.points.get (1 % path.points.size);
1904
1905 get_segment (thickness, 0, 0.00001, p1, p2, out start);
1906 get_segment (-thickness, 0, 0.00001, p1, p2, out start_inside);
1907
1908 previous = start.copy ();
1909 previous_inside = start_inside.copy ();
1910
1911 previous.flags |= EditPoint.CURVE;
1912 previous_inside.flags |= EditPoint.CURVE;
1913
1914 side1.add_point (previous);
1915 side2.add_point (previous_inside);
1916 }
1917
1918 min_increment = 0.013;
1919
1920 for (i = 0; i < size; i++) {
1921 p1 = path.points.get (i % path.points.size);
1922 p2 = path.points.get ((i + 1) % path.points.size);
1923 p3 = path.points.get ((i + 2) % path.points.size);
1924
1925 tolerance = 0.13 / sqrt (stroke_width);
1926 step_increment = 1.05;
1927 step_size = 0.039 / stroke_width;
1928
1929 corner1 = new EditPoint ();
1930
1931 if (p1.type == PointType.HIDDEN
1932 || p2.type == PointType.HIDDEN) {
1933 continue;
1934 }
1935
1936 step = 0;
1937 keep = 0;
1938 step_size = 0.1;
1939
1940 while (step < 1 - 2 * step_size) {
1941 Path.get_point_for_step (p1, p2, step, out x, out y);
1942 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2);
1943 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3);
1944
1945 flat = is_flat (x, y, x2, y2, x3, y3, tolerance);
1946
1947 Path.get_point_for_step (p1, p2, step, out x, out y);
1948 Path.get_point_for_step (p1, p2, step + step_size / step_increment, out x2, out y2);
1949 Path.get_point_for_step (p1, p2, step + 2 * step_size / step_increment, out x3, out y3);
1950
1951 f_next = is_flat (x, y, x2, y2, x3, y3, tolerance);
1952
1953 Path.get_point_for_step (p1, p2, step, out x, out y);
1954 Path.get_point_for_step (p1, p2, step + step_size * step_increment, out x2, out y2);
1955 Path.get_point_for_step (p1, p2, step + 2 * step_size * step_increment, out x3, out y3);
1956
1957 f_bigger = is_flat (x, y, x2, y2, x3, y3, tolerance);
1958
1959 if (!flat && !f_next && step_size > min_increment) {
1960 step_size /= step_increment;
1961 continue;
1962 }
1963
1964 if (flat && f_bigger && step_size < 0.25) {
1965 step_size *= step_increment;
1966 continue;
1967 }
1968
1969 get_segment (thickness, step, step_size, p1, p2, out corner1);
1970 get_segment (-thickness, step, step_size, p1, p2, out corner1_inside);
1971
1972 previous.get_right_handle ().length *= step_size;
1973 corner1.get_left_handle ().length *= step_size;
1974 previous_inside.get_right_handle ().length *= step_size;
1975 corner1_inside.get_left_handle ().length *= step_size;
1976
1977 previous = corner1.copy ();
1978 previous_inside = corner1_inside.copy ();
1979
1980 if (keep == 0 && step > 0.3) { // keep two points per segment
1981 on_curve = true;
1982 keep++;
1983 } else if (keep == 1 && step > 0.6) {
1984 on_curve = true;
1985 keep++;
1986 } else {
1987 on_curve = false;
1988 }
1989
1990 if (!on_curve) {
1991 previous.flags |= EditPoint.CURVE;
1992 previous_inside.flags |= EditPoint.CURVE;
1993 } else {
1994 previous.flags |= EditPoint.CURVE_KEEP;
1995 previous_inside.flags |= EditPoint.CURVE_KEEP;
1996 }
1997
1998 side1.add_point (previous);
1999 side2.add_point (previous_inside);
2000
2001 step += step_size;
2002 }
2003
2004 previous.get_right_handle ().length *= step_size;
2005 corner1.get_left_handle ().length *= step_size;
2006 previous_inside.get_right_handle ().length *= step_size;
2007 corner1_inside.get_left_handle ().length *= step_size;
2008
2009 get_segment (thickness, 1 - 0.00001, 0.00001, p1, p2, out corner1);
2010 get_segment (-thickness, 1 - 0.00001, 0.00001, p1, p2, out corner1_inside);
2011
2012 previous = corner1.copy ();
2013 previous_inside = corner1_inside.copy ();
2014
2015 previous.get_right_handle ().length *= step_size;
2016 previous.get_left_handle ().length *= step_size;
2017 previous_inside.get_right_handle ().length *= step_size;
2018 previous_inside.get_left_handle ().length *= step_size;
2019
2020 previous.flags |= EditPoint.CURVE;
2021 previous_inside.flags |= EditPoint.CURVE;
2022
2023 side1.add_point (previous);
2024 side2.add_point (previous_inside);
2025
2026 l = p2.get_left_handle ();
2027 r = p2.get_right_handle ();
2028
2029 if (fabs ((l.angle + r.angle + PI) % (2 * PI) - PI) > 0.005) { // FIXME: 0.01
2030 if (!path.is_open () || i < size - 1) {
2031 get_segment (thickness, 0, 0.00001, p2, p3, out start);
2032 add_corner (side1, previous, start, p2.copy (), thickness);
2033
2034 get_segment (-thickness, 0, 0.00001, p2, p3, out start);
2035 add_corner (side2, previous_inside, start, p2.copy (), thickness);
2036 }
2037 }
2038
2039 if (fast) {
2040 EditPoint s1, s2;
2041 bool open;
2042
2043 convert_to_curve (side1);
2044 convert_to_curve (side2);
2045
2046 side2.reverse ();
2047 s1 = side1.get_last_point ().copy ();
2048 s2 = side2.get_first_point ().copy ();
2049
2050 open = path.is_open ();
2051
2052 if (!open) {
2053 path.reopen ();
2054 }
2055
2056 pl.append (merge_stroke_parts (path, side1, side2));
2057
2058 if (!open) {
2059 path.close ();
2060 }
2061
2062 side1 = new Path ();
2063 side2 = new Path ();
2064
2065 side1.add_point (s1);
2066 side2.add_point (s2);
2067 }
2068 }
2069
2070 if (!fast) {
2071 side1.remove_points_on_points ();
2072 side2.remove_points_on_points ();
2073
2074 convert_to_curve (side1);
2075 convert_to_curve (side2);
2076
2077 side2.reverse ();
2078 pl = merge_stroke_parts (path, side1, side2);
2079 }
2080
2081 return pl;
2082 }
2083
2084 static void convert_to_curve (Path path) {
2085
2086 if (path.is_open ()) {
2087 path.get_first_point ().flags &= EditPoint.ALL ^ EditPoint.CURVE;
2088 path.get_last_point ().flags &= EditPoint.ALL ^ EditPoint.CURVE;
2089 }
2090
2091 path.recalculate_linear_handles ();
2092 path.remove_points_on_points ();
2093
2094 foreach (EditPoint ep in path.points) {
2095 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) {
2096 ep.convert_to_curve ();
2097 }
2098 }
2099
2100 foreach (EditPoint ep in path.points) {
2101 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) {
2102 ep.set_tie_handle (true);
2103 }
2104 }
2105
2106 foreach (EditPoint ep in path.points) {
2107 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) {
2108 ep.process_tied_handle ();
2109 }
2110 }
2111 }
2112
2113 public static void get_segment (double stroke_thickness, double step, double step_size,
2114 EditPoint p1, EditPoint p2, out EditPoint ep1) {
2115
2116 double thickness = stroke_thickness / 2;
2117 Path overlay;
2118 double x, y, x2, y2, x3, y3;
2119 EditPoint corner1, corner2, corner3;
2120 PointType type;
2121 double handle1_x, handle1_y, handle2_x, handle2_y;
2122
2123 Path.get_point_for_step (p1, p2, step, out x, out y);
2124 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2);
2125 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3);
2126
2127 overlay = new Path ();
2128
2129 type = p1.get_right_handle ().type;
2130 corner1 = new EditPoint (x, y, type);
2131 corner2 = new EditPoint (x2, y2, type);
2132 corner3 = new EditPoint (x3, y3, type);
2133
2134 corner2.convert_to_line (); // FIXME: delete
2135
2136 overlay.add_point (corner1);
2137 overlay.add_point (corner2);
2138 overlay.add_point (corner3);
2139
2140 overlay.close ();
2141 overlay.recalculate_linear_handles ();
2142
2143 move_segment (corner1, corner2, thickness);
2144
2145 ep1 = corner2;
2146 }
2147
2148 public static PathList merge_stroke_parts (Path p, Path side1, Path side2) {
2149 Path merged = new Path ();
2150 PathList paths = new PathList ();
2151
2152 if (!p.is_open () && p.is_filled ()) {
2153 side1.close ();
2154 side1.update_region_boundaries ();
2155 paths.add (side1);
2156 } else if (!p.is_open () && !p.is_filled ()) {
2157 side1.update_region_boundaries ();
2158 paths.add (side1);
2159 side2.update_region_boundaries ();
2160 paths.add (side2);
2161 side1.close ();
2162 side2.close ();
2163 } else if (p.is_open ()) {
2164 side2.reverse ();
2165 merged = merge_strokes (p, side1, side2);
2166 merged.close ();
2167 merged.update_region_boundaries ();
2168 paths.add (merged);
2169 merged.reverse ();
2170 } else {
2171 warning ("Can not create stroke.");
2172 paths.add (p);
2173 }
2174
2175 return paths;
2176 }
2177 }
2178
2179 }
2180