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