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