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