The Birdfont Source Code


All Repositories / birdfont.git / blob – RSS feed

StrokeTool.vala in libbirdfont

This file is a part of the Birdfont project.

Contributing

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

Revisions

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