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