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