diff --git a/mono/EllipseTruncate/ActiveAngleRange.cs b/mono/EllipseTruncate/ActiveAngleRange.cs new file mode 100644 index 0000000..4e4df29 --- /dev/null +++ b/mono/EllipseTruncate/ActiveAngleRange.cs @@ -0,0 +1,157 @@ +using System; + +namespace EllipseTruncate { + public class ActiveAngleRange { + public double width = 0.1; + + public Point point; + public double radius; + public AngleRange.Entry current; + public AngleRange a = new AngleRange(); + public AngleRange b = new AngleRange(); + + public ActiveAngleRange(Point point, double radius) { + this.point = point; + this.radius = radius; + } + + public void add() { + a.add(current); + current = new AngleRange.Entry(); + } + + public void xor() { + a.xor(current); + current = new AngleRange.Entry(); + } + + public void subtract() { + a.subtract(current); + current = new AngleRange.Entry(); + } + + public void scale(Cairo.Context context, double level = 1.0) { + double k = Math.Pow(1.0 + 1.5*width, level); + context.Scale(k, k); + } + + public void draw(Cairo.Context context, uint a0, uint a1, double level = 0.0) { + if (a0 == a1) return; + + context.Save(); + scale(context, level); + context.LineWidth = width; + double aa0 = AngleRange.toDouble(a0); + double aa1 = AngleRange.toDouble(a1); + if (a1 < a0) aa1 += AngleRange.period; + if (aa1 < aa0) return; + + context.Arc(0.0, 0.0, 1.0, aa0, aa1); + context.Stroke(); + context.Restore(); + } + + public void draw(Cairo.Context context, AngleRange r, double level = 0.0) { + context.Save(); + scale(context, level); + if (r.isEmpty()) { + context.LineWidth = 0.25*width; + context.SetDash(new double[] { 0.1, 0.02 }, 0.0); + context.Arc(0.0, 0.0, 1.0, 0.0, 2.0*Math.PI); + context.Stroke(); + } else + if (r.isFull()) { + context.LineWidth = width; + context.Arc(0.0, 0.0, 1.0, 0.0, 2.0*Math.PI); + context.Stroke(); + context.LineWidth = 0.25*width; + context.SetDash(new double[] { 0.1, 0.03 }, 0.0); + context.Arc(0.0, 0.0, 1.0, 0.0, 2.0*Math.PI); + context.Stroke(); + } else { + context.LineWidth = 0.25*width; + context.Arc(0.0, 0.0, 1.0, 0.0, 2.0*Math.PI); + context.Stroke(); + bool f = r.flip; + uint prev = r.angles[r.angles.Count - 1]; + foreach(uint a in r.angles) { + if (f) draw(context, prev, a); + prev = a; f = !f; + } + } + + if (!r.check()) { + context.LineWidth = width; + context.SetDash(new double[] { 0.1, 0.02 }, 0.0); + context.Arc(0.0, 0.0, 1.0, 0.0, 2.0*Math.PI); + context.Stroke(); + } + + context.Restore(); + } + + public void draw(Cairo.Context context) { + context.Save(); + context.Translate(point.x, point.y); + context.Scale(radius, radius); + + AngleRange x = new AngleRange(); + + // back circle + context.SetSourceRGBA(1.0, 0.0, 0.0, 0.1); + context.Arc(0.0, 0.0, 1.0, 0.0, 2.0*Math.PI); + context.Fill(); + + // a + context.SetSourceRGBA(0.0, 0.0, 0.0, 0.5); + draw(context, a); + + // b + context.SetSourceRGBA(0.0, 0.0, 1.0, 0.5); + draw(context, b, 1.0); + + // current + context.SetSourceRGBA(0.0, 0.0, 1.0, 0.5); + if (!current.isEmpty()) + draw(context, current.a0, current.a1); + + // !a + context.SetSourceRGBA(0.5, 0.5, 0.5, 0.5); + x.set(a); x.invert(); + draw(context, x, -1.0); + + scale(context); + + // a xor b + scale(context); + context.SetSourceRGBA(0.0, 0.5, 0.0, 0.5); + x.set(a); + x.xor(b); + draw(context, x); + + // a | b + scale(context); + context.SetSourceRGBA(0.0, 0.5, 0.0, 0.5); + x.set(a); + x.add(b); + draw(context, x); + + // a & ~b + scale(context); + context.SetSourceRGBA(0.0, 0.5, 0.0, 0.5); + x.set(a); + x.subtract(b); + draw(context, x); + + // a & b + scale(context); + context.SetSourceRGBA(0.0, 0.5, 0.0, 0.5); + x.set(a); + x.intersect(b); + draw(context, x); + + context.Restore(); + } + } +} + diff --git a/mono/EllipseTruncate/AngleRange.cs b/mono/EllipseTruncate/AngleRange.cs new file mode 100644 index 0000000..e224787 --- /dev/null +++ b/mono/EllipseTruncate/AngleRange.cs @@ -0,0 +1,243 @@ +using System; +using System.Collections.Generic; + +namespace EllipseTruncate { + public class AngleRange { + public static readonly double min = -Math.PI; + public static readonly double max = Math.PI; + public static readonly double period = max - min; + + public static readonly uint half = uint.MaxValue/2+1; + public static readonly uint step = uint.MaxValue/16+1; + + public static uint discrete(uint a) + { return unchecked((a + step/2)/step*step); } + public static uint toUIntDiscrete(double a) + { return discrete(toUInt(a)); } + public static uint toUInt(double a) + { return unchecked((uint)Math.Round((a-min)/period*uint.MaxValue)); } + public static double toDouble(uint a) + { return (double)a/(double)uint.MaxValue*period + min; } + + public struct Entry { + public uint a0, a1; + public Entry(uint a0, uint a1) + { this.a0 = a0; this.a1 = a1; } + public bool isEmpty() + { return a0 == a1; } + public Entry flipped() + { return new Entry(a1, a0); } + } + + public bool flip = false; + public readonly List angles = new List(); + + public AngleRange(bool fill = false) + { flip = fill; } + + public bool isEmpty() + { return angles.Count == 0 && !flip; } + public bool isFull() + { return angles.Count == 0 && flip; } + + public void clear() + { angles.Clear(); flip = false; } + public void fill() + { angles.Clear(); flip = true; } + + private void doSet(uint a0, uint a1) { + angles.Clear(); + if (a0 < a1) { + flip = false; + angles.Add(a0); + angles.Add(a1); + } else { + flip = true; + angles.Add(a1); + angles.Add(a0); + } + } + + public void set(Entry e) { + if (e.isEmpty()) { clear(); return; } + doSet(e.a0, e.a1); + } + + public void set(AngleRange r, bool flip = false) { + if (r == this) return; + this.flip = (r.flip != flip); + angles.Clear(); + angles.AddRange(r.angles); + } + + public bool check() { + if (angles.Count % 2 != 0) + return false; + for(int i = 1; i < angles.Count; ++i) + if (angles[i-1] >= angles[i]) + return false; + return true; + } + + public void invert() + { flip = !flip; } + + private int find(uint a) { + int i0 = 0, i1 = angles.Count - 1; + if (a < angles[0]) return i1; + if (angles[i1] <= a) return i1; + while(true) { + int i = (i1 + i0)/2; + if (i == i0) break; + if (angles[i] <= a) i0 = i; else i1 = i; + } + return i0; + } + + private void remove(int p0, int p1) { + if (p1 < p0) { + angles.RemoveRange(p0, angles.Count - p0); + angles.RemoveRange(0, p1 + 1); + } else { + angles.RemoveRange(p0, p1 - p0 + 1); + } + } + + private void insert(uint a) { + int p = find(a); + if (angles[p] == a) angles.RemoveAt(p); else + if (a < angles[0]) angles.Insert(0, a); else + angles.Insert(p+1, a); + } + + private int decrease(int i) + { return i == 0 ? angles.Count - 1: i - 1; } + private int increase(int i) + { return (i + 1)%angles.Count; } + + public void xor(Entry e) { + if (e.isEmpty()) return; + if (isEmpty()) { doSet(e.a0, e.a1); return; } + if (isFull()) { doSet(e.a1, e.a0); return; } + if (e.a1 < e.a0) flip = !flip; + insert(e.a0); + insert(e.a1); + } + + public void xor(AngleRange r) { + if (r.isEmpty()) { return; } + if (r.isFull()) { invert(); return; } + if (isEmpty()) { set(r); return; } + if (isFull()) { set(r, true); return; } + flip = flip != r.flip; + foreach(uint a in r.angles) + insert(a); + } + + private bool doAdd(uint a0, uint a1) { + int p0 = find(a0); + int p1 = find(a1); + if (p0 == p1) { + bool v = (p0%2 != 0) == flip; + if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) { + if (v) { fill(); return true; } + doSet(a0, a1); + } else + if (!v) { + if (a1 < a0) flip = true; + insert(a0); + insert(a1); + } + return false; + } + + bool v0 = (p0%2 != 0) == flip; + bool v1 = (p1%2 != 0) == flip; + remove(increase(p0), p1); + if (!v0) insert(a0); + if (!v1) insert(a1); + if (angles.Count == 0) { flip = true; return true; } + if (a1 < a0) flip = true; + return false; + } + + private bool doSubtract(uint a0, uint a1) { + int p0 = find(a0); + int p1 = find(a1); + if (p0 == p1) { + bool v = (p0%2 != 0) == flip; + if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) { + if (!v) { clear(); return true; } + doSet(a1, a0); + } else + if (v) { + if (a1 < a0) flip = false; + insert(a0); + insert(a1); + } + return false; + } + + bool v0 = (p0%2 != 0) == flip; + bool v1 = (p1%2 != 0) == flip; + remove(increase(p0), p1); + if (v0) insert(a0); + if (v1) insert(a1); + if (angles.Count == 0) { flip = false; return true; } + if (a1 < a0) flip = false; + return false; + } + + public void add(Entry e) { + if (!isFull() && !e.isEmpty()) + { if (isEmpty()) doSet(e.a0, e.a1); else doAdd(e.a0, e.a1); } + } + + public void subtract(Entry e) { + if (!isEmpty() && !e.isEmpty()) + { if (isFull()) doSet(e.a1, e.a0); else doSubtract(e.a0, e.a1); } + } + + public void intersect(Entry e) { + if (!isEmpty()) { + if (e.isEmpty()) clear(); + else if (isFull()) doSet(e.a0, e.a1); + else doSubtract(e.a1, e.a0); + } + } + + public void add(AngleRange r) { + if (r == this || isFull() || r.isEmpty()) return; + if (isEmpty()) { set(r); return; } + if (r.isFull()) { fill(); return; } + bool f = r.flip; + uint prev = r.angles[r.angles.Count - 1]; + foreach(uint a in r.angles) + if (f && doAdd(prev, a)) return; + else { prev = a; f = !f; } + } + + public void subtract(AngleRange r) { + if (isEmpty() || r.isEmpty()) return; + if (r == this || r.isFull()) { clear(); return; } + if (isFull()) { set(r); invert(); return; } + bool f = r.flip; + uint prev = r.angles[r.angles.Count - 1]; + foreach(uint a in r.angles) + if (f && doSubtract(prev, a)) return; + else { prev = a; f = !f; } + } + + public void intersect(AngleRange r) { + if (r == this || isEmpty() || r.isFull()) return; + if (r.isEmpty()) { clear(); return; } + if (isFull()) { set(r); return; } + bool f = !r.flip; + uint prev = r.angles[r.angles.Count - 1]; + foreach(uint a in r.angles) + if (f && doSubtract(prev, a)) return; + else { prev = a; f = !f; } + } + } +} + diff --git a/mono/EllipseTruncate/Ellipse.cs b/mono/EllipseTruncate/Ellipse.cs index 33a8f6d..f6b9e08 100644 --- a/mono/EllipseTruncate/Ellipse.cs +++ b/mono/EllipseTruncate/Ellipse.cs @@ -1,43 +1,7 @@ using System; +using System.Collections.Generic; namespace EllipseTruncate { - public struct AngleRange { - public double angle, size; - - public AngleRange(double angle, double size) - { this.angle = angle; this.size = size; } - public bool isEmpty() - { return size <= Geometry.precision; } - public bool isFull() - { return size >= 2.0*Math.PI - Geometry.precision; } - public double end() - { return wrap(angle + size); } - public bool contains(double a) - { return diff(a, angle) < size; } - public bool intersects(AngleRange r) - { return contains(r.angle) || r.contains(angle); } - public AngleRange union(AngleRange r) { - double da = diff(r.angle, angle); - if (da <= size + Geometry.precision) - return new AngleRange(angle, Math.Max(size, da + r.size)); - da = 2.0*Math.PI - da; - if (da <= r.size + Geometry.precision) - return new AngleRange(r.angle, Math.Max(r.size, da + size)); - da = Math.Min(angle, r.angle); - return new AngleRange(da, Math.Max(angle + size, r.angle + r.size) - da); - } - - public static AngleRange byAngles(double a0, double a1) - { return new AngleRange(a0, diff(a1, a0)); } - public static double diff(double a1, double a0) - { return a0 < a1 ? a1 - a0 : a1 - a0 + 2.0*Math.PI; } - public static double wrap(double angle) { - return angle > Math.PI ? angle - 2.0*Math.PI - : angle < -Math.PI ? angle + 2.0*Math.PI - : angle; - } - } - public class Ellipse { public Point center; public Point p1; @@ -100,33 +64,32 @@ namespace EllipseTruncate { private static void swap(ref int a, ref int b) { int c = a; a = b; b = c; } - private bool cutRange(ref int index, AngleRange[] ranges, double da, double h) { - if (h <= Geometry.precision - 1.0) { + private bool cutRange(AngleRange range, uint da, double h) { + if (h <= Geometry.precision - 1.0) return true; - } else - if (h >= 1.0 - Geometry.precision) { + if (h >= 1.0 - Geometry.precision) return false; - } else { - double a = Math.Asin(h); - ranges[index].angle = AngleRange.wrap( a < 0.0 - ? da - a - Math.PI - : da - a + Math.PI ); - ranges[index].size = Math.PI + a + a; - int j = index; - for(int i = 0, r = 0; i < index;) { - if (r > 0) ranges[i] = ranges[i + r]; - if (ranges[i].intersects(ranges[j])) { - if (j < i) { ranges[j] = ranges[i].union(ranges[j]); ++r; --index; } - else { ranges[i] = ranges[i].union(ranges[j]); j = i; ++i; } - if (ranges[j].isFull()) - return false; - } else ++i; - } - if (j == index) ++index; - } - return true; + uint a = AngleRange.toUInt(Math.Asin(h)); + range.subtract(new AngleRange.Entry( + da - a, (da + a)^AngleRange.half )); + return !range.isEmpty(); } + public void putSegment(Cairo.Context context, double da, double s, double c, double a0, double a1) { + int cnt = (int)Math.Floor((a1 - a0)/da); + Point r = new Point(1.0, 0.0).rotate(a0); + Point p = matrix*r; + context.MoveTo(p.x, p.y); + for(int j = 0; j < cnt; ++j) { + r = new Point(r.x*c - r.y*s, r.y*c + r.x*s); + p = matrix*r; + context.LineTo(p.x, p.y); + } + r = new Point(1.0, 0.0).rotate(a1); + p = matrix*r; + context.LineTo(p.x, p.y); + } + public void drawTruncated(Cairo.Context context, Point b0, Point b1, Point b2) { Point dx = matrixInv.turn(b1 - b0); Point dy = matrixInv.turn(b2 - b0); @@ -134,18 +97,14 @@ namespace EllipseTruncate { Point ny = dy.rotate90().normalize(); Point o = matrixInv*b0; - double ax = dx.atan(); - double ay = dy.atan(); - double aax = AngleRange.wrap(ax + Math.PI); - double aay = AngleRange.wrap(ay + Math.PI); + uint ax = AngleRange.toUInt(dx.atan()); + uint ay = AngleRange.toUInt(dy.atan()); double sign = nx*dy; if (Math.Abs(sign) <= Geometry.precision) return; if (sign < 0.0) { - double a; nx *= -1.0; ny *= -1.0; - a = ax; ax = aax; aax = a; - a = ay; ay = aay; aay = a; + ax ^= AngleRange.half; ay ^= AngleRange.half; } context.Save(); @@ -159,28 +118,12 @@ namespace EllipseTruncate { context.Fill(); context.Restore(); - // gather invisible ranges - AngleRange[] cutRanges = new AngleRange[4]; - int count = 0; - if ( !cutRange(ref count, cutRanges, ax , (o*nx)) ) return; - if ( !cutRange(ref count, cutRanges, aax, -((o+dx+dy)*nx)) ) return; - if ( !cutRange(ref count, cutRanges, ay , (o+dx)*ny) ) return; - if ( !cutRange(ref count, cutRanges, aay, -((o+dy)*ny)) ) return; - - // sort bounds - for(int i = 0; i < count; ++i) - for(int j = i+1; j < count; ++j) - if (cutRanges[j].angle < cutRanges[i].angle) - { AngleRange r = cutRanges[i]; cutRanges[i] = cutRanges[j]; cutRanges[j] = r; } - - // invert bounds - AngleRange[] ranges = new AngleRange[4]; - for(int i = 0; i < count; ++i) - ranges[i] = AngleRange.byAngles(cutRanges[(i > 0 ? i : count) - 1].end(), cutRanges[i].angle); - - // dummy - if (count == 0) - ranges[count++] = new AngleRange(0.0, 2.0*Math.PI); + // build ranges + AngleRange range = new AngleRange(true); + if ( !cutRange(range, ax, o*nx) ) return; + if ( !cutRange(range, ax^AngleRange.half, -((o+dx+dy)*nx)) ) return; + if ( !cutRange(range, ay, (o+dx)*ny) ) return; + if ( !cutRange(range, ay^AngleRange.half, -((o+dy)*ny)) ) return; // draw int segments = 100; @@ -191,21 +134,20 @@ namespace EllipseTruncate { context.Save(); context.LineWidth = 2.0; context.SetSourceRGBA(0.0, 0.0, 1.0, 1.0); - for(int i = 0; i < count; ++i) { - double angle = ranges[i].angle; - double size = ranges[i].size; - int cnt = (int)Math.Floor(size/da); - Point r = new Point(1.0, 0.0).rotate(angle); - Point p = matrix*r; - context.MoveTo(p.x, p.y); - for(int j = 0; j < cnt; ++j) { - r = new Point(r.x*c - r.y*s, r.y*c + r.x*s); - p = matrix*r; - context.LineTo(p.x, p.y); + if (range.isFull()) { + putSegment(context, da, s, c, 0.0, AngleRange.period); + } else { + bool f = range.flip; + uint prev = range.angles[range.angles.Count - 1]; + foreach(uint a in range.angles) { + if (f) { + double a0 = AngleRange.toDouble(prev); + double a1 = AngleRange.toDouble(a); + if (a < prev) a1 += AngleRange.period; + putSegment(context, da, s, c, a0, a1); + } + prev = a; f = !f; } - r = new Point(1.0, 0.0).rotate(angle + size); - p = matrix*r; - context.LineTo(p.x, p.y); } context.Stroke(); context.Restore(); diff --git a/mono/EllipseTruncate/EllipseTruncate.csproj b/mono/EllipseTruncate/EllipseTruncate.csproj index 3f7e0a9..352161f 100644 --- a/mono/EllipseTruncate/EllipseTruncate.csproj +++ b/mono/EllipseTruncate/EllipseTruncate.csproj @@ -41,6 +41,8 @@ + + diff --git a/mono/EllipseTruncate/MainWindow.cs b/mono/EllipseTruncate/MainWindow.cs index 520eee1..05aa102 100644 --- a/mono/EllipseTruncate/MainWindow.cs +++ b/mono/EllipseTruncate/MainWindow.cs @@ -18,9 +18,14 @@ namespace EllipseTruncate { Gtk.Application.Run(); } + Point cursor; Point offset; ActivePoint point; + ActiveAngleRange rangeAdd; + ActiveAngleRange rangeXor; + ActiveAngleRange rangeSub; List points = new List(); + List ranges = new List(); ActivePoint ellipse0 = new ActivePoint(500.0, 500.0), ellipse1 = new ActivePoint(600.0, 500.0), @@ -28,6 +33,8 @@ namespace EllipseTruncate { ActivePoint bounds0 = new ActivePoint(450.0, 500.0), bounds1 = new ActivePoint(500.0, 700.0), bounds2 = new ActivePoint(600.0, 550.0); + ActiveAngleRange rangeA = new ActiveAngleRange(new Point(150.0, 150.0), 50.0); + ActiveAngleRange rangeB = new ActiveAngleRange(new Point(400.0, 150.0), 50.0); public MainWindow(): base(Gtk.WindowType.Toplevel) { Events = Gdk.EventMask.KeyPressMask @@ -37,7 +44,10 @@ namespace EllipseTruncate { | Gdk.EventMask.ButtonMotionMask | Gdk.EventMask.PointerMotionMask; ExtensionEvents = Gdk.ExtensionMode.All; + rangeA.b = rangeB.a; + rangeB.b = rangeA.a; points.AddRange(new ActivePoint[] {ellipse0, ellipse1, ellipse2, bounds0, bounds1, bounds2}); + ranges.AddRange(new ActiveAngleRange[] {rangeA, rangeB}); } private bool refreshOnIdle() @@ -89,34 +99,96 @@ namespace EllipseTruncate { ellipse.drawFull(context); ellipse.drawTruncated(context, bounds0.point, bounds1.point, bounds2.point); + // draw ranges + foreach(ActiveAngleRange rl in ranges) { + rl.draw(context); + if ((cursor - rl.point).len() < 2.0*rl.radius || !rl.current.isEmpty()) { + context.Save(); + context.SetSourceRGBA(0.0, 0.0, 0.0, 0.5); + context.LineWidth = 1.0; + context.MoveTo(rl.point.x, rl.point.y); + context.LineTo(cursor.x, cursor.y); + context.Stroke(); + context.Restore(); + } + } + context.Restore(); context.Dispose(); return false; } + + private void releaseButton() { + if (rangeAdd != null) rangeAdd.add(); + if (rangeXor != null) rangeXor.xor(); + if (rangeSub != null) rangeSub.subtract(); + point = null; + rangeAdd = null; + rangeXor = null; + rangeSub = null; + } protected override bool OnButtonPressEvent(Gdk.EventButton e) { + cursor = new Point(e.X, e.Y); + releaseButton(); + + ActivePoint ap = null; + Point o = new Point(); + foreach(ActivePoint p in points) + if ((p.point - cursor).len() <= 5.0) + { o = p.point - cursor; ap = p; } + ActiveAngleRange ar = null; + uint a0 = 0; + foreach(ActiveAngleRange r in ranges) + if ((r.point - cursor).len() < 2.0*r.radius) + { ar = r; a0 = AngleRange.toUIntDiscrete((cursor - r.point).atan()); } + if (e.Button == 1) { - Point cursor = new Point(e.X, e.Y); - point = null; - foreach(ActivePoint p in points) - if ((p.point - cursor).len() <= 5.0) - { offset = p.point - cursor; point = p; } + if (ap != null) { + point = ap; + offset = o; + } else + if (ar != null) { + ar.current = new AngleRange.Entry(); + ar.current.a0 = a0; + rangeAdd = ar; + } + } else + if (e.Button == 2) { + if (ar != null) { + ar.current = new AngleRange.Entry(); + ar.current.a0 = a0; + rangeXor = ar; + } + } else + if (e.Button == 3) { + if (ar != null) { + ar.current = new AngleRange.Entry(); + ar.current.a0 = a0; + rangeSub = ar; + } } + Refresh(); return false; } protected override bool OnButtonReleaseEvent(Gdk.EventButton e) { - if (e.Button == 1) point = null; + cursor = new Point(e.X, e.Y); + releaseButton(); Refresh(); return false; } protected override bool OnMotionNotifyEvent(Gdk.EventMotion e) { - if (point != null) { - Point cursor = new Point(e.X, e.Y); - point.point = cursor + offset; - } + cursor = new Point(e.X, e.Y); + if (point != null) point.point = cursor + offset; + if (rangeAdd != null) + rangeAdd.current.a1 = AngleRange.toUIntDiscrete((cursor - rangeAdd.point).atan()); + if (rangeXor != null) + rangeXor.current.a1 = AngleRange.toUIntDiscrete((cursor - rangeXor.point).atan()); + if (rangeSub != null) + rangeSub.current.a1 = AngleRange.toUIntDiscrete((cursor - rangeSub.point).atan()); Refresh(); return false; }