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