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