The Birdfont Source Code


All Repositories / birdfont.git / blob – RSS feed

StrokeTool.vala in libbirdfont

This file is a part of the Birdfont project.

Contributing

Send patches or pull requests to johan.mattsson.m@gmail.com.
Clone this repository: git clone https://github.com/johanmattssonm/birdfont.git

Revisions

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