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