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