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