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