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