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