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