The Birdfont Source Code


All Repositories / birdfont.git / blob – RSS feed

StrokeTool.vala in libbirdfont

This file is a part of the Birdfont project.

Contributing

Send patches or pull requests to johan.mattsson.m@gmail.com.
Clone this repository: git clone https://github.com/johanmattssonm/birdfont.git

Revisions

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