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