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