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