|
 |
d33d2a |
using System;
|
|
|
d33d2a |
using System.Collections.Generic;
|
|
|
d33d2a |
using System.Linq;
|
|
|
f6cc12 |
using System.Drawing;
|
|
|
d33d2a |
|
|
|
d33d2a |
namespace Contours {
|
|
|
d33d2a |
public class Shape {
|
|
|
7c6265 |
class Exception: System.Exception { }
|
|
|
7c6265 |
|
|
|
f6cc12 |
class Position {
|
|
|
f6cc12 |
public Point point;
|
|
|
d33d2a |
public readonly Circuit<position, link=""> links;</position,>
|
|
|
d33d2a |
|
|
|
d33d2a |
public Position() {
|
|
|
d33d2a |
links = new Circuit<position, link="">(this);</position,>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
public Position(Point point): this() { this.point = point; }
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
class Contour {
|
|
|
098941 |
public bool inverted = false;
|
|
|
098941 |
|
|
|
098941 |
public Contour parent;
|
|
|
bb5d1a |
public readonly List<contour> childs = new List<contour>();</contour></contour>
|
|
|
098941 |
|
|
|
d33d2a |
public readonly Circuit<contour, link=""> forward;</contour,>
|
|
|
d33d2a |
public readonly Circuit<contour, link=""> backward;</contour,>
|
|
|
d33d2a |
|
|
|
d33d2a |
public Contour() {
|
|
|
d33d2a |
forward = new Circuit<contour, link="">(this);</contour,>
|
|
|
d33d2a |
backward = new Circuit<contour, link="">(this);</contour,>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
class Link {
|
|
|
f6cc12 |
public bool forward = false;
|
|
|
f6cc12 |
public Position nextPosition = null;
|
|
|
f6cc12 |
|
|
|
d33d2a |
public readonly Circuit<position, link="">.Entry position;</position,>
|
|
|
d33d2a |
public readonly Circuit<contour, link="">.Entry contour;</contour,>
|
|
|
d33d2a |
|
|
|
d33d2a |
public Link() {
|
|
|
d33d2a |
position = new Circuit<position, link="">.Entry(this);</position,>
|
|
|
d33d2a |
contour = new Circuit<contour, link="">.Entry(this);</contour,>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
public Link split(Shape shape, Position position) {
|
|
|
04c11c |
if (position.point == this.position.getParent().point) return this;
|
|
|
04c11c |
if (position.point == nextPosition.point) return nextPosition.links.getFirst();
|
|
|
04c11c |
|
|
|
04c11c |
shape.log.linkSplitted(this, position);
|
|
|
04c11c |
|
|
|
d33d2a |
Link link = new Link();
|
|
|
d33d2a |
link.position.insertBack(position.links);
|
|
|
d33d2a |
link.contour.insertAfterOf(contour);
|
|
|
f6cc12 |
link.forward = forward;
|
|
|
f6cc12 |
link.nextPosition = nextPosition;
|
|
|
f6cc12 |
nextPosition = position;
|
|
|
f6cc12 |
shape.links.Add(link);
|
|
|
d33d2a |
return link;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
public Link split(Shape shape, Link positionLink) {
|
|
|
f6cc12 |
return split(shape, positionLink.position.getParent());
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
04c11c |
|
|
|
04c11c |
class Log {
|
|
|
04c11c |
public bool enabled = true;
|
|
|
04c11c |
public string filename = "log.txt";
|
|
|
04c11c |
|
|
|
04c11c |
public void line(string line) {
|
|
|
04c11c |
if (!enabled) return;
|
|
|
04c11c |
System.IO.File.AppendAllLines(filename, new string[] { line });
|
|
|
04c11c |
}
|
|
|
04c11c |
|
|
|
04c11c |
public void linkCreated(Link link) {
|
|
|
04c11c |
if (!enabled) return;
|
|
|
04c11c |
line(string.Format(
|
|
|
04c11c |
"Link created {0} {1} {2}",
|
|
|
04c11c |
link.forward ? "->" : "<-",
|
|
|
04c11c |
link.position.getParent().point,
|
|
|
04c11c |
link.nextPosition.point ));
|
|
|
04c11c |
}
|
|
|
04c11c |
|
|
|
04c11c |
public void linkRemoved(Link link) {
|
|
|
04c11c |
if (!enabled) return;
|
|
|
04c11c |
line(string.Format(
|
|
|
04c11c |
"Link removed {0} {1} {2}",
|
|
|
04c11c |
link.forward ? "->" : "<-",
|
|
|
04c11c |
link.position.getParent().point,
|
|
|
04c11c |
link.nextPosition.point ));
|
|
|
04c11c |
}
|
|
|
04c11c |
|
|
|
04c11c |
public void linkSplitted(Link link, Position position) {
|
|
|
04c11c |
if (!enabled) return;
|
|
|
04c11c |
line(string.Format(
|
|
|
04c11c |
"Link splitted {0} {1}/{3}/{2}",
|
|
|
04c11c |
link.forward ? "->" : "<-",
|
|
|
04c11c |
link.position.getParent().point,
|
|
|
04c11c |
link.nextPosition.point,
|
|
|
04c11c |
position.point ));
|
|
|
04c11c |
}
|
|
|
04c11c |
|
|
|
04c11c |
public void linkSwapped(Link a, Link b) {
|
|
|
04c11c |
if (!enabled) return;
|
|
|
04c11c |
line(string.Format(
|
|
|
04c11c |
"Link swapped {0} {1} {2} - {3} {4} {5}",
|
|
|
04c11c |
a.forward ? "->" : "<-",
|
|
|
04c11c |
a.position.getParent().point,
|
|
|
04c11c |
a.nextPosition.point,
|
|
|
04c11c |
b.forward ? "->" : "<-",
|
|
|
04c11c |
b.position.getParent().point,
|
|
|
04c11c |
b.nextPosition.point ));
|
|
|
04c11c |
}
|
|
|
04c11c |
}
|
|
|
d33d2a |
|
|
|
d33d2a |
|
|
|
f6cc12 |
readonly List<position> positions = new List<position>();</position></position>
|
|
|
f6cc12 |
readonly List<link> links = new List<link>();
|
|
|
f6cc12 |
readonly List<contour> contours = new List<contour>();</contour></contour>
|
|
|
f6cc12 |
readonly List<contour> rootContours = new List<contour>();</contour></contour>
|
|
|
04c11c |
readonly Log log = new Log();
|
|
|
f6cc12 |
|
|
|
f6cc12 |
public void clear() {
|
|
|
f6cc12 |
positions.Clear();
|
|
|
f6cc12 |
links.Clear();
|
|
|
f6cc12 |
contours.Clear();
|
|
|
f6cc12 |
rootContours.Clear();
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
public void setContour(IEnumerable<point> contour) {</point>
|
|
|
f6cc12 |
setContours(new IEnumerable<point>[] { contour });</point>
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
7c6265 |
public void setContours(IEnumerable<ienumerable<ienumerable<point>>> contours) {</ienumerable<ienumerable<point>
|
|
|
7c6265 |
List<ienumerable<point>> list = new List<ienumerable<point>>();</ienumerable<point></ienumerable<point>
|
|
|
7c6265 |
foreach(IEnumerable<ienumerable<point>> c in contours)</ienumerable<point>
|
|
|
7c6265 |
list.AddRange(c);
|
|
|
7c6265 |
setContours(list);
|
|
|
7c6265 |
}
|
|
|
7c6265 |
|
|
|
f6cc12 |
public void setContours(IEnumerable<ienumerable<point>> contours) {</ienumerable<point>
|
|
|
f6cc12 |
clear();
|
|
|
04c11c |
|
|
|
04c11c |
log.line("---- setContours begin ----");
|
|
|
04c11c |
|
|
|
f6cc12 |
foreach(IEnumerable<point> contour in contours) {</point>
|
|
|
f6cc12 |
if (contour.Count() >= 3) {
|
|
|
f6cc12 |
Link firstForward = null;
|
|
|
f6cc12 |
Link firstBackward = null;
|
|
|
f6cc12 |
Link previousForward = null;
|
|
|
f6cc12 |
Link previousBackward = null;
|
|
|
f6cc12 |
foreach(Point point in contour) {
|
|
|
f6cc12 |
Position position = new Position(point);
|
|
|
bb5d1a |
positions.Add(position);
|
|
|
d33d2a |
|
|
|
f6cc12 |
Link forward = new Link();
|
|
|
f6cc12 |
forward.forward = true;
|
|
|
f6cc12 |
forward.position.insertBack(position.links);
|
|
|
f6cc12 |
if (previousForward != null)
|
|
|
f6cc12 |
previousForward.nextPosition = forward.position.getParent();
|
|
|
f6cc12 |
links.Add(forward);
|
|
|
f6cc12 |
|
|
|
f6cc12 |
Link backward = new Link();
|
|
|
f6cc12 |
backward.forward = false;
|
|
|
f6cc12 |
backward.position.insertBack(position.links);
|
|
|
f6cc12 |
if (previousBackward != null)
|
|
|
f6cc12 |
backward.nextPosition = previousBackward.position.getParent();
|
|
|
f6cc12 |
links.Add(backward);
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (firstForward == null) firstForward = forward;
|
|
|
f6cc12 |
if (firstBackward == null) firstBackward = backward;
|
|
|
f6cc12 |
previousForward = forward;
|
|
|
f6cc12 |
previousBackward = backward;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
previousForward.nextPosition = firstForward.position.getParent();
|
|
|
f6cc12 |
firstBackward.nextPosition = previousBackward.position.getParent();
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
}
|
|
|
04c11c |
foreach(Link link in links)
|
|
|
04c11c |
log.linkCreated(link);
|
|
|
f6cc12 |
|
|
|
f6cc12 |
calculate(true);
|
|
|
04c11c |
|
|
|
04c11c |
log.line("---- setContours end ----");
|
|
|
d33d2a |
}
|
|
|
098941 |
|
|
|
eb0c54 |
// returns list of root contour groups
|
|
|
eb0c54 |
// first contour in group is outer contour, others - inner
|
|
|
eb0c54 |
public List<list<list<point>>> getContours() {</list<list<point>
|
|
|
eb0c54 |
List<list<list<point>>> groups = new List<list<list<point>>>();</list<list<point></list<list<point>
|
|
|
eb0c54 |
foreach(Contour root in rootContours) {
|
|
|
eb0c54 |
List<list<point>> list = new List<list<point>>();</list<point></list<point>
|
|
|
eb0c54 |
list.Add(contourToList(root));
|
|
|
eb0c54 |
foreach(Contour c in root.childs)
|
|
|
eb0c54 |
list.Add(contourToList(c));
|
|
|
bb5d1a |
groups.Add(list);
|
|
|
098941 |
}
|
|
|
eb0c54 |
return groups;
|
|
|
098941 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
List<point> contourToList(Contour contour) {</point>
|
|
|
eb0c54 |
List<point> list = new List<point>();</point></point>
|
|
|
bb5d1a |
for(Link link = contour.forward.getFirst(); link != null; link = link.contour.getNextLinear())
|
|
|
eb0c54 |
list.Add(link.position.getParent().point);
|
|
|
eb0c54 |
return list;
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
f6cc12 |
void resetTraceInformation() {
|
|
|
f6cc12 |
for(int i = 0; i < contours.Count; ++i) {
|
|
|
f6cc12 |
contours[i].forward.clear();
|
|
|
f6cc12 |
contours[i].backward.clear();
|
|
|
f6cc12 |
contours[i].childs.Clear();
|
|
|
f6cc12 |
contours[i].parent = null;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
contours.Clear();
|
|
|
f6cc12 |
rootContours.Clear();
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
void removeLink(Link link) {
|
|
|
04c11c |
log.linkRemoved(link);
|
|
|
f6cc12 |
link.position.unlink();
|
|
|
f6cc12 |
link.contour.unlink();
|
|
|
f6cc12 |
link.nextPosition = null;
|
|
|
f6cc12 |
links.Remove(link);
|
|
|
f6cc12 |
}
|
|
|
098941 |
|
|
|
f6cc12 |
void removeEmptyPositions() {
|
|
|
f6cc12 |
for(int i = 0; i < positions.Count; ++i)
|
|
|
f6cc12 |
if (positions[i].links.empty())
|
|
|
f6cc12 |
positions.RemoveAt(i--);
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
void findIntersections() {
|
|
|
098941 |
bool retry = true;
|
|
|
098941 |
while(retry) {
|
|
|
098941 |
retry = false;
|
|
|
098941 |
|
|
|
d33d2a |
// merge positions
|
|
|
f6cc12 |
// this procedure may create zero-length links
|
|
|
f6cc12 |
for(int i = 0; i < positions.Count; ++i) {
|
|
|
f6cc12 |
for(int j = i+1; j < positions.Count; ++j) {
|
|
|
f6cc12 |
if (positions[i].point == positions[j].point) {
|
|
|
f6cc12 |
while(positions[j].links.getFirst() != null)
|
|
|
f6cc12 |
positions[j].links.getFirst().position.insertBack(positions[i].links);
|
|
|
f6cc12 |
positions.RemoveAt(j--);
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
f6cc12 |
|
|
|
d33d2a |
// remove zero-length links
|
|
|
f6cc12 |
// this procedure may create empty positions
|
|
|
f6cc12 |
for(int i = 0; i < links.Count; ++i)
|
|
|
f6cc12 |
if (links[i].position.getParent() == links[i].nextPosition)
|
|
|
f6cc12 |
removeLink(links[i--]);
|
|
|
f6cc12 |
|
|
|
f6cc12 |
// so we need to...
|
|
|
f6cc12 |
removeEmptyPositions();
|
|
|
f6cc12 |
|
|
|
d33d2a |
// check intersections
|
|
|
f6cc12 |
// this procedure may create new positions, new links and ne intersections
|
|
|
f6cc12 |
// so we need to repeat all cycle when intersection found
|
|
|
f6cc12 |
for(int i = 0; i < links.Count; ++i) {
|
|
|
f6cc12 |
for(int j = i+1; j < links.Count; ++j) {
|
|
|
f6cc12 |
Link a = links[i];
|
|
|
f6cc12 |
Link b = links[j];
|
|
|
f6cc12 |
Position a0 = a.position.getParent();
|
|
|
f6cc12 |
Position a1 = a.nextPosition;
|
|
|
f6cc12 |
Position b0 = b.position.getParent();
|
|
|
f6cc12 |
Position b1 = b.nextPosition;
|
|
|
f6cc12 |
Point c = new Point(0, 0);
|
|
|
f6cc12 |
retry = true; // will reset to false if no intersection
|
|
|
f6cc12 |
|
|
|
f6cc12 |
switch(Geometry.findIntersection(a0.point, a1.point, b0.point, b1.point, out c))
|
|
|
d33d2a |
{
|
|
|
f6cc12 |
case Geometry.IntersectionType.Cross:
|
|
|
f6cc12 |
Position p = new Position(c);
|
|
|
f6cc12 |
positions.Add(p);
|
|
|
f6cc12 |
a.split(this, p);
|
|
|
f6cc12 |
b.split(this, p);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Touch_a0:
|
|
|
f6cc12 |
b.split(this, a0);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Touch_a1:
|
|
|
f6cc12 |
b.split(this, a1);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Touch_b0:
|
|
|
f6cc12 |
a.split(this, b0);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Touch_b1:
|
|
|
f6cc12 |
a.split(this, b1);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_a0_b0_a1_b1:
|
|
|
f6cc12 |
a.split(this, b0);
|
|
|
f6cc12 |
b.split(this, a1);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_a0_b0_b1_a1:
|
|
|
f6cc12 |
a.split(this, b0).split(this, b1);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_a0_b1_a1_b0:
|
|
|
f6cc12 |
a.split(this, b1);
|
|
|
f6cc12 |
b.split(this, a1);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_a0_b1_b0_a1:
|
|
|
f6cc12 |
a.split(this, b1).split(this, b0);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_b0_a0_a1_b1:
|
|
|
f6cc12 |
b.split(this, a0).split(this, a1);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_b0_a0_b1_a1:
|
|
|
f6cc12 |
a.split(this, b1);
|
|
|
f6cc12 |
b.split(this, a0);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_b1_a0_a1_b0:
|
|
|
f6cc12 |
b.split(this, a1).split(this, a0);
|
|
|
d33d2a |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Along_b1_a0_b0_a1:
|
|
|
f6cc12 |
a.split(this, b0);
|
|
|
f6cc12 |
b.split(this, a0);
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
default:
|
|
|
d33d2a |
retry = false;
|
|
|
d33d2a |
break;
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|
|
|
f6cc12 |
// This function removes link from it position
|
|
|
f6cc12 |
// and also recursive removes part of contour to nearest fork
|
|
|
e5b120 |
void removeLinkFromPosition(Link link) {
|
|
|
e5b120 |
Position position = link.position.getParent();
|
|
|
e5b120 |
Link nextToRemove = null;
|
|
|
e5b120 |
|
|
|
04c11c |
// remove back link
|
|
|
f6cc12 |
if (link.nextPosition != null) {
|
|
|
f6cc12 |
Link backLink = link.nextPosition.links.getFirst();
|
|
|
e5b120 |
while (backLink != null) {
|
|
|
04c11c |
if ( backLink.forward != link.forward
|
|
|
04c11c |
&& backLink.nextPosition == position )
|
|
|
e5b120 |
{
|
|
|
04c11c |
removeLink(backLink);
|
|
|
e5b120 |
break;
|
|
|
e5b120 |
}
|
|
|
04c11c |
backLink = backLink.position.getNextLinear();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
f6cc12 |
if (link.nextPosition.links.getCount() == 1)
|
|
|
f6cc12 |
nextToRemove = link.nextPosition.links.getFirst();
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
e5b120 |
// remove
|
|
|
f6cc12 |
removeLink(link);
|
|
|
e5b120 |
|
|
|
e5b120 |
// remove next
|
|
|
e5b120 |
if (nextToRemove != null)
|
|
|
e5b120 |
removeLinkFromPosition(nextToRemove);
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
f6cc12 |
// Before trace contours we can (and should) to do some actions
|
|
|
f6cc12 |
// to optimize links in each vertes.
|
|
|
f6cc12 |
// So we can remove duplicated contour chunks
|
|
|
f6cc12 |
// and chunks which placed inside contours of similar type
|
|
|
f6cc12 |
// and not affecting to final image
|
|
|
f6cc12 |
void optimizePositions() {
|
|
|
f6cc12 |
foreach(Position position in positions) {
|
|
|
f6cc12 |
// remove duplicates
|
|
|
f6cc12 |
for(Link a = position.links.getFirst(); a != null; a = a.position.getNextLinear()) {
|
|
|
f6cc12 |
Position otherPosition = a.nextPosition;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
// count forward and backward links
|
|
|
f6cc12 |
int count = 0;
|
|
|
f6cc12 |
Link forwardLink = null;
|
|
|
f6cc12 |
Link backwardLink = null;
|
|
|
f6cc12 |
Link b = a;
|
|
|
f6cc12 |
do {
|
|
|
f6cc12 |
if (b.nextPosition == otherPosition) {
|
|
|
f6cc12 |
if (b.forward) { forwardLink = b; ++count; }
|
|
|
f6cc12 |
else { backwardLink = b; --count; }
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
b.position.getNext();
|
|
|
f6cc12 |
} while(b != a);
|
|
|
f6cc12 |
|
|
|
f6cc12 |
// remove extra links
|
|
|
f6cc12 |
Link linkToSave = count > 0 ? forwardLink
|
|
|
f6cc12 |
: count < 0 ? backwardLink
|
|
|
f6cc12 |
: null;
|
|
|
f6cc12 |
b = position.links.getFirst();
|
|
|
f6cc12 |
while(b != null) {
|
|
|
f6cc12 |
if (b.nextPosition == otherPosition && b != linkToSave) {
|
|
|
f6cc12 |
// remove link, a and b becomes invalid
|
|
|
f6cc12 |
removeLinkFromPosition(b);
|
|
|
f6cc12 |
// so reset a and b to repeat the current and parent cycles
|
|
|
f6cc12 |
b = a = position.links.getFirst();
|
|
|
f6cc12 |
} else {
|
|
|
f6cc12 |
b = b.position.getNextLinear();
|
|
|
f6cc12 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (position.links.getCount() >= 3) {
|
|
|
f6cc12 |
// sort links
|
|
|
f6cc12 |
Link first = position.links.getFirst();
|
|
|
f6cc12 |
Link a = first;
|
|
|
f6cc12 |
while (true) {
|
|
|
f6cc12 |
Link b = a.position.getNext();
|
|
|
f6cc12 |
Link c = b.position.getNext();
|
|
|
f6cc12 |
if ( !Geometry.isCCW(
|
|
|
f6cc12 |
position.point,
|
|
|
f6cc12 |
a.nextPosition.point,
|
|
|
f6cc12 |
b.nextPosition.point,
|
|
|
f6cc12 |
c.nextPosition.point ))
|
|
|
f6cc12 |
{
|
|
|
04c11c |
log.linkSwapped(b, c);
|
|
|
f6cc12 |
b.position.swapWith(c.position);
|
|
|
f6cc12 |
first = a = c;
|
|
|
f6cc12 |
continue;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
a = b;
|
|
|
f6cc12 |
if (a == first) break;
|
|
|
f6cc12 |
};
|
|
|
f6cc12 |
|
|
|
f6cc12 |
// remove invisible contours from position
|
|
|
04c11c |
a = first = position.links.getFirst();
|
|
|
04c11c |
while(true) {
|
|
|
f6cc12 |
bool previous = a.position.getPrevious().forward;
|
|
|
f6cc12 |
bool current = a.forward;
|
|
|
f6cc12 |
bool next = a.position.getNext().forward;
|
|
|
f6cc12 |
if ( ( previous && current && !next)
|
|
|
f6cc12 |
|| (!previous && !current && next) )
|
|
|
f6cc12 |
{
|
|
|
f6cc12 |
// remove link
|
|
|
f6cc12 |
removeLinkFromPosition(a);
|
|
|
04c11c |
if (position.links.getCount() < 3) break;
|
|
|
04c11c |
a = first = position.links.getFirst();
|
|
|
04c11c |
} else {
|
|
|
04c11c |
a = a.position.getNext();
|
|
|
04c11c |
if (a == first) break;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
};
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
e5b120 |
|
|
|
f6cc12 |
void buildContours() {
|
|
|
f6cc12 |
for(int i = 0; i < links.Count; ++i) {
|
|
|
f6cc12 |
if (links[i].forward && links[i].contour.getParent() == null) {
|
|
|
e5b120 |
Contour contour = new Contour();
|
|
|
f6cc12 |
contours.Add(contour);
|
|
|
098941 |
|
|
|
f6cc12 |
Link forwardLink = links[i];
|
|
|
e5b120 |
Link backwardLink = null;
|
|
|
098941 |
|
|
|
098941 |
do {
|
|
|
bb5d1a |
if (forwardLink == null || !forwardLink.forward || forwardLink.contour.getParent() != null)
|
|
|
bb5d1a |
throw new Exception();
|
|
|
bb5d1a |
|
|
|
098941 |
// find pair
|
|
|
04c11c |
for(Link l = forwardLink.nextPosition.links.getFirst(); l != null; l = l.position.getNextLinear())
|
|
|
f6cc12 |
if (l.nextPosition == forwardLink.position.getParent())
|
|
|
098941 |
{ backwardLink = l; break; }
|
|
|
bb5d1a |
if (backwardLink == null || backwardLink.forward || backwardLink.contour.getParent() != null)
|
|
|
098941 |
throw new Exception();
|
|
|
098941 |
|
|
|
098941 |
forwardLink.contour.insertBack(contour.forward);
|
|
|
367b01 |
backwardLink.contour.insertBack(contour.backward);
|
|
|
098941 |
|
|
|
f6cc12 |
// select first link by the left (links should be CCW-ordered)
|
|
|
098941 |
forwardLink = backwardLink.position.getNext();
|
|
|
f6cc12 |
} while (forwardLink != links[i]);
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
f6cc12 |
// Normally we should not have free links after tracing
|
|
|
098941 |
void removeFreeLinks() {
|
|
|
f6cc12 |
for(int i = 0; i < links.Count; ++i)
|
|
|
f6cc12 |
if (links[i].contour.getParent() == null)
|
|
|
367b01 |
throw new Exception();
|
|
|
098941 |
}
|
|
|
75fa8e |
|
|
|
f6cc12 |
int countIntersectionsWithContour(Point p0, Point p1, Contour contour) {
|
|
|
098941 |
int count = 0;
|
|
|
098941 |
for(Link link = contour.forward.getFirst(); link != null; link = link.contour.getNextLinear()) {
|
|
|
f6cc12 |
Point pp0 = link.position.getParent().point;
|
|
|
f6cc12 |
Point pp1 = link.contour.getNext().position.getParent().point;
|
|
|
f6cc12 |
int d = Math.Sign( (long)(p0.Y - p1.Y)*(long)(pp1.X - pp0.X)
|
|
|
f6cc12 |
+ (long)(p1.X - p0.X)*(long)(pp1.Y - pp0.Y) );
|
|
|
f6cc12 |
Point c;
|
|
|
f6cc12 |
switch(Geometry.findIntersection(p0, p1, pp0, pp1, out c)) {
|
|
|
f6cc12 |
case Geometry.IntersectionType.Cross:
|
|
|
098941 |
count += 2*d;
|
|
|
098941 |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Touch_b0:
|
|
|
098941 |
count += d;
|
|
|
098941 |
break;
|
|
|
f6cc12 |
case Geometry.IntersectionType.Touch_b1:
|
|
|
098941 |
count -= d;
|
|
|
098941 |
break;
|
|
|
098941 |
default:
|
|
|
098941 |
break;
|
|
|
e5b120 |
}
|
|
|
e5b120 |
}
|
|
|
098941 |
return count;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
bool isContourInverted(Contour contour) {
|
|
|
75fa8e |
Link first = contour.forward.getFirst();
|
|
|
f6cc12 |
Point p0 = first.position.getParent().point;
|
|
|
f6cc12 |
Point p1 = first.contour.getNext().position.getParent().point;
|
|
|
f6cc12 |
Geometry.makeLongestLine(p0, ref p1);
|
|
|
f6cc12 |
return countIntersectionsWithContour(p0, p1, contour) < 0;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
098941 |
bool isContourInside(Contour inner, Contour outer) {
|
|
|
75fa8e |
Link first = inner.forward.getFirst();
|
|
|
f6cc12 |
Point p0 = first.position.getParent().point;
|
|
|
f6cc12 |
Point p1 = first.contour.getNext().position.getParent().point;
|
|
|
f6cc12 |
Geometry.makeLongestLine(p0, ref p1);
|
|
|
f6cc12 |
return countIntersectionsWithContour(p0, p1, outer) != 0;
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
f6cc12 |
void organizeChildContours(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)
|
|
|
f6cc12 |
organizeChildContours(c, contour);
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
d6605c |
void invertContour(Contour contour) {
|
|
|
d6605c |
contour.inverted = !contour.inverted;
|
|
|
d6605c |
contour.forward.swapWith(contour.backward);
|
|
|
d6605c |
for(Link link = contour.forward.getFirst(); link != null; link.contour.getNextLinear())
|
|
|
d6605c |
link.forward = !link.forward;
|
|
|
d6605c |
for(Link link = contour.backward.getFirst(); link != null; link.contour.getNextLinear())
|
|
|
d6605c |
link.forward = !link.forward;
|
|
|
d6605c |
}
|
|
|
d6605c |
|
|
|
f6cc12 |
void buildContoursHierarhy(bool simple) {
|
|
|
098941 |
// calculate directions of contours
|
|
|
f6cc12 |
foreach(Contour contour in contours)
|
|
|
f6cc12 |
contour.inverted = isContourInverted(contour);
|
|
|
098941 |
|
|
|
098941 |
// find childs
|
|
|
f6cc12 |
rootContours.AddRange(contours);
|
|
|
f6cc12 |
for(int i = 0; i < contours.Count; ++i) {
|
|
|
f6cc12 |
for(int j = 0; j < contours.Count; ++j) {
|
|
|
f6cc12 |
if (isContourInside(contours[i], contours[j])) {
|
|
|
f6cc12 |
contours[j].childs.Add(contours[i]);
|
|
|
f6cc12 |
rootContours.Remove(contours[i]);
|
|
|
098941 |
} else
|
|
|
f6cc12 |
if (isContourInside(contours[j], contours[i])) {
|
|
|
f6cc12 |
contours[i].childs.Add(contours[j]);
|
|
|
f6cc12 |
rootContours.Remove(contours[j]);
|
|
|
098941 |
}
|
|
|
367b01 |
}
|
|
|
098941 |
}
|
|
|
098941 |
|
|
|
f6cc12 |
// organize childs
|
|
|
098941 |
foreach(Contour c in rootContours)
|
|
|
f6cc12 |
organizeChildContours(c, null);
|
|
|
f6cc12 |
|
|
|
367b01 |
// remove invisible contours
|
|
|
f6cc12 |
for(int i = 0; i < contours.Count; ++i) {
|
|
|
f6cc12 |
bool parentInverted = contours[i].parent == null || contours[i].parent.inverted;
|
|
|
f6cc12 |
if (parentInverted == contours[i].inverted) {
|
|
|
d6605c |
if (simple) {
|
|
|
d6605c |
// if simple then invert invisible contours instead of removing
|
|
|
d6605c |
invertContour(contours[i]);
|
|
|
d6605c |
} else {
|
|
|
d6605c |
// remove contour
|
|
|
d6605c |
foreach(Contour c in contours[i].childs)
|
|
|
d6605c |
c.parent = contours[i].parent;
|
|
|
d6605c |
List<contour> parentList = contours[i].parent == null</contour>
|
|
|
d6605c |
? rootContours
|
|
|
d6605c |
: contours[i].parent.childs;
|
|
|
d6605c |
parentList.AddRange(contours[i].childs);
|
|
|
d6605c |
|
|
|
d6605c |
contours[i].parent = null;
|
|
|
d6605c |
contours[i].childs.Clear();
|
|
|
d6605c |
while(!contours[i].forward.empty())
|
|
|
d6605c |
removeLink(contours[i].forward.getFirst());
|
|
|
d6605c |
while(!contours[i].backward.empty())
|
|
|
d6605c |
removeLink(contours[i].backward.getFirst());
|
|
|
d6605c |
|
|
|
d6605c |
contours.RemoveAt(i--);
|
|
|
d6605c |
}
|
|
|
367b01 |
}
|
|
|
367b01 |
}
|
|
|
e5b120 |
|
|
|
367b01 |
// move contours in the holes to root
|
|
|
367b01 |
for(int i = 0; i < rootContours.Count; ++i) {
|
|
|
367b01 |
Contour contourA = rootContours[i];
|
|
|
367b01 |
foreach(Contour contourB in contourA.childs) {
|
|
|
367b01 |
if (contourB.childs.Count != 0) {
|
|
|
367b01 |
foreach(Contour c in contourB.childs)
|
|
|
367b01 |
c.parent = null;
|
|
|
367b01 |
rootContours.AddRange(contourB.childs);
|
|
|
367b01 |
}
|
|
|
367b01 |
}
|
|
|
367b01 |
}
|
|
|
e5b120 |
}
|
|
|
367b01 |
|
|
|
f6cc12 |
void calculate(bool simple) {
|
|
|
f6cc12 |
resetTraceInformation();
|
|
|
e5b120 |
findIntersections();
|
|
|
e5b120 |
optimizePositions();
|
|
|
f6cc12 |
buildContours();
|
|
|
f6cc12 |
removeFreeLinks();
|
|
|
f6cc12 |
buildContoursHierarhy(simple);
|
|
|
098941 |
removeEmptyPositions();
|
|
|
d33d2a |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
public void invert() {
|
|
|
eb0c54 |
foreach(Contour contour in contours)
|
|
|
d6605c |
invertContour(contour);
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
static Shape mix(Shape a, bool invertA, Shape b, bool invertB) {
|
|
|
eb0c54 |
Shape sum = new Shape();
|
|
|
04c11c |
sum.log.enabled = a.log.enabled && b.log.enabled;
|
|
|
04c11c |
|
|
|
04c11c |
sum.log.line("---- mix begin ----");
|
|
|
eb0c54 |
|
|
|
eb0c54 |
// clone a
|
|
|
eb0c54 |
for(int i = 0; i < a.positions.Count; ++i)
|
|
|
eb0c54 |
sum.positions.Add(new Position(a.positions[i].point));
|
|
|
eb0c54 |
for(int i = 0; i < a.positions.Count; ++i) {
|
|
|
bb5d1a |
for(Link link = a.positions[i].links.getFirst(); link != null; link = link.position.getNextLinear()) {
|
|
|
eb0c54 |
Link l = new Link();
|
|
|
eb0c54 |
l.forward = invertA != link.forward;
|
|
|
eb0c54 |
l.nextPosition = sum.positions[a.positions.IndexOf(link.nextPosition)];
|
|
|
bb5d1a |
l.position.insertBack(sum.positions[i].links);
|
|
|
eb0c54 |
sum.links.Add(l);
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
// clone b
|
|
|
eb0c54 |
for(int i = 0; i < b.positions.Count; ++i)
|
|
|
eb0c54 |
sum.positions.Add(new Position(b.positions[i].point));
|
|
|
eb0c54 |
for(int i = 0; i < b.positions.Count; ++i) {
|
|
|
bb5d1a |
for(Link link = b.positions[i].links.getFirst(); link != null; link = link.position.getNextLinear()) {
|
|
|
eb0c54 |
Link l = new Link();
|
|
|
eb0c54 |
l.forward = invertB != link.forward;
|
|
|
eb0c54 |
l.nextPosition = sum.positions[a.positions.Count + b.positions.IndexOf(link.nextPosition)];
|
|
|
bb5d1a |
l.position.insertBack(sum.positions[a.positions.Count + i].links);
|
|
|
bb5d1a |
sum.links.Add(l);
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
}
|
|
|
04c11c |
foreach(Link link in sum.links)
|
|
|
04c11c |
sum.log.linkCreated(link);
|
|
|
eb0c54 |
|
|
|
eb0c54 |
sum.calculate(false);
|
|
|
04c11c |
|
|
|
04c11c |
sum.log.line("---- mix end ----");
|
|
|
04c11c |
|
|
|
eb0c54 |
return sum;
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
public static Shape add(Shape a, Shape b) {
|
|
|
eb0c54 |
return mix(a, false, b, false);
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
public static Shape subtract(Shape a, Shape b) {
|
|
|
eb0c54 |
return mix(a, false, b, true);
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
public static Shape xor(Shape a, Shape b) {
|
|
|
eb0c54 |
return add(subtract(a, b), subtract(b, a));
|
|
|
eb0c54 |
}
|
|
|
eb0c54 |
|
|
|
eb0c54 |
public static Shape intersection(Shape a, Shape b) {
|
|
|
eb0c54 |
return subtract(add(a, b), xor(a, b));
|
|
|
eb0c54 |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
}
|
|
|
d33d2a |
|