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