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