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