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