The Birdfont Source Code


All Repositories / birdfont.git / blob – RSS feed

StrokeTool.vala in libbirdfont

This file is a part of the Birdfont project.

Contributing

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

Revisions

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