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