#include "common/genpoly.h"
#include "common/ellipse2bezier.h"
using namespace std;
#define GEMS_DONT_INTERSECT 0
#define GEMS_DO_INTERSECT 1
#define GEMS_COLLINEAR 2
#ifndef TRUE
#define TRUE 1
#define FALSE (!TRUE)
#endif
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define NIL(t) (t)0
Coord origin;
Coord mysincos(double rads) {
Coord rv;
rv.y = sin(rads);
rv.x = sqrt(1.0 - rv.y * rv.y);
if((rads > M_PI_2) && (rads < M_PI + M_PI_2)) rv.x = -rv.x;
return rv;
}
void regpolygon(double size,int nsides,Line &out) {
double t,theta;
int i;
assert (nsides >= 3);
out.clear();
out.degree = 1;
theta = (2.0 * M_PI) / nsides;
t = (1.5 * M_PI) + (theta / 2.0);
for(i = 0; i < nsides; i++) {
out.push_back(mysincos(t)*size);
t = t + theta;
if(t >= 2.0 * M_PI) t = t - 2.0 * M_PI;
}
out.push_back(out[0]);
}
static void rotate(Line &poly, double rot) {
unsigned i;
double r,theta,new_theta;
Coord p;
for(i = 0; i < poly.size(); i++) {
p = poly[i];
r = sqrt(p.x * p.x + p.y * p.y);
theta = atan2(p.y,p.x);
new_theta = theta + rot;
while(new_theta > 2.0 * M_PI)
new_theta -= 2.0 * M_PI;
while(new_theta < 0.0)
new_theta += 2.0*M_PI;
p = mysincos(new_theta);
p.x = p.x * r; p.y = p.y * r;
poly[i] = p;
}
}
static void skew_and_distort(Line &poly, double skew, double distortion) {
unsigned i;
Coord p;
double scale;
scale = hypot(poly[0].x,poly[0].y);
if(distortion<0.0)
distortion = 1.0/(1.0-distortion);
else
distortion = 1.0 + distortion;
for(i = 0; i < poly.size(); i++) {
p = poly[i];
poly[i].x = p.x * (1 + p.y * (distortion - 1) / (2 * scale)) + skew * p.y;
}
}
#ifdef QUADS
#define quadrant(cd) ((((cd).x>0)?1:0)|(((cd).y>0)?2:0))
#define quadrantize(cd,q) (cd).x = (q&1)?fabs((cd).x):(-fabs((cd).x));\
(cd).y = (q&2)?fabs((cd).y):(-fabs((cd).y));
#endif
template<typename Reaction>
static void box_and_poly(Reaction &r,Line &poly,Coord box) {
Coord half(box.x / 2.0,box.y / 2.0);
Segment D1(Coord(-half.x,-half.y),Coord(half.x,half.y)),
D2(Coord(-half.x,half.y),Coord(half.x,-half.y));
for(unsigned i = 0; i < poly.size()-1; i+=poly.degree) {
Position P = poly.Intersection(i,D1);
if(!P.valid)
P = poly.Intersection(i,D2);
if(!r.grok(box,P))
break;
}
}
struct FindScaling {
double s;
FindScaling() : s(0.0) {}
inline bool grok(Coord box,Position P) {
if(P.valid)
s = MAX(s,fabs(box.x/P.x/2.0));
return true;
}
};
static double scale_for_interior(Line &poly, Coord box) {
FindScaling r;
box_and_poly(r,poly,box);
return r.s;
}
struct HitTest {
bool hasHit;
HitTest() : hasHit(false) {}
inline bool grok(Coord box,Position P) {
if(P.valid) {
hasHit = true;
return false;
}
return true;
}
};
Coord polysize(const Line &poly) {
unsigned i;
Coord low,high,p,rv;
low = high = poly[0];
for(i = 1; i < poly.size(); i++) {
p = poly[i];
if(low.x > p.x) low.x = p.x;
if(low.y > p.y) low.y = p.y;
if(high.x < p.x) high.x = p.x;
if(high.y < p.y) high.y = p.y;
}
rv.x = high.x - low.x;
rv.y = high.y - low.y;
return rv;
}
static Coord scale_for_exterior(const Line &poly, Coord external_box) {
Coord size = polysize(poly),
rv;
rv.x = external_box.x / size.x;
rv.y = external_box.y / size.y;
return rv;
}
static void scalexy(Line &poly, Coord scale) {
unsigned i;
for(i = 0; i < poly.size(); i++) {
poly[i].x *= scale.x;
poly[i].y *= scale.y;
}
}
const double Infinity = 99999.0; inline bool leps(double a) {
return fabs(a)<1e-8;
}
inline double sqr(double a) {
return a*a;
}
inline double slope(Segment L) {
Coord d = L.a - L.b;
double m = d.y/d.x;
if(fabs(d.x)<1e-3 || fabs(m)>1e3)
m = Infinity;
if(fabs(m)<1e-3)
m = 0.0;
return m;
}
static Coord distance_along_line(Coord pt,double slope,double dist,bool toward) {
double a,b,c,
ofs,
tmp,tmp2;
Coord rv;
if(dist==0.0)
return pt;
if(slope==Infinity || slope==-Infinity) {
if(toward==(pt.y>0.0))
return Coord(pt.x,pt.y-dist);
else
return Coord(pt.x,pt.y+dist);
}
ofs = pt.y - slope*pt.x;
a = 1.0 + sqr(slope);
b = -2.0*pt.x + 2.0*ofs*slope - 2.0*pt.y*slope;
c = sqr(pt.x) + sqr(ofs) - 2.0*pt.y*ofs + sqr(pt.y) - sqr(dist);
assert(a);
tmp = -b/(2.0*a);
assert(sqr(b)>4.0*a*c);
tmp2 = sqrt(sqr(b)-4.0*a*c)/(2.0*a);
double x1 = tmp+tmp2,
x2 = tmp-tmp2;
if((hypot(x1,slope*x1 + ofs)<hypot(x2,slope*x2 + ofs)) == toward)
rv.x = x1;
else
rv.x = x2;
rv.y = slope*rv.x + ofs;
return rv;
}
static void calc_periphery(const Line &poly,double dist,bool inward,Line &out) {
Segment E; Coord midpt, lmid, fmid; double m, n, b; double lm=-17.0,lb=-17.0, fm=-17.0,fb=-17.0; Coord q, lq, fq; out.clear();
out.degree = poly.degree;
out.push_back(Coord(0,0));
for(unsigned i = 0; i < poly.size()-1; i++) {
E.a = poly[i];
E.b = poly[i+1];
m = slope(E);
if(fabs(m)<1e-3)
n = m<0.0?Infinity:-Infinity;
else
n = -1.0/m;
midpt = (E.a+E.b)/2.0;
q = distance_along_line(midpt,n,dist,inward);
b = q.y - m*q.x;
if(i==0) {
fm = m;
fb = b;
fmid = midpt;
fq = q;
}
else {
Coord c;
if(leps(m-lm))
c = (lq + q)/2.0;
else {
if(m==Infinity||m==-Infinity) { c.x = q.x;
c.y = lm*c.x+lb;
}
else if(lm==Infinity||lm==-Infinity) {
c.x = lq.x;
c.y = m*c.x+b;
}
else {
c.x = (lb - b) / (m - lm);
c.y = m*c.x+b;
}
}
assert(c.y<1e5 && c.y>-1e5);
out.push_back(c);
}
lm = m;
lb = b;
lmid = midpt;
lq = q;
}
Coord c;
if(leps(fm-lm))
c = (fq+lq)/2.0;
else {
if(fm==Infinity||fm==-Infinity) { c.x = fq.x;
c.y = lm*c.x+lb;
}
else if(lm==Infinity||lm==-Infinity) {
c.x = lq.x;
c.y = fm*c.x+fb;
}
else {
c.x = (lb - fb) / (fm - lm);
c.y = fm*c.x+fb;
}
}
out[0] = c;
out.push_back(c);
}
void makePeripheries(int peris,double perispace,bool inward,Lines &out) {
if(peris) {
Line *last = &out.front();
for(int i = 0; i < peris; i++) {
Line *next;
if(inward) {
out.push_back(Line());
next = &out.back();
}
else {
out.push_front(Line());
next = &out.front();
}
calc_periphery(*last,perispace,inward,*next);
last = next;
}
}
}
void genpoly(const PolyDef &arg,Lines &out) {
Coord scaling;
int symmetric;
if(!((arg.interior_box.x && arg.interior_box.y) ||
(arg.exterior_box.x && arg.exterior_box.y)) ||
!arg.interior_box.x != !arg.interior_box.y ||
!arg.exterior_box.x != !arg.exterior_box.y ||
arg.interior_box.x<0.0 || arg.interior_box.y<0.0 ||
arg.exterior_box.x<0.0 || arg.exterior_box.y<0.0)
throw BadPolyBounds();
double startsize = arg.interior_box.x?min(arg.interior_box.x,arg.interior_box.y)/2.0:1.0;
out.clear();
out.push_back(Line());
Line &first = out.back();
if(arg.input.size()) {
if(!arg.input.degree || arg.input.size()<3)
throw BadInputPoly();
first = arg.input*startsize;
}
else if(arg.isEllipse) {
if(!arg.aspect)
throw BadPolyDef();
Rect r(-startsize,-arg.aspect*startsize,startsize,arg.aspect*startsize);
ellipse2bezier(r,first);
}
else {
if(arg.sides < 3)
throw BadPolyDef();
regpolygon(startsize,arg.sides,first);
}
if(arg.skew != 0.0 || arg.distortion != 0.0) {
symmetric = FALSE;
skew_and_distort(first,arg.skew,arg.distortion);
}
else symmetric = TRUE;
if(arg.rotation != 0.0)
rotate(first,arg.rotation);
bool inward; if(arg.interior_box.x || arg.interior_box.y) {
inward = false;
if(arg.regular) {
double s = scale_for_interior(first,arg.interior_box);
scaling = Coord(s,s);
scaling.x = scaling.y = MAX(scaling.x,scaling.y); }
else {
double m = MIN(arg.interior_box.x,arg.interior_box.y);
double s = scale_for_interior(first,Coord(m,m));
if(arg.interior_box.x>arg.interior_box.y) {
scaling.y = s;
scaling.x = s*arg.interior_box.x/arg.interior_box.y;
}
else {
scaling.x = s;
scaling.y = s*arg.interior_box.y/arg.interior_box.x;
}
}
}
else {
scaling = scale_for_exterior(first,arg.exterior_box);
inward = true;
if(arg.regular)
scaling.x = scaling.y = MIN(scaling.x,scaling.y);
}
scalexy(first,scaling);
makePeripheries(arg.peripheries,arg.perispacing,inward,out);
if(!inward && (arg.exterior_box.x || arg.exterior_box.y)) {
Coord size = polysize(out.front());
bool tooSmall = false;
if(size.x-arg.exterior_box.x<-1e-5) {
tooSmall = true;
size.x = arg.exterior_box.x;
}
if(size.y-arg.exterior_box.y<-1e-5) {
tooSmall = true;
size.y = arg.exterior_box.y;
}
if(tooSmall) {
Coord scaleExt = scale_for_exterior(out.front(),size);
scalexy(out.front(),scaleExt);
out.erase(++out.begin(),out.end());
makePeripheries(arg.peripheries,arg.perispacing,true,out);
}
}
}