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