The Birdfont Source Code


All Repositories / birdfont.git / blob – RSS feed

StrokeTool.vala in libbirdfont

This file is a part of the Birdfont project.

Contributing

Send patches or pull requests to johan.mattsson.m@gmail.com.
Clone this repository: git clone https://github.com/johanmattssonm/birdfont.git

Revisions

View the latest version of libbirdfont/StrokeTool.vala.
Remove debugging colors
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 enum LineCap { 21 BUTT, 22 SQUARE, 23 ROUND 24 } 25 26 public class StrokeTool : Tool { 27 28 public static double stroke_width = 0; 29 public static bool add_stroke = false; 30 31 public static bool show_stroke_tools = false; 32 public static bool convert_stroke = false; 33 34 public static LineCap line_cap = LineCap.BUTT; 35 36 public StrokeTool (string tooltip) { 37 } 38 39 /** Create strokes for the selected outlines. */ 40 public static void stroke_selected_paths () { 41 Glyph g = MainWindow.get_current_glyph (); 42 PathList paths = new PathList (); 43 44 convert_stroke = true; 45 g.store_undo_state (); 46 47 foreach (Path p in g.active_paths) { 48 if (p.stroke > 0) { 49 paths.append (p.get_stroke ()); 50 } 51 } 52 53 if (paths.paths.size > 0) { 54 foreach (Path p in g.active_paths) { 55 g.layers.remove_path (p); 56 } 57 58 g.active_paths.clear (); 59 60 foreach (Path np in paths.paths) { 61 g.add_path (np); 62 g.active_paths.add (np); 63 } 64 65 PenTool.update_orientation (); 66 67 GlyphCanvas.redraw (); 68 } 69 70 PenTool.update_orientation (); 71 convert_stroke = false; 72 } 73 74 public static PathList get_stroke_fast (Path path, double thickness) { 75 PathList o; 76 Path stroke; 77 78 stroke = path.copy (); 79 stroke.remove_points_on_points (0.3); 80 o = create_stroke (stroke, thickness, false); // set to true for faster stroke 81 82 return o; 83 } 84 85 public static PathList get_stroke (Path path, double thickness) { 86 PathList o, m; 87 Path stroke; 88 89 stroke = path.copy (); 90 stroke.remove_points_on_points (0.3); 91 o = create_stroke (stroke, thickness, false); 92 o = get_all_parts (o); 93 o = remove_intersection_paths (o); 94 o = merge (o); 95 96 m = new PathList (); 97 foreach (Path p in o.paths) { 98 m.add (simplify_stroke (p)); 99 } 100 101 return m; 102 } 103 104 static void reset_flags (PathList o) { 105 foreach (Path p in o.paths) { 106 foreach (EditPoint ep in p.points) { 107 ep.flags &= uint.MAX ^ 108 (EditPoint.INTERSECTION 109 | EditPoint.COPIED 110 | EditPoint.NEW_CORNER 111 | EditPoint.SELF_INTERSECTION); 112 } 113 p.update_region_boundaries (); 114 } 115 } 116 117 public static void merge_selected_paths () { 118 Glyph g = MainWindow.get_current_glyph (); 119 PathList o = new PathList (); 120 PathList r; 121 PathList new_paths = new PathList (); 122 123 g.store_undo_state (); 124 125 foreach (Path p in g.active_paths) { 126 p.close (); 127 o.add (p); 128 } 129 130 o = remove_overlap (o); 131 132 reset_flags (o); 133 134 new_paths.append (o); 135 for (int i = 0; i < o.paths.size; i++) { 136 for (int j = 0; j < o.paths.size; j++) { 137 Path p1, p2; 138 139 p1 = o.paths.get (i); 140 p2 = o.paths.get (j); 141 142 if (i == j) { 143 continue; 144 } 145 146 r = merge_selected (p1, p2, false); 147 148 remove_merged_curve_parts (r); 149 150 if (r.paths.size > 0) { 151 reset_flags (r); 152 new_paths.append (r); 153 154 new_paths.remove (p1); 155 new_paths.remove (p2); 156 157 i = 0; 158 j = 0; 159 } 160 } 161 } 162 163 foreach (Path p in g.active_paths) { 164 g.delete_path (p); 165 } 166 167 g.clear_active_paths (); 168 169 remove_merged_curve_parts (new_paths); 170 171 foreach (Path p in new_paths.paths) { 172 g.add_path (p); 173 g.add_active_path (null, p); 174 } 175 176 PenTool.update_orientation (); 177 GlyphCanvas.redraw (); 178 } 179 180 static PathList remove_overlap (PathList pl) { 181 PathList r = new PathList (); 182 183 foreach (Path p in pl.paths) { 184 PathList m = merge_selected (p, new Path (), true); 185 186 if (m.paths.size > 0) { 187 r.append (m); 188 } else { 189 r.add (p); 190 } 191 } 192 193 return r; 194 } 195 196 static void remove_merged_curve_parts (PathList r) { 197 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> (); 198 PathList flat = new PathList (); 199 200 foreach (Path p in r.paths) { 201 p.update_region_boundaries (); 202 flat.add (p.flatten ()); 203 } 204 205 foreach (Path p in r.paths) { 206 PathList pl = get_insides (flat, p); 207 208 int counters = 0; 209 int clockwise = 0; 210 211 foreach (Path i in pl.paths) { 212 if (i.is_clockwise ()) { 213 clockwise++; 214 } else { 215 counters++; 216 } 217 } 218 219 if (p.is_clockwise ()) { 220 if (clockwise - 1 > counters) { 221 remove.add (p); 222 break; 223 } 224 } else { 225 if (clockwise < counters - 1) { 226 remove.add (p); 227 break; 228 } 229 } 230 } 231 232 foreach (Path p in remove) { 233 r.paths.remove (p); 234 remove_merged_curve_parts (r); 235 return; 236 } 237 } 238 239 public static PathList merge_selected (Path path1, Path path2, 240 bool self_intersection) { 241 242 PathList flat = new PathList (); 243 PathList o = new PathList (); 244 PathList pl = new PathList (); 245 PathList r = new PathList (); 246 247 pl.add (path1); 248 pl.add (path2); 249 250 if (!self_intersection) { 251 if (!path1.boundaries_intersecting (path2)) { 252 return r; 253 } 254 } 255 256 foreach (Path p in pl.paths) { 257 if (p.stroke == 0) { 258 o.add (p); 259 flat.add (p.copy ().flatten (50)); 260 } 261 } 262 263 flat = merge (flat); 264 265 bool has_split_point = false; 266 foreach (Path p in flat.paths) { 267 foreach (EditPoint ep in p.points) { 268 if ((ep.flags & EditPoint.SPLIT_POINT) > 0) { 269 foreach (Path pp in o.paths) { 270 EditPoint lep = new EditPoint (); 271 272 if (pp.points.size > 1) { 273 pp.get_closest_point_on_path (lep, ep.x, ep.y, null, null); 274 275 if (Path.distance_to_point (lep, (!) lep.prev) < 0.1 276 || Path.distance_to_point (lep, (!) lep.next) < 0.1) { 277 // FIXME: find a better solution 278 continue; 279 } 280 281 if (Path.distance_to_point (ep, lep) < 0.1) { 282 EditPoint lep2 = new EditPoint (); 283 pp.get_closest_point_on_path (lep2, ep.x, ep.y, lep.prev, lep.next); 284 285 if (lep.prev != null) { 286 lep.get_left_handle ().type = lep.get_prev ().get_right_handle ().type; 287 } else { 288 lep.get_left_handle ().type = pp.get_last_point ().get_right_handle ().type; 289 } 290 291 if (lep.next != null) { 292 lep.get_right_handle ().type = lep.get_next ().get_left_handle ().type; 293 } else { 294 lep.get_left_handle ().type = pp.get_first_point ().get_right_handle ().type; 295 } 296 297 if (lep2.prev != null) { 298 lep2.get_left_handle ().type = lep2.get_prev ().get_right_handle ().type; 299 } else { 300 lep2.get_left_handle ().type = pp.get_first_point ().get_right_handle ().type; 301 } 302 303 if (lep2.next != null) { 304 lep2.get_right_handle ().type = lep2.get_next ().get_left_handle ().type; 305 } else { 306 lep2.get_left_handle ().type = pp.get_last_point ().get_right_handle ().type; 307 } 308 309 // self intersection 310 if (Path.distance_to_point (ep, lep2) < 0.1 311 && Path.distance_to_point (ep, lep) < 0.1) { 312 pp.insert_new_point_on_path (lep); 313 pp.insert_new_point_on_path (lep2); 314 315 lep.flags |= EditPoint.SELF_INTERSECTION; 316 lep2.flags |= EditPoint.SELF_INTERSECTION; 317 318 lep.tie_handles = false; 319 lep.reflective_point = false; 320 lep2.tie_handles = false; 321 lep2.reflective_point = false; 322 } else { 323 pp.insert_new_point_on_path (lep); 324 lep.flags |= EditPoint.INTERSECTION; 325 lep.tie_handles = false; 326 lep.reflective_point = false; 327 } 328 329 has_split_point = true; 330 } 331 } 332 } 333 } 334 } 335 } 336 337 if (!has_split_point) { 338 return r; 339 } 340 341 // remove double intersection points 342 EditPoint prev = new EditPoint (); 343 foreach (Path pp in o.paths) { 344 foreach (EditPoint ep in pp.points) { 345 if (((prev.flags & EditPoint.SELF_INTERSECTION) > 0 || (prev.flags & EditPoint.INTERSECTION) > 0) 346 && ((ep.flags & EditPoint.SELF_INTERSECTION) > 0 || (ep.flags & EditPoint.INTERSECTION) > 0) 347 && fabs (ep.x - prev.x) < 0.2 348 && fabs (ep.y - prev.y) < 0.2) { 349 prev.deleted = true; 350 } 351 352 prev = ep; 353 } 354 } 355 356 foreach (Path pp in o.paths) { 357 pp.remove_deleted_points (); 358 } 359 360 foreach (Path p in o.paths) { 361 foreach (EditPoint ep in p.points) { 362 ep.flags &= uint.MAX ^ EditPoint.COPIED; 363 } 364 } 365 366 return_val_if_fail (o.paths.size == 2, r); 367 368 Path p1, p2; 369 370 p1 = o.paths.get (0); 371 p2 = o.paths.get (1); 372 PathList parts = new PathList (); 373 374 if (self_intersection) { 375 // remove overlap 376 PathList self_parts; 377 378 self_parts = remove_self_intersections (p1); 379 parts.append (self_parts); 380 } else { 381 // merge two path 382 PathList merged_paths = merge_paths_with_curves (p1, p2); 383 384 if (merged_paths.paths.size > 0) { 385 parts.append (merged_paths); 386 } else { 387 parts.add (p1); 388 parts.add (p2); 389 } 390 } 391 392 foreach (Path p in parts.paths) { 393 reset_intersections (p); 394 } 395 396 return parts; 397 } 398 399 static PathList remove_self_intersections (Path original) { 400 Path merged = new Path (); 401 IntersectionList intersections = new IntersectionList (); 402 EditPoint ep1, ep2, found; 403 double d; 404 double min_d; 405 Path current; 406 bool found_intersection; 407 PathList parts; 408 int i = 0; 409 Path path = original.copy (); 410 411 parts = new PathList (); 412 413 if (path.points.size <= 1) { 414 return parts; 415 } 416 417 // reset copied points 418 foreach (EditPoint n in path.points) { 419 n.flags &= uint.MAX ^ EditPoint.COPIED; 420 } 421 422 // build list of intersection points 423 for (i = 0; i < path.points.size; i++) { 424 ep1 = path.points.get (i); 425 426 if ((ep1.flags & EditPoint.SELF_INTERSECTION) > 0 427 && (ep1.flags & EditPoint.COPIED) == 0) { 428 ep1.flags |= EditPoint.COPIED; 429 430 found = new EditPoint (); 431 min_d = double.MAX; 432 found_intersection = false; 433 434 for (int j = 0; j < path.points.size; j++) { 435 ep2 = path.points.get (j); 436 d = Path.distance_to_point (ep1, ep2); 437 if ((ep2.flags & EditPoint.COPIED) == 0 438 && (ep2.flags & EditPoint.SELF_INTERSECTION) > 0) { 439 if (d < min_d) { 440 min_d = d; 441 found_intersection = true; 442 found = ep2; 443 } 444 } 445 } 446 447 if (!found_intersection) { 448 warning (@"No self intersection:\n$(ep1)"); 449 return parts; 450 } 451 452 ep1.tie_handles = false; 453 ep1.reflective_point = false; 454 found.tie_handles = false; 455 found.reflective_point = false; 456 457 found.flags |= EditPoint.COPIED; 458 Intersection intersection = new Intersection (ep1, path, found, path); 459 intersection.self_intersection = true; 460 intersections.points.add (intersection); 461 } 462 } 463 464 // reset copy flag 465 foreach (EditPoint n in path.points) { 466 n.flags &= uint.MAX ^ EditPoint.COPIED; 467 } 468 469 if (intersections.points.size == 0) { 470 warning ("No intersection points."); 471 return parts; 472 } 473 474 current = path; 475 current.reverse (); 476 477 while (true) { 478 EditPoint modified; 479 i = 0; 480 Intersection new_start = new Intersection.empty (); 481 ep1 = current.points.get (i); 482 current = path; 483 484 modified = ep1.copy (); 485 486 for (i = 0; i < current.points.size; i++) { 487 ep1 = current.points.get (i); 488 modified = ep1.copy (); 489 if ((ep1.flags & EditPoint.COPIED) == 0 490 && (ep1.flags & EditPoint.SELF_INTERSECTION) == 0) { 491 break; 492 } 493 } 494 495 if (i >= current.points.size || (ep1.flags & EditPoint.COPIED) > 0) { 496 // all points have been copied 497 break; 498 } 499 500 while (true) { 501 502 if ((ep1.flags & EditPoint.SELF_INTERSECTION) > 0) { 503 bool other; 504 EditPointHandle handle; 505 506 handle = ep1.get_left_handle (); 507 new_start = intersections.get_point (ep1, out other); 508 509 i = index_of (current, other ? new_start.point : new_start.other_point); 510 511 if (!(0 <= i < current.points.size)) { 512 warning (@"Index out of bounds. ($i)"); 513 return parts; 514 } 515 516 ep1 = current.points.get (i); 517 modified = ep1.copy (); 518 modified.left_handle.move_to_coordinate (handle.x, handle.y); 519 } 520 521 if ((ep1.flags & EditPoint.COPIED) > 0) { 522 merged.close (); 523 524 merged.close (); 525 merged.create_list (); 526 parts.add (merged); 527 528 foreach (EditPoint n in merged.points) { 529 n.flags &= uint.MAX ^ EditPoint.SELF_INTERSECTION; 530 } 531 532 merged.reverse (); 533 534 merged = new Path (); 535 536 break; 537 } 538 539 // adjust the other handle 540 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 541 ep1.left_handle.convert_to_curve (); 542 ep1.right_handle.convert_to_curve (); 543 ep1.tie_handles = false; 544 ep1.reflective_point = false; 545 } 546 547 // add point to path 548 ep1.flags |= EditPoint.COPIED; 549 merged.add_point (modified.copy ()); 550 551 i++; 552 ep1 = current.points.get (i % current.points.size); 553 modified = ep1.copy (); 554 } 555 556 ep1.flags |= EditPoint.COPIED; 557 } 558 559 return parts; 560 } 561 562 static PathList merge_paths_with_curves (Path path1, Path path2) { 563 PathList r = new PathList (); 564 IntersectionList intersections = new IntersectionList (); 565 EditPoint ep1, ep2, found; 566 double d; 567 double min_d; 568 Path current; 569 bool found_intersection; 570 Path flat1, flat2; 571 572 if (path1.points.size <= 1 || path2.points.size <= 1) { 573 return r; 574 } 575 576 flat1 = path1.flatten (); 577 flat2 = path2.flatten (); 578 579 // reset copied points 580 foreach (EditPoint n in path2.points) { 581 n.flags &= uint.MAX ^ EditPoint.COPIED; 582 } 583 584 // build list of intersection points 585 for (int i = 0; i < path1.points.size; i++) { 586 ep1 = path1.points.get (i); 587 588 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 589 found = new EditPoint (); 590 min_d = double.MAX; 591 found_intersection = false; 592 for (int j = 0; j < path2.points.size; j++) { 593 ep2 = path2.points.get (j); 594 d = Path.distance_to_point (ep1, ep2); 595 if ((ep2.flags & EditPoint.COPIED) == 0 596 && (ep2.flags & EditPoint.INTERSECTION) > 0) { 597 if (d < min_d) { 598 min_d = d; 599 found_intersection = true; 600 found = ep2; 601 } 602 } 603 } 604 605 if (!found_intersection) { 606 warning (@"No intersection for:\n $(ep1)"); 607 return r; 608 } 609 610 found.flags |= EditPoint.COPIED; 611 612 ep1.tie_handles = false; 613 ep1.reflective_point = false; 614 found.tie_handles = false; 615 found.reflective_point = false; 616 Intersection intersection = new Intersection (ep1, path1, found, path2); 617 intersections.points.add (intersection); 618 } 619 } 620 621 // reset copy flag 622 foreach (EditPoint n in path1.points) { 623 n.flags &= uint.MAX ^ EditPoint.COPIED; 624 } 625 626 foreach (EditPoint n in path2.points) { 627 n.flags &= uint.MAX ^ EditPoint.COPIED; 628 } 629 630 if (intersections.points.size == 0) { 631 warning ("No intersection points."); 632 return r; 633 } 634 635 Path new_path = new Path (); 636 current = path1; 637 while (true) { 638 // find a beginning of a new part 639 bool find_parts = false; 640 Intersection new_start = new Intersection.empty (); 641 foreach (Intersection inter in intersections.points) { 642 if (!inter.done && !find_parts) { 643 find_parts = true; 644 new_start = inter; 645 current = new_start.path; 646 } 647 } 648 649 if (new_path.points.size > 0) { 650 new_path.close (); 651 new_path.recalculate_linear_handles (); 652 new_path.update_region_boundaries (); 653 r.add (new_path); 654 } 655 656 if (!find_parts) { // no more parts 657 break; 658 } 659 660 if ((new_start.get_point (current).flags & EditPoint.COPIED) > 0) { 661 current = new_start.get_other_path (current); 662 } 663 664 int i = index_of (current, new_start.get_point (current)); 665 666 if (i < 0) { 667 warning ("i < 0"); 668 return r; 669 } 670 671 EditPoint previous = new EditPoint (); 672 new_path = new Path (); 673 ep1 = current.points.get (i); 674 current = new_start.get_other_path (current); // swap at first iteration 675 bool first = true; 676 while (true) { 677 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 678 bool other; 679 680 previous = ep1; 681 682 if (likely (intersections.has_point (ep1))) { 683 new_start = intersections.get_point (ep1, out other); 684 current = new_start.get_other_path (current); 685 i = index_of (current, new_start.get_point (current)); 686 687 if (!(0 <= i < current.points.size)) { 688 warning (@"Index out of bounds. ($i)"); 689 return r; 690 } 691 692 ep1 = current.points.get (i); 693 ep2 = current.points.get ((i + 1) % current.points.size); 694 695 double px, py; 696 697 Path.get_point_for_step (ep1, ep2, 0.5, out px, out py); 698 bool inside = (current == path1 && flat2.is_over_coordinate (px, py)) 699 || (current == path2 && flat1.is_over_coordinate (px, py)); 700 701 bool other_inside = (current != path1 && flat2.is_over_coordinate (px, py)) 702 || (current != path2 && flat1.is_over_coordinate (px, py)); 703 704 if (inside && !other_inside) { 705 current = new_start.get_other_path (current); 706 i = index_of (current, new_start.get_point (current)); 707 708 if (!(0 <= i < current.points.size)) { 709 warning (@"Index out of bounds. ($i >= $(current.points.size)) "); 710 return r; 711 } 712 713 new_start.done = true; 714 ep1 = current.points.get (i); 715 } 716 717 inside = (current == path1 && flat2.is_over_coordinate (px, py)) 718 || (current == path2 && flat1.is_over_coordinate (px, py)); 719 720 if (first) { 721 Path c = new_start.get_other_path (current); 722 if (c.points.size >= 1) { 723 previous = c.get_first_point (); 724 } 725 726 first = false; 727 } 728 } 729 } 730 731 if ((ep1.flags & EditPoint.COPIED) > 0) { 732 new_path.close (); 733 734 if (new_path.points.size >= 1) { 735 EditPoint first_point = new_path.get_first_point (); 736 EditPointHandle h; 737 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 738 first_point.left_handle.move_to_coordinate (previous.left_handle.x, previous.left_handle.y); 739 740 if (first_point.next != null) { 741 h = first_point.get_next ().get_left_handle (); 742 h.process_connected_handle (); 743 } 744 } 745 } 746 747 break; 748 } 749 750 // adjust the other handle 751 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 752 ep1.left_handle.convert_to_curve (); 753 ep1.right_handle.convert_to_curve (); 754 } 755 756 // add point to path 757 ep1.flags |= EditPoint.COPIED; 758 new_path.add_point (ep1.copy ()); 759 760 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { // FIXME SELF INTERSECTION 761 new_path.get_last_point ().left_handle.move_to_coordinate (previous.left_handle.x, previous.left_handle.y); 762 } 763 764 i++; 765 ep1 = current.points.get (i % current.points.size); 766 } 767 768 ep1.flags |= EditPoint.COPIED; 769 770 if (!new_start.done) { 771 new_start.done = (new_start.get_other_point (current).flags & EditPoint.COPIED) > 0; 772 } 773 } 774 775 return r; 776 } 777 778 static Path simplify_stroke (Path p) { 779 Path simplified = new Path (); 780 Path segment, added_segment; 781 EditPoint ep, ep_start, last, first, segment_last; 782 int start, stop; 783 int j; 784 785 segment_last = new EditPoint (); 786 last = new EditPoint (); 787 788 foreach (EditPoint e in p.points) { 789 PenTool.convert_point_type (e, PointType.CUBIC); 790 } 791 792 foreach (EditPoint e in p.points) { 793 if ((e.flags & EditPoint.CURVE) == 0) { 794 p.set_new_start (e); 795 break; 796 } 797 } 798 799 for (int i = 0; i < p.points.size; i++) { 800 ep = p.points.get (i); 801 802 if ((ep.flags & EditPoint.CURVE) > 0) { 803 start = i; 804 for (j = start + 1; j < p.points.size; j++) { 805 ep = p.points.get (j); 806 if ((ep.flags & EditPoint.CURVE) == 0) { 807 break; 808 } 809 } 810 811 stop = j; 812 start -= 1; 813 814 if (start < 0) { 815 warning ("start < 0"); 816 start = 0; 817 } 818 819 if (stop >= p.points.size) { 820 warning ("stop >= p.points.size"); 821 stop = p.points.size - 1; 822 } 823 824 ep_start = p.points.get (start); 825 ep = p.points.get (stop); 826 827 double l = Path.distance_to_point (ep_start, ep); 828 segment = fit_bezier_path (p, start, stop, 0.00001 * l * l); 829 830 added_segment = segment.copy (); 831 832 if (simplified.points.size > 0) { 833 last = simplified.get_last_point (); 834 } 835 836 if (added_segment.points.size > 0) { 837 segment_last = added_segment.get_last_point (); 838 first = added_segment.get_first_point (); 839 segment_last.right_handle = ep_start.get_right_handle ().copy (); 840 841 if (simplified.points.size > 1) { 842 simplified.delete_last_point (); 843 } 844 845 first.set_tie_handle (false); 846 last.set_tie_handle (false); 847 848 last.get_right_handle ().x = first.get_right_handle ().x; 849 last.get_right_handle ().y = first.get_right_handle ().y; 850 851 first.get_left_handle ().convert_to_curve (); 852 first.get_left_handle ().x = last.get_left_handle ().x; 853 first.get_left_handle ().y = last.get_left_handle ().y; 854 855 last = added_segment.get_last_point (); 856 last.right_handle = ep.get_right_handle ().copy (); 857 last.recalculate_linear_handles (); 858 859 simplified.append_path (added_segment); 860 861 segment_last.right_handle = ep.get_right_handle ().copy (); 862 863 if (added_segment.points.size > 0) { 864 if (ep_start.get_right_handle ().is_line ()) { 865 first = added_segment.get_first_point (); 866 first.recalculate_linear_handles (); 867 } 868 } 869 } else { 870 warning ("No points in segment."); 871 } 872 873 i = stop; 874 } else { 875 simplified.add_point (ep.copy ()); 876 } 877 } 878 879 simplified.recalculate_linear_handles (); 880 simplified.close (); 881 882 simplified.remove_points_on_points (0.01); 883 884 return simplified; 885 } 886 887 static Path fit_bezier_path (Path p, int start, int stop, double error) { 888 int index, size; 889 Path simplified; 890 double[] lines; 891 double[] result; 892 EditPoint ep; 893 894 simplified = new Path (); 895 896 return_val_if_fail (0 <= start < p.points.size, simplified); 897 return_val_if_fail (0 <= stop < p.points.size, simplified); 898 899 size = stop - start + 1; 900 lines = new double[2 * size]; 901 902 index = 0; 903 904 for (int i = start; i <= stop; i++) { 905 ep = p.points.get (i); 906 lines[index] = ep.x; 907 index++; 908 909 lines[index] = ep.y; 910 index++; 911 } 912 913 return_val_if_fail (2 * size == index, new Path ()); 914 915 Gems.fit_bezier_curve_to_line (lines, error, out result); 916 917 return_val_if_fail (!is_null (result), simplified); 918 919 for (int i = 0; i + 7 < result.length; i += 8) { 920 simplified.add_cubic_bezier_points ( 921 result[i], result[i + 1], 922 result[i + 2], result[i + 3], 923 result[i + 4], result[i + 5], 924 result[i + 6], result[i + 7]); 925 } 926 927 return simplified; 928 } 929 930 static PathList remove_intersection_paths (PathList pl) { 931 PathList r = new PathList (); 932 933 foreach (Path p in pl.paths) { 934 if (p.points.size > 7) { 935 r.add (p); 936 } else if (!has_new_corner (p)) { 937 r.add (p); 938 } else if (counters (pl, p) == 0) { 939 r.add (p); 940 } 941 } 942 943 return r; 944 } 945 946 static bool has_new_corner (Path p) { 947 foreach (EditPoint ep in p.points) { 948 if ((ep.flags & EditPoint.NEW_CORNER) > 0) { 949 return true; 950 } 951 } 952 953 return false; 954 } 955 956 static void add_line_cap (Path path, Path stroke1, Path stroke2, bool last_cap) { 957 if (path.line_cap == LineCap.SQUARE) { 958 add_square_cap (path, stroke1, stroke2, last_cap); 959 } else if (path.line_cap == LineCap.ROUND) { 960 add_round_cap (path, stroke1, stroke2, last_cap); 961 } 962 } 963 964 static void add_round_cap (Path path, Path stroke1, Path stroke2, bool last_cap) { 965 double px, py; 966 double step, start_angle, stop_angle; 967 double radius; 968 EditPoint n, nstart, nend; 969 Path cap = new Path (); 970 971 EditPoint start, end; 972 EditPointHandle last_handle; 973 EditPoint first, last; 974 975 stroke1.remove_points_on_points (); 976 stroke2.remove_points_on_points (); 977 978 last_handle = path.get_first_point ().get_right_handle (); 979 start = stroke1.get_last_point (); 980 end = stroke2.get_first_point (); 981 982 start_angle = last_handle.angle + PI / 2; 983 stop_angle = start_angle + PI; 984 985 nstart = cap.add (start.x, start.y); 986 radius = Path.distance_to_point (start, end) / 2; 987 step = PI / 5; 988 989 for (int j = 0; j < 5; j++) { 990 double angle = start_angle + step * j; 991 px = radius * cos (angle) + last_handle.parent.x; 992 py = radius * sin (angle) + last_handle.parent.y; 993 n = cap.add (px, py); 994 995 n.type = PointType.LINE_CUBIC; 996 n.get_right_handle ().type = PointType.LINE_CUBIC; 997 n.get_left_handle ().type = PointType.LINE_CUBIC; 998 } 999 1000 nend = cap.add (end.x, end.y); 1001 1002 for (int i = 0; i < cap.points.size; i++) { 1003 cap.points.get (i).recalculate_linear_handles (); 1004 } 1005 1006 int size = cap.points.size; 1007 1008 for (int i = 1; i < size; i++) { 1009 n = cap.points.get (i); 1010 n.convert_to_curve (); 1011 n.set_tie_handle (true); 1012 n.process_tied_handle (); 1013 } 1014 1015 int f = stroke1.points.size - 1; 1016 1017 for (int i = 2; i < cap.points.size - 1; i++) { 1018 n = cap.points.get (i).copy (); 1019 stroke1.add_point (n); 1020 } 1021 1022 cap.remove_points_on_points (); 1023 return_if_fail (0 < f < stroke1.points.size); 1024 1025 first = stroke1.points.get (f); 1026 1027 last = stroke1.get_last_point (); 1028 last.convert_to_curve (); 1029 1030 last = stroke1.add_point (stroke2.get_first_point ()); 1031 stroke2.delete_first_point (); 1032 1033 last.convert_to_line (); 1034 last.recalculate_linear_handles (); 1035 1036 last.next = stroke1.add_point (stroke2.get_first_point ()).get_link_item (); 1037 stroke2.delete_first_point (); 1038 1039 last.get_left_handle ().convert_to_curve (); 1040 last.get_left_handle ().angle = last.get_right_handle ().angle + PI; 1041 last.flags = EditPoint.CURVE_KEEP; 1042 1043 double a; 1044 double l; 1045 1046 return_if_fail (cap.points.size > 1); 1047 1048 a = (first.get_left_handle ().angle + PI) % (2 * PI); 1049 l = cap.points.get (1).get_right_handle ().length; 1050 1051 first.get_right_handle ().convert_to_curve (); 1052 first.get_right_handle ().angle = a; 1053 first.get_right_handle ().length = l; 1054 1055 a = (first.get_left_handle ().angle + PI) % (2 * PI); 1056 1057 last.get_left_handle ().convert_to_curve (); 1058 last.get_left_handle ().angle = a; 1059 last.get_left_handle ().length = l; 1060 } 1061 1062 static void add_square_cap (Path path, Path stroke1, Path stroke2, bool last_cap) { 1063 EditPointHandle last_handle; 1064 EditPoint start; 1065 EditPoint end; 1066 EditPoint n; 1067 double x, y; 1068 double stroke_width = path.stroke / 2; 1069 1070 last_handle = path.get_first_point ().get_right_handle (); 1071 start = stroke1.get_last_point (); 1072 end = stroke2.get_first_point (); 1073 1074 y = sin (last_handle.angle - PI) * stroke_width; 1075 x = cos (last_handle.angle - PI) * stroke_width; 1076 1077 n = stroke1.add (start.x + x, start.y + y); 1078 n.type = PointType.CUBIC; 1079 n.get_right_handle ().type = PointType.CUBIC; 1080 n.get_left_handle ().type = PointType.CUBIC; 1081 n.convert_to_line (); 1082 1083 n = stroke1.add (end.x + x, end.y + y); 1084 n.type = PointType.CUBIC; 1085 n.get_right_handle ().type = PointType.CUBIC; 1086 n.get_left_handle ().type = PointType.CUBIC; 1087 n.convert_to_line (); 1088 } 1089 1090 /** Create one stroke from the outline and counter stroke and close the 1091 * open endings. 1092 * 1093 * @param path the path to create stroke for 1094 * @param stroke for the outline of path 1095 * @param stroke for the counter path 1096 */ 1097 static Path merge_strokes (Path path, Path stroke, Path counter) { 1098 1099 Path merged; 1100 EditPoint last_counter, first; 1101 1102 merged = stroke.copy (); 1103 merged.reverse (); 1104 1105 last_counter = new EditPoint (); 1106 first = new EditPoint (); 1107 1108 add_line_cap (path, merged, counter, true); 1109 path.reverse (); 1110 1111 add_line_cap (path, counter, merged, true); 1112 path.reverse (); 1113 1114 merged.append_path (counter); 1115 1116 merged.close (); 1117 merged.create_list (); 1118 merged.recalculate_linear_handles (); 1119 1120 return merged; 1121 } 1122 1123 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) { 1124 EditPointHandle r, l; 1125 double m, n; 1126 double qx, qy; 1127 1128 stroke_start.set_tie_handle (false); 1129 stroke_stop.set_tie_handle (false); 1130 1131 r = stroke_start.get_right_handle (); 1132 l = stroke_stop.get_left_handle (); 1133 1134 m = cos (r.angle + PI / 2) * thickness; 1135 n = sin (r.angle + PI / 2) * thickness; 1136 1137 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n); 1138 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n); 1139 1140 stroke_start.independent_x += m; 1141 stroke_start.independent_y += n; 1142 1143 qx = cos (l.angle - PI / 2) * thickness; 1144 qy = sin (l.angle - PI / 2) * thickness; 1145 1146 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy); 1147 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy); 1148 1149 stroke_stop.independent_x += qx; 1150 stroke_stop.independent_y += qy; 1151 } 1152 1153 static void add_corner (Path stroked, EditPoint previous, EditPoint next, 1154 EditPoint original, double stroke_width) { 1155 1156 double ratio; 1157 double distance; 1158 EditPoint corner; 1159 double corner_x, corner_y; 1160 EditPointHandle previous_handle; 1161 EditPointHandle next_handle; 1162 EditPoint cutoff1, cutoff2; 1163 double adjusted_stroke = (stroke_width * 0.999999) / 2.0; 1164 bool d1, d2; 1165 1166 previous_handle = previous.get_left_handle (); 1167 next_handle = next.get_right_handle (); 1168 1169 previous_handle.angle += PI; 1170 next_handle.angle += PI; 1171 1172 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y); 1173 corner = new EditPoint (corner_x, corner_y, previous.type); 1174 corner.convert_to_line (); 1175 1176 previous_handle.angle -= PI; 1177 next_handle.angle -= PI; 1178 1179 distance = Path.distance_to_point (corner, original); 1180 ratio = 1.5 * fabs (adjusted_stroke) / distance; 1181 1182 double or = original.get_right_handle ().angle; 1183 double ol = original.get_left_handle ().angle; 1184 1185 if (previous.prev == null) { // FIXME: first point 1186 warning ("Point before corner."); 1187 d1 = false; 1188 d2 = false; 1189 } else { 1190 d1 = corner.x - previous.x >= 0 == previous.x - previous.get_prev ().x >= 0; 1191 d2 = corner.y - previous.y >= 0 == previous.y - previous.get_prev ().y >= 0; 1192 } 1193 1194 if (ratio > 1) { 1195 if (!d1 && !d2) { 1196 return; 1197 } else { 1198 stroked.add_point (corner); 1199 } 1200 } else { 1201 1202 cutoff1 = new EditPoint (); 1203 cutoff1.set_point_type (previous.type); 1204 cutoff1.convert_to_line (); 1205 1206 cutoff2 = new EditPoint (); 1207 cutoff2.set_point_type (previous.type); 1208 cutoff2.convert_to_line (); 1209 1210 if (fabs (or - ol) < 0.001) { 1211 cutoff1.x = previous.x + 1.5 * fabs (adjusted_stroke) * -cos (or); 1212 cutoff1.y = previous.y + 1.5 * fabs (adjusted_stroke) * -sin (or); 1213 1214 cutoff2.x = next.x + 1.5 * fabs (adjusted_stroke) * -cos (or); 1215 cutoff2.y = next.y + 1.5 * fabs (adjusted_stroke) * -sin (or); 1216 } else { 1217 cutoff1.x = previous.x + (corner.x - previous.x) * ratio; 1218 cutoff1.y = previous.y + (corner.y - previous.y) * ratio; 1219 1220 cutoff2.x = next.x + (corner.x - next.x) * ratio; 1221 cutoff2.y = next.y + (corner.y - next.y) * ratio; 1222 } 1223 1224 if (!cutoff1.is_valid () || cutoff2.is_valid ()) { 1225 cutoff1 = stroked.add_point (cutoff1); 1226 cutoff2 = stroked.add_point (cutoff2); 1227 } 1228 1229 cutoff1.recalculate_linear_handles (); 1230 cutoff2.recalculate_linear_handles (); 1231 1232 // self intersection 1233 if (!d1 && !d2) { 1234 cutoff1.deleted = true; 1235 cutoff2.deleted = true; 1236 1237 stroked.remove_deleted_points (); 1238 return; 1239 } 1240 1241 if (distance > 4 * stroke_width) { 1242 previous.flags = EditPoint.NONE; 1243 next.flags = EditPoint.NONE; 1244 } else { 1245 previous.flags |= EditPoint.NEW_CORNER; 1246 next.flags |= EditPoint.NEW_CORNER; 1247 } 1248 } 1249 } 1250 1251 static PathList get_parts (Path path) { 1252 PathList intersections; 1253 PathList r; 1254 1255 r = get_parts_self (path); 1256 intersections = new PathList (); 1257 1258 foreach (Path p in r.paths) { 1259 intersections.add (p); 1260 } 1261 1262 return intersections; 1263 } 1264 1265 static bool split_corner (PathList pl) { 1266 EditPoint p1, p2; 1267 EditPoint a1, a2; 1268 PathList result; 1269 bool split; 1270 1271 foreach (Path p in pl.paths) { 1272 if (p.points.size == 0) { 1273 continue; 1274 } 1275 1276 for (int index = 1; index < p.points.size + 2; index++) { 1277 p1 = p.points.get ((index - 1) % p.points.size); 1278 p2 = p.points.get (index % p.points.size); 1279 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 1280 a2 = p.points.get ((index + 4) % p.points.size); 1281 1282 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 1283 || (p2.flags & EditPoint.STROKE_OFFSET) > 0 1284 || (a1.flags & EditPoint.STROKE_OFFSET) > 0 1285 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) { 1286 1287 split = split_segment (p, a1, a2, p1, p2, out result); 1288 1289 if (split) { 1290 pl.append (result); 1291 pl.paths.remove (p); 1292 split_corner (pl); 1293 return true; 1294 } else { 1295 p1 = p.points.get ((index - 1) % p.points.size); 1296 p2 = p.points.get (index % p.points.size); 1297 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead 1298 a2 = p.points.get ((index + 3) % p.points.size); 1299 1300 split = split_segment (p, a1, a2, p1, p2, out result); 1301 1302 if (split) { 1303 pl.append (result); 1304 pl.paths.remove (p); 1305 split_corner (pl); 1306 return true; 1307 } else { 1308 p1 = p.points.get ((index - 1) % p.points.size); 1309 p2 = p.points.get (index % p.points.size); 1310 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 1311 a2 = p.points.get ((index + 4) % p.points.size); 1312 1313 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 1314 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) { 1315 p1.flags = EditPoint.COUNTER_TO_OUTLINE; 1316 a1.flags = EditPoint.COUNTER_TO_OUTLINE; 1317 } 1318 } 1319 } 1320 } 1321 } 1322 } 1323 1324 return false; 1325 } 1326 1327 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) { 1328 double ix, iy; 1329 bool intersection; 1330 int i; 1331 1332 result = new PathList (); 1333 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true); 1334 1335 if (intersection) { 1336 add_intersection (p, first, next, ix, iy); 1337 add_intersection (p, p1, p2, ix, iy); 1338 1339 i = mark_intersection_as_deleted (p); 1340 return_val_if_fail (i == 2, false); 1341 1342 result.append (get_remaining_points (p.copy ())); 1343 } 1344 1345 return intersection; 1346 } 1347 1348 static bool split_path (Path path1, Path path2, PathList result) { 1349 PathList pl1, pl2; 1350 Path a1, a2, b1, b2; 1351 Path m1, m2; 1352 int i; 1353 1354 if (path1 == path2) { 1355 return false; 1356 } 1357 1358 if (add_intersection_points (path1, path2, 2)) { 1359 i = mark_intersection_as_deleted (path1); 1360 if (i != 2) { 1361 warning (@"Expecting 2 points, $i points found."); 1362 return false; 1363 } 1364 1365 i = mark_intersection_as_deleted (path2); 1366 if (i != 2) { 1367 warning (@"Expecting 2 points, $i points found."); 1368 return false; 1369 } 1370 1371 1372 pl1 = get_remaining_points (path1.copy ()); 1373 pl2 = get_remaining_points (path2.copy ()); 1374 1375 return_if_fail (pl1.paths.size == 2); 1376 return_if_fail (pl2.paths.size == 2); 1377 1378 a1 = pl1.paths.get (0); 1379 a2 = pl1.paths.get (1); 1380 b1 = pl2.paths.get (0); 1381 b2 = pl2.paths.get (1); 1382 1383 m1 = PenTool.merge_open_paths (a1, b2); 1384 m2 = PenTool.merge_open_paths (b1, a2); 1385 1386 result.add (m1); 1387 result.add (m2); 1388 1389 return true; 1390 } 1391 1392 return false; 1393 } 1394 1395 static PathList split_paths (PathList pl) { 1396 PathList n = new PathList (); 1397 1398 n.append (pl); 1399 1400 foreach (Path p1 in pl.paths) { 1401 foreach (Path p2 in pl.paths) { 1402 if (p1 != p2) { 1403 if (split_path (p1, p2, n)) { 1404 n.paths.remove (p1); 1405 n.paths.remove (p2); 1406 return split_paths (n); 1407 } 1408 } 1409 } 1410 } 1411 1412 return n; 1413 } 1414 1415 static PathList get_parts_self (Path path, PathList? paths = null) { 1416 PathList pl; 1417 PathList r; 1418 1419 r = paths == null ? new PathList () : (!) paths; 1420 pl = split (path); 1421 1422 foreach (Path part in pl.paths) { 1423 if (!has_self_intersection (part)) { 1424 r.add (part); 1425 } else { 1426 get_parts_self (part, r); 1427 } 1428 } 1429 1430 if (r.paths.size == 0) { 1431 warning ("No parts in path"); 1432 } 1433 1434 return r; 1435 } 1436 1437 1438 static bool has_intersection_points (Path path) { 1439 foreach (EditPoint p in path.points) { 1440 if ((p.flags & EditPoint.INTERSECTION) > 0) { 1441 return true; 1442 } 1443 } 1444 return false; 1445 } 1446 1447 /** Split one path at intersection points in two parts. */ 1448 static PathList split (Path path) { 1449 Path new_path; 1450 PathList pl; 1451 int i; 1452 1453 if (!has_intersection_points (path)) { 1454 add_self_intersection_points (path); 1455 } else { 1456 warning ("points already created."); 1457 } 1458 1459 foreach (EditPoint p in path.points) { 1460 if (insides (p, path) == 1) { 1461 path.set_new_start (p); 1462 path.close (); 1463 break; 1464 } 1465 } 1466 1467 i = mark_intersection_as_deleted (path); 1468 1469 if (!(i == 0 || i == 2)) { 1470 warning (@"Split should only create two parts, $i points will be deleted."); 1471 } 1472 1473 new_path = path.copy (); 1474 pl = get_remaining_points (new_path); 1475 1476 return pl; 1477 } 1478 1479 static PathList process_deleted_control_points (Path path) { 1480 PathList paths, nl, pl, rl, result; 1481 1482 paths = new PathList (); 1483 rl = new PathList (); 1484 pl = new PathList (); 1485 nl = new PathList (); 1486 1487 if (!path.has_deleted_point ()) { 1488 return pl; 1489 } 1490 1491 pl.add (path); 1492 1493 foreach (Path p in pl.paths) { 1494 nl = p.process_deleted_points (); 1495 1496 if (nl.paths.size > 0) { 1497 rl.append (nl); 1498 rl.paths.remove (p); 1499 } 1500 } 1501 1502 result = new PathList (); 1503 foreach (Path p in rl.paths) { 1504 pl = process_deleted_control_points (p); 1505 1506 if (pl.paths.size > 0) { 1507 result.append (pl); 1508 } else { 1509 result.add (p); 1510 } 1511 } 1512 1513 for (int i = 1; i < result.paths.size; i++) { 1514 result.paths.get (i).reverse (); 1515 } 1516 1517 paths.append (result); 1518 1519 return paths; 1520 } 1521 1522 static PathList get_remaining_points (Path old_path) { 1523 PathList pl; 1524 1525 old_path.close (); 1526 pl = process_deleted_control_points (old_path); 1527 1528 if (pl.paths.size == 0) { 1529 pl.add (old_path); 1530 } 1531 1532 foreach (Path pn in pl.paths) { 1533 pn.close (); 1534 } 1535 1536 return pl; 1537 } 1538 1539 static bool has_self_intersection (Path path) { 1540 bool intersection = false; 1541 1542 path.all_segments ((ep1, ep2) => { 1543 double ix, iy; 1544 EditPoint p1, p2; 1545 1546 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true)) { 1547 intersection = true; 1548 return false; 1549 } 1550 1551 return true; 1552 }); 1553 1554 return intersection; 1555 } 1556 1557 static bool add_self_intersection_points (Path path, bool only_offsets = false) { 1558 bool intersection = false; 1559 1560 path.all_segments ((ep1, ep2) => { 1561 double ix, iy; 1562 EditPoint p1, p2; 1563 1564 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) { 1565 add_intersection (path, ep1, ep2, ix, iy); 1566 add_intersection (path, p1, p2, ix, iy); 1567 1568 intersection = true; 1569 return false; 1570 } 1571 1572 return true; 1573 }); 1574 1575 return intersection; 1576 } 1577 1578 static EditPoint add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) { 1579 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> (); 1580 EditPoint ep1 = new EditPoint (); 1581 EditPoint ep2 = new EditPoint (); 1582 EditPoint ep3 = new EditPoint (); 1583 double d; 1584 1585 if (next == path.get_first_point ()) { 1586 ep1.prev = null; 1587 } else { 1588 ep1.prev = prev; 1589 } 1590 1591 ep1.prev = prev; 1592 ep1.next = ep2; 1593 ep1.flags |= EditPoint.NEW_CORNER | EditPoint.SPLIT_POINT; 1594 ep1.type = prev.type; 1595 ep1.x = px; 1596 ep1.y = py; 1597 ep1.color = c; 1598 n.add (ep1); 1599 1600 ep2.prev = ep1; 1601 ep2.next = ep3; 1602 ep2.flags |= EditPoint.INTERSECTION | EditPoint.SPLIT_POINT; 1603 ep2.type = prev.type; 1604 ep2.x = px; 1605 ep2.y = py; 1606 ep2.color = c; 1607 n.add (ep2); 1608 1609 ep3.prev = ep2; 1610 ep3.next = next; 1611 ep3.flags |= EditPoint.NEW_CORNER | EditPoint.SPLIT_POINT; 1612 ep3.type = prev.type; 1613 ep3.x = px; 1614 ep3.y = py; 1615 ep3.color = c; 1616 n.add (ep3); 1617 1618 next.get_left_handle ().convert_to_line (); 1619 1620 foreach (EditPoint np in n) { 1621 np = path.add_point_after (np, np.prev); 1622 path.create_list (); 1623 } 1624 1625 PenTool.convert_point_to_line (ep1, true); 1626 PenTool.convert_point_to_line (ep2, true); 1627 PenTool.convert_point_to_line (ep3, true); 1628 1629 ep1.recalculate_linear_handles (); 1630 ep2.recalculate_linear_handles (); 1631 ep3.recalculate_linear_handles (); 1632 1633 d = Path.distance_to_point (prev, next); 1634 prev.get_right_handle ().length *= Path.distance_to_point (prev, ep1) / d; 1635 next.get_left_handle ().length *= Path.distance_to_point (ep3, next) / d; 1636 1637 next.recalculate_linear_handles (); 1638 1639 return ep2; 1640 } 1641 1642 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next, 1643 out double ix, out double iy, 1644 bool skip_points_on_points = false) { 1645 double cross_x, cross_y; 1646 1647 ix = 0; 1648 iy = 0; 1649 1650 if (is_line (ep.x, ep.y, p1.x, p1.y, next.x, next.y)) { 1651 ix = p1.x; 1652 iy = p1.y; 1653 return true; 1654 } 1655 1656 if (is_line (ep.x, ep.y, p2.x, p2.y, next.x, next.y)) { 1657 ix = p2.x; 1658 iy = p2.y; 1659 return true; 1660 } 1661 1662 if (is_line (p1.x, p1.y, ep.x, ep.y, p2.x, p2.y)) { 1663 ix = ep.x; 1664 iy = ep.y; 1665 return true; 1666 } 1667 1668 if (is_line (p1.x, p1.y, next.x, next.y, p2.x, p2.y)) { 1669 ix = next.x; 1670 iy = next.y; 1671 return true; 1672 } 1673 1674 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y); 1675 1676 if (fmin (ep.x, next.x) <= cross_x <= fmax (ep.x, next.x) 1677 && fmin (ep.y, next.y) <= cross_y <= fmax (ep.y, next.y)) { 1678 // iterate to find intersection. 1679 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y) 1680 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) { 1681 1682 ix = cross_x; 1683 iy = cross_y; 1684 1685 return true; 1686 } 1687 } 1688 1689 return false; 1690 } 1691 1692 static bool segment_intersects (Path path, EditPoint ep, EditPoint next, 1693 out double ix, out double iy, 1694 out EditPoint ia, out EditPoint ib, 1695 bool skip_points_on_points = false, 1696 bool only_offsets = false) { 1697 1698 EditPoint p1, p2; 1699 bool intersection, inter; 1700 double iix, iiy; 1701 1702 double distance, min_distance; 1703 1704 intersection = false; 1705 1706 ix = 0; 1707 iy = 0; 1708 1709 iix = 0; 1710 iiy = 0; 1711 1712 ia = new EditPoint (); 1713 ib = new EditPoint (); 1714 1715 if (path.points.size == 0) { 1716 return false; 1717 } 1718 1719 min_distance = double.MAX; 1720 p1 = path.points.get (path.points.size - 1); 1721 for (int i = 0; i < path.points.size; i++) { 1722 p2 = path.points.get (i); 1723 1724 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0) 1725 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0) 1726 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0) 1727 && ((next.flags & EditPoint.STROKE_OFFSET) > 0); 1728 1729 if (!only_offsets || is_offset) { 1730 if (p1 != ep && p2 != next) { 1731 inter = segments_intersects (p1, p2, ep, next, out iix, out iiy, 1732 skip_points_on_points); 1733 1734 if (inter) { 1735 distance = Path.distance (ep.x, iix, ep.y, iiy); 1736 if (distance < min_distance) { 1737 ia = p1; 1738 ib = p2; 1739 ix = iix; 1740 iy = iiy; 1741 intersection = true; 1742 min_distance = distance; 1743 } 1744 } 1745 } 1746 } 1747 1748 p1 = p2; 1749 } 1750 1751 return intersection; 1752 } 1753 1754 /** @return true if p2 is on the line p1 to p3 */ 1755 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.01) { 1756 return fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3) 1757 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3) 1758 && is_flat (x1, y1, x2, y2, x3, y3, tolerance); 1759 } 1760 1761 public static bool is_flat (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.001) { 1762 double ds = Path.distance (x1, x3, y1, y3); 1763 double d1 = Path.distance (x1, x2, y1, y2); 1764 double d2 = Path.distance (x2, x3, y2, y3); 1765 double p = d1 / ds; 1766 double x = fabs ((x3 - x1) * p - (x2 - x1)) / ds; 1767 double y = fabs ((y3 - y1) * p - (y2 - y1)) / ds; 1768 double d = fabs (ds - (d1 + d2)) / ds; 1769 1770 return ds > 0.001 && d1 > 0.001 && d2 > 0.001 1771 && d < tolerance && x < tolerance && y < tolerance; 1772 } 1773 1774 // indside becomes outside in some paths 1775 static void remove_points_in_stroke (PathList pl) { 1776 PathList r; 1777 1778 foreach (Path p in pl.paths) { 1779 if (remove_points_in_stroke_for_path (p, pl, out r)) { 1780 pl.append (r); 1781 remove_points_in_stroke (pl); 1782 return; 1783 } 1784 } 1785 } 1786 1787 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) { 1788 EditPoint start_ep; 1789 EditPoint start_next; 1790 EditPoint start_prev; 1791 EditPoint end_ep = new EditPoint (); 1792 EditPoint end_next; 1793 EditPoint end_prev; 1794 1795 result = new PathList (); 1796 1797 for (int i = 1; i < p.points.size + 1; i++) { 1798 start_prev = p.points.get ((i - 1) % p.points.size); 1799 start_ep = p.points.get (i % p.points.size); 1800 start_next = p.points.get ((i + 1) % p.points.size); 1801 1802 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1803 for (int j = i; j < p.points.size + i; j++) { 1804 end_prev = p.points.get ((j - 1) % p.points.size); 1805 end_ep = p.points.get (j % p.points.size); 1806 end_next = p.points.get ((j + 1) % p.points.size); 1807 1808 1809 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1810 start_ep.flags = EditPoint.NONE; 1811 end_ep.flags = EditPoint.NONE; 1812 1813 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) { 1814 return true; 1815 } 1816 } 1817 } 1818 } 1819 1820 start_ep.flags = EditPoint.NONE; 1821 end_ep.flags = EditPoint.NONE; 1822 } 1823 1824 return false; 1825 } 1826 1827 static bool merge_segments (PathList pl, 1828 Path path1, EditPoint start1, EditPoint stop1, 1829 EditPoint start2, EditPoint stop2, 1830 out PathList result) { 1831 1832 result = new PathList (); 1833 1834 PathList r1; 1835 PathList r2; 1836 1837 foreach (Path path2 in pl.paths) { 1838 if (path2 != path1) { 1839 reset_intersections (path1); 1840 reset_intersections (path2); 1841 1842 if (add_merge_intersection_point (path1, path2, start1, stop1)) { 1843 if (add_merge_intersection_point (path1, path2, start2, stop2)) { 1844 1845 r1 = get_remaining_points (path1.copy ()); 1846 r2 = get_remaining_points (path2.copy ()); 1847 1848 if (r1.paths.size != 2) { 1849 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n"); 1850 reset_intersections (path1); 1851 reset_intersections (path2); 1852 return true; 1853 } 1854 1855 if (r2.paths.size != 2) { 1856 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n"); 1857 reset_intersections (path1); 1858 reset_intersections (path2); 1859 return true; 1860 } 1861 1862 pl.paths.remove (path1); 1863 pl.paths.remove (path2); 1864 1865 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (), 1866 r2.paths.get (0).get_first_point ()); 1867 1868 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (), 1869 r2.paths.get (1).get_first_point ()); 1870 1871 Path m1, m2; 1872 1873 if (d1 > d2) { 1874 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0)); 1875 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1)); 1876 } else { 1877 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0)); 1878 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1)); 1879 } 1880 1881 result.add (m1); 1882 result.add (m2); 1883 1884 return true; 1885 } else { 1886 reset_intersections (path1); 1887 reset_intersections (path2); 1888 } 1889 } else { 1890 reset_intersections (path1); 1891 reset_intersections (path2); 1892 } 1893 } 1894 } 1895 1896 return false; 1897 } 1898 1899 static void reset_intersections (Path p) { 1900 foreach (EditPoint ep in p.points) { 1901 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION; 1902 ep.flags &= uint.MAX ^ EditPoint.COPIED; 1903 ep.flags &= uint.MAX ^ EditPoint.SELF_INTERSECTION; 1904 ep.deleted = false; 1905 } 1906 p.remove_points_on_points (); 1907 } 1908 1909 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) { 1910 double ix, iy; 1911 bool intersection; 1912 1913 intersection = false; 1914 ix = 0; 1915 iy = 0; 1916 path2.all_segments ((p1, p2) => { 1917 int i; 1918 1919 intersection = segments_intersects (first, next, p1, p2, out ix, out iy); 1920 1921 if (intersection) { 1922 add_intersection (path1, first, next, ix, iy); 1923 add_intersection (path2, p1, p2, ix, iy); 1924 1925 i = mark_intersection_as_deleted (path1); 1926 i = mark_intersection_as_deleted (path2); 1927 } 1928 1929 return !intersection; 1930 }); 1931 1932 return intersection; 1933 } 1934 1935 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) { 1936 outline = new Path (); 1937 foreach (Path p in pl.paths) { 1938 if (p != ps.path) { 1939 if (is_inside (ps.point, p)) { 1940 outline = p; 1941 return true; 1942 } 1943 } 1944 } 1945 1946 return false; 1947 } 1948 1949 static PathList get_all_parts (PathList pl) { 1950 PathList m; 1951 bool intersects = false; 1952 PathList r = new PathList (); 1953 1954 foreach (Path p in pl.paths) { 1955 if (has_self_intersection (p)) { 1956 m = get_parts (p); 1957 r.append (m); 1958 intersects = true; 1959 } else { 1960 r.add (p); 1961 } 1962 } 1963 1964 foreach (Path p in r.paths) { 1965 p.close (); 1966 p.update_region_boundaries (); 1967 } 1968 1969 if (intersects) { 1970 return get_all_parts (r); 1971 } 1972 1973 return r; 1974 } 1975 1976 public static PathList merge (PathList pl) { 1977 bool error = false; 1978 PathList m; 1979 PathList r = pl; 1980 Path p1, p2; 1981 1982 r = get_all_parts (r); 1983 1984 while (paths_has_intersection (r, out p1, out p2)) { 1985 if (merge_path (p1, p2, out m, out error)) { 1986 r.paths.remove (p1); 1987 r.paths.remove (p2); 1988 1989 foreach (Path np in m.paths) { 1990 np.remove_points_on_points (); 1991 r.add (np); 1992 } 1993 1994 r = get_all_parts (r); 1995 } else { 1996 warning ("Not merged."); 1997 error = true; 1998 } 1999 2000 if (error) { 2001 warning ("Merge error"); 2002 break; 2003 } 2004 } 2005 2006 if (!error) { 2007 remove_merged_parts (r); 2008 } 2009 2010 foreach (Path p in r.paths) { 2011 p.close (); 2012 p.recalculate_linear_handles (); 2013 } 2014 2015 return r; 2016 } 2017 2018 static void remove_merged_parts (PathList r) { 2019 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> (); 2020 int c; 2021 2022 foreach (Path p in r.paths) { 2023 p.update_region_boundaries (); 2024 } 2025 2026 foreach (Path p in r.paths) { 2027 c = counters (r, p); 2028 2029 if (c % 2 == 0) { 2030 if (!p.is_clockwise ()) { 2031 remove.add (p); 2032 } 2033 } else { 2034 if (p.is_clockwise ()) { 2035 remove.add (p); 2036 } 2037 } 2038 } 2039 2040 foreach (Path p in remove) { 2041 r.paths.remove (p); 2042 } 2043 } 2044 2045 public static PathList get_insides (PathList pl, Path path) { 2046 bool inside = false; 2047 PathList insides = new PathList (); 2048 2049 foreach (Path p in pl.paths) { 2050 if (p.points.size > 1 2051 && p != path 2052 && path.boundaries_intersecting (p)) { 2053 2054 inside = true; 2055 foreach (EditPoint ep in path.points) { 2056 if (!is_inside (ep, p)) { 2057 inside = false; 2058 break; 2059 } 2060 } 2061 2062 if (inside) { 2063 insides.add (p); // add the flat inside to the list 2064 } 2065 } 2066 } 2067 2068 return insides; 2069 } 2070 2071 public static int counters (PathList pl, Path path) { 2072 int inside_count = 0; 2073 bool inside; 2074 2075 foreach (Path p in pl.paths) { 2076 inside = true; 2077 2078 if (p.points.size > 1 2079 && p != path 2080 && path.boundaries_intersecting (p)) { 2081 2082 foreach (EditPoint ep in path.points) { 2083 if (!is_inside (ep, p)) { 2084 inside = false; 2085 break; 2086 } 2087 } 2088 2089 if (inside) { 2090 inside_count++; 2091 } 2092 } 2093 } 2094 2095 return inside_count; 2096 } 2097 2098 public static bool is_inside (EditPoint point, Path path) { 2099 EditPoint prev; 2100 bool inside = false; 2101 2102 if (path.points.size <= 1) { 2103 return false; 2104 } 2105 2106 prev = path.points.get (path.points.size - 1); 2107 2108 foreach (EditPoint p in path.points) { 2109 if ((fabs (p.x - point.x) < 0.1 && fabs (p.y - point.y) < 0.1) 2110 || (fabs (prev.x - point.x) < 0.1 && fabs (prev.y - point.y) < 0.1)) { 2111 return true; 2112 } else if ((p.y > point.y) != (prev.y > point.y) 2113 && point.x < (prev.x - p.x) * (point.y - p.y) / (prev.y - p.y) + p.x) { 2114 inside = !inside; 2115 } 2116 2117 prev = p; 2118 } 2119 2120 return inside; 2121 } 2122 2123 public static int insides (EditPoint point, Path path) { 2124 EditPoint prev; 2125 int inside = 0; 2126 2127 if (path.points.size <= 1) { 2128 return 0; 2129 } 2130 2131 prev = path.get_last_point (); 2132 2133 foreach (EditPoint start in path.points) { 2134 if (start.x == point.x && point.y == start.y) { 2135 inside++; 2136 } else if ((start.y > point.y) != (prev.y > point.y) 2137 && point.x < (prev.x - start.x) * (point.y - start.y) / (prev.y - start.y) + start.x) { 2138 inside++; 2139 } 2140 2141 prev = start; 2142 } 2143 2144 return inside; 2145 } 2146 2147 static bool merge_path (Path path1, Path path2, out PathList merged_paths, out bool error) { 2148 IntersectionList intersections; 2149 EditPoint ep1, next, p1, p2, pp1, pp2; 2150 Path path, other, merged; 2151 PathList r, other_paths, result; 2152 bool intersects; 2153 int s, i; 2154 double ix, iy, iix, iiy; 2155 bool merge = false; 2156 EditPoint intersection_point, other_intersection_point; 2157 bool path1_direction, path2_direction; 2158 2159 error = false; 2160 merged_paths = new PathList (); 2161 intersections = new IntersectionList (); 2162 2163 if (path1.points.size == 0) { 2164 return false; 2165 } 2166 2167 if (path2.points.size == 0) { 2168 return false; 2169 } 2170 2171 reset_intersections (path1); 2172 reset_intersections (path2); 2173 2174 iix = 0; 2175 iiy = 0; 2176 2177 result = new PathList (); 2178 2179 if (path1.points.size == 0 || path2.points.size == 0) { 2180 warning ("No points in path."); 2181 error = true; 2182 return false; 2183 } 2184 2185 if (!path1.boundaries_intersecting (path2)) { 2186 return false; 2187 } 2188 2189 Path original_path1 = path1.copy (); 2190 Path original_path2 = path2.copy (); 2191 2192 s = 0; 2193 foreach (EditPoint e in original_path1.points) { 2194 if (!is_inside (e, original_path2) 2195 && insides (e, original_path1) == 1) { // FIXME: later as well 2196 break; 2197 } 2198 s++; 2199 } 2200 2201 if (s >= path1.points.size) { 2202 Path t; 2203 t = original_path1; 2204 original_path1 = original_path2; 2205 original_path2 = t; 2206 s = 0; 2207 foreach (EditPoint e in original_path1.points) { 2208 if (!is_inside (e, original_path2)) { 2209 break; 2210 } 2211 s++; 2212 } 2213 } 2214 2215 if (s >= original_path1.points.size) { 2216 warning ("No start point found."); 2217 error = true; 2218 return false; 2219 } 2220 2221 path = original_path1; 2222 other = original_path2; 2223 2224 other_paths = new PathList (); 2225 r = new PathList (); 2226 other_paths.add (path); 2227 other_paths.add (other); 2228 intersects = false; 2229 p1 = new EditPoint (); 2230 p2 = new EditPoint (); 2231 pp1 = new EditPoint (); 2232 pp2 = new EditPoint (); 2233 2234 ix = 0; 2235 iy = 0; 2236 i = s; 2237 merged = new Path (); 2238 2239 path1_direction = is_clockwise (original_path1); 2240 path2_direction = is_clockwise (original_path1); 2241 2242 while (true) { 2243 ep1 = path.points.get (i % path.points.size); 2244 next = path.points.get ((i + 1) % path.points.size); 2245 2246 if ((ep1.flags & EditPoint.COPIED) > 0) { 2247 if (merge) { 2248 merged.close (); 2249 result.add (merged.copy ()); 2250 } 2251 2252 merged = new Path (); 2253 2254 bool find_parts = false; 2255 Intersection new_start = new Intersection.empty (); 2256 foreach (Intersection inter in intersections.points) { 2257 if (!inter.done && !find_parts) { 2258 find_parts = true; 2259 new_start = inter; 2260 break; 2261 } 2262 } 2263 2264 if (!find_parts) { 2265 break; // done, no more parts to merge 2266 } else { 2267 // set start point for next part 2268 path = new_start.other_path; 2269 2270 if (path.points.size == 0) { 2271 warning ("No points."); 2272 error = true; 2273 return false; 2274 } 2275 2276 i = index_of (path, new_start.get_point (path)); 2277 2278 if (i < 0) { 2279 warning ("Start point not found."); 2280 error = true; 2281 return false; 2282 } 2283 2284 ep1 = path.points.get (i % path.points.size); 2285 next = path.points.get ((i + 1) % path.points.size); 2286 2287 if ((ep1.flags & EditPoint.INTERSECTION) == 0) { 2288 warning ("Not starting on an intersection point."); 2289 error = true; 2290 return false; 2291 } 2292 2293 new_start.done = true; 2294 } 2295 } 2296 2297 intersects = false; 2298 2299 double dm; 2300 double d; 2301 2302 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 2303 Intersection current_intersection; 2304 bool continue_on_other_path; 2305 current_intersection = intersections.get_point (ep1, out continue_on_other_path); 2306 current_intersection.done = true; 2307 2308 // take the other part of an intersection 2309 if ((next.flags & EditPoint.COPIED) != 0) { 2310 bool next_is_intersection = false; 2311 bool next_continue_on_other_path; 2312 2313 next_is_intersection = ((next.flags & EditPoint.INTERSECTION) > 0); 2314 2315 if (next_is_intersection) { 2316 Intersection next_intersection = intersections.get_point (next, out next_continue_on_other_path); 2317 2318 ep1.flags |= EditPoint.COPIED; 2319 merged.add_point (ep1.copy ()); 2320 2321 if (!next_intersection.done) { 2322 EditPoint new_start_point; 2323 2324 path = next_continue_on_other_path 2325 ? next_intersection.other_path : next_intersection.path; 2326 2327 new_start_point = next_continue_on_other_path 2328 ? next_intersection.other_point : next_intersection.point; 2329 2330 i = index_of (path, new_start_point); 2331 2332 if (i < 0) { 2333 warning ("Point not found in path.\n"); 2334 error = true; 2335 return false; 2336 } 2337 2338 ep1 = path.points.get (i % path.points.size); 2339 next = path.points.get ((i + 1) % path.points.size); 2340 } else { 2341 warning ("Part is already created.\n"); 2342 error = true; 2343 return false; 2344 } 2345 } else { 2346 ep1.flags |= EditPoint.COPIED; 2347 merged.add_point (ep1.copy ()); 2348 2349 EditPoint new_start_point; 2350 2351 if ((next.flags & EditPoint.COPIED) > 0) { 2352 path = current_intersection.get_other_path (path); 2353 new_start_point = current_intersection.get_point (path); 2354 i = index_of (path, new_start_point); 2355 2356 if (i < 0) { 2357 warning ("Point not found in path."); 2358 error = true; 2359 return false; 2360 } 2361 2362 ep1 = path.points.get (i % path.points.size); 2363 next = path.points.get ((i + 1) % path.points.size); 2364 2365 if ((next.flags & EditPoint.INTERSECTION) > 0) { 2366 warning ("Wrong type."); 2367 error = true; 2368 return false; 2369 } 2370 2371 if ((next.flags & EditPoint.COPIED) > 0) { 2372 merged.add_point (ep1.copy ()); 2373 continue; 2374 } 2375 } else { 2376 ep1.flags |= EditPoint.COPIED; 2377 merged.add_point (ep1.copy ()); 2378 } 2379 } 2380 } else { 2381 ep1.flags |= EditPoint.COPIED; 2382 2383 if (path1_direction == path2_direction) { 2384 if (!is_inside (ep1, original_path1)) { 2385 merged.add_point (ep1.copy ()); 2386 } 2387 } else { 2388 merged.add_point (ep1.copy ()); 2389 } 2390 } 2391 2392 current_intersection.done = true; 2393 } else { 2394 // find new intersection 2395 dm = double.MAX; 2396 foreach (Path o in other_paths.paths) { 2397 bool inter = segment_intersects (o, ep1, next, out iix, out iiy, 2398 out pp1, out pp2, false, false); 2399 d = Path.distance (ep1.x, iix, ep1.y, iiy); 2400 if (d < dm && inter) { 2401 other = o; 2402 dm = d; 2403 intersects = true; 2404 p1 = pp1; 2405 p2 = pp2; 2406 ix = iix; 2407 iy = iiy; 2408 } 2409 2410 if (d < 0.0001) { 2411 intersects = false; 2412 } 2413 } 2414 2415 if (intersects) { 2416 merged.add_point (ep1.copy ()); 2417 ep1.flags |= EditPoint.COPIED; 2418 2419 intersection_point = add_intersection (path, ep1, next, ix, iy); 2420 other_intersection_point = add_intersection (other, p1, p2, ix, iy); 2421 2422 bool g = false; 2423 foreach (Intersection old_intersection in intersections.points) { 2424 if (old_intersection.point == intersection_point 2425 || old_intersection.other_point == other_intersection_point) { 2426 old_intersection.done = true; 2427 g = true; 2428 } 2429 } 2430 2431 if (!g) { 2432 Intersection ip = new Intersection (intersection_point, path, other_intersection_point, other); 2433 intersections.points.add (ip); 2434 } 2435 2436 merged.add_point (intersection_point.copy ()); 2437 intersection_point.flags |= EditPoint.COPIED; 2438 2439 i = index_of (other, other_intersection_point); 2440 2441 if (i < 0) { 2442 warning (@"Point not found ($i)."); 2443 break; 2444 } 2445 2446 path = other; 2447 merge = true; 2448 } else { 2449 ep1.flags |= EditPoint.COPIED; 2450 merged.add_point (ep1.copy ()); 2451 2452 PointSelection ps; 2453 Path outline; 2454 2455 // remove points inside of path 2456 if (is_clockwise (original_path2)) { 2457 ps = new PointSelection (ep1, merged); 2458 if (is_inside_of_path (ps, result, out outline)) { 2459 ep1.deleted = true; 2460 } 2461 } 2462 } 2463 } 2464 2465 i++; 2466 } 2467 2468 if (merge) { 2469 original_path1.remove_points_on_points (); 2470 original_path2.remove_points_on_points (); 2471 original_path1.remove_deleted_points (); 2472 original_path2.remove_deleted_points (); 2473 2474 foreach (Path np in result.paths) { 2475 Path p = np.copy (); 2476 bool has_direction = true; 2477 2478 p.remove_points_on_points (); 2479 2480 if (has_direction) { 2481 p.close (); 2482 reset_intersections (p); 2483 merged_paths.append (get_parts (p)); 2484 p.update_region_boundaries (); 2485 p.recalculate_linear_handles (); 2486 } 2487 } 2488 } 2489 2490 return merge && !error; 2491 } 2492 2493 static int index_of (Path p, EditPoint ep) { 2494 int i = 0; 2495 foreach (EditPoint e in p.points) { 2496 if (e == ep) { 2497 return i; 2498 } 2499 i++; 2500 } 2501 2502 return -1; 2503 } 2504 2505 public static int counters_in_point_in_path (Path p, EditPoint ep) { 2506 int inside_count = 0; 2507 bool inside; 2508 2509 if (p.points.size > 1) { 2510 inside = true; 2511 2512 if (!is_inside (ep, p)) { 2513 inside = false; 2514 } 2515 2516 if (inside) { 2517 inside_count++; 2518 } 2519 } 2520 2521 return inside_count; 2522 } 2523 2524 static int mark_intersection_as_deleted (Path path) { 2525 int i = 0; 2526 2527 foreach (EditPoint p in path.points) { 2528 if ((p.flags & EditPoint.INTERSECTION) > 0) { 2529 p.deleted = true; 2530 i++; 2531 } 2532 } 2533 2534 return i; 2535 } 2536 2537 /** @param n number of interrsections to find per path. */ 2538 static bool add_intersection_points (Path path1, Path path2, int n = 1) { 2539 bool intersection = false; 2540 int found = 0; 2541 2542 path1.all_segments ((ep1, ep2) => { 2543 double ix, iy; 2544 EditPoint p1, p2; 2545 bool i; 2546 2547 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 2548 out p1, out p2, true); 2549 2550 if (i) { 2551 add_intersection (path1, ep1, ep2, ix, iy); 2552 add_intersection (path2, p1, p2, ix, iy); 2553 intersection = true; 2554 found++; 2555 return found < n; 2556 } 2557 2558 return true; 2559 }); 2560 2561 if (intersection && found != n) { 2562 warning (@"Wrong number of points, $found != $n"); 2563 } 2564 2565 return intersection; 2566 } 2567 2568 /** @param n number of interrsections to find per path. */ 2569 static bool has_intersection (Path path1, Path path2) { 2570 bool intersection = false; 2571 2572 if (!path1.boundaries_intersecting (path2)) { 2573 return false; 2574 } 2575 2576 path1.all_segments ((ep1, ep2) => { 2577 double ix, iy; 2578 EditPoint p1, p2; 2579 bool i; 2580 2581 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 2582 out p1, out p2, true); 2583 2584 if (i) { 2585 intersection = true; 2586 } 2587 2588 return !intersection; 2589 }); 2590 2591 return intersection; 2592 } 2593 2594 static bool paths_has_intersection (PathList r, out Path path1, out Path path2) { 2595 int i, j; 2596 path1 = new Path (); 2597 path2 = new Path (); 2598 2599 i = 0; 2600 foreach (Path p1 in r.paths) { 2601 2602 j = 0; 2603 foreach (Path p2 in r.paths) { 2604 if (p1 != p2) { 2605 if (has_intersection (p1, p2)) { 2606 path1 = p1; 2607 path2 = p2; 2608 return true; 2609 } 2610 } 2611 j++; 2612 } 2613 i++; 2614 } 2615 return false; 2616 } 2617 2618 public static bool has_points_outside (PathList pl, Path p) { 2619 if (pl.paths.size != 2) { 2620 warning ("Stroke should only create two parts."); 2621 return false; 2622 } 2623 2624 foreach (Path path in pl.paths) { 2625 if (path != p) { 2626 foreach (EditPoint ep in p.points) { 2627 if (!is_inside (ep, path)) { 2628 return true; 2629 } 2630 } 2631 } 2632 } 2633 2634 return false; 2635 } 2636 2637 static bool is_clockwise (Path p) { 2638 double sum = 0; 2639 EditPoint p1, p2; 2640 2641 EditPointHandle l, r; 2642 2643 p.recalculate_linear_handles (); 2644 2645 if (p.points.size < 3) { 2646 return true; 2647 } 2648 2649 for (int i = 0; i < p.points.size; i++) { 2650 p1 = p.points.get (i); 2651 p2 = p.points.get ((i + 1) % p.points.size); 2652 2653 l = p1.get_left_handle (); 2654 r = p1.get_right_handle (); 2655 if (!(fabs (l.angle - r.angle) < 0.0001 && l.length > 0.01 && r.length > 0.01)) { 2656 sum += (p2.x - p1.x) * (p2.y + p1.y); 2657 } 2658 } 2659 2660 return sum > 0; 2661 } 2662 2663 public static PathList create_stroke (Path original_path, 2664 double thickness, bool fast) { 2665 2666 PathList pl; 2667 EditPoint p1, p2, p3; 2668 EditPoint previous, previous_inside, start, start_inside; 2669 2670 Path side1, side2; 2671 2672 double x, y, x2, y2, x3, y3; 2673 int size; 2674 bool flat, f_next, f_bigger; 2675 int i; 2676 2677 double tolerance; 2678 double step_increment; 2679 double step_size; 2680 EditPoint corner1, corner1_inside; 2681 double step; 2682 double min_increment; 2683 2684 EditPointHandle l, r; 2685 2686 Path path = original_path.copy (); 2687 2688 int keep; 2689 bool on_curve; 2690 2691 pl = new PathList (); 2692 size = path.is_open () ? path.points.size - 1 : path.points.size; 2693 2694 side1 = new Path (); 2695 side2 = new Path (); 2696 2697 foreach (EditPoint ph in path.points) { 2698 if (ph.type == PointType.HIDDEN) { 2699 ph.type = PointType.CUBIC; 2700 } 2701 } 2702 path.remove_deleted_points (); 2703 2704 if (path.points.size < 2) { 2705 return pl; 2706 } 2707 2708 previous = new EditPoint (); 2709 previous_inside = new EditPoint (); 2710 corner1 = new EditPoint (); 2711 corner1_inside = new EditPoint (); 2712 2713 if (path.is_open () || fast) { 2714 p1 = path.points.get (0); 2715 p2 = path.points.get (1 % path.points.size); 2716 2717 get_segment (thickness, 0, 0.00001, p1, p2, out start); 2718 get_segment (-thickness, 0, 0.00001, p1, p2, out start_inside); 2719 2720 previous = start.copy (); 2721 previous_inside = start_inside.copy (); 2722 2723 previous.flags |= EditPoint.CURVE_KEEP; 2724 previous_inside.flags |= EditPoint.CURVE_KEEP; 2725 2726 side1.add_point (previous); 2727 side2.add_point (previous_inside); 2728 } 2729 2730 min_increment = 0.013; 2731 2732 for (i = 0; i < size; i++) { 2733 p1 = path.points.get (i % path.points.size); 2734 p2 = path.points.get ((i + 1) % path.points.size); 2735 p3 = path.points.get ((i + 2) % path.points.size); 2736 2737 tolerance = 0.01; // 0.13 / sqrt (stroke_width) 2738 step_increment = 1.05; 2739 step_size = 0.039; // / stroke_width; 2740 2741 corner1 = new EditPoint (); 2742 2743 if (p1.type == PointType.HIDDEN 2744 || p2.type == PointType.HIDDEN) { 2745 continue; 2746 } 2747 2748 get_segment (thickness, 0, 0.00001, p1, p2, out start); 2749 get_segment (-thickness, 0, 0.00001, p1, p2, out start_inside); 2750 2751 previous = start.copy (); 2752 previous_inside = start_inside.copy (); 2753 2754 previous.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2755 previous_inside.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2756 2757 side1.add_point (previous); 2758 side2.add_point (previous_inside); 2759 2760 step = step_size; 2761 keep = 0; 2762 step_size = 0.01; 2763 2764 while (step < 1 - 2 * step_size) { 2765 Path.get_point_for_step (p1, p2, step, out x, out y); 2766 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2); 2767 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3); 2768 2769 flat = is_flat (x, y, x2, y2, x3, y3, tolerance); 2770 2771 Path.get_point_for_step (p1, p2, step, out x, out y); 2772 Path.get_point_for_step (p1, p2, step + step_size / step_increment, out x2, out y2); 2773 Path.get_point_for_step (p1, p2, step + 2 * step_size / step_increment, out x3, out y3); 2774 2775 f_next = is_flat (x, y, x2, y2, x3, y3, tolerance); 2776 2777 Path.get_point_for_step (p1, p2, step, out x, out y); 2778 Path.get_point_for_step (p1, p2, step + step_size * step_increment, out x2, out y2); 2779 Path.get_point_for_step (p1, p2, step + 2 * step_size * step_increment, out x3, out y3); 2780 2781 f_bigger = is_flat (x, y, x2, y2, x3, y3, tolerance); 2782 2783 if (!flat && !f_next && step_size > min_increment) { 2784 step_size /= step_increment; 2785 continue; 2786 } 2787 2788 if (flat && f_bigger && step_size < 0.1) { 2789 step_size *= step_increment; 2790 continue; 2791 } 2792 2793 get_segment (thickness, step, step_size, p1, p2, out corner1); 2794 get_segment (-thickness, step, step_size, p1, p2, out corner1_inside); 2795 2796 previous.get_right_handle ().length *= step_size; 2797 corner1.get_left_handle ().length *= step_size; 2798 previous_inside.get_right_handle ().length *= step_size; 2799 corner1_inside.get_left_handle ().length *= step_size; 2800 2801 previous = corner1.copy (); 2802 previous_inside = corner1_inside.copy (); 2803 2804 if (keep == 0 && step > 0.3) { // keep two points per segment 2805 on_curve = true; 2806 keep++; 2807 } else if (keep == 1 && step > 0.6) { 2808 on_curve = true; 2809 keep++; 2810 } else { 2811 on_curve = false; 2812 } 2813 2814 if (!on_curve) { 2815 previous.flags |= EditPoint.CURVE; 2816 previous_inside.flags |= EditPoint.CURVE; 2817 } else { 2818 previous.flags |= EditPoint.CURVE_KEEP; 2819 previous_inside.flags |= EditPoint.CURVE_KEEP; 2820 } 2821 2822 side1.add_point (previous); 2823 side2.add_point (previous_inside); 2824 2825 step += step_size; 2826 } 2827 2828 previous.get_right_handle ().length *= step_size; 2829 corner1.get_left_handle ().length *= step_size; 2830 previous_inside.get_right_handle ().length *= step_size; 2831 corner1_inside.get_left_handle ().length *= step_size; 2832 2833 get_segment (thickness, 1 - 0.00001, 0.00001, p1, p2, out corner1); 2834 get_segment (-thickness, 1 - 0.00001, 0.00001, p1, p2, out corner1_inside); 2835 2836 previous = corner1.copy (); 2837 previous_inside = corner1_inside.copy (); 2838 2839 previous.get_right_handle ().length *= step_size; 2840 previous.get_left_handle ().length *= step_size; 2841 previous_inside.get_right_handle ().length *= step_size; 2842 previous_inside.get_left_handle ().length *= step_size; 2843 2844 previous.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2845 previous_inside.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2846 2847 side1.add_point (previous); 2848 side2.add_point (previous_inside); 2849 2850 l = p2.get_left_handle (); 2851 r = p2.get_right_handle (); 2852 2853 if (fabs ((l.angle + r.angle + PI) % (2 * PI) - PI) > 0.005) { 2854 if (!path.is_open () || i < size - 1) { 2855 get_segment (thickness, 0, 0.00001, p2, p3, out start); 2856 add_corner (side1, previous, start, p2.copy (), thickness); 2857 2858 get_segment (-thickness, 0, 0.00001, p2, p3, out start); 2859 add_corner (side2, previous_inside, start, p2.copy (), thickness); 2860 } 2861 } 2862 2863 if (fast) { 2864 EditPoint s1, s2; 2865 bool open; 2866 2867 convert_to_curve (side1); 2868 convert_to_curve (side2); 2869 2870 side2.reverse (); 2871 s1 = side1.get_last_point ().copy (); 2872 s2 = side2.get_first_point ().copy (); 2873 2874 s1.flags &= EditPoint.CURVE ^ EditPoint.ALL; 2875 s2.flags &= EditPoint.CURVE ^ EditPoint.ALL; 2876 2877 s1.convert_to_line (); 2878 s2.convert_to_line (); 2879 2880 open = path.is_open (); 2881 2882 if (!open) { 2883 path.reopen (); 2884 } 2885 2886 pl.append (merge_stroke_parts (path, side1, side2)); 2887 2888 if (!open) { 2889 path.close (); 2890 } 2891 2892 side1 = new Path (); 2893 side2 = new Path (); 2894 2895 get_segment (thickness, 0, 0.00001, p2, p3, out start); 2896 get_segment (-thickness, 0, 0.00001, p2, p3, out start_inside); 2897 2898 previous = start.copy (); 2899 previous_inside = start_inside.copy (); 2900 2901 previous.flags |= EditPoint.CURVE; 2902 previous_inside.flags |= EditPoint.CURVE; 2903 2904 side1.add_point (previous); 2905 side2.add_point (previous_inside); 2906 } 2907 } 2908 2909 if (!fast) { 2910 side1.remove_points_on_points (); 2911 side2.remove_points_on_points (); 2912 2913 convert_to_curve (side1); 2914 convert_to_curve (side2); 2915 2916 side2.reverse (); 2917 2918 pl = merge_stroke_parts (path, side1, side2); 2919 } 2920 2921 if (fast) { 2922 foreach (Path p in pl.paths) { 2923 p.close (); 2924 convert_to_curve (p); 2925 } 2926 } 2927 2928 return pl; 2929 } 2930 2931 static void convert_to_curve (Path path) { 2932 if (path.is_open ()) { 2933 path.get_first_point ().flags &= EditPoint.ALL ^ EditPoint.CURVE; 2934 path.get_last_point ().flags &= EditPoint.ALL ^ EditPoint.CURVE; 2935 } 2936 2937 path.recalculate_linear_handles (); 2938 path.remove_points_on_points (); 2939 2940 foreach (EditPoint ep in path.points) { 2941 if ((ep.flags & EditPoint.SEGMENT_END) == 0) { 2942 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) { 2943 ep.convert_to_curve (); 2944 } 2945 } 2946 } 2947 2948 foreach (EditPoint ep in path.points) { 2949 if ((ep.flags & EditPoint.SEGMENT_END) == 0) { 2950 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) { 2951 ep.set_tie_handle (true); 2952 } 2953 } 2954 } 2955 2956 foreach (EditPoint ep in path.points) { 2957 if ((ep.flags & EditPoint.SEGMENT_END) == 0) { 2958 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) { 2959 ep.process_tied_handle (); 2960 } 2961 } 2962 } 2963 } 2964 2965 public static void get_segment (double stroke_thickness, double step, double step_size, 2966 EditPoint p1, EditPoint p2, out EditPoint ep1) { 2967 2968 double thickness = stroke_thickness / 2; 2969 Path overlay; 2970 double x, y, x2, y2, x3, y3; 2971 EditPoint corner1, corner2, corner3; 2972 PointType type; 2973 2974 Path.get_point_for_step (p1, p2, step, out x, out y); 2975 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2); 2976 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3); 2977 2978 overlay = new Path (); 2979 2980 type = p1.get_right_handle ().type; 2981 corner1 = new EditPoint (x, y, type); 2982 corner2 = new EditPoint (x2, y2, type); 2983 corner3 = new EditPoint (x3, y3, type); 2984 2985 corner2.convert_to_line (); 2986 2987 overlay.add_point (corner1); 2988 overlay.add_point (corner2); 2989 overlay.add_point (corner3); 2990 2991 overlay.close (); 2992 overlay.recalculate_linear_handles (); 2993 2994 move_segment (corner1, corner2, thickness); 2995 2996 ep1 = corner2; 2997 } 2998 2999 public static PathList merge_stroke_parts (Path p, Path side1, Path side2) { 3000 Path merged = new Path (); 3001 PathList paths = new PathList (); 3002 3003 if (!p.is_open ()) { 3004 side1.update_region_boundaries (); 3005 paths.add (side1); 3006 side2.update_region_boundaries (); 3007 paths.add (side2); 3008 side1.close (); 3009 side2.close (); 3010 } else if (p.is_open ()) { 3011 side2.reverse (); 3012 merged = merge_strokes (p, side1, side2); 3013 merged.close (); 3014 merged.update_region_boundaries (); 3015 paths.add (merged); 3016 merged.reverse (); 3017 } else { 3018 warning ("Can not create stroke."); 3019 paths.add (p); 3020 } 3021 3022 return paths; 3023 } 3024 } 3025 3026 } 3027