+ private static class Imprecise {
+ public static Point center(Mesh m, Point v1, Point v2, Point v3) {
+ return m.point((float)((double)v1.x+(double)v2.x+(double)v3.x)/3,
+ (float)(((double)v1.y+(double)v2.y+(double)v3.y)/3));
+ }
+ public static boolean near(Point a, Point b) {
+ return ddistance(a.x, a.y, b.x, b.y) <= epsilon;
+ }
+ public static boolean incircle(Point v1, Point v2, Point v3, Point p) {
+ /*
+ float a = 0;
+ Q: for(int q=0; q<2; q++) {
+ for(int i=0; i<3; i++) {
+ if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
+ Point t = v2; v2=v3; v3=v1; v1 = t;
+ }
+ Point t = v2; v2=v3; v3=t;
+ }
+ if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
+ double a1 = (v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
+ double a2 = (v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
+ double ccx = (a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2;
+ double ccy = (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2;
+ double r2 = (v1.x-ccx)*(v1.x-ccx)+(v1.y-ccy)*(v1.y-ccy);
+ double pd = (p.x-ccx)*(p.x-ccx)+(p.y-ccy)*(p.y-ccy);
+ return r2 > pd;
+ */
+ return Predicates.incircle(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, p.x, p.y)>0;
+ }
+ public static Point midpoint(Mesh m, Point a, Point b) { return m.point((a.x+b.x)/2,(a.y+b.y)/2); }
+ private static double ddistance(double x1, double y1, double x2, double y2) {
+ return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
+ public static float area(Point p1, Point p2, Point p3) {
+ float x1 = p1.x;
+ float x2 = p2.x;
+ float x3 = p3.x;
+ float y1 = p1.y;
+ float y2 = p2.y;
+ float y3 = p3.y;
+ double a = ddistance(x1,y1,x2,y2);
+ double b = ddistance(x2,y2,x3,y3);
+ double c = ddistance(x3,y3,x1,y1);
+ double s = (a+b+c)/2;
+ double t = s*(s-a)*(s-b)*(s-c);
+ if (t < 0) return 0;
+ return (float)Math.sqrt(t);
+ }
+
+ public static Point intersect(Mesh m, Point v1, Point v2, Point v3, Point v4) {
+ double a1 = v2.y-v1.y;
+ double a2 = v4.y-v3.y;
+ double b1 = v1.x-v2.x;
+ double b2 = v3.x-v4.x;
+ double c1 = -1 * (a1*v1.x+b1*v1.y);
+ double c2 = -1 * (a2*v3.x+b2*v3.y);
+ double x = (b2*c1-c2*b1)/(b1*a2-b2*a1);
+ double y = (a2*c1-c2*a1)/(a1*b2-a2*b1);
+ if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n ");
+ return m.point((float)x,(float)y);
+ }
+ public static int side(Point p1, Point p2, Point p3) {
+ /*
+ int ret = 0;
+ float x0 = p1.x;
+ float x = p2.x;
+ float x2 = p3.x;
+ float y0 = p1.y;
+ float y = p2.y;
+ float y2 = p3.y;
+
+ // this MUST be done to double precision
+ double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2);
+ if (c > 0) ret = b>=0 ? -1 : 1;
+ else if (c < 0) ret = b>=0 ? 1 : -1;
+ else ret = 0;
+ return ret;
+ */
+ return Predicates.side(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
+ }
+