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.
Speed optimizaton in merging 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 class StrokeTool : Tool { 21 22 static bool stroke_selected = false; 23 static int iterations = 0; 24 25 public StrokeTool (string tooltip) { 26 iterations = 10; 27 select_action.connect((self) => { 28 stroke_selected = true; 29 iterations++; 30 stroke_selected_paths (); 31 stroke_selected = false; 32 }); 33 } 34 35 public static void set_stroke_for_selected_paths (double width) { 36 Glyph g = MainWindow.get_current_glyph (); 37 38 foreach (Path p in g.active_paths) { 39 p.set_stroke (width); 40 } 41 42 GlyphCanvas.redraw (); 43 } 44 45 /** Create strokes for the selected outlines. */ 46 void stroke_selected_paths () { 47 Glyph g = MainWindow.get_current_glyph (); 48 PathList paths = new PathList (); 49 50 foreach (Path p in g.active_paths) { 51 if (p.stroke > 0) { 52 paths.append (get_stroke (p, p.stroke)); 53 } 54 } 55 56 // FIXME: delete 57 Path? last = null; 58 foreach (Path p in g.active_paths) { 59 if (p.stroke == 0) { 60 if (last != null) { 61 PathList pl; 62 if (merge_path (p, (!) last, out pl)) { 63 paths.paths.remove (p); 64 paths.paths.remove ((!) last); 65 paths.append (pl); 66 g.path_list.remove (p); 67 g.path_list.remove ((!) last); 68 } else { 69 print (@"Paths can't be merged."); 70 } 71 } 72 73 last = p; 74 } 75 } 76 77 foreach (Path np in paths.paths) { 78 g.add_path (np); 79 } 80 } 81 82 public static PathList get_stroke (Path path, double thickness) { 83 PathList n; 84 PathList o = new PathList (); 85 Path original = path.copy (); 86 87 original.remove_points_on_points (); 88 89 n = get_stroke_outline (original, thickness); 90 91 o = split_corners (n); 92 remove_self_intersecting_corners (o); 93 94 o = merge (o); 95 96 /* 97 PathList parts = new PathList (); 98 foreach (Path p in o.paths) { 99 parts.append (split (p)); 100 } 101 102 return parts; 103 */ 104 105 return o; 106 } 107 108 static bool is_corner_self_intersection (Path p) { 109 EditPointHandle l, r; 110 bool corner, i, remove; 111 112 remove = false; 113 i = false; 114 p.remove_points_on_points (); 115 foreach (EditPoint ep in p.points) { 116 117 corner = (ep.flags & EditPoint.NEW_CORNER) > 0; 118 119 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 120 return false; 121 } 122 123 if (corner || i) { 124 l = ep.get_left_handle (); 125 r = ep.get_right_handle (); 126 127 if (fabs (l.angle - r.angle) < 0.005) { 128 remove = true; 129 } 130 } 131 132 i = corner && p.points.size == 4; 133 } 134 135 return remove; 136 } 137 138 static void remove_self_intersecting_corners (PathList pl) { 139 PathList parts; 140 foreach (Path p in pl.paths) { 141 142 if (is_corner_self_intersection (p)) { 143 parts = get_parts (p); 144 if (parts.paths.size > 1) { 145 pl.append (parts); 146 remove_self_intersecting_corners (pl); 147 return; 148 } else { 149 150 if (has_self_intersection (p)) { // FIXME: DELETE 151 warning ("Path ha self intersection."); 152 } 153 154 pl.paths.remove (p); 155 remove_self_intersecting_corners (pl); 156 return; 157 } 158 } 159 } 160 } 161 162 public static PathList get_stroke_outline (Path path, double thickness) { 163 return get_strokes (path, thickness); 164 } 165 166 public static PathList get_strokes (Path p, double thickness) { 167 Path counter = new Path (); 168 Path outline = new Path (); 169 Path merged = new Path (); 170 PathList paths = new PathList (); 171 172 if (!p.is_open () && p.is_filled ()) { 173 outline = create_stroke (p, thickness); 174 outline.close (); 175 176 outline.update_region_boundaries (); 177 paths.add (outline); 178 } else if (!p.is_open () && !p.is_filled ()) { 179 outline = create_stroke (p, thickness); 180 counter = create_stroke (p, -1 * thickness); 181 182 if (p.is_clockwise ()) { 183 outline.force_direction (Direction.CLOCKWISE); 184 } else { 185 outline.force_direction (Direction.COUNTER_CLOCKWISE); 186 } 187 188 if (outline.is_clockwise ()) { 189 counter.force_direction (Direction.COUNTER_CLOCKWISE); 190 } else { 191 counter.force_direction (Direction.CLOCKWISE); 192 } 193 194 outline.update_region_boundaries (); 195 paths.add (outline); 196 197 counter.update_region_boundaries (); 198 paths.add (counter); 199 } else if (p.is_open ()) { // FIXME: this can create many parts 200 outline = create_stroke (p, thickness); 201 counter = create_stroke (p, -1 * thickness); 202 merged = merge_strokes (p, outline, counter, thickness); 203 204 if (p.is_clockwise ()) { 205 merged.force_direction (Direction.CLOCKWISE); 206 } else { 207 merged.force_direction (Direction.COUNTER_CLOCKWISE); 208 } 209 210 merged.update_region_boundaries (); 211 paths.add (merged); 212 } else { 213 warning ("Can not create stroke."); 214 paths.add (p); 215 } 216 217 return paths; 218 } 219 220 /** Create one stroke from the outline and counter stroke and close the 221 * open endings. 222 * 223 * @param path the path to create stroke for 224 * @param stroke for the outline of path 225 * @param stroke for the counter path 226 */ 227 static Path merge_strokes (Path path, Path stroke, Path counter, double thickness) { 228 Path merged; 229 230 counter.reverse (); 231 merged = stroke.copy (); 232 233 if (path.is_open ()) { 234 merged.delete_last_point (); 235 counter.delete_first_point (); 236 merged.delete_last_point (); 237 counter.delete_first_point (); 238 } 239 240 merged.append_path (counter); 241 242 merged.close (); 243 merged.create_list (); 244 merged.recalculate_linear_handles (); 245 246 return merged; 247 } 248 249 static Path create_stroke (Path p, double thickness) { 250 Path stroked; 251 Path path; 252 253 if (p.points.size >= 2) { 254 path = p.copy (); 255 //FIXME: DELETE path.remove_points_on_points (); 256 stroked = generate_stroke (path, thickness); 257 258 if (!p.is_open ()) { 259 stroked.reverse (); 260 stroked.close (); 261 } 262 } else { 263 // TODO: create stroke for a path with one point 264 warning ("One point."); 265 stroked = new Path (); 266 } 267 268 return stroked; 269 } 270 271 static Path generate_stroke (Path p, double thickness) { 272 Path stroked = new Path (); 273 EditPoint start = new EditPoint (); 274 EditPoint end; 275 EditPoint previous; 276 int i; 277 278 previous = p.get_first_point ().copy (); 279 move_segment (start, previous, thickness); 280 281 i = 0; 282 foreach (EditPoint ep in p.points) { 283 start = ep.copy (); 284 end = ep.get_next ().copy (); 285 286 move_segment (start, end, thickness); 287 288 if (start == p.get_last_point ()) { 289 end = p.get_first_point (); 290 } 291 292 if (!p.is_open () || (i != 0 && i != p.points.size - 1)) { 293 add_corner (stroked, previous, start, ep.copy (), thickness); 294 } 295 296 stroked.add_point (start); 297 298 if (end.get_left_handle ().length > 0) { 299 stroked.add_point (end); 300 } 301 302 // open ends around corner 303 start.get_left_handle ().convert_to_line (); 304 end.get_right_handle ().convert_to_line (); 305 306 start.flags |= EditPoint.STROKE_OFFSET; 307 end.flags |= EditPoint.STROKE_OFFSET; 308 309 previous = end; 310 311 i++; 312 } 313 314 stroked.recalculate_linear_handles (); 315 316 return stroked; 317 } 318 319 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) { 320 EditPointHandle r, l; 321 double m, n; 322 double qx, qy; 323 324 stroke_start.set_tie_handle (false); 325 stroke_stop.set_tie_handle (false); 326 327 r = stroke_start.get_right_handle (); 328 l = stroke_stop.get_left_handle (); 329 330 m = cos (r.angle + PI / 2) * thickness; 331 n = sin (r.angle + PI / 2) * thickness; 332 333 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n); 334 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n); 335 336 stroke_start.independent_x += m; 337 stroke_start.independent_y += n; 338 339 qx = cos (l.angle - PI / 2) * thickness; 340 qy = sin (l.angle - PI / 2) * thickness; 341 342 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy); 343 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy); 344 345 stroke_stop.independent_x += qx; 346 stroke_stop.independent_y += qy; 347 } 348 349 static void add_corner (Path stroked, EditPoint previous, EditPoint next, 350 EditPoint original, double stroke_width) { 351 352 double ratio; 353 double distance; 354 EditPoint corner; 355 double corner_x, corner_y; 356 EditPointHandle previous_handle; 357 EditPointHandle next_handle; 358 EditPoint cutoff1, cutoff2; 359 360 previous_handle = previous.get_left_handle (); 361 next_handle = next.get_right_handle (); 362 363 previous_handle.angle += PI; 364 next_handle.angle += PI; 365 366 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y); 367 corner = new EditPoint (corner_x, corner_y, previous.type); 368 corner.convert_to_line (); 369 370 previous_handle.angle -= PI; 371 next_handle.angle -= PI; 372 373 distance = Path.distance_to_point (corner, original); 374 ratio = 1.5 * fabs (stroke_width) / distance; 375 376 if (distance < 0.1) { 377 previous.flags |= EditPoint.NEW_CORNER; 378 next.flags |= EditPoint.NEW_CORNER; 379 } else { 380 if (ratio > 1) { 381 stroked.add_point (corner); 382 } else { 383 cutoff1 = new EditPoint (); 384 cutoff1.set_point_type (previous.type); 385 cutoff1.convert_to_line (); 386 387 cutoff2 = new EditPoint (); 388 cutoff2.set_point_type (previous.type); 389 cutoff2.convert_to_line (); 390 391 cutoff1.x = previous.x + (corner.x - previous.x) * ratio; 392 cutoff1.y = previous.y + (corner.y - previous.y) * ratio; 393 394 cutoff2.x = next.x + (corner.x - next.x) * ratio; 395 cutoff2.y = next.y + (corner.y - next.y) * ratio; 396 397 cutoff1 = stroked.add_point (cutoff1); 398 cutoff2 = stroked.add_point (cutoff2); 399 400 cutoff1.recalculate_linear_handles (); 401 cutoff2.recalculate_linear_handles (); 402 403 previous.flags |= EditPoint.NEW_CORNER; 404 next.flags |= EditPoint.NEW_CORNER; 405 } 406 } 407 } 408 409 static PathList get_parts (Path path) { 410 PathList intersections; 411 PathList r; 412 413 r = get_parts_self (path); 414 intersections = new PathList (); 415 416 foreach (Path p in r.paths) { 417 intersections.add (p); 418 } 419 420 // return split_paths (intersections); 421 return intersections; 422 } 423 424 static PathList split_corners (PathList result) { 425 split_corner (result); 426 return result; 427 } 428 429 static bool split_corner (PathList pl) { 430 EditPoint p1, p2; 431 EditPoint a1, a2; 432 PathList r; 433 bool split; 434 435 foreach (Path p in pl.paths) { 436 if (p.points.size == 0) { 437 continue; 438 } 439 440 for (int index = 1; index < p.points.size + 2; index++) { 441 p1 = p.points.get ((index - 1) % p.points.size); 442 p2 = p.points.get (index % p.points.size); 443 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 444 a2 = p.points.get ((index + 4) % p.points.size); 445 446 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 447 || (p2.flags & EditPoint.STROKE_OFFSET) > 0 448 || (a1.flags & EditPoint.STROKE_OFFSET) > 0 449 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) { // FIXME: safe? 450 451 split = split_segment (p, a1, a2, p1, p2, out r); 452 453 if (split) { 454 pl.append (r); 455 pl.paths.remove (p); 456 split_corner (pl); 457 return true; 458 } else { 459 p1 = p.points.get ((index - 1) % p.points.size); 460 p2 = p.points.get (index % p.points.size); 461 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead 462 a2 = p.points.get ((index + 3) % p.points.size); 463 464 split = split_segment (p, a1, a2, p1, p2, out r); 465 466 if (split) { 467 pl.append (r); 468 pl.paths.remove (p); 469 split_corner (pl); 470 return true; 471 } else { 472 473 // FIXME: the special case, merge counter path with outline here 474 p1 = p.points.get ((index - 1) % p.points.size); 475 p2 = p.points.get (index % p.points.size); 476 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 477 a2 = p.points.get ((index + 4) % p.points.size); 478 479 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 480 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) { 481 p1.flags = EditPoint.COUNTER_TO_OUTLINE; 482 a1.flags = EditPoint.COUNTER_TO_OUTLINE; 483 484 p1.counter_to_outline = true; 485 a1.counter_to_outline = true; 486 } 487 } 488 } 489 } 490 } 491 } 492 493 return false; 494 } 495 496 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) { 497 double ix, iy; 498 bool intersection; 499 int i; 500 501 result = new PathList (); 502 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true); 503 504 if (intersection) { 505 add_intersection (p, first, next, ix, iy); 506 add_intersection (p, p1, p2, ix, iy); 507 508 i = mark_intersection_as_deleted (p); 509 return_val_if_fail (i == 2, false); 510 511 result.append (get_remaining_points (p.copy ())); 512 } 513 514 return intersection; 515 } 516 517 static bool split_path (Path path1, Path path2, PathList result) { 518 PathList pl1, pl2; 519 Path a1, a2, b1, b2; 520 Path m1, m2; 521 int i; 522 523 if (path1 == path2) { 524 return false; 525 } 526 527 if (add_intersection_points (path1, path2, 2)) { 528 i = mark_intersection_as_deleted (path1); 529 return_if_fail (i == 2); 530 531 i = mark_intersection_as_deleted (path2); 532 return_if_fail (i == 2); 533 534 pl1 = get_remaining_points (path1.copy ()); 535 pl2 = get_remaining_points (path2.copy ()); 536 537 return_if_fail (pl1.paths.size == 2); 538 return_if_fail (pl2.paths.size == 2); 539 540 a1 = pl1.paths.get (0); 541 a2 = pl1.paths.get (1); 542 b1 = pl2.paths.get (0); 543 b2 = pl2.paths.get (1); 544 545 m1 = PenTool.merge_open_paths (a1, b2); 546 m2 = PenTool.merge_open_paths (b1, a2); 547 548 result.add (m1); 549 result.add (m2); 550 551 return true; 552 } 553 554 return false; 555 } 556 557 static PathList split_paths (PathList pl) { 558 PathList n = new PathList (); 559 560 n.append (pl); 561 562 foreach (Path p1 in pl.paths) { 563 foreach (Path p2 in pl.paths) { 564 if (p1 != p2) { 565 if (split_path (p1, p2, n)) { 566 n.paths.remove (p1); 567 n.paths.remove (p2); 568 return split_paths (n); 569 } 570 } 571 } 572 } 573 574 return n; 575 } 576 577 static PathList get_parts_self (Path path, PathList? paths = null) { 578 PathList pl; 579 PathList r; 580 581 r = paths == null ? new PathList () : (!) paths; 582 pl = split (path); 583 584 foreach (Path part in pl.paths) { 585 if (!has_self_intersection (part)) { 586 r.add (part); 587 } else { 588 get_parts_self (part, r); 589 } 590 } 591 592 if (r.paths.size == 0) { 593 warning ("No parts in path"); 594 } 595 596 return r; 597 } 598 599 static bool has_intersection_points (Path path) { 600 foreach (EditPoint p in path.points) { 601 if ((p.flags & EditPoint.INTERSECTION) > 0) { 602 return true; 603 } 604 } 605 return false; 606 } 607 608 /** Split one path at intersection points in two parts. */ 609 static PathList split (Path path) { 610 PathList pl; 611 int i; 612 613 if (!has_intersection_points (path)) { 614 add_self_intersection_points (path); 615 } else { 616 warning ("points already created."); 617 } 618 619 i = mark_intersection_as_deleted (path); 620 621 if (!(i == 0 || i == 2)) { 622 warning (@"Split should only create two parts, $i points will be deleted."); 623 } 624 625 pl = get_remaining_points (path.copy ()); 626 627 return pl; 628 } 629 630 static PathList process_deleted_control_points (Path path) { 631 PathList paths, nl, pl, rl; 632 633 paths = new PathList (); 634 rl = new PathList (); 635 pl = new PathList (); 636 nl = new PathList (); 637 638 if (!path.has_deleted_point ()) { 639 return pl; 640 } 641 642 pl.add (path); 643 644 foreach (Path p in pl.paths) { 645 nl = p.process_deleted_points (); 646 647 if (nl.paths.size > 0) { 648 rl.append (nl); 649 rl.paths.remove (p); 650 } 651 } 652 653 foreach (Path p in rl.paths) { 654 pl = process_deleted_control_points (p); 655 656 if (pl.paths.size > 0) { 657 paths.append (pl); 658 } else { 659 paths.add (p); 660 } 661 } 662 663 return paths; 664 } 665 666 static PathList get_remaining_points (Path old_path) { 667 PathList pl; 668 669 old_path.close (); 670 pl = process_deleted_control_points (old_path); 671 672 if (pl.paths.size == 0) { 673 pl.add (old_path); 674 } 675 676 foreach (Path pn in pl.paths) { 677 pn.close (); 678 } 679 680 return pl; 681 } 682 683 static bool has_self_intersection (Path path) { 684 bool intersection = false; 685 686 path.all_segments ((ep1, ep2) => { 687 double ix, iy; 688 EditPoint p1, p2; 689 690 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2)) { 691 intersection = true; 692 return false; 693 } 694 695 return true; 696 }); 697 698 return intersection; 699 } 700 701 static bool add_self_intersection_points (Path path, bool only_offsets = false) { 702 bool intersection = false; 703 704 path.all_segments ((ep1, ep2) => { 705 double ix, iy; 706 EditPoint p1, p2; 707 708 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) { 709 add_intersection (path, ep1, ep2, ix, iy); 710 add_intersection (path, p1, p2, ix, iy); 711 712 intersection = true; 713 return false; 714 } 715 716 return true; 717 }); 718 719 if (intersection) { 720 // FIXME: path.create_list (); 721 } 722 723 return intersection; 724 } 725 726 static EditPoint add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) { 727 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> (); 728 EditPoint ep1 = new EditPoint (); 729 EditPoint ep2 = new EditPoint (); 730 EditPoint ep3 = new EditPoint (); 731 732 if (next == path.get_first_point ()) { // FIXME: double check 733 ep1.prev = null; 734 } else { 735 ep1.prev = prev; 736 } 737 738 ep1.prev = prev; 739 ep1.next = ep2; 740 ep1.flags |= EditPoint.NEW_CORNER; 741 ep1.type = PointType.CUBIC; 742 ep1.x = px; 743 ep1.y = py; 744 ep1.color = c; 745 n.add (ep1); 746 747 ep2.prev = ep1; 748 ep2.next = ep3; 749 ep2.flags |= EditPoint.INTERSECTION; 750 ep2.type = PointType.QUADRATIC; 751 ep2.x = px; 752 ep2.y = py; 753 ep2.color = c; 754 n.add (ep2); 755 756 ep3.prev = ep2; 757 ep3.next = next; 758 ep3.flags |= EditPoint.NEW_CORNER; 759 ep3.type = PointType.CUBIC; 760 ep3.x = px; 761 ep3.y = py; 762 ep3.color = c; 763 n.add (ep3); 764 765 foreach (EditPoint np in n) { 766 np = path.add_point_after (np, np.prev); 767 path.create_list (); 768 } 769 770 path.recalculate_linear_handles (); 771 772 return ep2; 773 } 774 775 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next, 776 out double ix, out double iy, 777 bool skip_points_on_points = false) { 778 double cross_x, cross_y; 779 780 ix = 0; 781 iy = 0; 782 783 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y); 784 785 if (Glyph.CANVAS_MIN < cross_x < Glyph.CANVAS_MAX 786 && Glyph.CANVAS_MIN < cross_y < Glyph.CANVAS_MAX) { 787 // iterate to find intersection. 788 789 if (skip_points_on_points || 790 !((ep.x == cross_x && ep.y == cross_y) 791 || (next.x == cross_x && next.y == cross_y) 792 || (p1.x == cross_x && p1.y == cross_y) 793 || (p2.x == cross_x && p2.y == cross_y))) { 794 795 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y) 796 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) { 797 798 ix = cross_x; 799 iy = cross_y; 800 801 return true; 802 } 803 } 804 } 805 806 return false; 807 } 808 809 static bool segment_intersects (Path path, EditPoint ep, EditPoint next, 810 out double ix, out double iy, 811 out EditPoint ia, out EditPoint ib, 812 bool skip_points_on_points = false, 813 bool only_offsets = false) { 814 815 EditPoint p1, p2; 816 bool intersection, inter; 817 double iix, iiy; 818 819 double distance, min_distance; 820 821 intersection = false; 822 823 ix = 0; 824 iy = 0; 825 826 iix = 0; 827 iiy = 0; 828 829 ia = new EditPoint (); 830 ib = new EditPoint (); 831 832 if (path.points.size == 0) { 833 return false; 834 } 835 836 min_distance = double.MAX; 837 p1 = path.points.get (path.points.size - 1); 838 for (int i = 0; i < path.points.size; i++) { 839 p2 = path.points.get (i); 840 841 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0) 842 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0) 843 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0) 844 && ((next.flags & EditPoint.STROKE_OFFSET) > 0); 845 846 if (!only_offsets || is_offset) { 847 if (p1 != ep && p2 != next) { 848 inter = segments_intersects (p1, p2, ep, next, out iix, out iiy, 849 skip_points_on_points); 850 851 if (inter) { 852 distance = Path.distance (ep.x, iix, ep.y, iiy); 853 if (distance < min_distance) { 854 ia = p1; 855 ib = p2; 856 ix = iix; 857 iy = iiy; 858 intersection = true; 859 min_distance = distance; 860 } 861 } 862 } 863 } 864 865 p1 = p2; 866 } 867 868 return intersection; 869 } 870 871 static bool same (EditPoint a, EditPoint b) { 872 return a.x == b.x && a.y == b.y; 873 } 874 875 /** @return true if p2 is on the line p1 to p3 */ 876 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3) { 877 double ds = Path.distance (x1, x3, y1, y3); 878 double d1 = Path.distance (x1, x2, y1, y2); 879 double d2 = Path.distance (x2, x3, y2, y3); 880 double p = d1 / ds; 881 double x = fabs ((x3 - x1) * p - (x2 - x1)); 882 double y = fabs ((y3 - y1) * p - (y2 - y1)); 883 double d = fabs (ds - (d1 + d2)); 884 885 // FIXME: delete print (@"$(fmin (x1, x3)) < $x2 && $x2 < $(fmax (x1, x3))\n"); 886 // FIXME: delete print (@"$(fmin (y1, y3)) < $y2 && $y2 < $(fmax (y1, y3))\n"); 887 888 return ds > 0.01 && d1 > 0.01 && d2 > 0.01 889 && d < 0.01 && x < 0.01 && y < 0.01 890 && fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3) 891 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3); 892 } 893 894 static Path get_outline (Path path) { 895 PathList pl = get_parts (path); 896 Path outline = new Path (); 897 int inside; 898 int min_inside = int.MAX; 899 int points = 0; 900 int i = 0; 901 902 foreach (Path p in pl.paths) { 903 inside = Path.counters (pl, p); 904 905 if (inside < min_inside) { 906 outline = p; 907 min_inside = inside; 908 } 909 910 i++; 911 } 912 913 if (min_inside == 0) { 914 foreach (Path p in pl.paths) { 915 if (p.points.size > points) { 916 outline = p; 917 points = p.points.size; 918 } 919 } 920 } 921 922 return outline; 923 } 924 925 static void remove_points_in_stroke (PathList pl) { 926 PathList result; 927 PathList r; 928 PathList parts; 929 930 foreach (Path p in pl.paths) { 931 if (remove_points_in_stroke_for_path (p, pl, out r)) { 932 pl.append (r); 933 remove_points_in_stroke (pl); 934 return; 935 } 936 } 937 } 938 939 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) { 940 bool remove = false; 941 EditPoint start_ep; 942 EditPoint start_next; 943 EditPoint start_prev; 944 EditPoint end_ep = new EditPoint (); 945 EditPoint end_next; 946 EditPoint end_prev; 947 Path path2; 948 EditPoint found = new EditPoint (); 949 950 result = new PathList (); 951 952 for (int i = 1; i < p.points.size + 1; i++) { 953 start_prev = p.points.get ((i - 1) % p.points.size); 954 start_ep = p.points.get (i % p.points.size); 955 start_next = p.points.get ((i + 1) % p.points.size); 956 957 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 958 for (int j = i; j < p.points.size + i; j++) { 959 end_prev = p.points.get ((j - 1) % p.points.size); 960 end_ep = p.points.get (j % p.points.size); 961 end_next = p.points.get ((j + 1) % p.points.size); 962 963 // FIXME: if (!is_inside_of_path 964 965 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 966 start_ep.flags = EditPoint.NONE; 967 end_ep.flags = EditPoint.NONE; 968 969 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) { 970 return true; 971 } 972 } 973 } 974 } 975 976 start_ep.flags = EditPoint.NONE; 977 end_ep.flags = EditPoint.NONE; 978 } 979 980 return false; 981 } 982 983 static bool merge_segments (PathList pl, 984 Path path1, EditPoint start1, EditPoint stop1, 985 EditPoint start2, EditPoint stop2, 986 out PathList result) { 987 988 result = new PathList (); 989 990 PathList r1; 991 PathList r2; 992 993 foreach (Path path2 in pl.paths) { 994 if (path2 != path1) { 995 reset_intersections (path1); 996 reset_intersections (path2); 997 998 if (add_merge_intersection_point (path1, path2, start1, stop1)) { 999 if (add_merge_intersection_point (path1, path2, start2, stop2)) { 1000 1001 r1 = get_remaining_points (path1.copy ()); 1002 r2 = get_remaining_points (path2.copy ()); 1003 1004 if (r1.paths.size != 2) { 1005 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n"); 1006 reset_intersections (path1); 1007 reset_intersections (path2); 1008 return true; 1009 } 1010 1011 if (r2.paths.size != 2) { 1012 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n"); 1013 reset_intersections (path1); 1014 reset_intersections (path2); 1015 return true; 1016 } 1017 1018 pl.paths.remove (path1); 1019 pl.paths.remove (path2); 1020 1021 // FIXME: find criteria 1022 1023 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (), 1024 r2.paths.get (0).get_first_point ()); 1025 1026 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (), 1027 r2.paths.get (1).get_first_point ()); 1028 1029 Path m1, m2; 1030 1031 if (d1 > d2) { 1032 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0)); 1033 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1)); 1034 } else { 1035 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0)); 1036 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1)); 1037 } 1038 1039 result.add (m1); 1040 result.add (m2); 1041 1042 return true; 1043 } else { 1044 reset_intersections (path1); 1045 reset_intersections (path2); 1046 } 1047 } else { 1048 reset_intersections (path1); 1049 reset_intersections (path2); 1050 } 1051 } 1052 } 1053 1054 return false; 1055 } 1056 1057 static void reset_intersections (Path p) { 1058 foreach (EditPoint ep in p.points) { 1059 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION; 1060 ep.deleted = false; 1061 } 1062 p.remove_points_on_points (); 1063 } 1064 1065 static bool has_counter_to_outline (Path p) { 1066 foreach (EditPoint ep in p.points) { 1067 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1068 return true; 1069 } 1070 } 1071 1072 return false; 1073 } 1074 1075 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) { 1076 double ix, iy; 1077 bool intersection; 1078 1079 intersection = false; 1080 ix = 0; 1081 iy = 0; 1082 path2.all_segments ((p1, p2) => { 1083 int i; 1084 1085 intersection = segments_intersects (first, next, p1, p2, out ix, out iy); 1086 1087 if (intersection) { 1088 add_intersection (path1, first, next, ix, iy); 1089 add_intersection (path2, p1, p2, ix, iy); 1090 1091 i = mark_intersection_as_deleted (path1); 1092 i = mark_intersection_as_deleted (path2); 1093 } 1094 1095 return !intersection; 1096 }); 1097 1098 return intersection; 1099 } 1100 1101 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) { 1102 outline = new Path (); 1103 foreach (Path p in pl.paths) { 1104 if (p != ps.path) { 1105 if (SvgParser.is_inside (ps.point, p)) { 1106 outline = p; 1107 return true; 1108 } 1109 } 1110 } 1111 1112 return false; 1113 } 1114 1115 static PathList merge (PathList pl) { 1116 PathList r; 1117 remove_points_in_stroke (pl); 1118 r = merge_paths (pl); 1119 //remove_merged_parts (r); 1120 return r; 1121 } 1122 1123 static void remove_merged_parts (PathList r) { 1124 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> (); 1125 foreach (Path p in r.paths) { 1126 1127 if (Path.is_counter (r, p)) { 1128 if (p.is_clockwise ()) { 1129 remove.add (p); 1130 } 1131 } else { 1132 if (!p.is_clockwise ()) { 1133 remove.add (p); 1134 } 1135 } 1136 1137 if (stroke_selected) { // FIXME: DELETE 1138 ((!) BirdFont.get_current_font ().get_glyph ("a")).add_path (p); 1139 } 1140 } 1141 1142 foreach (Path p in remove) { 1143 r.paths.remove (p); 1144 } 1145 } 1146 1147 static PathList merge_paths (PathList r) { 1148 PathList result = new PathList (); 1149 PathList m; 1150 1151 foreach (Path p1 in r.paths) { 1152 result.add (p1); 1153 } 1154 1155 foreach (Path p1 in r.paths) { 1156 foreach (Path p2 in r.paths) { 1157 if (p1 != p2) { 1158 p1.update_region_boundaries (); 1159 p2.update_region_boundaries (); 1160 if (merge_path (p1, p2, out m)) { 1161 result.append (m); 1162 result.paths.remove (p1); 1163 result.paths.remove (p2); 1164 return merge_paths (result); 1165 } 1166 } 1167 } 1168 } 1169 1170 return result; 1171 1172 } 1173 1174 public class Intersection : GLib.Object { 1175 public bool done = false; 1176 public EditPoint point; 1177 public EditPoint other_point; 1178 public Path path; 1179 public Path other_path; 1180 1181 public Intersection (EditPoint point, Path path, 1182 EditPoint other_point, Path other_path) { 1183 1184 this.point = point; 1185 this.path = path; 1186 this.other_point = other_point; 1187 this.other_path = other_path; 1188 } 1189 1190 public Intersection.empty () { 1191 this.point = new EditPoint (); 1192 this.path = new Path (); 1193 this.other_point = new EditPoint (); 1194 this.other_path = new Path (); 1195 } 1196 1197 public Path get_other_path (Path p) { 1198 if (p == path) { 1199 return other_path; 1200 } 1201 1202 if (p == other_path) { 1203 return path; 1204 } 1205 1206 warning ("Wrong intersection."); 1207 return new Path (); 1208 } 1209 1210 public EditPoint get_point (Path p) { 1211 if (p == path) { 1212 return point; 1213 } 1214 1215 if (p == other_path) { 1216 return other_point; 1217 } 1218 1219 warning ("Wrong intersection."); 1220 return new EditPoint (); 1221 } 1222 } 1223 1224 public class IntersectionList : GLib.Object { 1225 public Gee.ArrayList<Intersection> points = new Gee.ArrayList<Intersection> (); 1226 1227 public IntersectionList () { 1228 } 1229 1230 public Intersection get_point (EditPoint ep, out bool other) { 1231 other = false; 1232 foreach (Intersection i in points) { 1233 if (i.other_point == ep || i.point == ep) { 1234 other = (i.other_point == ep); 1235 return i; 1236 } 1237 } 1238 1239 warning ("No intersection found for point."); 1240 return new Intersection.empty (); 1241 } 1242 } 1243 1244 static bool merge_path (Path path1, Path path2, out PathList merged_paths) { 1245 IntersectionList intersections; 1246 EditPoint ep1, next, p1, p2, pp1, pp2; 1247 Path path, other, merged; 1248 PathList pl1, pl2, r, other_paths, result; 1249 bool intersects; 1250 int s, i; 1251 double ix, iy, iix, iiy; 1252 bool merge = false; 1253 EditPoint intersection_point, other_intersection_point; 1254 Intersection intersection; 1255 1256 merged_paths = new PathList (); 1257 intersections = new IntersectionList (); 1258 1259 iix = 0; 1260 iiy = 0; 1261 1262 result = new PathList (); 1263 1264 if (path1.points.size == 0 || path2.points.size == 0) { 1265 warning ("No points in path."); 1266 return false; 1267 } 1268 1269 if (!path1.boundaries_intersecting (path2)) { 1270 return false; 1271 } 1272 1273 Path original_path1 = path1.copy (); 1274 Path original_path2 = path2.copy (); 1275 1276 s = 0; 1277 foreach (EditPoint e in original_path1.points) { 1278 if (!SvgParser.is_inside (e, original_path2)) { 1279 break; 1280 } 1281 s++; 1282 } 1283 1284 if (s >= path1.points.size) { 1285 Path t; 1286 t = original_path1; 1287 original_path1 = original_path2; 1288 original_path2 = t; 1289 s = 0; 1290 foreach (EditPoint e in original_path1.points) { 1291 if (!SvgParser.is_inside (e, original_path2)) { 1292 break; 1293 } 1294 s++; 1295 } 1296 } 1297 1298 if (s >= original_path1.points.size) { 1299 warning ("No start point found."); 1300 return false; 1301 } 1302 1303 path = original_path1; 1304 other = original_path2; 1305 1306 other_paths = new PathList (); 1307 r = new PathList (); 1308 other_paths.add (path); 1309 other_paths.add (other); 1310 intersects = false; 1311 p1 = new EditPoint (); 1312 p2 = new EditPoint (); 1313 pp1 = new EditPoint (); 1314 pp2 = new EditPoint (); 1315 1316 ix = 0; 1317 iy = 0; 1318 i = s; 1319 merged = new Path (); 1320 1321 while (true) { 1322 ep1 = path.points.get (i % path.points.size); 1323 next = path.points.get ((i + 1) % path.points.size); 1324 1325 if ((ep1.flags & EditPoint.COPIED) > 0) { 1326 if (merge) { 1327 merged.close (); 1328 result.add (merged.copy ()); 1329 } 1330 1331 merged = new Path (); 1332 1333 bool find_parts = false; 1334 Intersection new_start = new Intersection.empty (); 1335 foreach (Intersection inter in intersections.points) { 1336 if (!inter.done && !find_parts) { 1337 find_parts = true; 1338 new_start = inter; 1339 break; 1340 } 1341 } 1342 1343 if (!find_parts) { 1344 break; // done, no more parts 1345 } else { 1346 // set start point for next part 1347 path = new_start.other_path; 1348 1349 if (path.points.size == 0) { 1350 warning ("No points."); 1351 return false; 1352 } 1353 1354 i = index_of (path, new_start.get_point (path)); 1355 1356 if (i < 0) { 1357 warning ("Start point not found."); 1358 return false; 1359 } 1360 1361 ep1 = path.points.get (i % path.points.size); 1362 next = path.points.get ((i + 1) % path.points.size); 1363 1364 if ((ep1.flags & EditPoint.INTERSECTION) == 0) { 1365 warning ("Not starting on an intersection point."); 1366 return false; 1367 } 1368 1369 new_start.done = true; 1370 } 1371 } 1372 1373 intersects = false; 1374 1375 double dm; 1376 double d; 1377 1378 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 1379 Intersection current_intersection; 1380 bool continue_on_other_path; 1381 current_intersection = intersections.get_point (ep1, out continue_on_other_path); 1382 current_intersection.done = true; 1383 1384 // take the other part of an intersection 1385 if ((next.flags & EditPoint.COPIED) != 0) { 1386 bool next_is_intersection = false; 1387 bool next_continue_on_other_path; 1388 1389 next_is_intersection = ((next.flags & EditPoint.INTERSECTION) > 0); 1390 1391 if (next_is_intersection) { 1392 Intersection next_intersection = intersections.get_point (next, out next_continue_on_other_path); 1393 1394 ep1.flags |= EditPoint.COPIED; 1395 merged.add_point (ep1.copy ()); 1396 1397 if (!next_intersection.done) { 1398 EditPoint new_start_point; 1399 1400 path = next_continue_on_other_path 1401 ? next_intersection.other_path : next_intersection.path; 1402 1403 new_start_point = next_continue_on_other_path 1404 ? next_intersection.other_point : next_intersection.point; 1405 1406 i = index_of (path, new_start_point); 1407 1408 if (i < 0) { 1409 warning ("Point not found in path.\n"); 1410 return false; 1411 } 1412 1413 ep1 = path.points.get (i % path.points.size); 1414 next = path.points.get ((i + 1) % path.points.size); 1415 } else { 1416 warning ("Part is already created.\n"); 1417 return false; 1418 } 1419 } else { 1420 ep1.flags |= EditPoint.COPIED; 1421 merged.add_point (ep1.copy ()); 1422 1423 EditPoint new_start_point; 1424 1425 if ((next.flags & EditPoint.COPIED) > 0) { 1426 path = current_intersection.get_other_path (path); 1427 new_start_point = current_intersection.get_point (path); 1428 i = index_of (path, new_start_point); 1429 1430 if (i < 0) { 1431 warning ("Point not found in path."); 1432 return false; 1433 } 1434 1435 ep1 = path.points.get (i % path.points.size); 1436 next = path.points.get ((i + 1) % path.points.size); 1437 1438 if ((next.flags & EditPoint.INTERSECTION) > 0) { 1439 warning ("Wrong type."); 1440 } 1441 1442 if ((next.flags & EditPoint.COPIED) > 0) { 1443 merged.add_point (ep1.copy ()); 1444 continue; 1445 } 1446 } else { 1447 ep1.flags |= EditPoint.COPIED; 1448 merged.add_point (ep1.copy ()); 1449 } 1450 } 1451 } else { 1452 ep1.flags |= EditPoint.COPIED; 1453 merged.add_point (ep1.copy ()); 1454 } 1455 1456 current_intersection.done = true; 1457 } else { 1458 // find new intersection 1459 dm = double.MAX; 1460 foreach (Path o in other_paths.paths) { 1461 bool inter = segment_intersects (o, ep1, next, out iix, out iiy, 1462 out pp1, out pp2, true); 1463 d = Path.distance (ep1.x, iix, ep1.y, iiy); 1464 if (d < dm && inter) { 1465 other = o; 1466 dm = d; 1467 intersects = true; 1468 p1 = pp1; 1469 p2 = pp2; 1470 ix = iix; 1471 iy = iiy; 1472 } 1473 } 1474 1475 if (intersects) { 1476 merged.add_point (ep1.copy ()); 1477 ep1.flags |= EditPoint.COPIED; 1478 1479 intersection_point = add_intersection (path, ep1, next, ix, iy); 1480 other_intersection_point = add_intersection (other, p1, p2, ix, iy); 1481 1482 bool g = false; 1483 bool stay = false; 1484 foreach (Intersection old_intersection in intersections.points) { 1485 if (old_intersection.point == intersection_point 1486 || old_intersection.other_point == other_intersection_point) { 1487 old_intersection.done = true; 1488 g = true; 1489 } 1490 } 1491 1492 if (!g) { 1493 Intersection ip = new Intersection (intersection_point, path, other_intersection_point, other); 1494 intersections.points.add (ip); 1495 } 1496 1497 merged.add_point (intersection_point.copy ()); 1498 intersection_point.flags |= EditPoint.COPIED; 1499 1500 i = index_of (other, other_intersection_point); 1501 1502 if (i < 0) { 1503 warning (@"Point not found ($i)."); 1504 break; 1505 } 1506 1507 path = other; 1508 merge = true; 1509 } else { 1510 ep1.flags |= EditPoint.COPIED; 1511 merged.add_point (ep1.copy ()); 1512 } 1513 } 1514 1515 i++; 1516 } 1517 1518 int counter; 1519 foreach (Path p in result.paths) { 1520 counter = Path.counters (result, p); 1521 if (counter == 0) { 1522 merged.force_direction (Direction.CLOCKWISE); 1523 } else { 1524 if (path1.is_clockwise () != original_path2.is_clockwise ()) { 1525 merged.force_direction (Direction.COUNTER_CLOCKWISE); 1526 } else { 1527 merged.force_direction (Direction.CLOCKWISE); 1528 } 1529 } 1530 1531 reset_intersections (p); 1532 merged_paths.add (p); 1533 p.update_region_boundaries (); 1534 p.recalculate_linear_handles (); 1535 } 1536 1537 return merge; 1538 } 1539 1540 static int index_of (Path p, EditPoint ep) { 1541 int i = 0; 1542 foreach (EditPoint e in p.points) { 1543 if (e == ep) { 1544 return i; 1545 } 1546 i++; 1547 } 1548 1549 return -1; 1550 } 1551 1552 static Path get_next_part (PathList pl, EditPoint ep) { 1553 double d, m; 1554 Path r; 1555 1556 r = new Path (); 1557 m = double.MAX; 1558 foreach (Path p in pl.paths) { 1559 d = Path.distance_to_point (p.get_last_point (), ep); 1560 if (d < m) { 1561 m = d; 1562 r = p; 1563 } 1564 } 1565 1566 return r; 1567 } 1568 1569 public static int counters_in_point_in_path (Path p, EditPoint ep) { 1570 int inside_count = 0; 1571 bool inside; 1572 1573 if (p.points.size > 1) { 1574 inside = true; 1575 1576 if (!SvgParser.is_inside (ep, p)) { 1577 inside = false; 1578 } 1579 1580 if (inside) { 1581 inside_count++; 1582 } 1583 } 1584 1585 return inside_count; 1586 } 1587 1588 static int mark_intersection_as_deleted (Path path) { 1589 int i = 0; 1590 1591 foreach (EditPoint p in path.points) { 1592 1593 if ((p.flags & EditPoint.INTERSECTION) > 0) { 1594 p.deleted = true; 1595 i++; 1596 } 1597 } 1598 1599 return i; 1600 } 1601 1602 /** @param n number of interrsections to find per path. */ 1603 static bool add_intersection_points (Path path1, Path path2, int n = 1) { 1604 bool intersection = false; 1605 int found = 0; 1606 1607 path1.all_segments ((ep1, ep2) => { 1608 double ix, iy; 1609 EditPoint p1, p2; 1610 bool i; 1611 1612 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 1613 out p1, out p2, true); 1614 1615 if (i) { 1616 add_intersection (path1, ep1, ep2, ix, iy); 1617 add_intersection (path2, p1, p2, ix, iy); 1618 intersection = true; 1619 found++; 1620 return found < n; 1621 } 1622 1623 return true; 1624 }); 1625 1626 return intersection; 1627 } 1628 1629 } 1630 1631 } 1632