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