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