#include "common/Dynagraph.h"
#include "voronoi/voronoi.h"
#include "voronoi/info.h"
#include "voronoi/edges.h"
using namespace std;
namespace Voronoi {
void VoronoiServer::chkBoundBox() {
bounds.valid = false;
for(vector<Info>::iterator ii = infos.nodes.begin(); ii !=infos.nodes.end(); ii++)
bounds |= gd<NodeGeom>(ii->layoutN).BoundingBox();
if(bounds.valid) {
Coord delta = bounds.Size()*margin;
bounds = Rect(bounds.l-delta.x,bounds.t+delta.y,bounds.r+delta.x,bounds.b-delta.y);
}
}
void VoronoiServer::makeInfo() {
int N = current->nodes().size();
infos.nodes.resize(N);
Layout::node_iter ni = current->nodes().begin();
vector<Info>::iterator ii = infos.nodes.begin();
for(; ni!=current->nodes().end(); ++ni,++ii) {
Layout::Node *n = *ni;
ii->site.coord = gd<NodeGeom>(n).pos;
ii->site.sitenbr = ii-infos.nodes.begin();
ii->site.refcnt = 1;
ii->layoutN = n;
ii->verts = 0;
}
}
struct scomp {
bool operator ()(Site *s1,Site *s2) {
if(s1 -> coord.y < s2 -> coord.y) return true;
if(s1 -> coord.y > s2 -> coord.y) return false;
if(s1 -> coord.x < s2 -> coord.x) return true;
return false;
}
};
void VoronoiServer::sortSites(vector<Site*> &sort) {
int nsites = current->nodes().size();
vector<Site*>::iterator sp;
vector<Info>::iterator ip;
sort.resize(nsites);
sp = sort.begin();
ip = infos.nodes.begin();
for (; ip!=infos.nodes.end(); ++ip) {
*sp++ = &(ip->site);
ip->verts = NULL;
ip->site.refcnt = 1;
}
std::sort(sort.begin(),sort.end(),scomp());
}
void VoronoiServer::geomUpdate (vector<Site*> &sort) {
sortSites (sort);
hedges.range = Rect(sort[0]->coord);
for(int i = 1; i < current->nodes().size(); i++)
hedges.range |= sort[i]->coord;
}
int VoronoiServer::countOverlap(int iter) {
int count = 0;
int i;
int nsites = current->nodes().size();
for (i = 0; i < nsites; ++i)
infos.nodes[i].overlaps = false;
for(vector<Info>::iterator ip = infos.nodes.begin(); ip!=infos.nodes.end(); ++ip)
for(vector<Info>::iterator jp = ip+1; jp!=infos.nodes.end(); ++jp)
if(gd<NodeGeom>(ip->layoutN).region.Overlaps(ip->site.coord,
jp->site.coord, gd<NodeGeom>(jp->layoutN).region)) {
count++;
ip->overlaps = jp->overlaps = true;
}
return count;
}
void VoronoiServer::increaseBoundBox() {
double ydelta = incr * bounds.Height(),
xdelta = incr * bounds.Width();
bounds.r += xdelta;
bounds.t += ydelta;
bounds.l -= xdelta;
bounds.b -= ydelta;
}
bool VoronoiServer::isInterior (Info* ip) {
Coord a;
PtItem* pt;
for (pt = ip->verts; pt; pt = pt->next) {
a = pt->p;
if ((a.x == bounds.l) || (a.x == bounds.r) ||
(a.y == bounds.b) || (a.y == bounds.t)) return false;
}
return true;
}
void VoronoiServer::newpos(Info* ip) {
PtItem* anchor = ip->verts;
Coord ws(0,0);
double totalArea = 0.0;
if(anchor && anchor->next && anchor->next->next) {
#ifdef VORLINES
{
Layout *l = infos.nodes.front().layoutN->g;
Line seg;
seg.degree = 1;
for(PtItem *p = anchor; p; p = p->next)
seg.push_back(p->p);
seg.push_back(anchor->p);
gd<Drawn>(l).push_back(seg);
}
#endif
for(PtItem *p = anchor->next,*q = p->next;q;p = q,q = q->next) {
double area = tri_area(anchor->p, p->p, q->p);
Coord ctr = centroid(anchor->p, p->p, q->p);
ws += ctr*area;
totalArea += area;
}
ip->site.coord = ws/totalArea;
}
else
ip->site.coord.x += 1;
}
void VoronoiServer::addCorners() {
vector<Info>::iterator ip = infos.nodes.begin(),
sws = ip,
nws = ip,
ses = ip,
nes = ip;
double swd = dSquared(ip->site.coord, bounds.SW());
double nwd = dSquared(ip->site.coord, bounds.NW());
double sed = dSquared(ip->site.coord, bounds.SE());
double ned = dSquared(ip->site.coord, bounds.NE());
double d;
while(++ip!=infos.nodes.end()) {
d = dSquared(ip->site.coord, bounds.SW());
if (d < swd) {
swd = d;
sws = ip;
}
d = dSquared(ip->site.coord, bounds.SE());
if (d < sed) {
sed = d;
ses = ip;
}
d = dSquared(ip->site.coord, bounds.NW());
if (d < nwd) {
nwd = d;
nws = ip;
}
d = dSquared(ip->site.coord, bounds.NE());
if (d < ned) {
ned = d;
nes = ip;
}
}
infos.addVertex (&sws->site, bounds.SW());
infos.addVertex (&ses->site, bounds.SE());
infos.addVertex (&nws->site, bounds.NW());
infos.addVertex (&nes->site, bounds.NE());
}
void VoronoiServer::newPos() {
addCorners ();
for(vector<Info>::iterator ii = infos.nodes.begin(); ii!=infos.nodes.end(); ++ii)
if (doAll || ii->overlaps)
newpos(&*ii);
}
bool VoronoiServer::vAdjust () {
int iterCnt = 0;
int overlapCnt = 0;
int badLevel = 0;
int increaseCnt = 0;
int cnt;
if (!useIter || (iterations > 0))
overlapCnt = countOverlap (iterCnt);
if ((overlapCnt == 0) || (iterations == 0))
return 0;
doAll = false;
vector<Site*> sort;
geomUpdate(sort);
voronoi(sort);
while (1) {
newPos ();
iterCnt++;
if (useIter && (iterCnt == iterations)) break;
cnt = countOverlap (iterCnt);
if (cnt == 0) break;
if (cnt >= overlapCnt) badLevel++;
else badLevel = 0;
overlapCnt = cnt;
switch (badLevel) {
case 0:
doAll = false;
break;
default :
doAll = true;
increaseCnt++;
increaseBoundBox ();
break;
}
geomUpdate(sort);
voronoi(sort);
}
return 1;
}
void VoronoiServer::updateLayout(ChangeQueue &Q) {
for(vector<Info>::iterator ii = infos.nodes.begin(); ii!=infos.nodes.end(); ++ii) {
gd<NodeGeom>(ii->layoutN).pos = ii->site.coord;
Q.ModNode(ii->layoutN,DG_UPD_MOVE);
}
}
void VoronoiServer::Process(ChangeQueue &Q) {
makeInfo();
chkBoundBox();
if(vAdjust())
updateLayout(Q);
#ifdef VORLINES
Q.GraphUpdateFlags() |= DG_UPD_LINES;
#endif
}
}