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