|
 |
d33d2a |
using System;
|
|
|
d33d2a |
using System.Collections.Generic;
|
|
|
d33d2a |
using System.Linq;
|
|
|
d33d2a |
|
|
|
d33d2a |
namespace Contours {
|
|
|
d33d2a |
public enum IntersectionType {
|
|
|
d33d2a |
None,
|
|
|
d33d2a |
Cross,
|
|
|
d33d2a |
Identical,
|
|
|
d33d2a |
Inverted,
|
|
|
d33d2a |
Touch_a0,
|
|
|
d33d2a |
Touch_a1,
|
|
|
d33d2a |
Touch_b0,
|
|
|
d33d2a |
Touch_b1,
|
|
|
d33d2a |
Touch_a0_b0,
|
|
|
d33d2a |
Touch_a0_b1,
|
|
|
d33d2a |
Touch_a1_b0,
|
|
|
d33d2a |
Touch_a1_b1,
|
|
|
d33d2a |
Along_a0_b0_a1_b1,
|
|
|
d33d2a |
Along_a0_b0_b1_a1,
|
|
|
d33d2a |
Along_a0_b1_a1_b0,
|
|
|
d33d2a |
Along_a0_b1_b0_a1,
|
|
|
d33d2a |
Along_b0_a0_a1_b1,
|
|
|
d33d2a |
Along_b0_a0_b1_a1,
|
|
|
d33d2a |
Along_b1_a0_a1_b0,
|
|
|
d33d2a |
Along_b1_a0_b0_a1
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public class Circuit<parent, child=""> where Parent: class where Child: class {</parent,>
|
|
|
d33d2a |
public class Entry {
|
|
|
d33d2a |
readonly Child owner;
|
|
|
d33d2a |
Circuit<parent, child=""> circuit;</parent,>
|
|
|
d33d2a |
Entry previous;
|
|
|
d33d2a |
Entry next;
|
|
|
d33d2a |
|
|
|
d33d2a |
public Entry(Child owner) { this.owner = owner; }
|
|
|
d33d2a |
|
|
|
d33d2a |
public Child getOwner() { return owner; }
|
|
|
d33d2a |
public Circuit<parent, child=""> getCircuit() { return circuit; }</parent,>
|
|
|
d33d2a |
public Parent getParent() {
|
|
|
d33d2a |
Circuit<parent, child=""> circuit = getCircuit();</parent,>
|
|
|
d33d2a |
return circuit == null ? null : circuit.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Entry getPreviousEntry() { return previous; }
|
|
|
d33d2a |
public Entry getNextEntry() { return next; }
|
|
|
d33d2a |
|
|
|
d33d2a |
public Entry getPreviousEntryLinear() {
|
|
|
d33d2a |
Entry e = getPreviousEntry();
|
|
|
d33d2a |
return e == null || e == circuit.last ? null : e;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
public Entry getNextEntryLinear() {
|
|
|
d33d2a |
Entry e = getNextEntry();
|
|
|
d33d2a |
return e == null || e == circuit.first ? null : e;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Child getPrevious() {
|
|
|
d33d2a |
Entry e = getPreviousEntry();
|
|
|
d33d2a |
return e == null ? null : e.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
public Child getNext() {
|
|
|
d33d2a |
Entry e = getNextEntry();
|
|
|
d33d2a |
return e == null ? null : e.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Child getPreviousLinear() {
|
|
|
d33d2a |
Entry e = getPreviousEntryLinear();
|
|
|
d33d2a |
return e == null ? null : e.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
public Child getNextLinear() {
|
|
|
d33d2a |
Entry e = getNextEntryLinear();
|
|
|
d33d2a |
return e == null ? null : e.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void unlink() {
|
|
|
e5b120 |
if (previous != null) previous.next = next;
|
|
|
e5b120 |
if (next != null) next.previous = previous;
|
|
|
e5b120 |
|
|
|
e5b120 |
if (circuit != null) {
|
|
|
e5b120 |
if (circuit.first == this) {
|
|
|
e5b120 |
circuit.first = next != this ? next : null;
|
|
|
e5b120 |
circuit.last = previous != this ? previous : null;
|
|
|
d33d2a |
}
|
|
|
e5b120 |
--circuit.count;
|
|
|
e5b120 |
circuit = null;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
previous = null;
|
|
|
d33d2a |
next = null;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void insertBack(Circuit<parent, child=""> circuit) {</parent,>
|
|
|
d33d2a |
unlink();
|
|
|
d33d2a |
if (circuit != null) {
|
|
|
d33d2a |
if (circuit.empty()) {
|
|
|
d33d2a |
this.circuit = circuit;
|
|
|
d33d2a |
previous = next = this;
|
|
|
d33d2a |
circuit.first = circuit.last = this;
|
|
|
d33d2a |
++circuit.count;
|
|
|
d33d2a |
} else {
|
|
|
d33d2a |
insertAfterOf(circuit.getLastEntry());
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void insertFront(Circuit<parent, child=""> circuit) {</parent,>
|
|
|
d33d2a |
unlink();
|
|
|
d33d2a |
if (circuit != null) {
|
|
|
d33d2a |
if (circuit.empty()) {
|
|
|
d33d2a |
this.circuit = circuit;
|
|
|
d33d2a |
previous = next = this;
|
|
|
d33d2a |
circuit.first = circuit.last = this;
|
|
|
d33d2a |
++circuit.count;
|
|
|
d33d2a |
} else {
|
|
|
d33d2a |
insertBeforeOf(circuit.getFirstEntry());
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void insertAfterOf(Entry entry) {
|
|
|
e5b120 |
if (entry == this) return;
|
|
|
d33d2a |
unlink();
|
|
|
e5b120 |
if (entry == null || entry.getCircuit() == null) return;
|
|
|
e5b120 |
|
|
|
d33d2a |
previous = entry;
|
|
|
d33d2a |
next = entry.next;
|
|
|
d33d2a |
previous.next = this;
|
|
|
e5b120 |
if (next != null) next.previous = this;
|
|
|
e5b120 |
circuit = entry.getCircuit();
|
|
|
e5b120 |
|
|
|
e5b120 |
if (circuit != null) {
|
|
|
e5b120 |
if (circuit.getLastEntry() == entry)
|
|
|
e5b120 |
circuit.last = this;
|
|
|
e5b120 |
++circuit.count;
|
|
|
e5b120 |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void insertBeforeOf(Entry entry) {
|
|
|
e5b120 |
if (entry == this) return;
|
|
|
d33d2a |
unlink();
|
|
|
e5b120 |
if (entry == null || entry.getCircuit() == null) return;
|
|
|
e5b120 |
|
|
|
d33d2a |
previous = entry.previous;
|
|
|
d33d2a |
next = entry;
|
|
|
e5b120 |
if (previous != null) previous.next = this;
|
|
|
d33d2a |
next.previous = this;
|
|
|
e5b120 |
circuit = entry.getCircuit();
|
|
|
e5b120 |
|
|
|
e5b120 |
if (circuit != null) {
|
|
|
e5b120 |
if (circuit.getFirstEntry() == entry)
|
|
|
e5b120 |
circuit.first = this;
|
|
|
e5b120 |
++circuit.count;
|
|
|
e5b120 |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
9f4b34 |
public void swapWith(Entry other) {
|
|
|
e5b120 |
if (other == this || other == null) return;
|
|
|
e5b120 |
|
|
|
d33d2a |
Circuit<parent, child=""> otherCircuit = other.circuit;</parent,>
|
|
|
d33d2a |
Entry otherPrevious = other.previous;
|
|
|
d33d2a |
Entry otherNext = other.next;
|
|
|
d33d2a |
|
|
|
d33d2a |
other.circuit = circuit;
|
|
|
d33d2a |
other.previous = previous;
|
|
|
d33d2a |
other.next = next;
|
|
|
d33d2a |
|
|
|
d33d2a |
if (otherCircuit != null) {
|
|
|
d33d2a |
if (otherCircuit.first == other)
|
|
|
d33d2a |
otherCircuit.first = this;
|
|
|
d33d2a |
if (otherCircuit.last == other)
|
|
|
d33d2a |
otherCircuit.last = this;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
if (circuit != null) {
|
|
|
d33d2a |
if (circuit.first == this)
|
|
|
d33d2a |
circuit.first = other;
|
|
|
d33d2a |
if (circuit.last == this)
|
|
|
d33d2a |
circuit.last = other;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
circuit = otherCircuit;
|
|
|
d33d2a |
previous = otherPrevious;
|
|
|
d33d2a |
next = otherNext;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
readonly Parent owner;
|
|
|
d33d2a |
Entry first;
|
|
|
d33d2a |
Entry last;
|
|
|
d33d2a |
int count = 0;
|
|
|
d33d2a |
|
|
|
d33d2a |
public Circuit(Parent owner) { this.owner = owner; }
|
|
|
d33d2a |
|
|
|
d33d2a |
public Parent getOwner() { return owner; }
|
|
|
d33d2a |
public int getCount() { return count; }
|
|
|
d33d2a |
|
|
|
d33d2a |
public Entry getFirstEntry() { return first; }
|
|
|
d33d2a |
public Entry getLastEntry() { return last; }
|
|
|
d33d2a |
|
|
|
d33d2a |
public Child getFirst() {
|
|
|
d33d2a |
Entry e = getFirstEntry();
|
|
|
d33d2a |
return e == null ? null : e.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
public Child getLast() {
|
|
|
d33d2a |
Entry e = getLastEntry();
|
|
|
d33d2a |
return e == null ? null : e.getOwner();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public bool empty() { return getFirstEntry() == null; }
|
|
|
e5b120 |
|
|
|
e5b120 |
public void clear() {
|
|
|
e5b120 |
while(!empty()) getFirstEntry().unlink();
|
|
|
e5b120 |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public class Shape {
|
|
|
d33d2a |
public class Position {
|
|
|
d33d2a |
public int x = 0;
|
|
|
d33d2a |
public int y = 0;
|
|
|
d33d2a |
public readonly Circuit<shape, position="">.Entry shape;</shape,>
|
|
|
d33d2a |
public readonly Circuit<position, link=""> links;</position,>
|
|
|
d33d2a |
|
|
|
d33d2a |
public Position() {
|
|
|
d33d2a |
shape = new Circuit<shape, position="">.Entry(this);</shape,>
|
|
|
d33d2a |
links = new Circuit<position, link="">(this);</position,>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Position(int x, int y): this() { this.x = x; this.y = y; }
|
|
|
d33d2a |
|
|
|
d33d2a |
public VectorInt toVectorInt() { return new VectorInt(x, y); }
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public class Contour {
|
|
|
098941 |
public bool inverted = false;
|
|
|
098941 |
|
|
|
098941 |
public Contour parent;
|
|
|
098941 |
public List<contour> childs;</contour>
|
|
|
098941 |
|
|
|
d33d2a |
public readonly Circuit<shape, contour="">.Entry shape;</shape,>
|
|
|
d33d2a |
public readonly Circuit<contour, link=""> forward;</contour,>
|
|
|
d33d2a |
public readonly Circuit<contour, link=""> backward;</contour,>
|
|
|
d33d2a |
|
|
|
d33d2a |
public Contour() {
|
|
|
d33d2a |
shape = new Circuit<shape, contour="">.Entry(this);</shape,>
|
|
|
d33d2a |
forward = new Circuit<contour, link="">(this);</contour,>
|
|
|
d33d2a |
backward = new Circuit<contour, link="">(this);</contour,>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public class Link {
|
|
|
d33d2a |
public readonly Circuit<shape, link="">.Entry shape;</shape,>
|
|
|
d33d2a |
public readonly Circuit<position, link="">.Entry position;</position,>
|
|
|
d33d2a |
public readonly Circuit<contour, link="">.Entry contour;</contour,>
|
|
|
e5b120 |
|
|
|
e5b120 |
public bool forward = false;
|
|
|
e5b120 |
public Position target = null;
|
|
|
d33d2a |
|
|
|
d33d2a |
public Link() {
|
|
|
d33d2a |
shape = new Circuit<shape, link="">.Entry(this);</shape,>
|
|
|
d33d2a |
position = new Circuit<position, link="">.Entry(this);</position,>
|
|
|
d33d2a |
contour = new Circuit<contour, link="">.Entry(this);</contour,>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void unlink() {
|
|
|
d33d2a |
contour.unlink();
|
|
|
d33d2a |
position.unlink();
|
|
|
d33d2a |
shape.unlink();
|
|
|
e5b120 |
target = null;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public static Link create(Position position, Circuit<contour, link=""> contourCircuit) {</contour,>
|
|
|
d33d2a |
Link link = new Link();
|
|
|
d33d2a |
link.shape.insertBack(contourCircuit.getOwner().shape.getParent().links);
|
|
|
d33d2a |
link.position.insertBack(position.links);
|
|
|
d33d2a |
link.contour.insertBack(contourCircuit);
|
|
|
e5b120 |
link.forward = contourCircuit == contourCircuit.getOwner().forward;
|
|
|
d33d2a |
return link;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Link createSplitAfter(Position position) {
|
|
|
d33d2a |
Link link = new Link();
|
|
|
e5b120 |
link.forward = forward;
|
|
|
d33d2a |
link.shape.insertBack(shape.getParent().links);
|
|
|
d33d2a |
link.position.insertBack(position.links);
|
|
|
d33d2a |
link.contour.insertAfterOf(contour);
|
|
|
d33d2a |
return link;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Link createSplitAfter(Circuit<position, link="">.Entry position) {</position,>
|
|
|
d33d2a |
Link link = new Link();
|
|
|
e5b120 |
link.forward = forward;
|
|
|
d33d2a |
link.shape.insertBack(shape.getParent().links);
|
|
|
d33d2a |
link.position.insertAfterOf(position);
|
|
|
d33d2a |
link.contour.insertAfterOf(contour);
|
|
|
d33d2a |
return link;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public Circuit<shape, position=""> positions;</shape,>
|
|
|
d33d2a |
public Circuit<shape, link=""> links;</shape,>
|
|
|
d33d2a |
public Circuit<shape, contour=""> contours;</shape,>
|
|
|
098941 |
public List<contour> rootContours;</contour>
|
|
|
d33d2a |
|
|
|
d33d2a |
public void addContours(ContourInt contours) {
|
|
|
d33d2a |
foreach(List<vectorint> contour in contours.contours)</vectorint>
|
|
|
d33d2a |
addContour(contour);
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public void addContour(ICollection<vectorint> points) {</vectorint>
|
|
|
d33d2a |
if (points.Count < 3)
|
|
|
d33d2a |
return;
|
|
|
d33d2a |
|
|
|
d33d2a |
Contour contour = new Contour();
|
|
|
d33d2a |
contour.shape.insertBack(contours);
|
|
|
d33d2a |
foreach(VectorInt point in points) {
|
|
|
d33d2a |
Position position = new Position(point.x, point.y);
|
|
|
d33d2a |
position.shape.insertBack(positions);
|
|
|
d33d2a |
Link.create(position, contour.forward);
|
|
|
d33d2a |
Link.create(position, contour.backward);
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public static int compare(VectorInt a0, VectorInt a1, VectorInt base0, VectorInt base1) {
|
|
|
d33d2a |
if (base0.x < base1.x && a0.x < a1.x) return -1;
|
|
|
d33d2a |
if (base0.x < base1.x && a1.x < a0.x) return 1;
|
|
|
d33d2a |
if (base1.x < base0.x && a0.x < a1.x) return 1;
|
|
|
d33d2a |
if (base1.x < base0.x && a1.x < a0.x) return -1;
|
|
|
d33d2a |
if (base0.y < base1.x && a0.y < a1.x) return -1;
|
|
|
d33d2a |
if (base0.y < base1.x && a1.y < a0.x) return 1;
|
|
|
d33d2a |
if (base1.y < base0.x && a0.y < a1.x) return 1;
|
|
|
d33d2a |
if (base1.y < base0.x && a1.y < a0.x) return -1;
|
|
|
d33d2a |
return 0;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
public static IntersectionType findIntersection(VectorInt a0, VectorInt a1, VectorInt b0, VectorInt b1, out VectorInt c) {
|
|
|
d33d2a |
c = new VectorInt();
|
|
|
d33d2a |
VectorInt da = new VectorInt(a1.x - a0.x, a1.y - a0.y);
|
|
|
d33d2a |
VectorInt db = new VectorInt(b1.x - b0.x, b1.y - b0.y);
|
|
|
d33d2a |
|
|
|
d33d2a |
if (a0.x == b0.x && a0.y == b0.y && a1.x == b1.x && a1.y == b1.y)
|
|
|
d33d2a |
return IntersectionType.Identical;
|
|
|
d33d2a |
|
|
|
d33d2a |
if (a0.x == b1.x && a0.y == b1.y && a1.x == b0.x && a1.y == b0.y)
|
|
|
d33d2a |
return IntersectionType.Inverted;
|
|
|
d33d2a |
|
|
|
d33d2a |
long divider = (long)da.x*(long)db.y - (long)db.x*(long)da.y;
|
|
|
d33d2a |
if (divider == 0) {
|
|
|
d33d2a |
if ((long)da.x*(long)(b0.y - a0.y) != (long)da.y*(long)(b0.x - a0.x))
|
|
|
d33d2a |
return IntersectionType.None;
|
|
|
d33d2a |
|
|
|
d33d2a |
int a0b0 = compare(a0, b0, a0, a1);
|
|
|
d33d2a |
int a0b1 = compare(a0, b1, a0, a1);
|
|
|
d33d2a |
int a1b0 = compare(a1, b0, a0, a1);
|
|
|
d33d2a |
int a1b1 = compare(a1, b1, a0, a1);
|
|
|
d33d2a |
int b0b1 = compare(b0, b1, a0, a1);
|
|
|
d33d2a |
int b0a0 = -a0b0;
|
|
|
d33d2a |
int b0a1 = -a1b0;
|
|
|
d33d2a |
int b1a0 = -a0b1;
|
|
|
d33d2a |
int b1a1 = -a1b1;
|
|
|
d33d2a |
int b1b0 = -b0b1;
|
|
|
d33d2a |
|
|
|
d33d2a |
// a0a1b0b1
|
|
|
d33d2a |
if (a1b0 == 0 && b0b1 < 0)
|
|
|
d33d2a |
return IntersectionType.Touch_a1_b0;
|
|
|
d33d2a |
// a0a1b1b0
|
|
|
d33d2a |
if (a1b1 == 0 && b1b0 < 0)
|
|
|
d33d2a |
return IntersectionType.Touch_a1_b1;
|
|
|
d33d2a |
// b0b1a0a1
|
|
|
d33d2a |
if (b0b1 < 0 && b1a0 == 0)
|
|
|
d33d2a |
return IntersectionType.Touch_a0_b1;
|
|
|
d33d2a |
// b1b0a0a1
|
|
|
d33d2a |
if (b1b0 < 0 && b0a0 == 0)
|
|
|
d33d2a |
return IntersectionType.Touch_a0_b0;
|
|
|
d33d2a |
|
|
|
d33d2a |
if (a0b0 <= 0 && b0a1 <= 0 && a1b1 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_a0_b0_a1_b1;
|
|
|
d33d2a |
if (a0b0 <= 0 && b0b1 <= 0 && b1a1 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_a0_b0_b1_a1;
|
|
|
d33d2a |
if (a0b1 <= 0 && b1a1 <= 0 && a1b0 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_a0_b1_a1_b0;
|
|
|
d33d2a |
if (a0b1 <= 0 && b1b0 <= 0 && b0a1 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_a0_b1_b0_a1;
|
|
|
d33d2a |
if (b0a0 <= 0 && /* a0a1 */ a1b1 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_b0_a0_a1_b1;
|
|
|
d33d2a |
if (b0a0 <= 0 && a0b1 <= 0 && b1a1 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_b0_a0_b1_a1;
|
|
|
d33d2a |
if (b1a0 <= 0 && /* a0a1 */ a1b0 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_b1_a0_a1_b0;
|
|
|
d33d2a |
if (b1a0 <= 0 && a0b0 <= 0 && b0a1 <= 0)
|
|
|
d33d2a |
return IntersectionType.Along_b1_a0_b0_a1;
|
|
|
d33d2a |
|
|
|
d33d2a |
return IntersectionType.None;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
if (a0.x == b0.x && a0.y == b0.y)
|
|
|
d33d2a |
return IntersectionType.Touch_a0_b0;
|
|
|
d33d2a |
if (a0.x == b1.x && a0.y == b1.y)
|
|
|
d33d2a |
return IntersectionType.Touch_a0_b1;
|
|
|
d33d2a |
if (a1.x == b0.x && a1.y == b0.y)
|
|
|
d33d2a |
return IntersectionType.Touch_a1_b0;
|
|
|
d33d2a |
if (a1.x == b1.x && a1.y == b1.y)
|
|
|
d33d2a |
return IntersectionType.Touch_a1_b1;
|
|
|
d33d2a |
|
|
|
d33d2a |
long numeratorX = (long)da.x*((long)b1.y*(long)b0.x - (long)b0.y*(long)b1.x)
|
|
|
d33d2a |
- (long)db.x*((long)a1.y*(long)a0.x - (long)a0.y*(long)a1.x);
|
|
|
d33d2a |
long numeratorY = (long)db.y*((long)a1.x*(long)a0.y - (long)a0.x*(long)a1.y)
|
|
|
d33d2a |
- (long)da.y*((long)b1.x*(long)b0.y - (long)b0.x*(long)b1.y);
|
|
|
d33d2a |
VectorInt p = new VectorInt((int)(numeratorX/divider), (int)(numeratorY/divider));
|
|
|
d33d2a |
if (compare(p, a0, a0, a1) < 0 || compare(p, a1, a0, a1) > 0)
|
|
|
d33d2a |
return IntersectionType.None;
|
|
|
d33d2a |
|
|
|
d33d2a |
if (p.x == a0.x && p.y == a0.y)
|
|
|
d33d2a |
return IntersectionType.Touch_a0;
|
|
|
d33d2a |
if (p.x == a1.x && p.y == a1.y)
|
|
|
d33d2a |
return IntersectionType.Touch_a1;
|
|
|
d33d2a |
if (p.x == b0.x && p.y == b0.y)
|
|
|
d33d2a |
return IntersectionType.Touch_b0;
|
|
|
d33d2a |
if (p.x == b1.x && p.y == b1.y)
|
|
|
d33d2a |
return IntersectionType.Touch_b1;
|
|
|
d33d2a |
|
|
|
d33d2a |
c = p;
|
|
|
d33d2a |
return IntersectionType.Cross;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
098941 |
public bool removeEmptyContours() {
|
|
|
098941 |
bool removed = false;
|
|
|
098941 |
|
|
|
d33d2a |
bool retry = true;
|
|
|
d33d2a |
while(retry) {
|
|
|
d33d2a |
retry = false;
|
|
|
9f4b34 |
for(Contour contour = contours.getFirst(); !retry && contour != null; contour = contour.shape.getNextLinear()) {
|
|
|
d33d2a |
if (contour.forward.getCount() < 3 || contour.backward.getCount() < 3) {
|
|
|
d33d2a |
while(contour.forward.getFirst() != null)
|
|
|
d33d2a |
contour.forward.getFirst().unlink();
|
|
|
d33d2a |
while(contour.backward.getFirst() != null)
|
|
|
d33d2a |
contour.backward.getFirst().unlink();
|
|
|
d33d2a |
contour.shape.unlink();
|
|
|
d33d2a |
retry = true;
|
|
|
098941 |
removed = true;
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
if (retry) continue;
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
public void findIntersections() {
|
|
|
098941 |
bool retry = true;
|
|
|
098941 |
while(retry) {
|
|
|
098941 |
retry = false;
|
|
|
098941 |
|
|
|
098941 |
retry = removeEmptyContours();
|
|
|
098941 |
if (retry) continue;
|
|
|
d33d2a |
|
|
|
d33d2a |
// remove empty positions
|
|
|
9f4b34 |
for(Position position = positions.getFirst(); !retry && position != null; position = position.shape.getNextLinear()) {
|
|
|
d33d2a |
if (position.links.empty()) {
|
|
|
d33d2a |
position.shape.unlink();
|
|
|
d33d2a |
retry = true;
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
if (retry) continue;
|
|
|
d33d2a |
|
|
|
d33d2a |
// merge positions
|
|
|
9f4b34 |
for(Position positionA = positions.getFirst(); !retry && positionA != null; positionA = positionA.shape.getNextLinear()) {
|
|
|
9f4b34 |
for(Position positionB = positionA.shape.getNextLinear(); !retry && positionB != null; positionB = positionB.shape.getNextLinear()) {
|
|
|
d33d2a |
if (positionA.x == positionB.x && positionA.y == positionB.y) {
|
|
|
d33d2a |
while(positionB.links.getFirst() != null)
|
|
|
d33d2a |
positionB.links.getFirst().position.insertBack(positionA.links);
|
|
|
d33d2a |
positionB.shape.unlink();
|
|
|
d33d2a |
retry = true;
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
if (retry) continue;
|
|
|
d33d2a |
|
|
|
d33d2a |
// remove zero-length links
|
|
|
9f4b34 |
for(Link linkA0 = links.getFirst(); !retry && linkA0 != null; linkA0 = linkA0.shape.getNextLinear()) {
|
|
|
d33d2a |
Link linkA1 = linkA0.contour.getNext();
|
|
|
d33d2a |
if (linkA0.position.getParent() == linkA1.position.getParent()) {
|
|
|
d33d2a |
linkA1.unlink();
|
|
|
d33d2a |
retry = true;
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
if (retry) continue;
|
|
|
d33d2a |
|
|
|
d33d2a |
// check intersections
|
|
|
9f4b34 |
for(Link linkA0 = links.getFirst(); !retry && linkA0 != null; linkA0 = linkA0.shape.getNextLinear()) {
|
|
|
d33d2a |
Link linkA1 = linkA0.contour.getNext();
|
|
|
9f4b34 |
for(Link linkB0 = links.getFirst(); !retry && linkB0 != null; linkB0 = linkB0.shape.getNextLinear()) {
|
|
|
d33d2a |
Link linkB1 = linkB0.contour.getNext();
|
|
|
d33d2a |
VectorInt cross = new VectorInt(0, 0);
|
|
|
d33d2a |
Position position;
|
|
|
d33d2a |
retry = true;
|
|
|
d33d2a |
switch( findIntersection( linkA0.position.getParent().toVectorInt(),
|
|
|
d33d2a |
linkA1.position.getParent().toVectorInt(),
|
|
|
d33d2a |
linkB0.position.getParent().toVectorInt(),
|
|
|
d33d2a |
linkB1.position.getParent().toVectorInt(),
|
|
|
d33d2a |
out cross ))
|
|
|
d33d2a |
{
|
|
|
d33d2a |
case IntersectionType.Cross:
|
|
|
d33d2a |
position = new Position(cross.x, cross.y);
|
|
|
d33d2a |
position.shape.insertBack(positions);
|
|
|
d33d2a |
linkA0.createSplitAfter(position);
|
|
|
d33d2a |
linkB0.createSplitAfter(position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Touch_a0:
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA0.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Touch_a1:
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA1.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Touch_b0:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB0.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Touch_b1:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB1.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_a0_b0_a1_b1:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB0.position);
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA1.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_a0_b0_b1_a1:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB0.position)
|
|
|
d33d2a |
.createSplitAfter(linkB1.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_a0_b1_a1_b0:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB1.position);
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA1.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_a0_b1_b0_a1:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB1.position)
|
|
|
d33d2a |
.createSplitAfter(linkB0.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_b0_a0_a1_b1:
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA0.position)
|
|
|
d33d2a |
.createSplitAfter(linkA1.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_b0_a0_b1_a1:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB1.position);
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA0.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_b1_a0_a1_b0:
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA1.position)
|
|
|
d33d2a |
.createSplitAfter(linkA0.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
case IntersectionType.Along_b1_a0_b0_a1:
|
|
|
d33d2a |
linkA0.createSplitAfter(linkB0.position);
|
|
|
d33d2a |
linkB0.createSplitAfter(linkA0.position);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
default:
|
|
|
d33d2a |
retry = false;
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
if (retry) continue;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
e5b120 |
void unlinkContoursChains() {
|
|
|
e5b120 |
while(!contours.empty()) {
|
|
|
e5b120 |
Contour contour = contours.getFirst();
|
|
|
e5b120 |
while(!contour.forward.empty()) {
|
|
|
e5b120 |
Link link = contour.forward.getFirst();
|
|
|
e5b120 |
link.target = link.contour.getNext().position.getParent();
|
|
|
e5b120 |
link.contour.unlink();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
while(!contour.backward.empty()) {
|
|
|
e5b120 |
Link link = contour.backward.getFirst();
|
|
|
e5b120 |
link.target = link.contour.getNext().position.getParent();
|
|
|
e5b120 |
link.contour.unlink();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
contour.shape.unlink();
|
|
|
098941 |
contour.childs.Clear();
|
|
|
098941 |
contour.parent = null;
|
|
|
e5b120 |
}
|
|
|
098941 |
rootContours.Clear();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
9f4b34 |
static bool compareAngle(VectorInt a, VectorInt b, VectorInt c) {
|
|
|
9f4b34 |
int d = a.x*c.y - a.y*c.x;
|
|
|
9f4b34 |
// angle AC < 180 deg
|
|
|
9f4b34 |
if (d > 0)
|
|
|
9f4b34 |
return a.x*b.y >= a.y*b.x && c.x*b.y <= c.y*b.x;
|
|
|
9f4b34 |
// angle AC > 180 deg
|
|
|
9f4b34 |
if (d < 0)
|
|
|
9f4b34 |
return a.x*b.y >= a.y*b.x || c.x*b.y <= c.y*b.x;
|
|
|
9f4b34 |
// angle AC == 180 deg
|
|
|
9f4b34 |
if ((a.x >= 0) != (c.x >= 0) || (a.y >= 0) != (c.y >= 0))
|
|
|
9f4b34 |
return a.x*b.y >= a.y*b.x;
|
|
|
9f4b34 |
// angle AC == 0 deg
|
|
|
9f4b34 |
return true;
|
|
|
9f4b34 |
}
|
|
|
9f4b34 |
|
|
|
9f4b34 |
static bool compareAngle(VectorInt center, VectorInt a, VectorInt b, VectorInt c) {
|
|
|
9f4b34 |
return compareAngle( new VectorInt(a.x - center.x, a.y - center.y),
|
|
|
9f4b34 |
new VectorInt(b.x - center.x, b.y - center.y),
|
|
|
9f4b34 |
new VectorInt(c.x - center.x, c.y - center.y) );
|
|
|
9f4b34 |
}
|
|
|
9f4b34 |
|
|
|
9f4b34 |
void sortLinksAtPosition(Position position) {
|
|
|
9f4b34 |
if (position.links.getCount() < 3) return;
|
|
|
9f4b34 |
Link first = position.links.getFirst();
|
|
|
9f4b34 |
Link linkA = first;
|
|
|
9f4b34 |
while (true) {
|
|
|
9f4b34 |
Link linkB = linkA.position.getNext();
|
|
|
9f4b34 |
Link linkC = linkB.position.getNext();
|
|
|
9f4b34 |
if ( !compareAngle(
|
|
|
9f4b34 |
position.toVectorInt(),
|
|
|
e5b120 |
linkA.target.toVectorInt(),
|
|
|
e5b120 |
linkB.target.toVectorInt(),
|
|
|
e5b120 |
linkC.target.toVectorInt() ))
|
|
|
9f4b34 |
{
|
|
|
9f4b34 |
linkB.position.swapWith(linkC.position);
|
|
|
9f4b34 |
first = linkA = linkC;
|
|
|
9f4b34 |
continue;
|
|
|
9f4b34 |
}
|
|
|
9f4b34 |
linkA = linkB;
|
|
|
9f4b34 |
if (linkA == first) break;
|
|
|
9f4b34 |
};
|
|
|
9f4b34 |
}
|
|
|
9f4b34 |
|
|
|
d33d2a |
void sortLinksAtPositions() {
|
|
|
9f4b34 |
for(Position position = positions.getFirst(); position != null; position = position.shape.getNextLinear())
|
|
|
9f4b34 |
sortLinksAtPosition(position);
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
e5b120 |
void removeLinkFromPosition(Link link) {
|
|
|
e5b120 |
Position position = link.position.getParent();
|
|
|
e5b120 |
Link nextToRemove = null;
|
|
|
e5b120 |
|
|
|
e5b120 |
// remove back link
|
|
|
e5b120 |
if (link.target != null) {
|
|
|
e5b120 |
Link backLink = link.target.links.getFirst();
|
|
|
e5b120 |
while (backLink != null) {
|
|
|
e5b120 |
Link l = backLink;
|
|
|
e5b120 |
backLink = backLink.position.getNextLinear();
|
|
|
e5b120 |
if ( l.forward != link.forward
|
|
|
e5b120 |
&& l.contour.getNext() != null
|
|
|
e5b120 |
&& l.contour.getNext().position.getParent() == position )
|
|
|
e5b120 |
{
|
|
|
e5b120 |
l.unlink();
|
|
|
e5b120 |
break;
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
if (link.target.links.getCount() == 1)
|
|
|
e5b120 |
nextToRemove = link.target.links.getFirst();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
// remove
|
|
|
e5b120 |
link.unlink();
|
|
|
e5b120 |
|
|
|
e5b120 |
// remove next
|
|
|
e5b120 |
if (nextToRemove != null)
|
|
|
e5b120 |
removeLinkFromPosition(nextToRemove);
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
void removeDuplicateLinksFromPosition(Position position) {
|
|
|
e5b120 |
for(Link linkA = position.links.getFirst(); linkA != null; linkA = linkA.position.getNextLinear()) {
|
|
|
e5b120 |
Position otherPosition = linkA.target;
|
|
|
e5b120 |
|
|
|
e5b120 |
// count forward and backward links
|
|
|
e5b120 |
int count = 0;
|
|
|
e5b120 |
Link forwardLink = null;
|
|
|
e5b120 |
Link backwardLink = null;
|
|
|
e5b120 |
Link linkB = linkA;
|
|
|
e5b120 |
do {
|
|
|
e5b120 |
if (linkB.target == otherPosition) {
|
|
|
e5b120 |
if (linkB.forward) { forwardLink = linkB; ++count; }
|
|
|
e5b120 |
else { backwardLink = linkB; --count; }
|
|
|
e5b120 |
}
|
|
|
e5b120 |
linkB.position.getNext();
|
|
|
e5b120 |
} while(linkB != linkA);
|
|
|
e5b120 |
|
|
|
e5b120 |
// remove extra links
|
|
|
e5b120 |
Link linkToSave = count > 0 ? forwardLink
|
|
|
e5b120 |
: count < 0 ? backwardLink
|
|
|
e5b120 |
: null;
|
|
|
e5b120 |
linkB = position.links.getFirst();
|
|
|
e5b120 |
while(linkB != null) {
|
|
|
e5b120 |
if (linkB.target == otherPosition && linkB != linkToSave) {
|
|
|
e5b120 |
removeLinkFromPosition(linkA);
|
|
|
e5b120 |
// reset linkA
|
|
|
e5b120 |
linkB = linkA = position.links.getFirst();
|
|
|
e5b120 |
} else {
|
|
|
e5b120 |
linkB = linkB.position.getNextLinear();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
void removeInvisibleContoursFromPosition(Position position) {
|
|
|
e5b120 |
if (position.links.getCount() < 3) return;
|
|
|
e5b120 |
Link first = position.links.getFirst();
|
|
|
e5b120 |
Link link = first.position.getNext();
|
|
|
e5b120 |
while(link != first) {
|
|
|
e5b120 |
bool previous = link.position.getPrevious().forward;
|
|
|
e5b120 |
bool current = link.forward;
|
|
|
e5b120 |
bool next = link.position.getNext().forward;
|
|
|
e5b120 |
if ( ( previous && current && !next)
|
|
|
e5b120 |
|| (!previous && !current && next) )
|
|
|
e5b120 |
{
|
|
|
e5b120 |
// remove link
|
|
|
e5b120 |
removeLinkFromPosition(link);
|
|
|
e5b120 |
first = position.links.getFirst();
|
|
|
e5b120 |
link = first.position.getNext();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
};
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
098941 |
void removeEmptyPositions() {
|
|
|
e5b120 |
for(Position position = positions.getFirst(); position != null;) {
|
|
|
e5b120 |
if (position.links.empty()) {
|
|
|
e5b120 |
Position p = position;
|
|
|
e5b120 |
position = position.shape.getNextLinear();
|
|
|
e5b120 |
p.shape.unlink();
|
|
|
e5b120 |
} else {
|
|
|
e5b120 |
position = position.shape.getNextLinear();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
098941 |
void optimizePositions() {
|
|
|
098941 |
// remove extra links
|
|
|
098941 |
for(Position position = positions.getFirst(); position != null; position = position.shape.getNextLinear()) {
|
|
|
098941 |
removeDuplicateLinksFromPosition(position);
|
|
|
098941 |
removeInvisibleContoursFromPosition(position);
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
e5b120 |
void traceContours() {
|
|
|
e5b120 |
for(Link linkA = links.getFirst(); linkA != null; linkA = linkA.shape.getNext()) {
|
|
|
e5b120 |
if (linkA.forward && linkA.contour.getParent() == null) {
|
|
|
e5b120 |
Contour contour = new Contour();
|
|
|
e5b120 |
contour.shape.insertBack(contours);
|
|
|
098941 |
|
|
|
e5b120 |
Link forwardLink = linkA;
|
|
|
e5b120 |
Link backwardLink = null;
|
|
|
098941 |
|
|
|
098941 |
do {
|
|
|
098941 |
// find pair
|
|
|
098941 |
for(Link l = linkA.target.links.getFirst(); l != null; l = l.position.getNext())
|
|
|
098941 |
if (l.target == linkA.position.getParent())
|
|
|
098941 |
{ backwardLink = l; break; }
|
|
|
098941 |
if (backwardLink == null)
|
|
|
098941 |
throw new Exception();
|
|
|
098941 |
|
|
|
098941 |
forwardLink.contour.insertBack(contour.forward);
|
|
|
098941 |
backwardLink.contour.insertBack(contour.backwardLink);
|
|
|
098941 |
|
|
|
098941 |
forwardLink = backwardLink.position.getNext();
|
|
|
098941 |
if ( !forwardLink.forward
|
|
|
098941 |
|| forwardLink == backwardLink
|
|
|
098941 |
|| forwardLink.contour.getParent() != null )
|
|
|
098941 |
throw new Exception();
|
|
|
098941 |
} while (forwardLink != linkA);
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
void removeFreeLinks() {
|
|
|
098941 |
for(Link linkA = links.getFirst(); linkA != null; linkA = linkA.shape.getNext())
|
|
|
098941 |
if (linkA.contour.getParent() == null)
|
|
|
098941 |
throw Exception();
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
void makeContourRay(Contour contour, bool invert, out VectorInt p0, out VectorInt p1) {
|
|
|
098941 |
Link first = contour.forward.getFirst();
|
|
|
098941 |
VectorInt previousPosition = first.contour.getPrevious().position.getParent().toVectorInt();
|
|
|
098941 |
VectorInt currentPosition = first.position.getParent().toVectorInt();
|
|
|
098941 |
VectorInt nextPosition = first.contour.getNext().position.getParent().toVectorInt();
|
|
|
098941 |
VectorInt direction = new VectorInt(
|
|
|
098941 |
previousPosition.y - nextPosition.y,
|
|
|
098941 |
nextPosition.x - previousPosition.x );
|
|
|
098941 |
|
|
|
098941 |
if (invert) { direction.x = -direction.x; direction.y = -direction.y; }
|
|
|
098941 |
|
|
|
098941 |
int amplifierX =
|
|
|
098941 |
direction.x > 0 ? (ContourInt.MaxValue - currentPosition.x)/direction.x + 1
|
|
|
098941 |
: direction.x < 0 ? (ContourInt.MaxValue + currentPosition.x)/(-direction.x) + 1
|
|
|
098941 |
: int.MaxValue;
|
|
|
098941 |
int amplifierY =
|
|
|
098941 |
direction.y > 0 ? (ContourInt.MaxValue - currentPosition.y)/direction.y + 1
|
|
|
098941 |
: direction.y < 0 ? (ContourInt.MaxValue + currentPosition.y)/(-direction.y) + 1
|
|
|
098941 |
: int.MaxValue;
|
|
|
098941 |
int amplifier = Math.Min(amplifierX, amplifierY);
|
|
|
098941 |
VectorInt farPosition = new VectorInt(
|
|
|
098941 |
currentPosition.x + direction.x*amplifier,
|
|
|
098941 |
currentPosition.y + direction.y*amplifier );
|
|
|
e5b120 |
|
|
|
098941 |
p0 = currentPosition;
|
|
|
098941 |
p1 = farPosition;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
int countContourIntersections(Contour contour, VectorInt p0, VectorInt p1) {
|
|
|
098941 |
int count = 0;
|
|
|
098941 |
for(Link link = contour.forward.getFirst(); link != null; link = link.contour.getNextLinear()) {
|
|
|
098941 |
VectorInt pp0 = link.position.getParent().toVectorInt();
|
|
|
098941 |
VectorInt pp1 = link.contour.getNext().position.getParent().toVectorInt();
|
|
|
098941 |
long d = (long)(p0.y - p1.y)*(long)(pp1.x - pp0.x)
|
|
|
098941 |
+ (long)(p1.x - p0.x)*(long)(pp1.y - pp0.y);
|
|
|
098941 |
d = Math.Sign(d);
|
|
|
098941 |
VectorInt c;
|
|
|
098941 |
switch(findIntersection(p0, p1, pp0, pp1, out c)) {
|
|
|
098941 |
case IntersectionType.Cross:
|
|
|
098941 |
count += 2*d;
|
|
|
098941 |
break;
|
|
|
098941 |
case IntersectionType.Touch_b0:
|
|
|
098941 |
count += d;
|
|
|
098941 |
break;
|
|
|
098941 |
case IntersectionType.Touch_b1:
|
|
|
098941 |
count -= d;
|
|
|
098941 |
break;
|
|
|
098941 |
default:
|
|
|
098941 |
break;
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
098941 |
return count;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
bool isContourInverted(Contour contour) {
|
|
|
098941 |
VectorInt p0, p1;
|
|
|
098941 |
makeContourRay(contour, false, out p0, out p1);
|
|
|
098941 |
return countContourIntersections(contour, p0, p1) == 0;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
bool isContourInside(Contour inner, Contour outer) {
|
|
|
098941 |
VectorInt p0, p1;
|
|
|
098941 |
makeContourRay(inner, inner.inverted, out p0, out p1);
|
|
|
098941 |
return countContourIntersections(outer, p0, p1) != 0;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
Contour findParent(Contour contour, Dictionary<contour, bool="" dictionary<contour,=""> > parents) {</contour,>
|
|
|
098941 |
if (!parents.ContainsKey(contour)) return null;
|
|
|
098941 |
if (parents[contour].Count == 1) return parents[contour].Keys.First;
|
|
|
098941 |
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
void sortChilds(Contour contour, Contour parent) {
|
|
|
098941 |
// set parent
|
|
|
098941 |
contour.parent = parent;
|
|
|
098941 |
|
|
|
098941 |
// remove sub-childs from parent list
|
|
|
098941 |
if (parent != null)
|
|
|
098941 |
foreach(Contour c in contour.childs)
|
|
|
098941 |
parent.childs.Remove(c);
|
|
|
098941 |
|
|
|
098941 |
// sub-calls
|
|
|
098941 |
foreach(Contour c in contour.childs)
|
|
|
098941 |
sortChilds(c, contour);
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
void sortContours() {
|
|
|
098941 |
// calculate directions of contours
|
|
|
098941 |
for(Contour contourA = contours.getFirst(); contourA != null; contourA = contourA.shape.getNext()) {
|
|
|
098941 |
contourA.inverted = isContourInverted(contourA);
|
|
|
098941 |
rootContours.Add(contourA);
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
// find childs
|
|
|
098941 |
for(Contour contourA = contours.getFirst(); contourA != null; contourA = contourA.shape.getNext()) {
|
|
|
098941 |
bool isRoot = true;
|
|
|
098941 |
for(Contour contourB = contourA.shape.getNextLinear(); contourB != null; contourB = contourB.shape.getNext())
|
|
|
098941 |
if (isContourInside(contourA, contourB)) {
|
|
|
098941 |
contourB.childs.Add(contourA);
|
|
|
098941 |
rootContours.Remove(contourA);
|
|
|
098941 |
} else
|
|
|
098941 |
if (isContourInside(contourA, contourB)) {
|
|
|
098941 |
contourA.childs.Add(contourB);
|
|
|
098941 |
rootContours.Remove(contourB);
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
// sort childs
|
|
|
098941 |
foreach(Contour c in rootContours)
|
|
|
098941 |
sortChilds(c, null);
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
void removeInvisibleContours() {
|
|
|
e5b120 |
// TODO:
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
void optimizeContours() {
|
|
|
e5b120 |
findIntersections();
|
|
|
e5b120 |
unlinkContoursChains();
|
|
|
e5b120 |
sortLinksAtPositions();
|
|
|
e5b120 |
optimizePositions();
|
|
|
e5b120 |
traceContours();
|
|
|
098941 |
removeEmptyContours();
|
|
|
e5b120 |
removeInvisibleContours();
|
|
|
098941 |
removeEmptyPositions();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|