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