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