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