|
|
782bf6 |
using System;
|
|
|
782bf6 |
using System.Collections.Generic;
|
|
|
782bf6 |
|
|
|
782bf6 |
namespace EllipseTruncate {
|
|
|
782bf6 |
public class AngleRange {
|
|
|
782bf6 |
public static readonly double min = -Math.PI;
|
|
|
782bf6 |
public static readonly double max = Math.PI;
|
|
|
782bf6 |
public static readonly double period = max - min;
|
|
|
782bf6 |
|
|
|
782bf6 |
public static readonly uint half = uint.MaxValue/2+1;
|
|
|
782bf6 |
public static readonly uint step = uint.MaxValue/16+1;
|
|
|
782bf6 |
|
|
|
782bf6 |
public static uint discrete(uint a)
|
|
|
782bf6 |
{ return unchecked((a + step/2)/step*step); }
|
|
|
782bf6 |
public static uint toUIntDiscrete(double a)
|
|
|
782bf6 |
{ return discrete(toUInt(a)); }
|
|
|
782bf6 |
public static uint toUInt(double a)
|
|
|
782bf6 |
{ return unchecked((uint)Math.Round((a-min)/period*uint.MaxValue)); }
|
|
|
782bf6 |
public static double toDouble(uint a)
|
|
|
782bf6 |
{ return (double)a/(double)uint.MaxValue*period + min; }
|
|
|
782bf6 |
|
|
|
782bf6 |
public struct Entry {
|
|
|
782bf6 |
public uint a0, a1;
|
|
|
782bf6 |
public Entry(uint a0, uint a1)
|
|
|
782bf6 |
{ this.a0 = a0; this.a1 = a1; }
|
|
|
782bf6 |
public bool isEmpty()
|
|
|
782bf6 |
{ return a0 == a1; }
|
|
|
782bf6 |
public Entry flipped()
|
|
|
782bf6 |
{ return new Entry(a1, a0); }
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public bool flip = false;
|
|
|
782bf6 |
public readonly List<uint> angles = new List<uint>();</uint></uint>
|
|
|
782bf6 |
|
|
|
782bf6 |
public AngleRange(bool fill = false)
|
|
|
782bf6 |
{ flip = fill; }
|
|
|
782bf6 |
|
|
|
782bf6 |
public bool isEmpty()
|
|
|
782bf6 |
{ return angles.Count == 0 && !flip; }
|
|
|
782bf6 |
public bool isFull()
|
|
|
782bf6 |
{ return angles.Count == 0 && flip; }
|
|
|
782bf6 |
|
|
|
782bf6 |
public void clear()
|
|
|
782bf6 |
{ angles.Clear(); flip = false; }
|
|
|
782bf6 |
public void fill()
|
|
|
782bf6 |
{ angles.Clear(); flip = true; }
|
|
|
782bf6 |
|
|
|
782bf6 |
private void doSet(uint a0, uint a1) {
|
|
|
782bf6 |
angles.Clear();
|
|
|
782bf6 |
if (a0 < a1) {
|
|
|
782bf6 |
flip = false;
|
|
|
782bf6 |
angles.Add(a0);
|
|
|
782bf6 |
angles.Add(a1);
|
|
|
782bf6 |
} else {
|
|
|
782bf6 |
flip = true;
|
|
|
782bf6 |
angles.Add(a1);
|
|
|
782bf6 |
angles.Add(a0);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void set(Entry e) {
|
|
|
782bf6 |
if (e.isEmpty()) { clear(); return; }
|
|
|
782bf6 |
doSet(e.a0, e.a1);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void set(AngleRange r, bool flip = false) {
|
|
|
782bf6 |
if (r == this) return;
|
|
|
782bf6 |
this.flip = (r.flip != flip);
|
|
|
782bf6 |
angles.Clear();
|
|
|
782bf6 |
angles.AddRange(r.angles);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public bool check() {
|
|
|
782bf6 |
if (angles.Count % 2 != 0)
|
|
|
782bf6 |
return false;
|
|
|
782bf6 |
for(int i = 1; i < angles.Count; ++i)
|
|
|
782bf6 |
if (angles[i-1] >= angles[i])
|
|
|
782bf6 |
return false;
|
|
|
782bf6 |
return true;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void invert()
|
|
|
782bf6 |
{ flip = !flip; }
|
|
|
782bf6 |
|
|
|
782bf6 |
private int find(uint a) {
|
|
|
782bf6 |
int i0 = 0, i1 = angles.Count - 1;
|
|
|
782bf6 |
if (a < angles[0]) return i1;
|
|
|
782bf6 |
if (angles[i1] <= a) return i1;
|
|
|
782bf6 |
while(true) {
|
|
|
782bf6 |
int i = (i1 + i0)/2;
|
|
|
782bf6 |
if (i == i0) break;
|
|
|
782bf6 |
if (angles[i] <= a) i0 = i; else i1 = i;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
return i0;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
private void remove(int p0, int p1) {
|
|
|
782bf6 |
if (p1 < p0) {
|
|
|
782bf6 |
angles.RemoveRange(p0, angles.Count - p0);
|
|
|
782bf6 |
angles.RemoveRange(0, p1 + 1);
|
|
|
782bf6 |
} else {
|
|
|
782bf6 |
angles.RemoveRange(p0, p1 - p0 + 1);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
private void insert(uint a) {
|
|
|
782bf6 |
int p = find(a);
|
|
|
782bf6 |
if (angles[p] == a) angles.RemoveAt(p); else
|
|
|
782bf6 |
if (a < angles[0]) angles.Insert(0, a); else
|
|
|
782bf6 |
angles.Insert(p+1, a);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
private int decrease(int i)
|
|
|
782bf6 |
{ return i == 0 ? angles.Count - 1: i - 1; }
|
|
|
782bf6 |
private int increase(int i)
|
|
|
782bf6 |
{ return (i + 1)%angles.Count; }
|
|
|
782bf6 |
|
|
|
782bf6 |
public void xor(Entry e) {
|
|
|
782bf6 |
if (e.isEmpty()) return;
|
|
|
782bf6 |
if (isEmpty()) { doSet(e.a0, e.a1); return; }
|
|
|
782bf6 |
if (isFull()) { doSet(e.a1, e.a0); return; }
|
|
|
782bf6 |
if (e.a1 < e.a0) flip = !flip;
|
|
|
782bf6 |
insert(e.a0);
|
|
|
782bf6 |
insert(e.a1);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void xor(AngleRange r) {
|
|
|
782bf6 |
if (r.isEmpty()) { return; }
|
|
|
782bf6 |
if (r.isFull()) { invert(); return; }
|
|
|
782bf6 |
if (isEmpty()) { set(r); return; }
|
|
|
782bf6 |
if (isFull()) { set(r, true); return; }
|
|
|
782bf6 |
flip = flip != r.flip;
|
|
|
782bf6 |
foreach(uint a in r.angles)
|
|
|
782bf6 |
insert(a);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
private bool doAdd(uint a0, uint a1) {
|
|
|
782bf6 |
int p0 = find(a0);
|
|
|
782bf6 |
int p1 = find(a1);
|
|
|
782bf6 |
if (p0 == p1) {
|
|
|
782bf6 |
bool v = (p0%2 != 0) == flip;
|
|
|
782bf6 |
if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) {
|
|
|
782bf6 |
if (v) { fill(); return true; }
|
|
|
782bf6 |
doSet(a0, a1);
|
|
|
782bf6 |
} else
|
|
|
782bf6 |
if (!v) {
|
|
|
782bf6 |
if (a1 < a0) flip = true;
|
|
|
782bf6 |
insert(a0);
|
|
|
782bf6 |
insert(a1);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
return false;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
bool v0 = (p0%2 != 0) == flip;
|
|
|
782bf6 |
bool v1 = (p1%2 != 0) == flip;
|
|
|
782bf6 |
remove(increase(p0), p1);
|
|
|
782bf6 |
if (!v0) insert(a0);
|
|
|
782bf6 |
if (!v1) insert(a1);
|
|
|
782bf6 |
if (angles.Count == 0) { flip = true; return true; }
|
|
|
782bf6 |
if (a1 < a0) flip = true;
|
|
|
782bf6 |
return false;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
private bool doSubtract(uint a0, uint a1) {
|
|
|
782bf6 |
int p0 = find(a0);
|
|
|
782bf6 |
int p1 = find(a1);
|
|
|
782bf6 |
if (p0 == p1) {
|
|
|
782bf6 |
bool v = (p0%2 != 0) == flip;
|
|
|
782bf6 |
if (angles[p0] != a0 && angles[p0] - a0 <= a1 - a0) {
|
|
|
782bf6 |
if (!v) { clear(); return true; }
|
|
|
782bf6 |
doSet(a1, a0);
|
|
|
782bf6 |
} else
|
|
|
782bf6 |
if (v) {
|
|
|
782bf6 |
if (a1 < a0) flip = false;
|
|
|
782bf6 |
insert(a0);
|
|
|
782bf6 |
insert(a1);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
return false;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
bool v0 = (p0%2 != 0) == flip;
|
|
|
782bf6 |
bool v1 = (p1%2 != 0) == flip;
|
|
|
782bf6 |
remove(increase(p0), p1);
|
|
|
782bf6 |
if (v0) insert(a0);
|
|
|
782bf6 |
if (v1) insert(a1);
|
|
|
782bf6 |
if (angles.Count == 0) { flip = false; return true; }
|
|
|
782bf6 |
if (a1 < a0) flip = false;
|
|
|
782bf6 |
return false;
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void add(Entry e) {
|
|
|
782bf6 |
if (!isFull() && !e.isEmpty())
|
|
|
782bf6 |
{ if (isEmpty()) doSet(e.a0, e.a1); else doAdd(e.a0, e.a1); }
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void subtract(Entry e) {
|
|
|
782bf6 |
if (!isEmpty() && !e.isEmpty())
|
|
|
782bf6 |
{ if (isFull()) doSet(e.a1, e.a0); else doSubtract(e.a0, e.a1); }
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void intersect(Entry e) {
|
|
|
782bf6 |
if (!isEmpty()) {
|
|
|
782bf6 |
if (e.isEmpty()) clear();
|
|
|
782bf6 |
else if (isFull()) doSet(e.a0, e.a1);
|
|
|
782bf6 |
else doSubtract(e.a1, e.a0);
|
|
|
782bf6 |
}
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void add(AngleRange r) {
|
|
|
782bf6 |
if (r == this || isFull() || r.isEmpty()) return;
|
|
|
782bf6 |
if (isEmpty()) { set(r); return; }
|
|
|
782bf6 |
if (r.isFull()) { fill(); return; }
|
|
|
782bf6 |
bool f = r.flip;
|
|
|
782bf6 |
uint prev = r.angles[r.angles.Count - 1];
|
|
|
782bf6 |
foreach(uint a in r.angles)
|
|
|
782bf6 |
if (f && doAdd(prev, a)) return;
|
|
|
782bf6 |
else { prev = a; f = !f; }
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void subtract(AngleRange r) {
|
|
|
782bf6 |
if (isEmpty() || r.isEmpty()) return;
|
|
|
782bf6 |
if (r == this || r.isFull()) { clear(); return; }
|
|
|
782bf6 |
if (isFull()) { set(r); invert(); return; }
|
|
|
782bf6 |
bool f = r.flip;
|
|
|
782bf6 |
uint prev = r.angles[r.angles.Count - 1];
|
|
|
782bf6 |
foreach(uint a in r.angles)
|
|
|
782bf6 |
if (f && doSubtract(prev, a)) return;
|
|
|
782bf6 |
else { prev = a; f = !f; }
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|
|
|
782bf6 |
public void intersect(AngleRange r) {
|
|
|
782bf6 |
if (r == this || isEmpty() || r.isFull()) return;
|
|
|
782bf6 |
if (r.isEmpty()) { clear(); return; }
|
|
|
782bf6 |
if (isFull()) { set(r); return; }
|
|
|
782bf6 |
bool f = !r.flip;
|
|
|
782bf6 |
uint prev = r.angles[r.angles.Count - 1];
|
|
|
782bf6 |
foreach(uint a in r.angles)
|
|
|
782bf6 |
if (f && doSubtract(prev, a)) return;
|
|
|
782bf6 |
else { prev = a; f = !f; }
|
|
|
782bf6 |
}
|
|
|
782bf6 |
}
|
|
|
782bf6 |
}
|
|
|
782bf6 |
|