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 self intersections
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 static void merge_selected_paths () { 105 Glyph g = MainWindow.get_current_glyph (); 106 PathList o = new PathList (); 107 PathList r; 108 PathList new_paths = new PathList (); 109 PathList removed_paths = new PathList (); 110 111 g.store_undo_state (); 112 113 foreach (Path p in g.active_paths) { 114 p.close (); 115 o.add (p); 116 } 117 118 for (int i = 0; i < o.paths.size; i++) { 119 for (int j = 0; j < o.paths.size; j++) { 120 Path p1, p2; 121 122 p1 = o.paths.get (i); 123 p2 = o.paths.get (j); 124 125 if (i == j) { 126 continue; 127 } 128 129 r = merge_selected (p1, p2); 130 131 // FIXME: delete 132 foreach (Path p in r.paths) { 133 ((!) BirdFont.get_current_font ().get_glyph_by_name ("c")).add_path (p.copy ()); 134 } 135 136 // FIXME: delete 137 ((!) BirdFont.get_current_font ().get_glyph_by_name ("d")).add_path (p1.copy ()); 138 ((!) BirdFont.get_current_font ().get_glyph_by_name ("d")).add_path (p2.copy ()); 139 140 remove_merged_curve_parts (r); 141 142 // FIXME: delete 143 print (@"Merge result $(r.paths.size) ($i, $j)\n"); 144 if (r.paths.size > 0) { 145 foreach (Path p in r.paths) { 146 foreach (EditPoint ep in p.points) { 147 ep.flags &= uint.MAX ^ 148 (EditPoint.INTERSECTION 149 | EditPoint.COPIED 150 | EditPoint.NEW_CORNER 151 | EditPoint.SELF_INTERSECTION); 152 } 153 p.update_region_boundaries (); 154 } 155 156 new_paths.append (r); 157 158 removed_paths.add (p1); 159 removed_paths.add (p2); 160 161 i = 0; 162 j = 0; 163 } 164 165 //FIXME: delete 166 print (@"Remaining $(o.paths.size)\n"); 167 foreach (Path p in o.paths) { 168 print (@"p.points.size $(p.points.size)\n"); 169 } 170 } 171 } 172 173 foreach (Path p in removed_paths.paths) { 174 g.delete_path (p); 175 } 176 177 g.clear_active_paths (); 178 179 remove_merged_curve_parts (new_paths); 180 181 foreach (Path p in new_paths.paths) { 182 g.add_path (p); 183 g.add_active_path (null, p); 184 } 185 186 GlyphCanvas.redraw (); 187 } 188 189 static void remove_merged_curve_parts (PathList r) { 190 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> (); 191 PathList flat = new PathList (); 192 193 print (@"remove_merged_curve_parts: $(r.paths.size)\n"); 194 195 foreach (Path p in r.paths) { 196 p.update_region_boundaries (); 197 flat.add (p.flatten ()); 198 } 199 200 foreach (Path p in r.paths) { 201 PathList pl = get_insides (flat, p); 202 203 int counters = 0; 204 int clockwise = 0; 205 206 foreach (Path i in pl.paths) { 207 if (i.is_clockwise ()) { 208 clockwise++; 209 } else { 210 counters++; 211 } 212 } 213 214 print (@"clockwise $clockwise counters $counters pl.size $(pl.paths.size)\n"); 215 216 if (p.is_clockwise ()) { 217 int c = clockwise - counters; 218 if (c % 2 == 0) { 219 remove.add (p); 220 break; 221 } 222 } else { 223 int c = clockwise - counters; 224 if (c % 2 == 1) { 225 remove.add (p); 226 break; 227 } 228 } 229 } 230 231 foreach (Path p in remove) { 232 r.paths.remove (p); 233 remove_merged_curve_parts (r); 234 return; 235 } 236 } 237 238 public static PathList merge_selected (Path path1, Path path2) { 239 PathList flat = new PathList (); 240 PathList o = new PathList (); 241 PathList pl = new PathList (); 242 PathList r = new PathList (); 243 244 pl.add (path1); 245 pl.add (path2); 246 247 if (!path1.boundaries_intersecting (path2)) { 248 return r; 249 } 250 251 foreach (Path p in pl.paths) { 252 if (p.stroke == 0) { 253 o.add (p); 254 flat.add (p.copy ().flatten (50)); 255 } 256 } 257 258 flat = merge (flat); 259 260 foreach (Path p in flat.paths) { 261 ((!) BirdFont.get_current_font ().get_glyph_by_name ("b")).add_path (p); 262 } 263 264 bool has_split_point = false; 265 foreach (Path p in flat.paths) { 266 foreach (EditPoint ep in p.points) { 267 if ((ep.flags & EditPoint.SPLIT_POINT) > 0) { 268 269 // FIXME: DELETE 270 ep.color = Color.pink (); 271 272 foreach (Path pp in o.paths) { 273 EditPoint lep = new EditPoint (); 274 pp.get_closest_point_on_path (lep, ep.x, ep.y, null, null); 275 276 if (Path.distance_to_point (lep, (!) lep.prev) < 0.1 277 || Path.distance_to_point (lep, (!) lep.next) < 0.1) { 278 // FIXME: find a better solution 279 continue; 280 } 281 282 if (Path.distance_to_point (ep, lep) < 0.1) { 283 EditPoint lep2 = new EditPoint (); 284 pp.get_closest_point_on_path (lep2, ep.x, ep.y, lep.prev, lep.next); 285 286 if (lep.prev != null) { 287 lep.get_left_handle ().type = lep.get_prev ().get_right_handle ().type; 288 } else { 289 lep.get_left_handle ().type = pp.get_last_point ().get_right_handle ().type; 290 } 291 292 if (lep.next != null) { 293 lep.get_right_handle ().type = lep.get_next ().get_left_handle ().type; 294 } else { 295 lep.get_left_handle ().type = pp.get_first_point ().get_right_handle ().type; 296 } 297 298 if (lep2.prev != null) { 299 lep2.get_left_handle ().type = lep2.get_prev ().get_right_handle ().type; 300 } else { 301 lep2.get_left_handle ().type = pp.get_first_point ().get_right_handle ().type; 302 } 303 304 if (lep2.next != null) { 305 lep2.get_right_handle ().type = lep2.get_next ().get_left_handle ().type; 306 } else { 307 lep2.get_left_handle ().type = pp.get_last_point ().get_right_handle ().type; 308 } 309 310 // self intersection 311 if (Path.distance_to_point (ep, lep2) < 0.1 312 && Path.distance_to_point (ep, lep) < 0.1) { 313 pp.insert_new_point_on_path (lep); 314 pp.insert_new_point_on_path (lep2); 315 316 lep.flags |= EditPoint.SELF_INTERSECTION; 317 lep2.flags |= EditPoint.SELF_INTERSECTION; 318 319 lep.tie_handles = false; 320 lep.reflective_point = false; 321 lep2.tie_handles = false; 322 lep2.reflective_point = false; 323 324 // FIXME: DELETE 325 lep2.color = Color.magenta (); 326 lep.color = Color.magenta (); 327 } else { 328 pp.insert_new_point_on_path (lep); 329 lep.flags |= EditPoint.INTERSECTION; 330 lep.tie_handles = false; 331 lep.reflective_point = false; 332 333 // FIXME: DELETE 334 lep2.color = Color.pink (); 335 lep.color = Color.pink (); 336 } 337 338 has_split_point = true; 339 } 340 } 341 } 342 } 343 } 344 345 if (!has_split_point) { 346 return r; 347 } 348 349 // remove double intersection points 350 EditPoint prev = new EditPoint (); 351 foreach (Path pp in o.paths) { 352 foreach (EditPoint ep in pp.points) { 353 if (((prev.flags & EditPoint.SELF_INTERSECTION) > 0 || (prev.flags & EditPoint.INTERSECTION) > 0) 354 && ((ep.flags & EditPoint.SELF_INTERSECTION) > 0 || (ep.flags & EditPoint.INTERSECTION) > 0) 355 && fabs (ep.x - prev.x) < 0.2 356 && fabs (ep.y - prev.y) < 0.2) { 357 prev.deleted = true; 358 } 359 360 prev = ep; 361 } 362 } 363 364 foreach (Path pp in o.paths) { 365 pp.remove_deleted_points (); 366 } 367 368 foreach (Path p in o.paths) { 369 foreach (EditPoint ep in p.points) { 370 ep.flags &= uint.MAX ^ EditPoint.COPIED; 371 } 372 } 373 374 // FIXME: delete 375 foreach (Path p in o.paths) { 376 ((!) BirdFont.get_current_font ().get_glyph_by_name ("a")).add_path (p); 377 } 378 379 return_val_if_fail (o.paths.size == 2, r); 380 381 Path p1, p2; 382 383 p1 = o.paths.get (0); 384 p2 = o.paths.get (1); 385 386 r = merge_paths_with_curves (p1, p2); 387 388 print (@"Result $(r.paths.size)\n"); 389 if (r.paths.size > 0) { 390 o.paths.remove (p1); 391 o.paths.remove (p2); 392 o.append (r); 393 } 394 395 // FIXME: remove split points 396 397 return r; 398 } 399 400 static PathList merge_paths_with_curves (Path path1, Path path2) { 401 PathList r = new PathList (); 402 IntersectionList intersections = new IntersectionList (); 403 EditPoint ep1, ep2, found; 404 double d; 405 double min_d; 406 Path current; 407 bool found_intersection; 408 Path flat1; 409 Path flat2; 410 411 flat1 = path1.flatten (); 412 flat2 = path2.flatten (); 413 414 if (path1.points.size <= 1 || path2.points.size <= 1) { 415 return r; 416 } 417 418 // reset copied points 419 foreach (EditPoint n in path2.points) { 420 n.flags &= uint.MAX ^ EditPoint.COPIED; 421 } 422 423 // build list of intersection points 424 for (int i = 0; i < path1.points.size; i++) { 425 ep1 = path1.points.get (i); 426 427 if ((ep1.flags & EditPoint.SELF_INTERSECTION) > 0 428 && (ep1.flags & EditPoint.COPIED) == 0) { 429 ep1.flags |= EditPoint.COPIED; 430 431 found = new EditPoint (); 432 min_d = double.MAX; 433 found_intersection = false; 434 435 for (int j = 0; j < path1.points.size; j++) { 436 ep2 = path1.points.get (j); 437 d = Path.distance_to_point (ep1, ep2); 438 if ((ep2.flags & EditPoint.COPIED) == 0 439 && (ep2.flags & EditPoint.SELF_INTERSECTION) > 0) { 440 if (d < min_d) { 441 min_d = d; 442 found_intersection = true; 443 found = ep2; 444 } 445 } 446 } 447 448 if (!found_intersection) { 449 warning (@"No self intersection:\n$(ep1)"); 450 return r; 451 } 452 453 ep1.tie_handles = false; 454 ep1.reflective_point = false; 455 found.tie_handles = false; 456 found.reflective_point = false; 457 458 found.flags |= EditPoint.COPIED; 459 Intersection intersection = new Intersection (ep1, path1, found, path1); 460 intersection.self_intersection = true; 461 intersections.points.add (intersection); 462 } 463 464 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 465 found = new EditPoint (); 466 min_d = double.MAX; 467 found_intersection = false; 468 for (int j = 0; j < path2.points.size; j++) { 469 ep2 = path2.points.get (j); 470 d = Path.distance_to_point (ep1, ep2); 471 if ((ep2.flags & EditPoint.COPIED) == 0 472 && (ep2.flags & EditPoint.INTERSECTION) > 0) { 473 if (d < min_d) { 474 min_d = d; 475 found_intersection = true; 476 found = ep2; 477 } 478 } 479 } 480 481 if (!found_intersection) { 482 warning (@"No intersection for:\n $(ep1)"); 483 return r; 484 } 485 486 found.flags |= EditPoint.COPIED; 487 488 print (@"Intersection in $(path1.points.size) ($(ep1.x),$(ep1.y)) and $(path2.points.size) ($(found.x),$(found.y))\n"); 489 ep1.tie_handles = false; 490 ep1.reflective_point = false; 491 found.tie_handles = false; 492 found.reflective_point = false; 493 Intersection intersection = new Intersection (ep1, path1, found, path2); 494 intersections.points.add (intersection); 495 } 496 } 497 498 // reset copy flag 499 foreach (EditPoint n in path1.points) { 500 n.flags &= uint.MAX ^ EditPoint.COPIED; 501 } 502 503 foreach (EditPoint n in path2.points) { 504 n.flags &= uint.MAX ^ EditPoint.COPIED; 505 } 506 507 if (intersections.points.size == 0) { 508 warning ("No intersection points."); 509 return r; 510 } 511 512 Path new_path = new Path (); 513 current = path1; 514 while (true) { 515 // find a beginning of a new part 516 bool find_parts = false; 517 Intersection new_start = new Intersection.empty (); 518 foreach (Intersection inter in intersections.points) { 519 if (!inter.done && !find_parts) { 520 find_parts = true; 521 new_start = inter; 522 current = new_start.path; 523 } 524 } 525 526 if (new_path.points.size > 0) { 527 new_path.close (); 528 new_path.recalculate_linear_handles (); 529 new_path.update_region_boundaries (); 530 r.add (new_path); 531 } 532 533 if (!find_parts) { // no more parts 534 break; 535 } 536 537 if ((new_start.get_point (current).flags & EditPoint.COPIED) > 0) { 538 current = new_start.get_other_path (current); 539 } 540 541 int i = index_of (current, new_start.get_point (current)); 542 543 if (i < 0) { 544 warning ("i < 0"); 545 return r; 546 } 547 548 EditPoint previous = new EditPoint (); 549 new_path = new Path (); 550 ep1 = current.points.get (i); 551 current = new_start.get_other_path (current); // swap at first iteration 552 bool first = true; 553 Intersection self_intersection_point = new Intersection.empty (); 554 while (true) { 555 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 556 bool other; 557 558 previous = ep1; 559 560 if (intersections.has_point (ep1)) { 561 print (@"INTERSECTION: $(ep1.x), $(ep1.y)\n"); 562 new_start = intersections.get_point (ep1, out other); 563 current = new_start.get_other_path (current); 564 i = index_of (current, new_start.get_point (current)); 565 566 if (!(0 <= i < current.points.size)) { 567 warning (@"Index out of bounds. ($i)"); 568 return r; 569 } 570 571 ep1 = current.points.get (i); 572 ep2 = current.points.get ((i + 1) % current.points.size); 573 574 double px, py; 575 576 Path.get_point_for_step (ep1, ep2, 0.5, out px, out py); 577 bool inside = (current == path1 && flat2.is_over_coordinate (px, py)) 578 || (current == path2 && flat1.is_over_coordinate (px, py)); 579 580 bool other_inside = (current != path1 && flat2.is_over_coordinate (px, py)) 581 || (current != path2 && flat1.is_over_coordinate (px, py)); 582 583 if (inside && !other_inside) { 584 current = new_start.get_other_path (current); 585 i = index_of (current, new_start.get_point (current)); 586 587 if (!(0 <= i < current.points.size)) { 588 warning (@"Index out of bounds. ($i >= $(current.points.size)) "); 589 return r; 590 } 591 592 new_start.done = true; 593 ep1 = current.points.get (i); 594 } 595 596 inside = (current == path1 && flat2.is_over_coordinate (px, py)) 597 || (current == path2 && flat1.is_over_coordinate (px, py)); 598 599 if (first) { 600 previous = new_start.get_other_path (current).get_first_point (); 601 first = false; 602 } 603 } else { 604 warning (@"Intersection not in list, $(ep1.x), $(ep1.y)\n"); 605 } 606 } 607 608 if ((ep1.flags & EditPoint.SELF_INTERSECTION) > 0) { 609 bool other; 610 print (@"SELF_INTERSECTION: $(ep1.x), $(ep1.y)\n"); 611 new_start = intersections.get_point (ep1, out other); 612 613 print (@"from $i "); 614 615 i = index_of (current, other ? new_start.point : new_start.other_point); 616 617 print (@"start at $i\n"); 618 619 if (!(0 <= i < current.points.size)) { 620 warning (@"Index out of bounds. ($i)"); 621 return r; 622 } 623 624 ep1 = current.points.get (i); 625 626 // take the other point if it already is copied 627 if ((ep1.flags & EditPoint.COPIED) > 0) { 628 i = index_of (current, !other ? new_start.point : new_start.other_point); 629 630 if (!(0 <= i < current.points.size)) { 631 warning (@"Index out of bounds. ($i)"); 632 return r; 633 } 634 635 ep1 = current.points.get (i); 636 } 637 } 638 639 if ((ep1.flags & EditPoint.COPIED) > 0) { 640 new_path.close (); 641 EditPoint first_point = new_path.get_first_point (); 642 EditPointHandle h; 643 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { // FIXME SELF INTERSECTION 644 first_point.left_handle.move_to_coordinate (previous.left_handle.x, previous.left_handle.y); 645 646 if (first_point.next != null) { 647 h = first_point.get_next ().get_left_handle (); 648 h.process_connected_handle (); 649 } 650 } 651 652 // self intersections will be copied twice 653 if ((ep1.flags & EditPoint.SELF_INTERSECTION) > 0) { 654 if ((ep1.flags & EditPoint.COPIED_SELF_INTERSECTION) == 0) { 655 ep1.flags |= EditPoint.COPIED_SELF_INTERSECTION; 656 } else { 657 print (@"DONE SELF_INTERSECTION $(ep1.x), $(ep1.y)\n"); 658 break; 659 } 660 } else { 661 print (@"DONE COPIED $(ep1.x), $(ep1.y)\n"); 662 break; 663 } 664 } 665 666 // adjust the other handle 667 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 668 ep1.left_handle.convert_to_curve (); 669 ep1.right_handle.convert_to_curve (); 670 } 671 672 // add point to path 673 ep1.flags |= EditPoint.COPIED; 674 new_path.add_point (ep1.copy ()); 675 676 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { // FIXME SELF INTERSECTION 677 new_path.get_last_point ().left_handle.move_to_coordinate (previous.left_handle.x, previous.left_handle.y); 678 } 679 680 print (@"Add point $(ep1.x), $(ep1.y)\n"); 681 682 i++; 683 ep1 = current.points.get (i % current.points.size); 684 } 685 686 ep1.flags |= EditPoint.COPIED; 687 688 if (!new_start.done) { 689 new_start.done = (new_start.get_other_point (current).flags & EditPoint.COPIED) > 0; 690 } 691 } 692 693 return r; 694 } 695 696 static Path simplify_stroke (Path p) { 697 Path simplified = new Path (); 698 Path segment, added_segment; 699 EditPoint ep, ep_start, last, first, segment_last; 700 int start, stop; 701 int j; 702 703 segment_last = new EditPoint (); 704 last = new EditPoint (); 705 706 foreach (EditPoint e in p.points) { 707 PenTool.convert_point_type (e, PointType.CUBIC); 708 } 709 710 foreach (EditPoint e in p.points) { 711 if ((e.flags & EditPoint.CURVE) == 0) { 712 p.set_new_start (e); 713 break; 714 } 715 } 716 717 for (int i = 0; i < p.points.size; i++) { 718 ep = p.points.get (i); 719 720 if ((ep.flags & EditPoint.CURVE) > 0) { 721 start = i; 722 for (j = start + 1; j < p.points.size; j++) { 723 ep = p.points.get (j); 724 if ((ep.flags & EditPoint.CURVE) == 0) { 725 break; 726 } 727 } 728 729 stop = j; 730 start -= 1; 731 732 if (start < 0) { 733 warning ("start < 0"); 734 start = 0; 735 } 736 737 if (stop >= p.points.size) { 738 warning ("stop >= p.points.size"); 739 stop = p.points.size - 1; 740 } 741 742 ep_start = p.points.get (start); 743 ep = p.points.get (stop); 744 745 double l = Path.distance_to_point (ep_start, ep); 746 segment = fit_bezier_path (p, start, stop, 0.00001 * l * l); 747 748 added_segment = segment.copy (); 749 750 if (simplified.points.size > 0) { 751 last = simplified.get_last_point (); 752 } 753 754 if (added_segment.points.size > 0) { 755 segment_last = added_segment.get_last_point (); 756 first = added_segment.get_first_point (); 757 segment_last.right_handle = ep_start.get_right_handle ().copy (); 758 759 if (simplified.points.size > 1) { 760 simplified.delete_last_point (); 761 } 762 763 first.set_tie_handle (false); 764 last.set_tie_handle (false); 765 766 last.get_right_handle ().x = first.get_right_handle ().x; 767 last.get_right_handle ().y = first.get_right_handle ().y; 768 769 first.get_left_handle ().convert_to_curve (); 770 first.get_left_handle ().x = last.get_left_handle ().x; 771 first.get_left_handle ().y = last.get_left_handle ().y; 772 773 last = added_segment.get_last_point (); 774 last.right_handle = ep.get_right_handle ().copy (); 775 last.recalculate_linear_handles (); 776 777 simplified.append_path (added_segment); 778 779 segment_last.right_handle = ep.get_right_handle ().copy (); 780 781 if (added_segment.points.size > 0) { 782 if (ep_start.get_right_handle ().is_line ()) { 783 first = added_segment.get_first_point (); 784 first.recalculate_linear_handles (); 785 } 786 } 787 } else { 788 warning ("No points in segment."); 789 } 790 791 i = stop; 792 } else { 793 simplified.add_point (ep.copy ()); 794 } 795 } 796 797 simplified.recalculate_linear_handles (); 798 simplified.close (); 799 800 simplified.remove_points_on_points (0.01); 801 802 return simplified; 803 } 804 805 static Path fit_bezier_path (Path p, int start, int stop, double error) { 806 int index, size; 807 Path simplified; 808 double[] lines; 809 double[] result; 810 EditPoint ep; 811 812 simplified = new Path (); 813 814 return_val_if_fail (0 <= start < p.points.size, simplified); 815 return_val_if_fail (0 <= stop < p.points.size, simplified); 816 817 size = stop - start + 1; 818 lines = new double[2 * size]; 819 820 index = 0; 821 822 for (int i = start; i <= stop; i++) { 823 ep = p.points.get (i); 824 lines[index] = ep.x; 825 index++; 826 827 lines[index] = ep.y; 828 index++; 829 } 830 831 return_val_if_fail (2 * size == index, new Path ()); 832 833 Gems.fit_bezier_curve_to_line (lines, error, out result); 834 835 return_val_if_fail (!is_null (result), simplified); 836 837 for (int i = 0; i + 7 < result.length; i += 8) { 838 simplified.add_cubic_bezier_points ( 839 result[i], result[i + 1], 840 result[i + 2], result[i + 3], 841 result[i + 4], result[i + 5], 842 result[i + 6], result[i + 7]); 843 } 844 845 return simplified; 846 } 847 848 static PathList remove_intersection_paths (PathList pl) { 849 PathList r = new PathList (); 850 851 foreach (Path p in pl.paths) { 852 if (p.points.size > 7) { 853 r.add (p); 854 } else if (!has_new_corner (p)) { 855 r.add (p); 856 } else if (counters (pl, p) == 0) { 857 r.add (p); 858 } 859 } 860 861 return r; 862 } 863 864 static bool has_new_corner (Path p) { 865 foreach (EditPoint ep in p.points) { 866 if ((ep.flags & EditPoint.NEW_CORNER) > 0) { 867 return true; 868 } 869 } 870 871 return false; 872 } 873 874 static void add_line_cap (Path path, Path stroke1, Path stroke2, bool last_cap) { 875 if (path.line_cap == LineCap.SQUARE) { 876 add_square_cap (path, stroke1, stroke2, last_cap); 877 } else if (path.line_cap == LineCap.ROUND) { 878 add_round_cap (path, stroke1, stroke2, last_cap); 879 } 880 } 881 882 static void add_round_cap (Path path, Path stroke1, Path stroke2, bool last_cap) { 883 double px, py; 884 double step, start_angle, stop_angle; 885 double radius; 886 EditPoint n, nstart, nend; 887 Path cap = new Path (); 888 889 EditPoint start, end; 890 EditPointHandle last_handle; 891 EditPoint first, last; 892 893 stroke1.remove_points_on_points (); 894 stroke2.remove_points_on_points (); 895 896 last_handle = path.get_first_point ().get_right_handle (); 897 start = stroke1.get_last_point (); 898 end = stroke2.get_first_point (); 899 900 start_angle = last_handle.angle + PI / 2; 901 stop_angle = start_angle + PI; 902 903 nstart = cap.add (start.x, start.y); 904 radius = Path.distance_to_point (start, end) / 2; 905 step = PI / 5; 906 907 for (int j = 0; j < 5; j++) { 908 double angle = start_angle + step * j; 909 px = radius * cos (angle) + last_handle.parent.x; 910 py = radius * sin (angle) + last_handle.parent.y; 911 n = cap.add (px, py); 912 913 n.type = PointType.LINE_CUBIC; 914 n.get_right_handle ().type = PointType.LINE_CUBIC; 915 n.get_left_handle ().type = PointType.LINE_CUBIC; 916 } 917 918 nend = cap.add (end.x, end.y); 919 920 for (int i = 0; i < cap.points.size; i++) { 921 cap.points.get (i).recalculate_linear_handles (); 922 } 923 924 int size = cap.points.size; 925 926 for (int i = 1; i < size; i++) { 927 n = cap.points.get (i); 928 n.convert_to_curve (); 929 n.set_tie_handle (true); 930 n.process_tied_handle (); 931 } 932 933 int f = stroke1.points.size - 1; 934 935 for (int i = 2; i < cap.points.size - 1; i++) { 936 n = cap.points.get (i).copy (); 937 stroke1.add_point (n); 938 } 939 940 cap.remove_points_on_points (); 941 return_if_fail (0 < f < stroke1.points.size); 942 943 first = stroke1.points.get (f); 944 945 last = stroke1.get_last_point (); 946 last.convert_to_curve (); 947 948 last = stroke1.add_point (stroke2.get_first_point ()); 949 stroke2.delete_first_point (); 950 951 last.convert_to_line (); 952 last.recalculate_linear_handles (); 953 954 last.next = stroke1.add_point (stroke2.get_first_point ()).get_link_item (); 955 stroke2.delete_first_point (); 956 957 last.get_left_handle ().convert_to_curve (); 958 last.get_left_handle ().angle = last.get_right_handle ().angle + PI; 959 last.flags = EditPoint.CURVE_KEEP; 960 961 double a; 962 double l; 963 964 return_if_fail (cap.points.size > 1); 965 966 a = (first.get_left_handle ().angle + PI) % (2 * PI); 967 l = cap.points.get (1).get_right_handle ().length; 968 969 first.get_right_handle ().convert_to_curve (); 970 first.get_right_handle ().angle = a; 971 first.get_right_handle ().length = l; 972 973 a = (first.get_left_handle ().angle + PI) % (2 * PI); 974 975 last.get_left_handle ().convert_to_curve (); 976 last.get_left_handle ().angle = a; 977 last.get_left_handle ().length = l; 978 } 979 980 static void add_square_cap (Path path, Path stroke1, Path stroke2, bool last_cap) { 981 EditPointHandle last_handle; 982 EditPoint start; 983 EditPoint end; 984 EditPoint n; 985 double x, y; 986 double stroke_width = path.stroke / 2; 987 988 last_handle = path.get_first_point ().get_right_handle (); 989 start = stroke1.get_last_point (); 990 end = stroke2.get_first_point (); 991 992 y = sin (last_handle.angle - PI) * stroke_width; 993 x = cos (last_handle.angle - PI) * stroke_width; 994 995 n = stroke1.add (start.x + x, start.y + y); 996 n.type = PointType.CUBIC; 997 n.get_right_handle ().type = PointType.CUBIC; 998 n.get_left_handle ().type = PointType.CUBIC; 999 n.convert_to_line (); 1000 1001 n = stroke1.add (end.x + x, end.y + y); 1002 n.type = PointType.CUBIC; 1003 n.get_right_handle ().type = PointType.CUBIC; 1004 n.get_left_handle ().type = PointType.CUBIC; 1005 n.convert_to_line (); 1006 } 1007 1008 /** Create one stroke from the outline and counter stroke and close the 1009 * open endings. 1010 * 1011 * @param path the path to create stroke for 1012 * @param stroke for the outline of path 1013 * @param stroke for the counter path 1014 */ 1015 static Path merge_strokes (Path path, Path stroke, Path counter) { 1016 1017 Path merged; 1018 EditPoint last_counter, first; 1019 1020 merged = stroke.copy (); 1021 merged.reverse (); 1022 1023 last_counter = new EditPoint (); 1024 first = new EditPoint (); 1025 1026 add_line_cap (path, merged, counter, true); 1027 path.reverse (); 1028 1029 add_line_cap (path, counter, merged, true); 1030 path.reverse (); 1031 1032 merged.append_path (counter); 1033 1034 merged.close (); 1035 merged.create_list (); 1036 merged.recalculate_linear_handles (); 1037 1038 return merged; 1039 } 1040 1041 static void move_segment (EditPoint stroke_start, EditPoint stroke_stop, double thickness) { 1042 EditPointHandle r, l; 1043 double m, n; 1044 double qx, qy; 1045 1046 stroke_start.set_tie_handle (false); 1047 stroke_stop.set_tie_handle (false); 1048 1049 r = stroke_start.get_right_handle (); 1050 l = stroke_stop.get_left_handle (); 1051 1052 m = cos (r.angle + PI / 2) * thickness; 1053 n = sin (r.angle + PI / 2) * thickness; 1054 1055 stroke_start.get_right_handle ().move_to_coordinate_delta (m, n); 1056 stroke_start.get_left_handle ().move_to_coordinate_delta (m, n); 1057 1058 stroke_start.independent_x += m; 1059 stroke_start.independent_y += n; 1060 1061 qx = cos (l.angle - PI / 2) * thickness; 1062 qy = sin (l.angle - PI / 2) * thickness; 1063 1064 stroke_stop.get_right_handle ().move_to_coordinate_delta (qx, qy); 1065 stroke_stop.get_left_handle ().move_to_coordinate_delta (qx, qy); 1066 1067 stroke_stop.independent_x += qx; 1068 stroke_stop.independent_y += qy; 1069 } 1070 1071 static void add_corner (Path stroked, EditPoint previous, EditPoint next, 1072 EditPoint original, double stroke_width) { 1073 1074 double ratio; 1075 double distance; 1076 EditPoint corner; 1077 double corner_x, corner_y; 1078 EditPointHandle previous_handle; 1079 EditPointHandle next_handle; 1080 EditPoint cutoff1, cutoff2; 1081 double adjusted_stroke = (stroke_width * 0.999999) / 2.0; 1082 bool d1, d2; 1083 1084 previous_handle = previous.get_left_handle (); 1085 next_handle = next.get_right_handle (); 1086 1087 previous_handle.angle += PI; 1088 next_handle.angle += PI; 1089 1090 Path.find_intersection_handle (previous_handle, next_handle, out corner_x, out corner_y); 1091 corner = new EditPoint (corner_x, corner_y, previous.type); 1092 corner.convert_to_line (); 1093 1094 previous_handle.angle -= PI; 1095 next_handle.angle -= PI; 1096 1097 distance = Path.distance_to_point (corner, original); 1098 ratio = 1.5 * fabs (adjusted_stroke) / distance; 1099 1100 double or = original.get_right_handle ().angle; 1101 double ol = original.get_left_handle ().angle; 1102 1103 if (previous.prev == null) { // FIXME: first point 1104 warning ("Point before corner."); 1105 d1 = false; 1106 d2 = false; 1107 } else { 1108 d1 = corner.x - previous.x >= 0 == previous.x - previous.get_prev ().x >= 0; 1109 d2 = corner.y - previous.y >= 0 == previous.y - previous.get_prev ().y >= 0; 1110 } 1111 1112 if (ratio > 1) { 1113 if (!d1 && !d2) { 1114 return; 1115 } else { 1116 stroked.add_point (corner); 1117 } 1118 } else { 1119 1120 cutoff1 = new EditPoint (); 1121 cutoff1.set_point_type (previous.type); 1122 cutoff1.convert_to_line (); 1123 1124 cutoff2 = new EditPoint (); 1125 cutoff2.set_point_type (previous.type); 1126 cutoff2.convert_to_line (); 1127 1128 if (fabs (or - ol) < 0.001) { 1129 cutoff1.x = previous.x + 1.5 * fabs (adjusted_stroke) * -cos (or); 1130 cutoff1.y = previous.y + 1.5 * fabs (adjusted_stroke) * -sin (or); 1131 1132 cutoff2.x = next.x + 1.5 * fabs (adjusted_stroke) * -cos (or); 1133 cutoff2.y = next.y + 1.5 * fabs (adjusted_stroke) * -sin (or); 1134 } else { 1135 cutoff1.x = previous.x + (corner.x - previous.x) * ratio; 1136 cutoff1.y = previous.y + (corner.y - previous.y) * ratio; 1137 1138 cutoff2.x = next.x + (corner.x - next.x) * ratio; 1139 cutoff2.y = next.y + (corner.y - next.y) * ratio; 1140 } 1141 1142 if (!cutoff1.is_valid () || cutoff2.is_valid ()) { 1143 cutoff1 = stroked.add_point (cutoff1); 1144 cutoff2 = stroked.add_point (cutoff2); 1145 } 1146 1147 cutoff1.recalculate_linear_handles (); 1148 cutoff2.recalculate_linear_handles (); 1149 1150 // self intersection 1151 if (!d1 && !d2) { 1152 cutoff1.deleted = true; 1153 cutoff2.deleted = true; 1154 1155 stroked.remove_deleted_points (); 1156 return; 1157 } 1158 1159 if (distance > 4 * stroke_width) { 1160 previous.flags = EditPoint.NONE; 1161 next.flags = EditPoint.NONE; 1162 } else { 1163 previous.flags |= EditPoint.NEW_CORNER; 1164 next.flags |= EditPoint.NEW_CORNER; 1165 } 1166 } 1167 } 1168 1169 static PathList get_parts (Path path) { 1170 PathList intersections; 1171 PathList r; 1172 1173 r = get_parts_self (path); 1174 intersections = new PathList (); 1175 1176 foreach (Path p in r.paths) { 1177 intersections.add (p); 1178 } 1179 1180 return intersections; 1181 } 1182 1183 static bool split_corner (PathList pl) { 1184 EditPoint p1, p2; 1185 EditPoint a1, a2; 1186 PathList result; 1187 bool split; 1188 1189 foreach (Path p in pl.paths) { 1190 if (p.points.size == 0) { 1191 continue; 1192 } 1193 1194 for (int index = 1; index < p.points.size + 2; index++) { 1195 p1 = p.points.get ((index - 1) % p.points.size); 1196 p2 = p.points.get (index % p.points.size); 1197 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 1198 a2 = p.points.get ((index + 4) % p.points.size); 1199 1200 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 1201 || (p2.flags & EditPoint.STROKE_OFFSET) > 0 1202 || (a1.flags & EditPoint.STROKE_OFFSET) > 0 1203 || (a2.flags & EditPoint.STROKE_OFFSET) > 0) { 1204 1205 split = split_segment (p, a1, a2, p1, p2, out result); 1206 1207 if (split) { 1208 pl.append (result); 1209 pl.paths.remove (p); 1210 split_corner (pl); 1211 return true; 1212 } else { 1213 p1 = p.points.get ((index - 1) % p.points.size); 1214 p2 = p.points.get (index % p.points.size); 1215 a1 = p.points.get ((index + 2) % p.points.size); // one point ahead 1216 a2 = p.points.get ((index + 3) % p.points.size); 1217 1218 split = split_segment (p, a1, a2, p1, p2, out result); 1219 1220 if (split) { 1221 pl.append (result); 1222 pl.paths.remove (p); 1223 split_corner (pl); 1224 return true; 1225 } else { 1226 p1 = p.points.get ((index - 1) % p.points.size); 1227 p2 = p.points.get (index % p.points.size); 1228 a1 = p.points.get ((index + 3) % p.points.size); // two points ahead 1229 a2 = p.points.get ((index + 4) % p.points.size); 1230 1231 if ((p1.flags & EditPoint.STROKE_OFFSET) > 0 1232 && (a1.flags & EditPoint.STROKE_OFFSET) > 0) { 1233 p1.flags = EditPoint.COUNTER_TO_OUTLINE; 1234 a1.flags = EditPoint.COUNTER_TO_OUTLINE; 1235 } 1236 } 1237 } 1238 } 1239 } 1240 } 1241 1242 return false; 1243 } 1244 1245 static bool split_segment (Path p, EditPoint first, EditPoint next, EditPoint p1, EditPoint p2, out PathList result) { 1246 double ix, iy; 1247 bool intersection; 1248 int i; 1249 1250 result = new PathList (); 1251 intersection = segments_intersects (first, next, p1, p2, out ix, out iy, true); 1252 1253 if (intersection) { 1254 add_intersection (p, first, next, ix, iy); 1255 add_intersection (p, p1, p2, ix, iy); 1256 1257 i = mark_intersection_as_deleted (p); 1258 return_val_if_fail (i == 2, false); 1259 1260 result.append (get_remaining_points (p.copy ())); 1261 } 1262 1263 return intersection; 1264 } 1265 1266 static bool split_path (Path path1, Path path2, PathList result) { 1267 PathList pl1, pl2; 1268 Path a1, a2, b1, b2; 1269 Path m1, m2; 1270 int i; 1271 1272 if (path1 == path2) { 1273 return false; 1274 } 1275 1276 if (add_intersection_points (path1, path2, 2)) { 1277 i = mark_intersection_as_deleted (path1); 1278 if (i != 2) { 1279 warning (@"Expecting 2 points, $i points found."); 1280 return false; 1281 } 1282 1283 i = mark_intersection_as_deleted (path2); 1284 if (i != 2) { 1285 warning (@"Expecting 2 points, $i points found."); 1286 return false; 1287 } 1288 1289 1290 pl1 = get_remaining_points (path1.copy ()); 1291 pl2 = get_remaining_points (path2.copy ()); 1292 1293 return_if_fail (pl1.paths.size == 2); 1294 return_if_fail (pl2.paths.size == 2); 1295 1296 a1 = pl1.paths.get (0); 1297 a2 = pl1.paths.get (1); 1298 b1 = pl2.paths.get (0); 1299 b2 = pl2.paths.get (1); 1300 1301 m1 = PenTool.merge_open_paths (a1, b2); 1302 m2 = PenTool.merge_open_paths (b1, a2); 1303 1304 result.add (m1); 1305 result.add (m2); 1306 1307 return true; 1308 } 1309 1310 return false; 1311 } 1312 1313 static PathList split_paths (PathList pl) { 1314 PathList n = new PathList (); 1315 1316 n.append (pl); 1317 1318 foreach (Path p1 in pl.paths) { 1319 foreach (Path p2 in pl.paths) { 1320 if (p1 != p2) { 1321 if (split_path (p1, p2, n)) { 1322 n.paths.remove (p1); 1323 n.paths.remove (p2); 1324 return split_paths (n); 1325 } 1326 } 1327 } 1328 } 1329 1330 return n; 1331 } 1332 1333 static PathList get_parts_self (Path path, PathList? paths = null) { 1334 PathList pl; 1335 PathList r; 1336 1337 r = paths == null ? new PathList () : (!) paths; 1338 pl = split (path); 1339 1340 foreach (Path part in pl.paths) { 1341 if (!has_self_intersection (part)) { 1342 r.add (part); 1343 } else { 1344 get_parts_self (part, r); 1345 } 1346 } 1347 1348 if (r.paths.size == 0) { 1349 warning ("No parts in path"); 1350 } 1351 1352 return r; 1353 } 1354 1355 1356 static bool has_intersection_points (Path path) { 1357 foreach (EditPoint p in path.points) { 1358 if ((p.flags & EditPoint.INTERSECTION) > 0) { 1359 return true; 1360 } 1361 } 1362 return false; 1363 } 1364 1365 /** Split one path at intersection points in two parts. */ 1366 static PathList split (Path path) { 1367 Path new_path; 1368 PathList pl; 1369 int i; 1370 1371 if (!has_intersection_points (path)) { 1372 add_self_intersection_points (path); 1373 } else { 1374 warning ("points already created."); 1375 } 1376 1377 foreach (EditPoint p in path.points) { 1378 if (insides (p, path) == 1) { 1379 path.set_new_start (p); 1380 path.close (); 1381 break; 1382 } 1383 } 1384 1385 i = mark_intersection_as_deleted (path); 1386 1387 if (!(i == 0 || i == 2)) { 1388 warning (@"Split should only create two parts, $i points will be deleted."); 1389 } 1390 1391 new_path = path.copy (); 1392 pl = get_remaining_points (new_path); 1393 1394 return pl; 1395 } 1396 1397 static PathList process_deleted_control_points (Path path) { 1398 PathList paths, nl, pl, rl, result; 1399 1400 paths = new PathList (); 1401 rl = new PathList (); 1402 pl = new PathList (); 1403 nl = new PathList (); 1404 1405 if (!path.has_deleted_point ()) { 1406 print ("No deleted points\n"); 1407 return pl; 1408 } 1409 1410 pl.add (path); 1411 1412 foreach (Path p in pl.paths) { 1413 nl = p.process_deleted_points (); 1414 1415 if (nl.paths.size > 0) { 1416 rl.append (nl); 1417 rl.paths.remove (p); 1418 } 1419 } 1420 1421 result = new PathList (); 1422 foreach (Path p in rl.paths) { 1423 pl = process_deleted_control_points (p); 1424 1425 if (pl.paths.size > 0) { 1426 result.append (pl); 1427 } else { 1428 result.add (p); 1429 } 1430 } 1431 1432 for (int i = 1; i < result.paths.size; i++) { 1433 result.paths.get (i).reverse (); 1434 } 1435 1436 paths.append (result); 1437 1438 return paths; 1439 } 1440 1441 static PathList get_remaining_points (Path old_path) { 1442 PathList pl; 1443 1444 old_path.close (); 1445 pl = process_deleted_control_points (old_path); 1446 1447 if (pl.paths.size == 0) { 1448 print ("No paths.\n"); 1449 pl.add (old_path); 1450 } 1451 1452 foreach (Path pn in pl.paths) { 1453 pn.close (); 1454 } 1455 1456 return pl; 1457 } 1458 1459 static bool has_self_intersection (Path path) { 1460 bool intersection = false; 1461 1462 path.all_segments ((ep1, ep2) => { 1463 double ix, iy; 1464 EditPoint p1, p2; 1465 1466 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true)) { 1467 intersection = true; 1468 return false; 1469 } 1470 1471 return true; 1472 }); 1473 1474 return intersection; 1475 } 1476 1477 static bool add_self_intersection_points (Path path, bool only_offsets = false) { 1478 bool intersection = false; 1479 1480 path.all_segments ((ep1, ep2) => { 1481 double ix, iy; 1482 EditPoint p1, p2; 1483 1484 if (segment_intersects (path, ep1, ep2, out ix, out iy, out p1, out p2, true, only_offsets)) { 1485 add_intersection (path, ep1, ep2, ix, iy); 1486 add_intersection (path, p1, p2, ix, iy); 1487 1488 intersection = true; 1489 return false; 1490 } 1491 1492 return true; 1493 }); 1494 1495 return intersection; 1496 } 1497 1498 static EditPoint add_intersection (Path path, EditPoint prev, EditPoint next, double px, double py, Color? c = null) { 1499 Gee.ArrayList<EditPoint> n = new Gee.ArrayList<EditPoint> (); 1500 EditPoint ep1 = new EditPoint (); 1501 EditPoint ep2 = new EditPoint (); 1502 EditPoint ep3 = new EditPoint (); 1503 double d; 1504 1505 if (next == path.get_first_point ()) { 1506 ep1.prev = null; 1507 } else { 1508 ep1.prev = prev; 1509 } 1510 1511 ep1.prev = prev; 1512 ep1.next = ep2; 1513 ep1.flags |= EditPoint.NEW_CORNER | EditPoint.SPLIT_POINT; 1514 ep1.type = prev.type; 1515 ep1.x = px; 1516 ep1.y = py; 1517 ep1.color = c; 1518 n.add (ep1); 1519 1520 ep2.prev = ep1; 1521 ep2.next = ep3; 1522 ep2.flags |= EditPoint.INTERSECTION | EditPoint.SPLIT_POINT; 1523 ep2.type = prev.type; 1524 ep2.x = px; 1525 ep2.y = py; 1526 ep2.color = c; 1527 n.add (ep2); 1528 1529 ep3.prev = ep2; 1530 ep3.next = next; 1531 ep3.flags |= EditPoint.NEW_CORNER | EditPoint.SPLIT_POINT; 1532 ep3.type = prev.type; 1533 ep3.x = px; 1534 ep3.y = py; 1535 ep3.color = c; 1536 n.add (ep3); 1537 1538 next.get_left_handle ().convert_to_line (); 1539 1540 foreach (EditPoint np in n) { 1541 np = path.add_point_after (np, np.prev); 1542 path.create_list (); 1543 } 1544 1545 PenTool.convert_point_to_line (ep1, true); 1546 PenTool.convert_point_to_line (ep2, true); 1547 PenTool.convert_point_to_line (ep3, true); 1548 1549 ep1.recalculate_linear_handles (); 1550 ep2.recalculate_linear_handles (); 1551 ep3.recalculate_linear_handles (); 1552 1553 d = Path.distance_to_point (prev, next); 1554 prev.get_right_handle ().length *= Path.distance_to_point (prev, ep1) / d; 1555 next.get_left_handle ().length *= Path.distance_to_point (ep3, next) / d; 1556 1557 next.recalculate_linear_handles (); 1558 1559 return ep2; 1560 } 1561 1562 static bool segments_intersects (EditPoint p1, EditPoint p2, EditPoint ep, EditPoint next, 1563 out double ix, out double iy, 1564 bool skip_points_on_points = false) { 1565 double cross_x, cross_y; 1566 1567 ix = 0; 1568 iy = 0; 1569 1570 if (is_line (ep.x, ep.y, p1.x, p1.y, next.x, next.y)) { 1571 ix = p1.x; 1572 iy = p1.y; 1573 return true; 1574 } 1575 1576 if (is_line (ep.x, ep.y, p2.x, p2.y, next.x, next.y)) { 1577 ix = p2.x; 1578 iy = p2.y; 1579 return true; 1580 } 1581 1582 if (is_line (p1.x, p1.y, ep.x, ep.y, p2.x, p2.y)) { 1583 ix = ep.x; 1584 iy = ep.y; 1585 return true; 1586 } 1587 1588 if (is_line (p1.x, p1.y, next.x, next.y, p2.x, p2.y)) { 1589 ix = next.x; 1590 iy = next.y; 1591 return true; 1592 } 1593 1594 Path.find_intersection_point (ep, next, p1, p2, out cross_x, out cross_y); 1595 1596 if (fmin (ep.x, next.x) <= cross_x <= fmax (ep.x, next.x) 1597 && fmin (ep.y, next.y) <= cross_y <= fmax (ep.y, next.y)) { 1598 // iterate to find intersection. 1599 if (is_line (ep.x, ep.y, cross_x, cross_y, next.x, next.y) 1600 && is_line (p1.x, p1.y, cross_x, cross_y, p2.x, p2.y)) { 1601 1602 ix = cross_x; 1603 iy = cross_y; 1604 1605 return true; 1606 } 1607 } 1608 1609 return false; 1610 } 1611 1612 static bool segment_intersects (Path path, EditPoint ep, EditPoint next, 1613 out double ix, out double iy, 1614 out EditPoint ia, out EditPoint ib, 1615 bool skip_points_on_points = false, 1616 bool only_offsets = false) { 1617 1618 EditPoint p1, p2; 1619 bool intersection, inter; 1620 double iix, iiy; 1621 1622 double distance, min_distance; 1623 1624 intersection = false; 1625 1626 ix = 0; 1627 iy = 0; 1628 1629 iix = 0; 1630 iiy = 0; 1631 1632 ia = new EditPoint (); 1633 ib = new EditPoint (); 1634 1635 if (path.points.size == 0) { 1636 return false; 1637 } 1638 1639 min_distance = double.MAX; 1640 p1 = path.points.get (path.points.size - 1); 1641 for (int i = 0; i < path.points.size; i++) { 1642 p2 = path.points.get (i); 1643 1644 bool is_offset = ((p1.flags & EditPoint.STROKE_OFFSET) > 0) 1645 && ((p2.flags & EditPoint.STROKE_OFFSET) > 0) 1646 && ((ep.flags & EditPoint.STROKE_OFFSET) > 0) 1647 && ((next.flags & EditPoint.STROKE_OFFSET) > 0); 1648 1649 if (!only_offsets || is_offset) { 1650 if (p1 != ep && p2 != next) { 1651 inter = segments_intersects (p1, p2, ep, next, out iix, out iiy, 1652 skip_points_on_points); 1653 1654 if (inter) { 1655 distance = Path.distance (ep.x, iix, ep.y, iiy); 1656 if (distance < min_distance) { 1657 ia = p1; 1658 ib = p2; 1659 ix = iix; 1660 iy = iiy; 1661 intersection = true; 1662 min_distance = distance; 1663 } 1664 } 1665 } 1666 } 1667 1668 p1 = p2; 1669 } 1670 1671 return intersection; 1672 } 1673 1674 /** @return true if p2 is on the line p1 to p3 */ 1675 static bool is_line (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.01) { 1676 return fmin (x1, x3) <= x2 && x2 <= fmax (x1, x3) 1677 && fmin (y1, y3) <= y2 && y2 <= fmax (y1, y3) 1678 && is_flat (x1, y1, x2, y2, x3, y3, tolerance); 1679 } 1680 1681 public static bool is_flat (double x1, double y1, double x2, double y2, double x3, double y3, double tolerance = 0.001) { 1682 double ds = Path.distance (x1, x3, y1, y3); 1683 double d1 = Path.distance (x1, x2, y1, y2); 1684 double d2 = Path.distance (x2, x3, y2, y3); 1685 double p = d1 / ds; 1686 double x = fabs ((x3 - x1) * p - (x2 - x1)) / ds; 1687 double y = fabs ((y3 - y1) * p - (y2 - y1)) / ds; 1688 double d = fabs (ds - (d1 + d2)) / ds; 1689 1690 return ds > 0.001 && d1 > 0.001 && d2 > 0.001 1691 && d < tolerance && x < tolerance && y < tolerance; 1692 } 1693 1694 // indside becomes outside in some paths 1695 static void remove_points_in_stroke (PathList pl) { 1696 PathList r; 1697 1698 foreach (Path p in pl.paths) { 1699 if (remove_points_in_stroke_for_path (p, pl, out r)) { 1700 pl.append (r); 1701 remove_points_in_stroke (pl); 1702 return; 1703 } 1704 } 1705 } 1706 1707 static bool remove_points_in_stroke_for_path (Path p, PathList pl, out PathList result) { 1708 EditPoint start_ep; 1709 EditPoint start_next; 1710 EditPoint start_prev; 1711 EditPoint end_ep = new EditPoint (); 1712 EditPoint end_next; 1713 EditPoint end_prev; 1714 1715 result = new PathList (); 1716 1717 for (int i = 1; i < p.points.size + 1; i++) { 1718 start_prev = p.points.get ((i - 1) % p.points.size); 1719 start_ep = p.points.get (i % p.points.size); 1720 start_next = p.points.get ((i + 1) % p.points.size); 1721 1722 if ((start_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1723 for (int j = i; j < p.points.size + i; j++) { 1724 end_prev = p.points.get ((j - 1) % p.points.size); 1725 end_ep = p.points.get (j % p.points.size); 1726 end_next = p.points.get ((j + 1) % p.points.size); 1727 1728 1729 if ((end_ep.flags & EditPoint.COUNTER_TO_OUTLINE) > 0) { 1730 start_ep.flags = EditPoint.NONE; 1731 end_ep.flags = EditPoint.NONE; 1732 1733 if (merge_segments (pl, p, start_prev, start_ep, end_ep, end_next, out result)) { 1734 return true; 1735 } 1736 } 1737 } 1738 } 1739 1740 start_ep.flags = EditPoint.NONE; 1741 end_ep.flags = EditPoint.NONE; 1742 } 1743 1744 return false; 1745 } 1746 1747 static bool merge_segments (PathList pl, 1748 Path path1, EditPoint start1, EditPoint stop1, 1749 EditPoint start2, EditPoint stop2, 1750 out PathList result) { 1751 1752 result = new PathList (); 1753 1754 PathList r1; 1755 PathList r2; 1756 1757 foreach (Path path2 in pl.paths) { 1758 if (path2 != path1) { 1759 reset_intersections (path1); 1760 reset_intersections (path2); 1761 1762 if (add_merge_intersection_point (path1, path2, start1, stop1)) { 1763 if (add_merge_intersection_point (path1, path2, start2, stop2)) { 1764 1765 r1 = get_remaining_points (path1.copy ()); 1766 r2 = get_remaining_points (path2.copy ()); 1767 1768 if (r1.paths.size != 2) { 1769 warning (@"Expecting two paths in r1 found $(r1.paths.size)\n"); 1770 reset_intersections (path1); 1771 reset_intersections (path2); 1772 return true; 1773 } 1774 1775 if (r2.paths.size != 2) { 1776 warning (@"Expecting two paths in r2 found $(r2.paths.size)\n"); 1777 reset_intersections (path1); 1778 reset_intersections (path2); 1779 return true; 1780 } 1781 1782 pl.paths.remove (path1); 1783 pl.paths.remove (path2); 1784 1785 double d1 = Path.point_distance (r1.paths.get (0).get_first_point (), 1786 r2.paths.get (0).get_first_point ()); 1787 1788 double d2 = Path.point_distance (r1.paths.get (0).get_first_point (), 1789 r2.paths.get (1).get_first_point ()); 1790 1791 Path m1, m2; 1792 1793 if (d1 > d2) { 1794 m1 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (0)); 1795 m2 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (1)); 1796 } else { 1797 m1 = PenTool.merge_open_paths (r1.paths.get (1), r2.paths.get (0)); 1798 m2 = PenTool.merge_open_paths (r1.paths.get (0), r2.paths.get (1)); 1799 } 1800 1801 result.add (m1); 1802 result.add (m2); 1803 1804 return true; 1805 } else { 1806 reset_intersections (path1); 1807 reset_intersections (path2); 1808 } 1809 } else { 1810 reset_intersections (path1); 1811 reset_intersections (path2); 1812 } 1813 } 1814 } 1815 1816 return false; 1817 } 1818 1819 static void reset_intersections (Path p) { 1820 foreach (EditPoint ep in p.points) { 1821 ep.flags &= uint.MAX ^ EditPoint.INTERSECTION; 1822 ep.flags &= uint.MAX ^ EditPoint.COPIED; 1823 ep.deleted = false; 1824 } 1825 p.remove_points_on_points (); 1826 } 1827 1828 static bool add_merge_intersection_point (Path path1, Path path2, EditPoint first, EditPoint next) { 1829 double ix, iy; 1830 bool intersection; 1831 1832 intersection = false; 1833 ix = 0; 1834 iy = 0; 1835 path2.all_segments ((p1, p2) => { 1836 int i; 1837 1838 intersection = segments_intersects (first, next, p1, p2, out ix, out iy); 1839 1840 if (intersection) { 1841 add_intersection (path1, first, next, ix, iy); 1842 add_intersection (path2, p1, p2, ix, iy); 1843 1844 i = mark_intersection_as_deleted (path1); 1845 i = mark_intersection_as_deleted (path2); 1846 } 1847 1848 return !intersection; 1849 }); 1850 1851 return intersection; 1852 } 1853 1854 static bool is_inside_of_path (PointSelection ps, PathList pl, out Path outline) { 1855 outline = new Path (); 1856 foreach (Path p in pl.paths) { 1857 if (p != ps.path) { 1858 if (is_inside (ps.point, p)) { 1859 outline = p; 1860 return true; 1861 } 1862 } 1863 } 1864 1865 return false; 1866 } 1867 1868 static PathList get_all_parts (PathList pl) { 1869 PathList m; 1870 bool intersects = false; 1871 PathList r = new PathList (); 1872 1873 foreach (Path p in pl.paths) { 1874 if (has_self_intersection (p)) { 1875 m = get_parts (p); 1876 r.append (m); 1877 intersects = true; 1878 } else { 1879 r.add (p); 1880 } 1881 } 1882 1883 foreach (Path p in r.paths) { 1884 p.close (); 1885 p.update_region_boundaries (); 1886 } 1887 1888 if (intersects) { 1889 return get_all_parts (r); 1890 } 1891 1892 return r; 1893 } 1894 1895 public static PathList merge (PathList pl) { 1896 bool error = false; 1897 PathList m; 1898 PathList r = pl; 1899 Path p1, p2; 1900 1901 r = get_all_parts (r); 1902 1903 while (paths_has_intersection (r, out p1, out p2)) { 1904 if (merge_path (p1, p2, out m, out error)) { 1905 r.paths.remove (p1); 1906 r.paths.remove (p2); 1907 1908 foreach (Path np in m.paths) { 1909 np.remove_points_on_points (); 1910 r.add (np); 1911 } 1912 1913 r = get_all_parts (r); 1914 } else { 1915 warning ("Not merged."); 1916 error = true; 1917 } 1918 1919 if (error) { 1920 warning ("Merge error"); 1921 break; 1922 } 1923 } 1924 1925 if (!error) { 1926 remove_merged_parts (r); 1927 } 1928 1929 foreach (Path p in r.paths) { 1930 p.close (); 1931 p.recalculate_linear_handles (); 1932 } 1933 1934 return r; 1935 } 1936 1937 static void remove_merged_parts (PathList r) { 1938 Gee.ArrayList<Path> remove = new Gee.ArrayList<Path> (); 1939 int c; 1940 1941 foreach (Path p in r.paths) { 1942 p.update_region_boundaries (); 1943 } 1944 1945 foreach (Path p in r.paths) { 1946 c = counters (r, p); 1947 1948 if (c % 2 == 0) { 1949 if (!p.is_clockwise ()) { 1950 remove.add (p); 1951 } 1952 } else { 1953 if (p.is_clockwise ()) { 1954 remove.add (p); 1955 } 1956 } 1957 } 1958 1959 foreach (Path p in remove) { 1960 r.paths.remove (p); 1961 } 1962 } 1963 1964 public static PathList get_insides (PathList pl, Path path) { 1965 bool inside = false; 1966 PathList insides = new PathList (); 1967 1968 foreach (Path p in pl.paths) { 1969 if (p.points.size > 1 1970 && p != path 1971 && path.boundaries_intersecting (p)) { 1972 1973 inside = true; 1974 foreach (EditPoint ep in path.points) { 1975 if (!is_inside (ep, p)) { 1976 inside = false; 1977 break; 1978 } 1979 } 1980 1981 if (inside) { 1982 insides.add (path); 1983 } 1984 } 1985 } 1986 1987 return insides; 1988 } 1989 1990 public static int counters (PathList pl, Path path) { 1991 int inside_count = 0; 1992 bool inside; 1993 1994 foreach (Path p in pl.paths) { 1995 inside = true; 1996 1997 if (p.points.size > 1 1998 && p != path 1999 && path.boundaries_intersecting (p)) { 2000 2001 foreach (EditPoint ep in path.points) { 2002 if (!is_inside (ep, p)) { 2003 inside = false; 2004 break; 2005 } 2006 } 2007 2008 if (inside) { 2009 inside_count++; 2010 } 2011 } 2012 } 2013 2014 return inside_count; 2015 } 2016 2017 public static bool is_inside (EditPoint point, Path path) { 2018 EditPoint prev; 2019 bool inside = false; 2020 2021 if (path.points.size <= 1) { 2022 return false; 2023 } 2024 2025 prev = path.points.get (path.points.size - 1); 2026 2027 foreach (EditPoint p in path.points) { 2028 // FIXME: double check stroke 2029 if ((fabs (p.x - point.x) < 0.1 && fabs (p.y - point.y) < 0.1) 2030 || (fabs (prev.x - point.x) < 0.1 && fabs (prev.y - point.y) < 0.1)) { 2031 return true; 2032 } else if ((p.y > point.y) != (prev.y > point.y) 2033 && point.x < (prev.x - p.x) * (point.y - p.y) / (prev.y - p.y) + p.x) { 2034 inside = !inside; 2035 } 2036 2037 prev = p; 2038 } 2039 2040 return inside; 2041 } 2042 2043 public static int insides (EditPoint point, Path path) { 2044 EditPoint prev; 2045 int inside = 0; 2046 2047 if (path.points.size <= 1) { 2048 return 0; 2049 } 2050 2051 prev = path.get_last_point (); 2052 2053 foreach (EditPoint start in path.points) { 2054 if (start.x == point.x && point.y == start.y) { 2055 inside++; 2056 } else if ((start.y > point.y) != (prev.y > point.y) 2057 && point.x < (prev.x - start.x) * (point.y - start.y) / (prev.y - start.y) + start.x) { 2058 inside++; 2059 } 2060 2061 prev = start; 2062 } 2063 2064 return inside; 2065 } 2066 2067 static bool merge_path (Path path1, Path path2, out PathList merged_paths, out bool error) { 2068 IntersectionList intersections; 2069 EditPoint ep1, next, p1, p2, pp1, pp2; 2070 Path path, other, merged; 2071 PathList r, other_paths, result; 2072 bool intersects; 2073 int s, i; 2074 double ix, iy, iix, iiy; 2075 bool merge = false; 2076 EditPoint intersection_point, other_intersection_point; 2077 bool path1_direction, path2_direction; 2078 2079 if (path1.points.size == 0) { 2080 return false; 2081 } 2082 2083 if (path2.points.size == 0) { 2084 return false; 2085 } 2086 2087 error = false; 2088 merged_paths = new PathList (); 2089 intersections = new IntersectionList (); 2090 2091 reset_intersections (path1); 2092 reset_intersections (path2); 2093 2094 iix = 0; 2095 iiy = 0; 2096 2097 result = new PathList (); 2098 2099 if (path1.points.size == 0 || path2.points.size == 0) { 2100 warning ("No points in path."); 2101 error = true; 2102 return false; 2103 } 2104 2105 if (!path1.boundaries_intersecting (path2)) { 2106 return false; 2107 } 2108 2109 Path original_path1 = path1.copy (); 2110 Path original_path2 = path2.copy (); 2111 2112 s = 0; 2113 foreach (EditPoint e in original_path1.points) { 2114 if (!is_inside (e, original_path2) 2115 && insides (e, original_path1) == 1) { // FIXME: later as well 2116 break; 2117 } 2118 s++; 2119 } 2120 2121 if (s >= path1.points.size) { 2122 Path t; 2123 t = original_path1; 2124 original_path1 = original_path2; 2125 original_path2 = t; 2126 s = 0; 2127 foreach (EditPoint e in original_path1.points) { 2128 if (!is_inside (e, original_path2)) { 2129 break; 2130 } 2131 s++; 2132 } 2133 } 2134 2135 if (s >= original_path1.points.size) { 2136 warning ("No start point found."); 2137 error = true; 2138 return false; 2139 } 2140 2141 path = original_path1; 2142 other = original_path2; 2143 2144 other_paths = new PathList (); 2145 r = new PathList (); 2146 other_paths.add (path); 2147 other_paths.add (other); 2148 intersects = false; 2149 p1 = new EditPoint (); 2150 p2 = new EditPoint (); 2151 pp1 = new EditPoint (); 2152 pp2 = new EditPoint (); 2153 2154 ix = 0; 2155 iy = 0; 2156 i = s; 2157 merged = new Path (); 2158 2159 path1_direction = is_clockwise (original_path1); 2160 path2_direction = is_clockwise (original_path1); 2161 2162 while (true) { 2163 ep1 = path.points.get (i % path.points.size); 2164 next = path.points.get ((i + 1) % path.points.size); 2165 2166 if ((ep1.flags & EditPoint.COPIED) > 0) { 2167 if (merge) { 2168 merged.close (); 2169 result.add (merged.copy ()); 2170 } 2171 2172 merged = new Path (); 2173 2174 bool find_parts = false; 2175 Intersection new_start = new Intersection.empty (); 2176 foreach (Intersection inter in intersections.points) { 2177 if (!inter.done && !find_parts) { 2178 find_parts = true; 2179 new_start = inter; 2180 break; 2181 } 2182 } 2183 2184 if (!find_parts) { 2185 break; // done, no more parts to merge 2186 } else { 2187 // set start point for next part 2188 path = new_start.other_path; 2189 2190 if (path.points.size == 0) { 2191 warning ("No points."); 2192 error = true; 2193 return false; 2194 } 2195 2196 i = index_of (path, new_start.get_point (path)); 2197 2198 if (i < 0) { 2199 warning ("Start point not found."); 2200 error = true; 2201 return false; 2202 } 2203 2204 ep1 = path.points.get (i % path.points.size); 2205 next = path.points.get ((i + 1) % path.points.size); 2206 2207 if ((ep1.flags & EditPoint.INTERSECTION) == 0) { 2208 warning ("Not starting on an intersection point."); 2209 error = true; 2210 return false; 2211 } 2212 2213 new_start.done = true; 2214 } 2215 } 2216 2217 intersects = false; 2218 2219 double dm; 2220 double d; 2221 2222 if ((ep1.flags & EditPoint.INTERSECTION) > 0) { 2223 Intersection current_intersection; 2224 bool continue_on_other_path; 2225 current_intersection = intersections.get_point (ep1, out continue_on_other_path); 2226 current_intersection.done = true; 2227 2228 // take the other part of an intersection 2229 if ((next.flags & EditPoint.COPIED) != 0) { 2230 bool next_is_intersection = false; 2231 bool next_continue_on_other_path; 2232 2233 next_is_intersection = ((next.flags & EditPoint.INTERSECTION) > 0); 2234 2235 if (next_is_intersection) { 2236 Intersection next_intersection = intersections.get_point (next, out next_continue_on_other_path); 2237 2238 ep1.flags |= EditPoint.COPIED; 2239 merged.add_point (ep1.copy ()); 2240 2241 if (!next_intersection.done) { 2242 EditPoint new_start_point; 2243 2244 path = next_continue_on_other_path 2245 ? next_intersection.other_path : next_intersection.path; 2246 2247 new_start_point = next_continue_on_other_path 2248 ? next_intersection.other_point : next_intersection.point; 2249 2250 i = index_of (path, new_start_point); 2251 2252 if (i < 0) { 2253 warning ("Point not found in path.\n"); 2254 error = true; 2255 return false; 2256 } 2257 2258 ep1 = path.points.get (i % path.points.size); 2259 next = path.points.get ((i + 1) % path.points.size); 2260 } else { 2261 warning ("Part is already created.\n"); 2262 error = true; 2263 return false; 2264 } 2265 } else { 2266 ep1.flags |= EditPoint.COPIED; 2267 merged.add_point (ep1.copy ()); 2268 2269 EditPoint new_start_point; 2270 2271 if ((next.flags & EditPoint.COPIED) > 0) { 2272 path = current_intersection.get_other_path (path); 2273 new_start_point = current_intersection.get_point (path); 2274 i = index_of (path, new_start_point); 2275 2276 if (i < 0) { 2277 warning ("Point not found in path."); 2278 error = true; 2279 return false; 2280 } 2281 2282 ep1 = path.points.get (i % path.points.size); 2283 next = path.points.get ((i + 1) % path.points.size); 2284 2285 if ((next.flags & EditPoint.INTERSECTION) > 0) { 2286 warning ("Wrong type."); 2287 error = true; 2288 return false; 2289 } 2290 2291 if ((next.flags & EditPoint.COPIED) > 0) { 2292 merged.add_point (ep1.copy ()); 2293 continue; 2294 } 2295 } else { 2296 ep1.flags |= EditPoint.COPIED; 2297 merged.add_point (ep1.copy ()); 2298 } 2299 } 2300 } else { 2301 ep1.flags |= EditPoint.COPIED; 2302 2303 if (path1_direction == path2_direction) { 2304 if (!is_inside (ep1, original_path1)) { 2305 merged.add_point (ep1.copy ()); 2306 } 2307 } else { 2308 merged.add_point (ep1.copy ()); 2309 } 2310 } 2311 2312 current_intersection.done = true; 2313 } else { 2314 // find new intersection 2315 dm = double.MAX; 2316 foreach (Path o in other_paths.paths) { 2317 bool inter = segment_intersects (o, ep1, next, out iix, out iiy, 2318 out pp1, out pp2, false, false); 2319 d = Path.distance (ep1.x, iix, ep1.y, iiy); 2320 if (d < dm && inter) { 2321 other = o; 2322 dm = d; 2323 intersects = true; 2324 p1 = pp1; 2325 p2 = pp2; 2326 ix = iix; 2327 iy = iiy; 2328 } 2329 2330 if (d < 0.0001) { 2331 intersects = false; 2332 } 2333 } 2334 2335 if (intersects) { 2336 merged.add_point (ep1.copy ()); 2337 ep1.flags |= EditPoint.COPIED; 2338 2339 intersection_point = add_intersection (path, ep1, next, ix, iy); 2340 other_intersection_point = add_intersection (other, p1, p2, ix, iy); 2341 2342 bool g = false; 2343 foreach (Intersection old_intersection in intersections.points) { 2344 if (old_intersection.point == intersection_point 2345 || old_intersection.other_point == other_intersection_point) { 2346 old_intersection.done = true; 2347 g = true; 2348 } 2349 } 2350 2351 if (!g) { 2352 Intersection ip = new Intersection (intersection_point, path, other_intersection_point, other); 2353 intersections.points.add (ip); 2354 } 2355 2356 merged.add_point (intersection_point.copy ()); 2357 intersection_point.flags |= EditPoint.COPIED; 2358 2359 i = index_of (other, other_intersection_point); 2360 2361 if (i < 0) { 2362 warning (@"Point not found ($i)."); 2363 break; 2364 } 2365 2366 path = other; 2367 merge = true; 2368 } else { 2369 ep1.flags |= EditPoint.COPIED; 2370 merged.add_point (ep1.copy ()); 2371 2372 PointSelection ps; 2373 Path outline; 2374 2375 // remove points inside of path 2376 if (is_clockwise (original_path2)) { 2377 ps = new PointSelection (ep1, merged); 2378 if (is_inside_of_path (ps, result, out outline)) { 2379 ep1.deleted = true; 2380 } 2381 } 2382 } 2383 } 2384 2385 i++; 2386 } 2387 2388 if (merge) { 2389 original_path1.remove_points_on_points (); 2390 original_path2.remove_points_on_points (); 2391 original_path1.remove_deleted_points (); 2392 original_path2.remove_deleted_points (); 2393 2394 foreach (Path np in result.paths) { 2395 Path p = np.copy (); 2396 bool has_direction = true; 2397 2398 p.remove_points_on_points (); 2399 2400 if (has_direction) { 2401 p.close (); 2402 reset_intersections (p); 2403 merged_paths.append (get_parts (p)); 2404 p.update_region_boundaries (); 2405 p.recalculate_linear_handles (); 2406 } 2407 } 2408 } 2409 2410 return merge && !error; 2411 } 2412 2413 static int index_of (Path p, EditPoint ep) { 2414 int i = 0; 2415 foreach (EditPoint e in p.points) { 2416 if (e == ep) { 2417 return i; 2418 } 2419 i++; 2420 } 2421 2422 return -1; 2423 } 2424 2425 public static int counters_in_point_in_path (Path p, EditPoint ep) { 2426 int inside_count = 0; 2427 bool inside; 2428 2429 if (p.points.size > 1) { 2430 inside = true; 2431 2432 if (!is_inside (ep, p)) { 2433 inside = false; 2434 } 2435 2436 if (inside) { 2437 inside_count++; 2438 } 2439 } 2440 2441 return inside_count; 2442 } 2443 2444 static int mark_intersection_as_deleted (Path path) { 2445 int i = 0; 2446 2447 foreach (EditPoint p in path.points) { 2448 if ((p.flags & EditPoint.INTERSECTION) > 0) { 2449 p.deleted = true; 2450 i++; 2451 } 2452 } 2453 2454 return i; 2455 } 2456 2457 /** @param n number of interrsections to find per path. */ 2458 static bool add_intersection_points (Path path1, Path path2, int n = 1) { 2459 bool intersection = false; 2460 int found = 0; 2461 2462 path1.all_segments ((ep1, ep2) => { 2463 double ix, iy; 2464 EditPoint p1, p2; 2465 bool i; 2466 2467 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 2468 out p1, out p2, true); 2469 2470 if (i) { 2471 add_intersection (path1, ep1, ep2, ix, iy); 2472 add_intersection (path2, p1, p2, ix, iy); 2473 intersection = true; 2474 found++; 2475 return found < n; 2476 } 2477 2478 return true; 2479 }); 2480 2481 if (intersection && found != n) { 2482 warning (@"Wrong number of points, $found != $n"); 2483 } 2484 2485 return intersection; 2486 } 2487 2488 /** @param n number of interrsections to find per path. */ 2489 static bool has_intersection (Path path1, Path path2) { 2490 bool intersection = false; 2491 2492 if (!path1.boundaries_intersecting (path2)) { 2493 return false; 2494 } 2495 2496 path1.all_segments ((ep1, ep2) => { 2497 double ix, iy; 2498 EditPoint p1, p2; 2499 bool i; 2500 2501 i = segment_intersects (path2, ep1, ep2, out ix, out iy, 2502 out p1, out p2, true); 2503 2504 if (i) { 2505 intersection = true; 2506 } 2507 2508 return !intersection; 2509 }); 2510 2511 return intersection; 2512 } 2513 2514 static bool paths_has_intersection (PathList r, out Path path1, out Path path2) { 2515 int i, j; 2516 path1 = new Path (); 2517 path2 = new Path (); 2518 2519 i = 0; 2520 foreach (Path p1 in r.paths) { 2521 2522 j = 0; 2523 foreach (Path p2 in r.paths) { 2524 if (p1 != p2) { 2525 if (has_intersection (p1, p2)) { 2526 path1 = p1; 2527 path2 = p2; 2528 return true; 2529 } 2530 } 2531 j++; 2532 } 2533 i++; 2534 } 2535 return false; 2536 } 2537 2538 public static bool has_points_outside (PathList pl, Path p) { 2539 if (pl.paths.size != 2) { 2540 warning ("Stroke should only create two parts."); 2541 return false; 2542 } 2543 2544 foreach (Path path in pl.paths) { 2545 if (path != p) { 2546 foreach (EditPoint ep in p.points) { 2547 if (!is_inside (ep, path)) { 2548 return true; 2549 } 2550 } 2551 } 2552 } 2553 2554 return false; 2555 } 2556 2557 static bool is_clockwise (Path p) { 2558 double sum = 0; 2559 EditPoint p1, p2; 2560 2561 EditPointHandle l, r; 2562 2563 p.recalculate_linear_handles (); 2564 2565 if (p.points.size < 3) { 2566 return true; 2567 } 2568 2569 for (int i = 0; i < p.points.size; i++) { 2570 p1 = p.points.get (i); 2571 p2 = p.points.get ((i + 1) % p.points.size); 2572 2573 l = p1.get_left_handle (); 2574 r = p1.get_right_handle (); 2575 if (!(fabs (l.angle - r.angle) < 0.0001 && l.length > 0.01 && r.length > 0.01)) { 2576 sum += (p2.x - p1.x) * (p2.y + p1.y); 2577 } 2578 } 2579 2580 return sum > 0; 2581 } 2582 2583 public static PathList create_stroke (Path original_path, 2584 double thickness, bool fast) { 2585 2586 PathList pl; 2587 EditPoint p1, p2, p3; 2588 EditPoint previous, previous_inside, start, start_inside; 2589 2590 Path side1, side2; 2591 2592 double x, y, x2, y2, x3, y3; 2593 int size; 2594 bool flat, f_next, f_bigger; 2595 int i; 2596 2597 double tolerance; 2598 double step_increment; 2599 double step_size; 2600 EditPoint corner1, corner1_inside; 2601 double step; 2602 double min_increment; 2603 2604 EditPointHandle l, r; 2605 2606 Path path = original_path.copy (); 2607 2608 int keep; 2609 bool on_curve; 2610 2611 pl = new PathList (); 2612 size = path.is_open () ? path.points.size - 1 : path.points.size; 2613 2614 side1 = new Path (); 2615 side2 = new Path (); 2616 2617 foreach (EditPoint ph in path.points) { 2618 if (ph.type == PointType.HIDDEN) { 2619 ph.type = PointType.CUBIC; 2620 } 2621 } 2622 path.remove_deleted_points (); 2623 2624 if (path.points.size < 2) { 2625 return pl; 2626 } 2627 2628 previous = new EditPoint (); 2629 previous_inside = new EditPoint (); 2630 corner1 = new EditPoint (); 2631 corner1_inside = new EditPoint (); 2632 2633 if (path.is_open () || fast) { 2634 p1 = path.points.get (0); 2635 p2 = path.points.get (1 % path.points.size); 2636 2637 get_segment (thickness, 0, 0.00001, p1, p2, out start); 2638 get_segment (-thickness, 0, 0.00001, p1, p2, out start_inside); 2639 2640 previous = start.copy (); 2641 previous_inside = start_inside.copy (); 2642 2643 previous.flags |= EditPoint.CURVE_KEEP; 2644 previous_inside.flags |= EditPoint.CURVE_KEEP; 2645 2646 side1.add_point (previous); 2647 side2.add_point (previous_inside); 2648 } 2649 2650 min_increment = 0.013; 2651 2652 for (i = 0; i < size; i++) { 2653 p1 = path.points.get (i % path.points.size); 2654 p2 = path.points.get ((i + 1) % path.points.size); 2655 p3 = path.points.get ((i + 2) % path.points.size); 2656 2657 tolerance = 0.01; // 0.13 / sqrt (stroke_width) 2658 step_increment = 1.05; 2659 step_size = 0.039; // / stroke_width; 2660 2661 corner1 = new EditPoint (); 2662 2663 if (p1.type == PointType.HIDDEN 2664 || p2.type == PointType.HIDDEN) { 2665 continue; 2666 } 2667 2668 get_segment (thickness, 0, 0.00001, p1, p2, out start); 2669 get_segment (-thickness, 0, 0.00001, p1, p2, out start_inside); 2670 2671 previous = start.copy (); 2672 previous_inside = start_inside.copy (); 2673 2674 previous.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2675 previous_inside.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2676 2677 side1.add_point (previous); 2678 side2.add_point (previous_inside); 2679 2680 step = step_size; 2681 keep = 0; 2682 step_size = 0.01; 2683 2684 while (step < 1 - 2 * step_size) { 2685 Path.get_point_for_step (p1, p2, step, out x, out y); 2686 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2); 2687 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3); 2688 2689 flat = is_flat (x, y, x2, y2, x3, y3, tolerance); 2690 2691 Path.get_point_for_step (p1, p2, step, out x, out y); 2692 Path.get_point_for_step (p1, p2, step + step_size / step_increment, out x2, out y2); 2693 Path.get_point_for_step (p1, p2, step + 2 * step_size / step_increment, out x3, out y3); 2694 2695 f_next = is_flat (x, y, x2, y2, x3, y3, tolerance); 2696 2697 Path.get_point_for_step (p1, p2, step, out x, out y); 2698 Path.get_point_for_step (p1, p2, step + step_size * step_increment, out x2, out y2); 2699 Path.get_point_for_step (p1, p2, step + 2 * step_size * step_increment, out x3, out y3); 2700 2701 f_bigger = is_flat (x, y, x2, y2, x3, y3, tolerance); 2702 2703 if (!flat && !f_next && step_size > min_increment) { 2704 step_size /= step_increment; 2705 continue; 2706 } 2707 2708 if (flat && f_bigger && step_size < 0.1) { 2709 step_size *= step_increment; 2710 continue; 2711 } 2712 2713 get_segment (thickness, step, step_size, p1, p2, out corner1); 2714 get_segment (-thickness, step, step_size, p1, p2, out corner1_inside); 2715 2716 previous.get_right_handle ().length *= step_size; 2717 corner1.get_left_handle ().length *= step_size; 2718 previous_inside.get_right_handle ().length *= step_size; 2719 corner1_inside.get_left_handle ().length *= step_size; 2720 2721 previous = corner1.copy (); 2722 previous_inside = corner1_inside.copy (); 2723 2724 if (keep == 0 && step > 0.3) { // keep two points per segment 2725 on_curve = true; 2726 keep++; 2727 } else if (keep == 1 && step > 0.6) { 2728 on_curve = true; 2729 keep++; 2730 } else { 2731 on_curve = false; 2732 } 2733 2734 if (!on_curve) { 2735 previous.flags |= EditPoint.CURVE; 2736 previous_inside.flags |= EditPoint.CURVE; 2737 } else { 2738 previous.flags |= EditPoint.CURVE_KEEP; 2739 previous_inside.flags |= EditPoint.CURVE_KEEP; 2740 } 2741 2742 side1.add_point (previous); 2743 side2.add_point (previous_inside); 2744 2745 step += step_size; 2746 } 2747 2748 previous.get_right_handle ().length *= step_size; 2749 corner1.get_left_handle ().length *= step_size; 2750 previous_inside.get_right_handle ().length *= step_size; 2751 corner1_inside.get_left_handle ().length *= step_size; 2752 2753 get_segment (thickness, 1 - 0.00001, 0.00001, p1, p2, out corner1); 2754 get_segment (-thickness, 1 - 0.00001, 0.00001, p1, p2, out corner1_inside); 2755 2756 previous = corner1.copy (); 2757 previous_inside = corner1_inside.copy (); 2758 2759 previous.get_right_handle ().length *= step_size; 2760 previous.get_left_handle ().length *= step_size; 2761 previous_inside.get_right_handle ().length *= step_size; 2762 previous_inside.get_left_handle ().length *= step_size; 2763 2764 previous.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2765 previous_inside.flags |= EditPoint.CURVE | EditPoint.SEGMENT_END; 2766 2767 side1.add_point (previous); 2768 side2.add_point (previous_inside); 2769 2770 l = p2.get_left_handle (); 2771 r = p2.get_right_handle (); 2772 2773 if (fabs ((l.angle + r.angle + PI) % (2 * PI) - PI) > 0.005) { // FIXME: 0.01 2774 if (!path.is_open () || i < size - 1) { 2775 get_segment (thickness, 0, 0.00001, p2, p3, out start); 2776 add_corner (side1, previous, start, p2.copy (), thickness); 2777 2778 get_segment (-thickness, 0, 0.00001, p2, p3, out start); 2779 add_corner (side2, previous_inside, start, p2.copy (), thickness); 2780 } 2781 } 2782 2783 if (fast) { 2784 EditPoint s1, s2; 2785 bool open; 2786 2787 convert_to_curve (side1); 2788 convert_to_curve (side2); 2789 2790 side2.reverse (); 2791 s1 = side1.get_last_point ().copy (); 2792 s2 = side2.get_first_point ().copy (); 2793 2794 s1.flags &= EditPoint.CURVE ^ EditPoint.ALL; 2795 s2.flags &= EditPoint.CURVE ^ EditPoint.ALL; 2796 2797 s1.convert_to_line (); 2798 s2.convert_to_line (); 2799 2800 open = path.is_open (); 2801 2802 if (!open) { 2803 path.reopen (); 2804 } 2805 2806 pl.append (merge_stroke_parts (path, side1, side2)); 2807 2808 if (!open) { 2809 path.close (); 2810 } 2811 2812 side1 = new Path (); 2813 side2 = new Path (); 2814 2815 get_segment (thickness, 0, 0.00001, p2, p3, out start); 2816 get_segment (-thickness, 0, 0.00001, p2, p3, out start_inside); 2817 2818 previous = start.copy (); 2819 previous_inside = start_inside.copy (); 2820 2821 previous.flags |= EditPoint.CURVE; 2822 previous_inside.flags |= EditPoint.CURVE; 2823 2824 side1.add_point (previous); 2825 side2.add_point (previous_inside); 2826 } 2827 } 2828 2829 if (!fast) { 2830 side1.remove_points_on_points (); 2831 side2.remove_points_on_points (); 2832 2833 convert_to_curve (side1); 2834 convert_to_curve (side2); 2835 2836 side2.reverse (); 2837 2838 pl = merge_stroke_parts (path, side1, side2); 2839 } 2840 2841 if (fast) { 2842 foreach (Path p in pl.paths) { 2843 p.close (); 2844 convert_to_curve (p); 2845 } 2846 } 2847 2848 return pl; 2849 } 2850 2851 static void convert_to_curve (Path path) { 2852 if (path.is_open ()) { 2853 path.get_first_point ().flags &= EditPoint.ALL ^ EditPoint.CURVE; 2854 path.get_last_point ().flags &= EditPoint.ALL ^ EditPoint.CURVE; 2855 } 2856 2857 path.recalculate_linear_handles (); 2858 path.remove_points_on_points (); 2859 2860 foreach (EditPoint ep in path.points) { 2861 if ((ep.flags & EditPoint.SEGMENT_END) == 0) { 2862 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) { 2863 ep.convert_to_curve (); 2864 } 2865 } 2866 } 2867 2868 foreach (EditPoint ep in path.points) { 2869 if ((ep.flags & EditPoint.SEGMENT_END) == 0) { 2870 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) { 2871 ep.set_tie_handle (true); 2872 } 2873 } 2874 } 2875 2876 foreach (EditPoint ep in path.points) { 2877 if ((ep.flags & EditPoint.SEGMENT_END) == 0) { 2878 if ((ep.flags & EditPoint.CURVE) > 0 || (ep.flags & EditPoint.CURVE_KEEP) > 0) { 2879 ep.process_tied_handle (); 2880 } 2881 } 2882 } 2883 } 2884 2885 public static void get_segment (double stroke_thickness, double step, double step_size, 2886 EditPoint p1, EditPoint p2, out EditPoint ep1) { 2887 2888 double thickness = stroke_thickness / 2; 2889 Path overlay; 2890 double x, y, x2, y2, x3, y3; 2891 EditPoint corner1, corner2, corner3; 2892 PointType type; 2893 2894 Path.get_point_for_step (p1, p2, step, out x, out y); 2895 Path.get_point_for_step (p1, p2, step + step_size, out x2, out y2); 2896 Path.get_point_for_step (p1, p2, step + 2 * step_size, out x3, out y3); 2897 2898 overlay = new Path (); 2899 2900 type = p1.get_right_handle ().type; 2901 corner1 = new EditPoint (x, y, type); 2902 corner2 = new EditPoint (x2, y2, type); 2903 corner3 = new EditPoint (x3, y3, type); 2904 2905 corner2.convert_to_line (); 2906 2907 overlay.add_point (corner1); 2908 overlay.add_point (corner2); 2909 overlay.add_point (corner3); 2910 2911 overlay.close (); 2912 overlay.recalculate_linear_handles (); 2913 2914 move_segment (corner1, corner2, thickness); 2915 2916 ep1 = corner2; 2917 } 2918 2919 public static PathList merge_stroke_parts (Path p, Path side1, Path side2) { 2920 Path merged = new Path (); 2921 PathList paths = new PathList (); 2922 2923 if (!p.is_open ()) { 2924 side1.update_region_boundaries (); 2925 paths.add (side1); 2926 side2.update_region_boundaries (); 2927 paths.add (side2); 2928 side1.close (); 2929 side2.close (); 2930 } else if (p.is_open ()) { 2931 side2.reverse (); 2932 merged = merge_strokes (p, side1, side2); 2933 merged.close (); 2934 merged.update_region_boundaries (); 2935 paths.add (merged); 2936 merged.reverse (); 2937 } else { 2938 warning ("Can not create stroke."); 2939 paths.add (p); 2940 } 2941 2942 return paths; 2943 } 2944 } 2945 2946 } 2947