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