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.
Merge stroke parts
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 public static double stroke_width = 0; 23 public static bool add_stroke = false; 24 25 public static bool show_stroke_tools = false; 26 public static bool stroke_selected = false; 27 28 public StrokeTool (string tooltip) { 29 } 30 31 /** Create strokes for the selected outlines. */ 32 public static void stroke_selected_paths () { 33 Glyph g = MainWindow.get_current_glyph (); 34 PathList paths = new PathList (); 35 36 stroke_selected = true; // FIXME: delete 37 38 g.store_undo_state (); 39 40 foreach (Path p in g.active_paths) { 41 if (p.stroke > 0) { 42 paths.append (get_stroke (p, p.stroke)); 43 } 44 } 45 46 // FIXME: delete 47 bool h = false; 48 foreach (Path p in g.active_paths) { 49 if (p.stroke == 0) { 50 h = true; 51 } 52 } 53 54 if (h) { 55 PathList n = new PathList (); 56 57 foreach (Path p in g.active_paths) { 58 if (p.stroke == 0) { 59 n.add (p); 60 } 61 } 62 63 n = merge (n); 64 paths.append (n); 65 } 66 67 if (paths.paths.size > 0) { 68 foreach (Path p in g.active_paths) { 69 g.path_list.remove (p); 70 } 71 72 g.active_paths.clear (); 73 74 foreach (Path np in paths.paths) { 75 g.add_path (np); 76 g.active_paths.add (np); 77 } 78 79 PenTool.update_orientation (); 80 81 GlyphCanvas.redraw (); 82 } 83 84 stroke_selected = false; // FIXME: delete 85 } 86 87 public static PathList get_stroke (Path path, double thickness) { 88 PathList n, o; 89 Path stroke = path.copy (); 90 91 /*if (!is_clockwise (stroke)) { 92 stroke.reverse (); 93 } 94 */ 95 96 stroke.remove_points_on_points (0.3); 97 98 // FIXME: flatten (stroke, thickness); 99 100 // n = get_stroke_outline (stroke, thickness); 101 102 o = get_overlay (stroke, thickness); 103 foreach (Path p in o.paths) { 104 if (stroke_selected) {// FIXME: DELETE 105 ((!) BirdFont.get_current_font ().get_glyph ("c")).add_path (p); 106 } 107 } 108 109 o = get_all_parts (o); // FIXME: only on stroke to outline 110 foreach (Path p in o.paths) { 111 if (stroke_selected) {// FIXME: DELETE 112 ((!) BirdFont.get_current_font ().get_glyph ("d")).add_path (p); 113 } 114 } 115 116 // FIXME: only on stroke to outline 117 o = merge (o); 118 119 // remove_merged_parts (o); 120 121 /* 122 foreach (Path p in n.paths) { 123 p.remove_points_on_points (0.3); 124 } 125 */ 126 127 // o = get_all_parts (n); 128 129 // Changing orientation causes a problem with self intersecting corners 130 // but it solves the problem where the original path is self intersection. 131 // According to the fill rule should intersection be counter paths but 132 // it is better to try to merge paths with filled intersections. 133 // 134 // TODO: Implement merging with other fill rules. 135 136 // this works for glyphs like 8 but not for other intersections 137 /* 138 foreach (Path p in o.paths) { 139 if (has_points_outside (o, p)) { 140 p.force_direction (Direction.CLOCKWISE); 141 } else { 142 p.force_direction (Direction.COUNTER_CLOCKWISE); 143 } 144 }*/ 145 146 //n = merge (n); 147 148 // FIXME: this needs to be solved. 149 // remove_self_intersecting_corners (n); 150 151 // n = remove_remaining_corners (n); 152 153 // return n; // FIXME: 154 return o; 155 } 156 157 static PathList remove_remaining_corners (PathList pl) { 158 PathList r = new PathList (); 159 160 foreach (Path p in pl.paths) { 161 if (!has_remove_parts (p)) { 162 r.add (p); 163 } else { 164 if (stroke_selected) { // FIXME: DELETE 165 ((!) BirdFont.get_current_font ().get_glyph ("k")).add_path (p); 166 } 167 } 168 } 169 170 return r; 171 } 172 173 static bool has_remove_parts (Path p) { 174 EditPointHandle l, r; 175 176 foreach (EditPoint ep in p.points) { 177 if ((ep.flags & EditPoint.REMOVE_PART) > 0 || (ep.flags & EditPoint.NEW_CORNER) > 0) { 178 l = ep.get_left_handle (); 179 r = ep.get_right_handle (); 180 181 if (fabs (l.angle - r.angle) < 0.005 182 && l.length > 0.001 183 && r.length > 0.001) { 184 185 if ((ep.flags & EditPoint.REMOVE_PART) > 0) { 186 if (p.points.size > 5) { 187 return false; 188 } 189 } 190 191 if ((ep.flags & EditPoint.NEW_CORNER) > 0) { 192 if (p.points.size > 5) { 193 return false; 194 } 195 } 196 197 ep.color = Color.red (); 198 return true; 199 } 200 } 201 } 202 203 return false; 204 } 205 206 static bool is_corner_self_intersection (Path p) { 207 EditPointHandle l, r; 208 bool corner, i, remove; 209 210 remove = false; 211 i = false; 212 p.remove_points_on_points (); 213 foreach (EditPoint ep in p.points) { 214 corner = (ep.flags & EditPoint.NEW_CORNER) > 0; 215 216 if (corner || i) { 217 l = ep.get_left_handle (); 218 r = ep.get_right_handle (); 219 220 if (fabs (l.angle - r.angle) < 0.005) { 221 remove = true; 222 ep.color = Color.red (); 223 } 224 225 if (Path.distance_to_point (ep.get_prev (), ep.get_next ()) < 1) { 226 ep.deleted = true; 227 ep.color = Color.red (); 228 p.remove_deleted_points (); 229 return is_corner_self_intersection (p) || is_counter_to_outline (p); 230 } 231 } 232 233 i = corner && p.points.size == 4; 234 235 if ((ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 236 ep.flags |= EditPoint.REMOVE_PART; 237 return false; 238 } 239 } 240 241 return remove; 242 } 243 244 static void remove_self_intersecting_corners (PathList pl) { 245 PathList parts; 246 foreach (Path p in pl.paths) { 247 248 if (is_corner_self_intersection (p)) { 249 parts = get_parts (p); 250 if (parts.paths.size > 1) { 251 pl.paths.remove (p); 252 pl.append (parts); 253 remove_self_intersecting_corners (pl); 254 return; 255 } else { 256 257 if (stroke_selected) { // FIXME: DELETE 258 ((!) BirdFont.get_current_font ().get_glyph ("l")).add_path (p); 259 } 260 261 pl.paths.remove (p); 262 remove_self_intersecting_corners (pl); 263 return; 264 } 265 } 266 } 267 } 268 269 /** Create one stroke from the outline and counter stroke and close the 270 * open endings. 271 * 272 * @param path the path to create stroke for 273 * @param stroke for the outline of path 274 * @param stroke for the counter path 275 */ 276 static Path merge_strokes (Path path, Path stroke, Path counter) { 277 Path merged; 278 EditPoint last_counter, first; 279 280 merged = stroke.copy (); 281 counter.reverse (); 282 283 counter.reverse (); 284 merged.reverse (); 285 286 last_counter = new EditPoint (); 287 first = new EditPoint (); 288 289 merged.append_path (counter); 290 291 merged.close (); 292 merged.create_list (); 293 merged.recalculate_linear_handles (); 294 295 if (path.is_open ()) { 296 first = merged.get_first_point (); 297 last_counter = merged.get_last_point (); 298 299 first.get_left_handle ().convert_to_line (); 300 first.recalculate_linear_handles (); 301 302 last_counter.get_right_handle ().convert_to_line (); 303 last_counter.recalculate_linear_handles (); 304 } 305 306 return merged; 307 } 308 309 static Path create_stroke (Path p, double thickness) { 310 Path stroked; 311 Path path; 312 313 if (p.points.size >= 2) { 314 path = p.copy (); 315 stroked = generate_stroke (path, thickness); 316 317 if (!p.is_open ()) { 318 stroked.reverse (); 319 stroked.close (); 320 } 321 } else { 322 // TODO: create stroke for a path with one point 323 warning ("One point."); 324 stroked = new Path (); 325 } 326 327 return stroked; 328 } 329 330 static Path generate_stroke (Path p, double thickness) { 331 Path stroked = new Path (); 332 EditPoint start = new EditPoint (); 333 EditPoint end; 334 EditPoint previous; 335 EditPoint next; 336 EditPoint ep; 337 338 EditPoint original_start; 339 EditPoint original_end; 340 EditPoint original_next; 341 342 int i; 343 bool bump, previous_bump; 344 double small_part = 0.4 * fabs (thickness); 345 346 previous = p.get_first_point ().copy (); 347 move_segment (start, previous, thickness); 348 349 i = 0; 350 previous_bump = false; 351 for (int j = 0; j < p.points.size; j++) { 352 original_start = p.points.get (j % p.points.size); 353 original_end = p.points.get ((j + 1) % p.points.size).copy (); 354 original_next = p.points.get ((j + 2) % p.points.size).copy (); 355 356 ep = original_start.copy (); 357 start = original_start.copy (); 358 end = original_end.copy (); 359 next = original_next.copy (); 360 361 bump = Path.distance_to_point (previous, start) < small_part; 362 bump = false; 363 364 if (bump) { 365 Gee.ArrayList<EditPoint> s = new Gee.ArrayList<EditPoint> (); 366 367 Path.all_of (start, end, (x, y, t) => { 368 EditPoint e = stroked.add (x, y); 369 e.set_point_type (PointType.LINE_CUBIC); 370 e.get_right_handle ().set_point_type (PointType.LINE_CUBIC); 371 e.get_left_handle ().set_point_type (PointType.LINE_CUBIC); 372 s.add (e); 373 return true; 374 }, 4); 375 376 foreach (EditPoint e in s) { 377 e.recalculate_linear_handles (); 378 move_segment (new EditPoint (), e, thickness); 379 } 380 } else { 381 move_segment (start, end, thickness); 382 } 383 384 if (start == p.get_last_point ()) { 385 end = p.get_first_point (); 386 } 387 388 start.flags |= EditPoint.STROKE_OFFSET; 389 end.flags |= EditPoint.STROKE_OFFSET; 390 391 bool flat = (Path.distance_to_point (previous, start) < 0.05 * thickness); 392 393 if (!flat && !p.is_open () || (i != 0 && i != p.points.size - 1)) { 394 if (!bump) { 395 if (!ep.tie_handles) { 396 add_corner (stroked, previous, start, ep.copy (), thickness); 397 } else { 398 warning ("Tied handles."); 399 } 400 } 401 } 402 403 if (!bump && start.is_valid () && end.is_valid ()) { 404 stroked.add_point (start); 405 stroked.add_point (end); 406 } else { 407 warning ("Bad point in stroke."); 408 } 409 410 adjust_handles (start, end, next, original_start, original_end, original_next); 411 412 // open ends around corner 413 start.get_left_handle ().convert_to_line (); 414 end.get_right_handle ().convert_to_line (); 415 416 previous = end; 417 previous_bump = bump; 418 419 i++; 420 } 421 422 stroked.recalculate_linear_handles (); 423 424 return stroked; 425 } 426 427 static void adjust_handles (EditPoint stroke_start, EditPoint stroke_end, EditPoint stroke_next, 428 EditPoint start, EditPoint end, EditPoint next) { 429 double px, py; 430 double dp = Path.distance_to_point (stroke_start, stroke_end); 431 double dn = Path.distance_to_point (stroke_end, stroke_next); 432 double op = Path.distance_to_point (start, end); 433 double on = Path.distance_to_point (end, next); 434 double rp = dp / op; 435 double rn = on / dn; 436 EditPointHandle r = stroke_start.get_right_handle (); 437 EditPointHandle l = stroke_end.get_left_handle (); 438 439 if (!r.is_line ()) { 440 if (r.type == PointType.CUBIC) { 441 r.length *= rp; 442 } else { 443 Path.find_intersection_handle (r, l, out px, out py); 444 445 if (EditPoint.is_valid_position (px, py)) { 446 l.move_to_coordinate (px, py); 447 r.move_to_coordinate (px, py); 448 } else { 449 warning ("Invalid position."); 450 } 451 } 452 453 if (l.type == PointType.CUBIC) { 454 l.length *= rn; 455 } 456 } 457 } 458 459 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) { 460 EditPointHandle r, l; 461 double m, n; 462 double qx, qy; 463 464 stroke_start.set_tie_handle (false); 465 stroke_stop.set_tie_handle (false); 466 467 r = stroke_start.get_right_handle (); 468 l = stroke_stop.get_left_handle (); 469 470 m = cos (r.angle + PI / 2) * thickness; 471 n = sin (r.angle + PI / 2) * thickness; 472 473 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n); 474 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n); 475 476 stroke_start.independent_x += m; 477 stroke_start.independent_y += n; 478 479 qx = cos (l.angle - PI / 2) * thickness; 480 qy = sin (l.angle - PI / 2) * thickness; 481 482 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy); 483 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy); 484 485 stroke_stop.independent_x += qx; 486 stroke_stop.independent_y += qy; 487 } 488 489 static void add_corner (Path stroked, EditPoint previous, EditPoint next, 490 EditPoint original, double stroke_width) { 491 492 double ratio; 493 double distance; 494 EditPoint corner; 495 double corner_x, corner_y; 496 EditPointHandle previous_handle; 497 EditPointHandle next_handle; 498 EditPoint cutoff1, cutoff2; 499 double adjusted_stroke = (stroke_width * 0.999999) / 2.0; 500 501 previous_handle = previous.get_left_handle (); 502 next_handle = next.get_right_handle (); 503 504 previous_handle.angle += PI; 505 next_handle.angle += PI; 506 507 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y); 508 corner = new EditPoint (corner_x, corner_y, previous.type); 509 corner.convert_to_line (); 510 511 previous_handle.angle -= PI; 512 next_handle.angle -= PI; 513 514 distance = Path.distance_to_point (corner, original); 515 ratio = 1.5 * fabs (adjusted_stroke) / distance; 516 517 if (ratio > 1) { 518 stroked.add_point (corner); 519 } else { 520 cutoff1 = new EditPoint (); 521 cutoff1.set_point_type (previous.type); 522 cutoff1.convert_to_line (); 523 524 cutoff2 = new EditPoint (); 525 cutoff2.set_point_type (previous.type); 526 cutoff2.convert_to_line (); 527 528 cutoff1.x = previous.x + (corner.x - previous.x) * ratio; 529 cutoff1.y = previous.y + (corner.y - previous.y) * ratio; 530 531 cutoff2.x = next.x + (corner.x - next.x) * ratio; 532 cutoff2.y = next.y + (corner.y - next.y) * ratio; 533 534 if (!cutoff1.is_valid () || cutoff2.is_valid ()) { 535 cutoff1 = stroked.add_point (cutoff1); 536 cutoff2 = stroked.add_point (cutoff2); 537 } 538 539 cutoff1.recalculate_linear_handles (); 540 cutoff2.recalculate_linear_handles (); 541 542 if (distance > 4 * stroke_width) { 543 previous.flags = EditPoint.NONE; 544 next.flags = EditPoint.NONE; 545 } else { 546 previous.flags |= EditPoint.NEW_CORNER; 547 next.flags |= EditPoint.NEW_CORNER; 548 } 549 } 550 } 551 552 static PathList get_parts (Path path) { 553 PathList intersections; 554 PathList r; 555 556 r = get_parts_self (path); 557 intersections = new PathList (); 558 559 foreach (Path p in r.paths) { 560 intersections.add (p); 561 } 562 563 return intersections; 564 } 565 566 public static bool is_counter_to_outline (Path p) { 567 EditPoint p1, p2; 568 EditPoint a1, a2; 569 570 if (p.points.size == 0) { 571 return false; 572 } 573 574 for (int index = 1; index < p.points.size + 2; index++) { 575 p1 = p.points.get ((index - 1) % p.points.size); 576 p2 = p.points.get (index % p.points.size); 577 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 578 a2 = p.points.get ((index + 4) % p.points.size); 579 580 if ((p2.flags & EditPoint.STROKE_OFFSET) > 0 581 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) { 582 return true; 583 } 584 } 585 586 return false; 587 } 588 589 static bool split_corner (PathList pl) { 590 EditPoint p1, p2; 591 EditPoint a1, a2; 592 PathList result; 593 bool split; 594 595 foreach (Path p in pl.paths) { 596 if (p.points.size == 0) { 597 continue; 598 } 599 600 for (int index = 1; index < p.points.size + 2; index++) { 601 p1 = p.points.get ((index - 1) % p.points.size); 602 p2 = p.points.get (index % p.points.size); 603 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 604 a2 = p.points.get ((index + 4) % p.points.size); 605 606 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 607 || (p2.flags & EditPoint.STROKE_OFFSET) > 0 608 || (a1.flags & EditPoint.STROKE_OFFSET) > 0 609 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) { 610 611 split = split_segment (p, a1, a2, p1, p2, out result); 612 613 if (split) { 614 pl.append (result); 615 pl.paths.remove (p); 616 split_corner (pl); 617 return true; 618 } else { 619 p1 = p.points.get ((index - 1) % p.points.size); 620 p2 = p.points.get (index % p.points.size); 621 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead 622 a2 = p.points.get ((index + 3) % p.points.size); 623 624 split = split_segment (p, a1, a2, p1, p2, out result); 625 626 if (split) { 627 pl.append (result); 628 pl.paths.remove (p); 629 split_corner (pl); 630 return true; 631 } else { 632 p1 = p.points.get ((index - 1) % p.points.size); 633 p2 = p.points.get (index % p.points.size); 634 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 635 a2 = p.points.get ((index + 4) % p.points.size); 636 637 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 638 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) { 639 p1.flags = EditPoint.COUNTER_TO_OUTLINE; 640 a1.flags = EditPoint.COUNTER_TO_OUTLINE; 641 } 642 } 643 } 644 } 645 } 646 } 647 648 return false; 649 } 650 651 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) { 652 double ix, iy; 653 bool intersection; 654 int i; 655 656 result = new PathList (); 657 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true); 658 659 if (intersection) { 660 add_intersection (p, first, next, ix, iy); 661 add_intersection (p, p1, p2, ix, iy); 662 663 i = mark_intersection_as_deleted (p); 664 return_val_if_fail (i == 2, false); 665 666 result.append (get_remaining_points (p.copy ())); 667 } 668 669 return intersection; 670 } 671 672 static bool split_path (Path path1, Path path2, PathList result) { 673 PathList pl1, pl2; 674 Path a1, a2, b1, b2; 675 Path m1, m2; 676 int i; 677 678 if (path1 == path2) { 679 return false; 680 } 681 682 if (add_intersection_points (path1, path2, 2)) { 683 i = mark_intersection_as_deleted (path1); 684 return_if_fail (i == 2); 685 686 i = mark_intersection_as_deleted (path2); 687 return_if_fail (i == 2); 688 689 pl1 = get_remaining_points (path1.copy ()); 690 pl2 = get_remaining_points (path2.copy ()); 691 692 return_if_fail (pl1.paths.size == 2); 693 return_if_fail (pl2.paths.size == 2); 694 695 a1 = pl1.paths.get (0); 696 a2 = pl1.paths.get (1); 697 b1 = pl2.paths.get (0); 698 b2 = pl2.paths.get (1); 699 700 m1 = PenTool.merge_open_paths (a1, b2); 701 m2 = PenTool.merge_open_paths (b1, a2); 702 703 result.add (m1); 704 result.add (m2); 705 706 return true; 707 } 708 709 return false; 710 } 711 712 static PathList split_paths (PathList pl) { 713 PathList n = new PathList (); 714 715 n.append (pl); 716 717 foreach (Path p1 in pl.paths) { 718 foreach (Path p2 in pl.paths) { 719 if (p1 != p2) { 720 if (split_path (p1, p2, n)) { 721 n.paths.remove (p1); 722 n.paths.remove (p2); 723 return split_paths (n); 724 } 725 } 726 } 727 } 728 729 return n; 730 } 731 732 static PathList get_parts_self (Path path, PathList? paths = null) { 733 PathList pl; 734 PathList r; 735 736 r = paths == null ? new PathList () : (!) paths; 737 pl = split (path); 738 739 foreach (Path part in pl.paths) { 740 if (!has_self_intersection (part)) { 741 r.add (part); 742 } else { 743 get_parts_self (part, r); 744 } 745 } 746 747 if (r.paths.size == 0) { 748 warning ("No parts in path"); 749 } 750 751 return r; 752 } 753 754 755 static bool has_intersection_points (Path path) { 756 foreach (EditPoint p in path.points) { 757 if ((p.flags & EditPoint.INTERSECTION) > 0) { 758 return true; 759 } 760 } 761 return false; 762 } 763 764 /** Split one path at intersection points in two parts. */ 765 static PathList split (Path path) { 766 Path new_path; 767 PathList pl; 768 int i; 769 770 if (!has_intersection_points (path)) { 771 add_self_intersection_points (path); 772 } else { 773 warning ("points already created."); 774 } 775 776 foreach (EditPoint p in path.points) { 777 if (insides (p, path) == 1) { 778 path.set_new_start (p); 779 path.close (); 780 break; 781 } 782 } 783 784 i = mark_intersection_as_deleted (path); 785 786 if (!(i == 0 || i == 2)) { 787 warning (@"Split should only create two parts, $i points will be deleted."); 788 } 789 790 new_path = path.copy (); 791 pl = get_remaining_points (new_path); 792 793 return pl; 794 } 795 796 static PathList process_deleted_control_points (Path path) { 797 PathList paths, nl, pl, rl, result; 798 799 paths = new PathList (); 800 rl = new PathList (); 801 pl = new PathList (); 802 nl = new PathList (); 803 804 if (!path.has_deleted_point ()) { 805 return pl; 806 } 807 808 pl.add (path); 809 810 foreach (Path p in pl.paths) { 811 nl = p.process_deleted_points (); 812 813 if (nl.paths.size > 0) { 814 rl.append (nl); 815 rl.paths.remove (p); 816 } 817 } 818 819 result = new PathList (); 820 foreach (Path p in rl.paths) { 821 pl = process_deleted_control_points (p); 822 823 if (pl.paths.size > 0) { 824 result.append (pl); 825 } else { 826 result.add (p); 827 } 828 } 829 830 for (int i = 1; i < result.paths.size; i++) { 831 result.paths.get (i).reverse (); 832 } 833 834 paths.append (result); 835 836 return paths; 837 } 838 839 static PathList get_remaining_points (Path old_path) { 840 PathList pl; 841 842 old_path.close (); 843 pl = process_deleted_control_points (old_path); 844 845 if (pl.paths.size == 0) { 846 pl.add (old_path); 847 } 848 849 foreach (Path pn in pl.paths) { 850 pn.close (); 851 } 852 853 return pl; 854 } 855 856 static bool has_self_intersection (Path path) { 857 bool intersection = false; 858 859 path.all_segments ((ep1, ep2) => { 860 double ix, iy; 861 EditPoint p1, p2; 862 863 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true)) { 864 intersection = true; 865 return false; 866 } 867 868 return true; 869 }); 870 871 return intersection; 872 } 873 874 static bool add_self_intersection_points (Path path, bool only_offsets = false) { 875 bool intersection = false; 876 877 path.all_segments ((ep1, ep2) => { 878 double ix, iy; 879 EditPoint p1, p2; 880 881 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) { 882 add_intersection (path, ep1, ep2, ix, iy); 883 add_intersection (path, p1, p2, ix, iy); 884 885 intersection = true; 886 return false; 887 } 888 889 return true; 890 }); 891 892 return intersection; 893 } 894 895 static EditPoint add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) { 896 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> (); 897 EditPoint ep1 = new EditPoint (); 898 EditPoint ep2 = new EditPoint (); 899 EditPoint ep3 = new EditPoint (); 900 901 if (next == path.get_first_point ()) { 902 ep1.prev = null; 903 } else { 904 ep1.prev = prev; 905 } 906 907 ep1.prev = prev; 908 ep1.next = ep2; 909 ep1.flags |= EditPoint.NEW_CORNER; 910 ep1.type = prev.type; 911 ep1.x = px; 912 ep1.y = py; 913 ep1.color = c; 914 n.add (ep1); 915 916 ep2.prev = ep1; 917 ep2.next = ep3; 918 ep2.flags |= EditPoint.INTERSECTION; 919 ep2.type = prev.type; 920 ep2.x = px; 921 ep2.y = py; 922 ep2.color = c; 923 n.add (ep2); 924 925 ep3.prev = ep2; 926 ep3.next = next; 927 ep3.flags |= EditPoint.NEW_CORNER; 928 ep3.type = prev.type; 929 ep3.x = px; 930 ep3.y = py; 931 ep3.color = c; 932 n.add (ep3); 933 934 foreach (EditPoint np in n) { 935 np = path.add_point_after (np, np.prev); 936 path.create_list (); 937 } 938 939 PenTool.convert_point_to_line (ep1, true); 940 PenTool.convert_point_to_line (ep2, true); 941 PenTool.convert_point_to_line (ep3, true); 942 943 ep1.recalculate_linear_handles (); 944 ep2.recalculate_linear_handles (); 945 ep3.recalculate_linear_handles (); 946 947 return ep2; 948 } 949 950 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next, 951 out double ix, out double iy, 952 bool skip_points_on_points = false) { 953 double cross_x, cross_y; 954 955 ix = 0; 956 iy = 0; 957 958 if (is_line (ep.x, ep.y, p1.x, p1.y, next.x, next.y)) { 959 ix = p1.x; 960 iy = p1.y; 961 return true; 962 } 963 964 if (is_line (ep.x, ep.y, p2.x, p2.y, next.x, next.y)) { 965 ix = p2.x; 966 iy = p2.y; 967 return true; 968 } 969 970 if (is_line (p1.x, p1.y, ep.x, ep.y, p2.x, p2.y)) { 971 ix = ep.x; 972 iy = ep.y; 973 return true; 974 } 975 976 if (is_line (p1.x, p1.y, next.x, next.y, p2.x, p2.y)) { 977 ix = next.x; 978 iy = next.y; 979 return true; 980 } 981 982 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y); 983 984 if (Glyph.CANVAS_MIN < cross_x < Glyph.CANVAS_MAX 985 && Glyph.CANVAS_MIN < cross_y < Glyph.CANVAS_MAX) { 986 // iterate to find intersection. 987 /* 988 if (skip_points_on_points || 989 !((ep.x == cross_x && ep.y == cross_y) 990 || (next.x == cross_x && next.y == cross_y) 991 || (p1.x == cross_x && p1.y == cross_y) 992 || (p2.x == cross_x && p2.y == cross_y))) { 993 */ 994 995 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y) 996 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) { 997 998 ix = cross_x; 999 iy = cross_y; 1000 1001 return true; 1002 } 1003 } 1004 // } 1005 1006 return false; 1007 } 1008 1009 static bool segment_intersects (Path path, EditPoint ep, EditPoint next, 1010 out double ix, out double iy, 1011 out EditPoint ia, out EditPoint ib, 1012 bool skip_points_on_points = false, 1013 bool only_offsets = false) { 1014 1015 EditPoint p1, p2; 1016 bool intersection, inter; 1017 double iix, iiy; 1018 1019 double distance, min_distance; 1020 1021 intersection = false; 1022 1023 ix = 0; 1024 iy = 0; 1025 1026 iix = 0; 1027 iiy = 0; 1028 1029 ia = new EditPoint (); 1030 ib = new EditPoint (); 1031 1032 if (path.points.size == 0) { 1033 return false; 1034 } 1035 1036 min_distance = double.MAX; 1037 p1 = path.points.get (path.points.size - 1); 1038 for (int i = 0; i < path.points.size; i++) { 1039 p2 = path.points.get (i); 1040 1041 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0) 1042 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0) 1043 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0) 1044 && ((next.flags & EditPoint.STROKE_OFFSET) > 0); 1045 1046 if (!only_offsets || is_offset) { 1047 if (p1 != ep && p2 != next) { 1048 inter = segments_intersects (p1, p2, ep, next, out iix, out iiy, 1049 skip_points_on_points); 1050 1051 if (inter) { 1052 distance = Path.distance (ep.x, iix, ep.y, iiy); 1053 if (distance < min_distance) { 1054 ia = p1; 1055 ib = p2; 1056 ix = iix; 1057 iy = iiy; 1058 intersection = true; 1059 min_distance = distance; 1060 } 1061 } 1062 } 1063 } 1064 1065 p1 = p2; 1066 } 1067 1068 return intersection; 1069 } 1070 1071 /** @return true if p2 is on the line p1 to p3 */ 1072 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.01) { 1073 return fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3) 1074 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3) 1075 && is_flat (x1, y1, x2, y2, x3, y3, tolerance); 1076 } 1077 1078 public static bool is_flat (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.001) { 1079 double ds = Path.distance (x1, x3, y1, y3); 1080 double d1 = Path.distance (x1, x2, y1, y2); 1081 double d2 = Path.distance (x2, x3, y2, y3); 1082 double p = d1 / ds; 1083 double x = fabs ((x3 - x1) * p - (x2 - x1)); 1084 double y = fabs ((y3 - y1) * p - (y2 - y1)); 1085 double d = fabs (ds - (d1 + d2)); 1086 1087 return ds > 0.001 && d1 > 0.001 && d2 > 0.001 1088 && d < tolerance && x < tolerance && y < tolerance; 1089 } 1090 1091 // indside becomes outside in some paths 1092 static void remove_points_in_stroke (PathList pl) { 1093 PathList r; 1094 1095 foreach (Path p in pl.paths) { 1096 if (remove_points_in_stroke_for_path (p, pl, out r)) { 1097 pl.append (r); 1098 remove_points_in_stroke (pl); 1099 return; 1100 } 1101 } 1102 } 1103 1104 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) { 1105 EditPoint start_ep; 1106 EditPoint start_next; 1107 EditPoint start_prev; 1108 EditPoint end_ep = new EditPoint (); 1109 EditPoint end_next; 1110 EditPoint end_prev; 1111 1112 result = new PathList (); 1113 1114 for (int i = 1; i < p.points.size + 1; i++) { 1115 start_prev = p.points.get ((i - 1) % p.points.size); 1116 start_ep = p.points.get (i % p.points.size); 1117 start_next = p.points.get ((i + 1) % p.points.size); 1118 1119 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1120 for (int j = i; j < p.points.size + i; j++) { 1121 end_prev = p.points.get ((j - 1) % p.points.size); 1122 end_ep = p.points.get (j % p.points.size); 1123 end_next = p.points.get ((j + 1) % p.points.size); 1124 1125 1126 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1127 start_ep.flags = EditPoint.NONE; 1128 end_ep.flags = EditPoint.NONE; 1129 1130 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) { 1131 return true; 1132 } 1133 } 1134 } 1135 } 1136 1137 start_ep.flags = EditPoint.NONE; 1138 end_ep.flags = EditPoint.NONE; 1139 } 1140 1141 return false; 1142 } 1143 1144 static bool merge_segments (PathList pl, 1145 Path path1, EditPoint start1, EditPoint stop1, 1146 EditPoint start2, EditPoint stop2, 1147 out PathList result) { 1148 1149 result = new PathList (); 1150 1151 PathList r1; 1152 PathList r2; 1153 1154 foreach (Path path2 in pl.paths) { 1155 if (path2 != path1) { 1156 reset_intersections (path1); 1157 reset_intersections (path2); 1158 1159 if (add_merge_intersection_point (path1, path2, start1, stop1)) { 1160 if (add_merge_intersection_point (path1, path2, start2, stop2)) { 1161 1162 r1 = get_remaining_points (path1.copy ()); 1163 r2 = get_remaining_points (path2.copy ()); 1164 1165 if (r1.paths.size != 2) { 1166 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n"); 1167 reset_intersections (path1); 1168 reset_intersections (path2); 1169 return true; 1170 } 1171 1172 if (r2.paths.size != 2) { 1173 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n"); 1174 reset_intersections (path1); 1175 reset_intersections (path2); 1176 return true; 1177 } 1178 1179 pl.paths.remove (path1); 1180 pl.paths.remove (path2); 1181 1182 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (), 1183 r2.paths.get (0).get_first_point ()); 1184 1185 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (), 1186 r2.paths.get (1).get_first_point ()); 1187 1188 Path m1, m2; 1189 1190 if (d1 > d2) { 1191 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0)); 1192 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1)); 1193 } else { 1194 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0)); 1195 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1)); 1196 } 1197 1198 result.add (m1); 1199 result.add (m2); 1200 1201 return true; 1202 } else { 1203 reset_intersections (path1); 1204 reset_intersections (path2); 1205 } 1206 } else { 1207 reset_intersections (path1); 1208 reset_intersections (path2); 1209 } 1210 } 1211 } 1212 1213 return false; 1214 } 1215 1216 static void reset_intersections (Path p) { 1217 foreach (EditPoint ep in p.points) { 1218 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION; 1219 ep.flags &= uint.MAX ^ EditPoint.COPIED; 1220 ep.deleted = false; 1221 } 1222 p.remove_points_on_points (); 1223 } 1224 1225 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) { 1226 double ix, iy; 1227 bool intersection; 1228 1229 intersection = false; 1230 ix = 0; 1231 iy = 0; 1232 path2.all_segments ((p1, p2) => { 1233 int i; 1234 1235 intersection = segments_intersects (first, next, p1, p2, out ix, out iy); 1236 1237 if (intersection) { 1238 add_intersection (path1, first, next, ix, iy); 1239 add_intersection (path2, p1, p2, ix, iy); 1240 1241 i = mark_intersection_as_deleted (path1); 1242 i = mark_intersection_as_deleted (path2); 1243 } 1244 1245 return !intersection; 1246 }); 1247 1248 return intersection; 1249 } 1250 1251 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) { 1252 outline = new Path (); 1253 foreach (Path p in pl.paths) { 1254 if (p != ps.path) { 1255 if (is_inside (ps.point, p)) { 1256 outline = p; 1257 return true; 1258 } 1259 } 1260 } 1261 1262 return false; 1263 } 1264 1265 static PathList get_all_parts (PathList pl) { 1266 PathList m; 1267 bool intersects = false; 1268 PathList r = new PathList (); 1269 1270 foreach (Path p in pl.paths) { 1271 if (has_self_intersection (p)) { 1272 m = get_parts (p); 1273 r.append (m); 1274 intersects = true; 1275 } else { 1276 r.add (p); 1277 } 1278 } 1279 1280 foreach (Path p in r.paths) { 1281 p.close (); 1282 p.update_region_boundaries (); 1283 } 1284 1285 if (intersects) { 1286 return get_all_parts (r); 1287 } 1288 1289 return r; 1290 } 1291 1292 static PathList merge (PathList pl) { 1293 bool error = false; 1294 PathList m; 1295 PathList r = pl; 1296 Path p1, p2; 1297 1298 r = get_all_parts (r); 1299 1300 while (paths_has_intersection (r, out p1, out p2)) { 1301 if (merge_path (p1, p2, out m, out error)) { 1302 r.paths.remove (p1); 1303 r.paths.remove (p2); 1304 1305 foreach (Path np in m.paths) { 1306 np.remove_points_on_points (); 1307 r.add (np); 1308 } 1309 1310 r = get_all_parts (r); 1311 } else { 1312 warning ("Not merged."); 1313 } 1314 1315 if (error) { 1316 warning ("Merge error"); 1317 break; 1318 } 1319 } 1320 1321 if (!error) { 1322 remove_merged_parts (r); 1323 } 1324 1325 foreach (Path p in r.paths) { 1326 p.close (); 1327 p.recalculate_linear_handles (); 1328 } 1329 1330 return r; 1331 } 1332 1333 static bool has_zero_area_segment (Path p) { 1334 EditPointHandle l, r; 1335 1336 p.recalculate_linear_handles (); 1337 1338 foreach (EditPoint ep in p.points) { 1339 l = ep.get_left_handle (); 1340 r = ep.get_right_handle (); 1341 if (!(fabs (l.angle - r.angle) < 0.0001 && l.length > 0.01 && r.length > 0.01)) { 1342 return false; 1343 } 1344 } 1345 return true; 1346 } 1347 1348 static void remove_merged_parts (PathList r) { 1349 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> (); 1350 int c; 1351 1352 foreach (Path p in r.paths) { 1353 p.update_region_boundaries (); 1354 } 1355 1356 foreach (Path p in r.paths) { 1357 c = counters (r, p); // FIXME: this needs improvements 1358 1359 if (has_zero_area_segment (p)) { 1360 remove.add (p); 1361 } 1362 1363 if (c % 2 == 0) { 1364 1365 if (!is_clockwise (p)) { 1366 remove.add (p); 1367 } 1368 1369 if (stroke_selected) 1370 ((!) BirdFont.get_current_font ().get_glyph ("m")).add_path (p); 1371 1372 } else { 1373 if (stroke_selected) 1374 ((!) BirdFont.get_current_font ().get_glyph ("n")).add_path (p); 1375 1376 if (is_clockwise (p)) { 1377 remove.add (p); 1378 } 1379 } 1380 } 1381 1382 if (stroke_selected) { // FIXME: DELETE 1383 foreach (Path mm in r.paths) 1384 ((!) BirdFont.get_current_font ().get_glyph ("i")).add_path (mm); 1385 } 1386 1387 foreach (Path p in remove) { 1388 r.paths.remove (p); 1389 } 1390 1391 if (stroke_selected) { // FIXME: DELETE 1392 foreach (Path mm in r.paths) 1393 ((!) BirdFont.get_current_font ().get_glyph ("j")).add_path (mm); 1394 } 1395 } 1396 1397 public static int counters (PathList pl, Path path) { 1398 int inside_count = 0; 1399 bool inside; 1400 1401 foreach (Path p in pl.paths) { 1402 inside = true; 1403 1404 if (p.points.size > 1 1405 && p != path 1406 && path.boundaries_intersecting (p)) { 1407 1408 // FIXME: all points can be corners in counter paths 1409 foreach (EditPoint ep in path.points) { 1410 if (!is_inside (ep, p)) { 1411 inside = false; 1412 } 1413 } 1414 1415 if (inside) { 1416 inside_count++; 1417 } 1418 } 1419 } 1420 1421 return inside_count; 1422 } 1423 1424 public static bool is_inside (EditPoint point, Path path) { 1425 EditPoint prev; 1426 bool inside = false; 1427 1428 if (path.points.size <= 1) { 1429 return false; 1430 } 1431 1432 /* //FIXME: DELETE 1433 if (!(path.xmin < point.x < path.xmax)) { 1434 return false; 1435 } 1436 1437 if (!(path.ymin < point.y < path.ymax)) { 1438 return false; 1439 } 1440 */ 1441 1442 prev = path.points.get (path.points.size - 1); 1443 1444 foreach (EditPoint p in path.points) { 1445 if ((p.x == point.x && p.y == point.y) || (prev.x == point.x && prev.y == point.y)) { 1446 point.color = Color.green (); 1447 return true; 1448 continue; 1449 } else if ((p.y > point.y) != (prev.y > point.y) 1450 && point.x < (prev.x - p.x) * (point.y - p.y) / (prev.y - p.y) + p.x) { 1451 inside = !inside; 1452 point.color = Color.yellow (); 1453 } 1454 1455 prev = p; 1456 } 1457 1458 return inside; 1459 } 1460 1461 public static int insides (EditPoint point, Path path) { 1462 EditPoint prev; 1463 int inside = 0; 1464 1465 if (path.points.size <= 1) { 1466 return 0; 1467 } 1468 1469 prev = path.get_last_point (); 1470 1471 foreach (EditPoint start in path.points) { 1472 if (start.x == point.x && point.y == start.y) { 1473 inside++; 1474 } else if ((start.y > point.y) != (prev.y > point.y) 1475 && point.x < (prev.x - start.x) * (point.y - start.y) / (prev.y - start.y) + start.x) { 1476 inside++; 1477 } 1478 1479 prev = start; 1480 } 1481 1482 return inside; 1483 } 1484 1485 static bool merge_path (Path path1, Path path2, out PathList merged_paths, out bool error) { 1486 IntersectionList intersections; 1487 EditPoint ep1, next, p1, p2, pp1, pp2; 1488 Path path, other, merged; 1489 PathList r, other_paths, result; 1490 bool intersects; 1491 int s, i; 1492 double ix, iy, iix, iiy; 1493 bool merge = false; 1494 EditPoint intersection_point, other_intersection_point; 1495 bool path1_direction, path2_direction; 1496 1497 error = false; 1498 merged_paths = new PathList (); 1499 intersections = new IntersectionList (); 1500 1501 reset_intersections (path1); 1502 reset_intersections (path2); 1503 1504 iix = 0; 1505 iiy = 0; 1506 1507 result = new PathList (); 1508 1509 if (path1.points.size == 0 || path2.points.size == 0) { 1510 warning ("No points in path."); 1511 error = true; 1512 return false; 1513 } 1514 1515 if (!path1.boundaries_intersecting (path2)) { 1516 return false; 1517 } 1518 1519 Path original_path1 = path1.copy (); 1520 Path original_path2 = path2.copy (); 1521 1522 s = 0; 1523 foreach (EditPoint e in original_path1.points) { 1524 if (!is_inside (e, original_path2) 1525 && insides (e, original_path1) == 1) { // FIXME: later as well 1526 break; 1527 } 1528 s++; 1529 } 1530 1531 if (s >= path1.points.size) { 1532 Path t; 1533 t = original_path1; 1534 original_path1 = original_path2; 1535 original_path2 = t; 1536 s = 0; 1537 foreach (EditPoint e in original_path1.points) { 1538 if (!is_inside (e, original_path2)) { 1539 break; 1540 } 1541 s++; 1542 } 1543 } 1544 1545 if (s >= original_path1.points.size) { 1546 warning ("No start point found."); 1547 error = true; 1548 return false; 1549 } 1550 1551 path = original_path1; 1552 other = original_path2; 1553 1554 other_paths = new PathList (); 1555 r = new PathList (); 1556 other_paths.add (path); 1557 other_paths.add (other); 1558 intersects = false; 1559 p1 = new EditPoint (); 1560 p2 = new EditPoint (); 1561 pp1 = new EditPoint (); 1562 pp2 = new EditPoint (); 1563 1564 ix = 0; 1565 iy = 0; 1566 i = s; 1567 merged = new Path (); 1568 1569 path1_direction = is_clockwise (original_path1); 1570 path2_direction = is_clockwise (original_path1); 1571 1572 while (true) { 1573 ep1 = path.points.get (i % path.points.size); 1574 next = path.points.get ((i + 1) % path.points.size); 1575 1576 if ((ep1.flags & EditPoint.COPIED) > 0) { 1577 if (merge) { 1578 merged.close (); 1579 result.add (merged.copy ()); 1580 } 1581 1582 merged = new Path (); 1583 1584 bool find_parts = false; 1585 Intersection new_start = new Intersection.empty (); 1586 foreach (Intersection inter in intersections.points) { 1587 if (!inter.done && !find_parts) { 1588 find_parts = true; 1589 new_start = inter; 1590 break; 1591 } 1592 } 1593 1594 if (!find_parts) { 1595 break; // done, no more parts to merge 1596 } else { 1597 // set start point for next part 1598 path = new_start.other_path; 1599 1600 if (path.points.size == 0) { 1601 warning ("No points."); 1602 error = true; 1603 return false; 1604 } 1605 1606 i = index_of (path, new_start.get_point (path)); 1607 1608 if (i < 0) { 1609 warning ("Start point not found."); 1610 error = true; 1611 return false; 1612 } 1613 1614 ep1 = path.points.get (i % path.points.size); 1615 next = path.points.get ((i + 1) % path.points.size); 1616 1617 if ((ep1.flags & EditPoint.INTERSECTION) == 0) { 1618 warning ("Not starting on an intersection point."); 1619 error = true; 1620 return false; 1621 } 1622 1623 new_start.done = true; 1624 } 1625 } 1626 1627 intersects = false; 1628 1629 double dm; 1630 double d; 1631 1632 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 1633 Intersection current_intersection; 1634 bool continue_on_other_path; 1635 current_intersection = intersections.get_point (ep1, out continue_on_other_path); 1636 current_intersection.done = true; 1637 1638 // take the other part of an intersection 1639 if ((next.flags & EditPoint.COPIED) != 0) { 1640 bool next_is_intersection = false; 1641 bool next_continue_on_other_path; 1642 1643 next_is_intersection = ((next.flags & EditPoint.INTERSECTION) > 0); 1644 1645 if (next_is_intersection) { 1646 Intersection next_intersection = intersections.get_point (next, out next_continue_on_other_path); 1647 1648 ep1.flags |= EditPoint.COPIED; 1649 merged.add_point (ep1.copy ()); 1650 1651 if (!next_intersection.done) { 1652 EditPoint new_start_point; 1653 1654 path = next_continue_on_other_path 1655 ? next_intersection.other_path : next_intersection.path; 1656 1657 new_start_point = next_continue_on_other_path 1658 ? next_intersection.other_point : next_intersection.point; 1659 1660 i = index_of (path, new_start_point); 1661 1662 if (i < 0) { 1663 warning ("Point not found in path.\n"); 1664 error = true; 1665 return false; 1666 } 1667 1668 ep1 = path.points.get (i % path.points.size); 1669 next = path.points.get ((i + 1) % path.points.size); 1670 } else { 1671 warning ("Part is already created.\n"); 1672 error = true; 1673 return false; 1674 } 1675 } else { 1676 ep1.flags |= EditPoint.COPIED; 1677 merged.add_point (ep1.copy ()); 1678 1679 EditPoint new_start_point; 1680 1681 if ((next.flags & EditPoint.COPIED) > 0) { 1682 path = current_intersection.get_other_path (path); 1683 new_start_point = current_intersection.get_point (path); 1684 i = index_of (path, new_start_point); 1685 1686 if (i < 0) { 1687 warning ("Point not found in path."); 1688 error = true; 1689 return false; 1690 } 1691 1692 ep1 = path.points.get (i % path.points.size); 1693 next = path.points.get ((i + 1) % path.points.size); 1694 1695 if ((next.flags & EditPoint.INTERSECTION) > 0) { 1696 warning ("Wrong type."); 1697 error = true; 1698 return false; 1699 } 1700 1701 if ((next.flags & EditPoint.COPIED) > 0) { 1702 merged.add_point (ep1.copy ()); 1703 continue; 1704 } 1705 } else { 1706 ep1.flags |= EditPoint.COPIED; 1707 merged.add_point (ep1.copy ()); 1708 } 1709 } 1710 } else { 1711 ep1.flags |= EditPoint.COPIED; 1712 1713 if (path1_direction == path2_direction) { 1714 if (!is_inside (ep1, original_path1)) { 1715 merged.add_point (ep1.copy ()); 1716 } 1717 } else { 1718 merged.add_point (ep1.copy ()); 1719 } 1720 } 1721 1722 current_intersection.done = true; 1723 } else { 1724 // find new intersection 1725 dm = double.MAX; 1726 foreach (Path o in other_paths.paths) { 1727 bool inter = segment_intersects (o, ep1, next, out iix, out iiy, 1728 out pp1, out pp2); 1729 d = Path.distance (ep1.x, iix, ep1.y, iiy); 1730 if (d < dm && inter) { 1731 other = o; 1732 dm = d; 1733 intersects = true; 1734 p1 = pp1; 1735 p2 = pp2; 1736 ix = iix; 1737 iy = iiy; 1738 } 1739 1740 if (d < 0.0001) { 1741 intersects = false; 1742 } 1743 } 1744 1745 if (intersects) { 1746 merged.add_point (ep1.copy ()); 1747 ep1.flags |= EditPoint.COPIED; 1748 1749 intersection_point = add_intersection (path, ep1, next, ix, iy); 1750 other_intersection_point = add_intersection (other, p1, p2, ix, iy); 1751 1752 bool g = false; 1753 foreach (Intersection old_intersection in intersections.points) { 1754 if (old_intersection.point == intersection_point 1755 || old_intersection.other_point == other_intersection_point) { 1756 old_intersection.done = true; 1757 g = true; 1758 } 1759 } 1760 1761 if (!g) { 1762 Intersection ip = new Intersection (intersection_point, path, other_intersection_point, other); 1763 intersections.points.add (ip); 1764 } 1765 1766 merged.add_point (intersection_point.copy ()); 1767 intersection_point.flags |= EditPoint.COPIED; 1768 1769 i = index_of (other, other_intersection_point); 1770 1771 if (i < 0) { 1772 warning (@"Point not found ($i)."); 1773 break; 1774 } 1775 1776 path = other; 1777 merge = true; 1778 } else { 1779 ep1.flags |= EditPoint.COPIED; 1780 merged.add_point (ep1.copy ()); 1781 1782 PointSelection ps; 1783 Path outline; 1784 1785 // remove points inside of path 1786 if (is_clockwise (original_path2)) { 1787 ps = new PointSelection (ep1, merged); 1788 if (is_inside_of_path (ps, result, out outline)) { 1789 ep1.deleted = true; 1790 ep1.color = Color.red (); 1791 } 1792 } 1793 } 1794 } 1795 1796 i++; 1797 } 1798 1799 if (merge) { 1800 original_path1.remove_points_on_points (); 1801 original_path2.remove_points_on_points (); 1802 original_path1.remove_deleted_points (); 1803 original_path2.remove_deleted_points (); 1804 1805 foreach (Path np in result.paths) { 1806 Path p = np.copy (); 1807 bool has_direction = true; 1808 1809 p.remove_points_on_points (); 1810 1811 if (has_direction) { 1812 p.close (); 1813 reset_intersections (p); 1814 merged_paths.append (get_parts (p)); 1815 p.update_region_boundaries (); 1816 p.recalculate_linear_handles (); 1817 } 1818 } 1819 } 1820 1821 return merge && !error; 1822 } 1823 1824 static int index_of (Path p, EditPoint ep) { 1825 int i = 0; 1826 foreach (EditPoint e in p.points) { 1827 if (e == ep) { 1828 return i; 1829 } 1830 i++; 1831 } 1832 1833 return -1; 1834 } 1835 1836 public static int counters_in_point_in_path (Path p, EditPoint ep) { 1837 int inside_count = 0; 1838 bool inside; 1839 1840 if (p.points.size > 1) { 1841 inside = true; 1842 1843 if (!is_inside (ep, p)) { 1844 inside = false; 1845 } 1846 1847 if (inside) { 1848 inside_count++; 1849 } 1850 } 1851 1852 return inside_count; 1853 } 1854 1855 static int mark_intersection_as_deleted (Path path) { 1856 int i = 0; 1857 1858 foreach (EditPoint p in path.points) { 1859 if ((p.flags & EditPoint.INTERSECTION) > 0) { 1860 p.deleted = true; 1861 i++; 1862 } 1863 } 1864 1865 return i; 1866 } 1867 1868 /** @param n number of interrsections to find per path. */ 1869 static bool add_intersection_points (Path path1, Path path2, int n = 1) { 1870 bool intersection = false; 1871 int found = 0; 1872 1873 path1.all_segments ((ep1, ep2) => { 1874 double ix, iy; 1875 EditPoint p1, p2; 1876 bool i; 1877 1878 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 1879 out p1, out p2, true); 1880 1881 if (i) { 1882 add_intersection (path1, ep1, ep2, ix, iy); 1883 add_intersection (path2, p1, p2, ix, iy); 1884 intersection = true; 1885 found++; 1886 return found < n; 1887 } 1888 1889 return true; 1890 }); 1891 1892 return intersection; 1893 } 1894 1895 /** @param n number of interrsections to find per path. */ 1896 static bool has_intersection (Path path1, Path path2) { 1897 bool intersection = false; 1898 1899 if (!path1.boundaries_intersecting (path2)) { 1900 return false; 1901 } 1902 1903 path1.all_segments ((ep1, ep2) => { 1904 double ix, iy; 1905 EditPoint p1, p2; 1906 bool i; 1907 1908 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 1909 out p1, out p2, true); 1910 1911 if (i) { 1912 intersection = true; 1913 } 1914 1915 return !intersection; 1916 }); 1917 1918 return intersection; 1919 } 1920 1921 static bool paths_has_intersection (PathList r, out Path path1, out Path path2) { 1922 int i, j; 1923 path1 = new Path (); 1924 path2 = new Path (); 1925 1926 i = 0; 1927 foreach (Path p1 in r.paths) { 1928 1929 j = 0; 1930 foreach (Path p2 in r.paths) { 1931 if (p1 != p2) { 1932 if (has_intersection (p1, p2)) { 1933 path1 = p1; 1934 path2 = p2; 1935 return true; 1936 } 1937 } 1938 j++; 1939 } 1940 i++; 1941 } 1942 return false; 1943 } 1944 1945 public static bool has_points_outside (PathList pl, Path p) { 1946 if (pl.paths.size != 2) { 1947 warning ("Stroke should only create two parts."); 1948 return false; 1949 } 1950 1951 foreach (Path path in pl.paths) { 1952 if (path != p) { 1953 foreach (EditPoint ep in p.points) { 1954 if (!is_inside (ep, path)) { 1955 return true; 1956 } 1957 } 1958 } 1959 } 1960 1961 return false; 1962 } 1963 1964 static bool is_clockwise (Path p) { 1965 double sum = 0; 1966 EditPoint p1, p2; 1967 1968 EditPointHandle l, r; 1969 1970 p.recalculate_linear_handles (); 1971 1972 return_val_if_fail (p.points.size >= 3, true); 1973 1974 for (int i = 0; i < p.points.size; i++) { 1975 p1 = p.points.get (i); 1976 p2 = p.points.get ((i + 1) % p.points.size); 1977 1978 l = p1.get_left_handle (); 1979 r = p1.get_right_handle (); 1980 if (!(fabs (l.angle - r.angle) < 0.0001 && l.length > 0.01 && r.length > 0.01)) { 1981 sum += (p2.x - p1.x) * (p2.y + p1.y); 1982 } 1983 } 1984 1985 return sum > 0; 1986 } 1987 1988 static void flatten (Path path, double stroke_width) { 1989 EditPoint start, end, new_point; 1990 double px, py; 1991 int size, i, added_points; 1992 double step = 0.5; 1993 bool open = path.is_open (); 1994 bool flat; 1995 1996 path.add_hidden_double_points (); 1997 size = open ? path.points.size - 1 : path.points.size; 1998 1999 i = 0; 2000 added_points = 0; 2001 while (i < size) { 2002 start = path.points.get (i); 2003 end = path.points.get ((i + 1) % path.points.size); 2004 2005 Path.get_point_for_step (start, end, step, out px, out py); 2006 2007 if (start.type == PointType.HIDDEN) { 2008 start.tie_handles = false; 2009 start.deleted = true; 2010 } 2011 2012 if (end.type == PointType.HIDDEN) { 2013 start.tie_handles = false; 2014 end.tie_handles = false; 2015 end.deleted = true; 2016 } 2017 2018 flat = is_flat (start.x, start.y, px, py, end.x, end.y, 0.05 * stroke_width) 2019 && ((px - start.x) > 0) == ((start.get_right_handle ().x - start.x) > 0) 2020 && ((py - start.y) > 0) == ((start.get_right_handle ().y - start.y) > 0); 2021 2022 if (unlikely (added_points > 20)) { 2023 warning ("More than twenty points added in stroke."); 2024 added_points = 0; 2025 i++; 2026 } else if (flat 2027 && Path.distance (start.x, px, start.y, py) > 0.1 * stroke_width 2028 && Path.distance (end.x, px, end.y, py) > 0.1 * stroke_width) { 2029 new_point = new EditPoint (px, py); 2030 new_point.prev = start; 2031 new_point.next = end; 2032 path.insert_new_point_on_path (new_point, step); 2033 added_points++; 2034 size++; 2035 } else { 2036 added_points = 0; 2037 i++; 2038 } 2039 } 2040 2041 path.remove_deleted_points (); 2042 path.remove_points_on_points (); 2043 2044 if (stroke_selected) { // FIXME: DELETE 2045 ((!) BirdFont.get_current_font ().get_glyph ("a")).add_path (path); 2046 } 2047 } 2048 2049 public static PathList get_overlay (Path path, double thickness) { 2050 PathList pl = new PathList (); 2051 Path np; 2052 EditPoint p1, p2, p3; 2053 EditPoint last1, last2; 2054 EditPoint previous, previous_inside, start, original_start; 2055 2056 Path side1, side2; 2057 2058 double x, y, x2, y2, x3, y3, next_x, next_y, step, prev_x, prev_y; 2059 double previus_x, previus_y, previus_x2, previus_y2; 2060 double previus_middle_x, previus_middle_y; 2061 int size = path.is_open () ? path.points.size - 1 : path.points.size; 2062 bool flat, f_next, f_bigger; 2063 int i; 2064 2065 double tolerance; 2066 double step_increment; 2067 double step_size; 2068 EditPoint corner1, corner1_inside; 2069 double min_step, max_step; 2070 2071 side1 = new Path (); 2072 side2 = new Path (); 2073 2074 return_val_if_fail (path.points.size > 1, pl); 2075 2076 previous = new EditPoint (); 2077 previous_inside = new EditPoint (); 2078 2079 if (path.is_open ()) { 2080 p1 = path.points.get (0); 2081 p2 = path.points.get (1 % path.points.size); 2082 2083 get_segment (thickness, 0, 0.0001, p1, p2, out start); 2084 side1.add_point (start.copy ()); 2085 2086 get_segment (-thickness, 0, 0.0001, p1, p2, out start); 2087 side2.add_point (start.copy ()); 2088 } 2089 2090 for (i = 0; i < size; i++) { 2091 p1 = path.points.get (i % path.points.size); 2092 p2 = path.points.get ((i + 1) % path.points.size); 2093 p3 = path.points.get ((i + 2) % path.points.size); 2094 2095 tolerance = 1.5 / sqrt (stroke_width); 2096 step_increment = 1.1; 2097 step_size = 0.039 / stroke_width; 2098 2099 corner1 = new EditPoint (); 2100 2101 step = 0; 2102 while (step < 1 - step_size) { 2103 Path.get_point_for_step (p1, p2, step, out x, out y); 2104 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2); 2105 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3); 2106 2107 flat = is_flat (x, y, x2, y2, x3, y3, tolerance); 2108 2109 Path.get_point_for_step (p1, p2, step, out x, out y); 2110 Path.get_point_for_step (p1, p2, step + step_size / step_increment, out x2, out y2); 2111 Path.get_point_for_step (p1, p2, step + 2 * step_size / step_increment, out x3, out y3); 2112 2113 f_next = is_flat (x, y, x2, y2, x3, y3, tolerance); 2114 2115 Path.get_point_for_step (p1, p2, step, out x, out y); 2116 Path.get_point_for_step (p1, p2, step + step_size * step_increment, out x2, out y2); 2117 Path.get_point_for_step (p1, p2, step + 2 * step_size * step_increment, out x3, out y3); 2118 2119 f_bigger = is_flat (x, y, x2, y2, x3, y3, tolerance); 2120 2121 if (!flat && !f_next && step_size > 0.013) { 2122 step_size /= step_increment; 2123 continue; 2124 } 2125 2126 if (flat && f_bigger && step_size < 0.5) { 2127 step_size *= step_increment; 2128 continue; 2129 } 2130 2131 get_segment (thickness, step, step_size, p1, p2, out corner1); 2132 get_segment (-thickness, step, step_size, p1, p2, out corner1_inside); 2133 2134 side1.add_point (corner1.copy ()); 2135 side2.add_point (corner1_inside.copy ()); 2136 2137 previous = corner1; 2138 previous_inside = corner1_inside; 2139 2140 step += step_size; 2141 } 2142 2143 get_segment (thickness, 1 - step_size, step_size, p1, p2, out corner1); 2144 get_segment (-thickness, 1 - step_size, step_size, p1, p2, out corner1_inside); 2145 side1.add_point (corner1.copy ()); 2146 side2.add_point (corner1_inside.copy ()); 2147 previous = corner1; 2148 previous_inside = corner1_inside; 2149 2150 if (!path.is_open () || i < size - 1) { 2151 get_segment (thickness, 0, 0.001, p2, p3, out start); 2152 add_corner (side1, previous, start, p2.copy (), thickness); 2153 2154 get_segment (-thickness, 0, 0.001, p2, p3, out start); 2155 add_corner (side2, previous_inside, start, p2.copy (), thickness); 2156 } 2157 } 2158 2159 side1.recalculate_linear_handles (); 2160 side2.recalculate_linear_handles (); 2161 2162 side2.reverse (); 2163 2164 pl = merge_stroke_parts (path, side1, side2); 2165 2166 return pl; 2167 } 2168 2169 public static void get_segment (double stroke_thickness, double step, double step_size, 2170 EditPoint p1, EditPoint p2, out EditPoint ep1) { 2171 2172 double thickness = stroke_thickness / 2; 2173 Path overlay; 2174 double x, y, x2, y2, x3, y3; 2175 EditPoint corner1, corner2, corner3; 2176 2177 Path.get_point_for_step (p1, p2, step, out x, out y); 2178 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2); 2179 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3); 2180 2181 overlay = new Path (); 2182 2183 corner1 = new EditPoint (x, y, PointType.LINE_CUBIC); 2184 corner2 = new EditPoint (x2, y2, PointType.LINE_CUBIC); 2185 corner3 = new EditPoint (x3, y3, PointType.LINE_CUBIC); 2186 2187 overlay.add_point (corner1); 2188 overlay.add_point (corner2); 2189 overlay.add_point (corner3); 2190 2191 overlay.close (); 2192 overlay.recalculate_linear_handles (); 2193 2194 move_segment (corner1, corner2, thickness); 2195 2196 ep1 = corner2; 2197 } 2198 2199 public static PathList merge_stroke_parts (Path p, Path side1, Path side2) { 2200 Path merged = new Path (); 2201 PathList paths = new PathList (); 2202 2203 if (!p.is_open () && p.is_filled ()) { 2204 side1.close (); 2205 side1.update_region_boundaries (); 2206 paths.add (side1); 2207 } else if (!p.is_open () && !p.is_filled ()) { 2208 side1.update_region_boundaries (); 2209 paths.add (side1); 2210 side2.update_region_boundaries (); 2211 paths.add (side2); 2212 side1.close (); 2213 side2.close (); 2214 } else if (p.is_open ()) { 2215 side2.reverse (); 2216 merged = merge_strokes (p, side1, side2); 2217 merged.close (); 2218 merged.update_region_boundaries (); 2219 paths.add (merged); 2220 merged.reverse (); 2221 } else { 2222 warning ("Can not create stroke."); 2223 paths.add (p); 2224 } 2225 2226 return paths; 2227 } 2228 } 2229 2230 } 2231