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