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