Source code

001/*
002 * To change this template, choose Tools | Templates
003 * and open the template in the editor.
004 */
005package sec.sun.awt.geom;
006
007import armyc2.c2sd.graphics2d.Rectangle2D;
008
009/**
010 *
011 * @author Michael Deutch
012 */
013public class CurveObject {
014
015    private Order0 order0 = null;
016    private Order1 order1 = null;
017    private Order2 order2 = null;
018    private Order3 order3 = null;
019    int order = -1;
020
021    public CurveObject(Object obj) {
022        if (obj instanceof Order0) {
023            order0 = (Order0) obj;
024            order = 0;
025        } else if (obj instanceof Order1) {
026            order1 = (Order1) obj;
027            order = 1;
028        } else if (obj instanceof Order2) {
029            order2 = (Order2) obj;
030            order = 2;
031        } else if (obj instanceof Order3) {
032            order3 = (Order3) obj;
033            order = 3;
034        }
035        setParent();
036    }
037
038    private void setParent() {
039        switch (order) {
040            case 0:
041                order0.setParent(this);
042                break;
043            case 1:
044                order1.setParent(this);
045                break;
046            case 2:
047                order2.setParent(this);
048                break;
049            case 3:
050                order3.setParent(this);
051                break;
052            default:
053                break;
054        }
055        return;
056    }
057
058    public Object getCurve() {
059        switch (order) {
060            case 0:
061                return order0;
062            case 1:
063                return order1;
064            case 2:
065                return order2;
066            case 3:
067                return order3;
068            default:
069                return null;
070        }
071    }
072
073    public int getOrder() {
074        return order;
075    }
076
077    public double getXTop() {
078        switch (order) {
079            case 0:
080                return order0.getXTop();
081            case 1:
082                return order1.getXTop();
083            case 2:
084                return order2.getXTop();
085            case 3:
086                return order3.getXTop();
087            default:
088                return -7;
089        }
090    }
091
092    public CurveObject(int direction) {
093        //this.direction = direction;
094        switch (order) {
095            case 0:
096                order0.direction = direction;
097                break;
098            case 1:
099                order1.direction = direction;
100                break;
101            case 2:
102                order2.direction = direction;
103                break;
104            case 3:
105                order3.direction = direction;
106                break;
107            default:
108                break;
109        }
110    }
111
112    public double getYTop() {
113        switch (order) {
114            case 0:
115                return order0.getYTop();
116            case 1:
117                return order1.getYTop();
118            case 2:
119                return order2.getYTop();
120            case 3:
121                return order3.getYTop();
122            default:
123                return -7;
124        }
125    }
126
127    public double getXBot() {
128        switch (order) {
129            case 0:
130                return order0.getXBot();
131            case 1:
132                return order1.getXBot();
133            case 2:
134                return order2.getXBot();
135            case 3:
136                return order3.getXBot();
137            default:
138                return -7;
139        }
140
141    }
142
143    public double getYBot() {
144        switch (order) {
145            case 0:
146                return order0.getYBot();
147            case 1:
148                return order1.getYBot();
149            case 2:
150                return order2.getYBot();
151            case 3:
152                return order3.getYBot();
153            default:
154                return -7;
155        }
156
157    }
158
159    public double getXMin() {
160        switch (order) {
161            case 0:
162                return order0.getXMin();
163            case 1:
164                return order1.getXMin();
165            case 2:
166                return order2.getXMin();
167            case 3:
168                return order3.getXMin();
169            default:
170                return -7;
171        }
172    }
173
174    public double getXMax() {
175        switch (order) {
176            case 0:
177                return order0.getXMax();
178            case 1:
179                return order1.getXMax();
180            case 2:
181                return order2.getXMax();
182            case 3:
183                return order3.getXMax();
184            default:
185                return -7;
186        }
187    }
188
189    public final int getDirection() {
190        //return direction;
191        switch (order) {
192            case 0:
193                return order0.direction;
194            case 1:
195                return order1.direction;
196            case 2:
197                return order2.direction;
198            case 3:
199                return order3.direction;
200            default:
201                return -1;
202        }
203    }
204
205    public double XforY(double y) {
206        switch (order) {
207            case 0:
208                return order0.XforY(y);
209            case 1:
210                return order1.XforY(y);
211            case 2:
212                return order2.XforY(y);
213            case 3:
214                return order3.XforY(y);
215            default:
216                return -7;
217        }
218    }
219
220    public Object getReversedCurve() {
221        switch (order) {
222            case 0:
223                return order0.getReversedCurve();
224            case 1:
225                return order1.getReversedCurve();
226            case 2:
227                return order2.getReversedCurve();
228            case 3:
229                return order3.getReversedCurve();
230            default:
231                return null;
232        }
233    }
234
235    public double getX0() {
236        switch (order) {
237            case 0:
238                return order0.getX0();
239            case 1:
240                return order1.getX0();
241            case 2:
242                return order2.getX0();
243            case 3:
244                return order3.getX0();
245            default:
246                return -7;
247        }
248    }
249
250    public double getY0() {
251        switch (order) {
252            case 0:
253                return order0.getY0();
254            case 1:
255                return order1.getY0();
256            case 2:
257                return order2.getY0();
258            case 3:
259                return order3.getY0();
260            default:
261                return -7;
262        }
263    }
264
265    public double getX1() {
266        switch (order) {
267            case 0:
268                return order0.getX1();
269            case 1:
270                return order1.getX1();
271            case 2:
272                return order2.getX1();
273            case 3:
274                return order3.getX1();
275            default:
276                return -7;
277        }
278    }
279
280    public double getY1() {
281        switch (order) {
282            case 0:
283                return order0.getY1();
284            case 1:
285                return order1.getY1();
286            case 2:
287                return order2.getY1();
288            case 3:
289                return order3.getY1();
290            default:
291                return -7;
292        }
293    }
294
295    public double XforT(double t) {
296        switch (order) {
297            case 0:
298                return order0.XforT(t);
299            case 1:
300                return order1.XforT(t);
301            case 2:
302                return order2.XforT(t);
303            case 3:
304                return order3.XforT(t);
305            default:
306                return -7;
307        }
308    }
309
310    public double YforT(double t) {
311        switch (order) {
312            case 0:
313                return order0.YforT(t);
314            case 1:
315                return order1.YforT(t);
316            case 2:
317                return order2.YforT(t);
318            case 3:
319                return order3.YforT(t);
320            default:
321                return -7;
322        }
323    }
324
325    public double TforY(double t) {
326        switch (order) {
327            case 0:
328                return order0.TforY(t);
329            case 1:
330                return order1.TforY(t);
331            case 2:
332                return order2.TforY(t);
333            case 3:
334                return order3.TforY(t);
335            default:
336                return -7;
337        }
338    }
339
340    public double nextVertical(double t0, double t1) {
341        switch (order) {
342            case 0:
343                return order0.nextVertical(t0, t1);
344            case 1:
345                return order1.nextVertical(t0, t1);
346            case 2:
347                return order2.nextVertical(t0, t1);
348            case 3:
349                return order3.nextVertical(t0, t1);
350            default:
351                return -7;
352        }
353    }
354
355    public String controlPointString() {
356        switch (order) {
357            case 0:
358                return "";
359            case 1:
360                return "";
361            case 2:
362                return order2.controlPointString();
363            case 3:
364                return order3.controlPointString();
365            default:
366                return "";
367        }
368    }
369
370    @Override
371    public String toString() {
372        return ("Curve["
373                + getOrder() + ", "
374                + ("(" + Curve.round(this.getX0()) + ", " + Curve.round(this.getY0()) + "), ")
375                + this.controlPointString()
376                + ("(" + Curve.round(getX1()) + ", " + Curve.round(getY1()) + "), ")
377                + //(direction == Curve.INCREASING ? "D" : "U")+
378                (this.getDirection() == Curve.INCREASING ? "D" : "U")
379                + "]");
380    }
381
382    public int crossingsFor(double x, double y) {
383        if (y >= this.getYTop() && y < this.getYBot()) {
384            if (x < this.getXMax() && (x < this.getXMin() || x < this.XforY(y))) {
385                return 1;
386            }
387        }
388        return 0;
389    }
390
391    public boolean accumulateCrossings(CrossingsObject c) {
392        double xhi = c.getXHi();
393        if (getXMin() >= xhi) {
394            return false;
395        }
396        double xlo = c.getXLo();
397        double ylo = c.getYLo();
398        double yhi = c.getYHi();
399        double y0 = getYTop();
400        double y1 = getYBot();
401        double tstart, ystart, tend, yend;
402        if (y0 < ylo) {
403            if (y1 <= ylo) {
404                return false;
405            }
406            ystart = ylo;
407            tstart = this.TforY(ylo);
408        } else {
409            if (y0 >= yhi) {
410                return false;
411            }
412            ystart = y0;
413            tstart = 0;
414        }
415        if (y1 > yhi) {
416            yend = yhi;
417            tend = TforY(yhi);
418        } else {
419            yend = y1;
420            tend = 1;
421        }
422        boolean hitLo = false;
423        boolean hitHi = false;
424        while (true) {
425            double x = XforT(tstart);
426            if (x < xhi) {
427                if (hitHi || x > xlo) {
428                    return true;
429                }
430                hitLo = true;
431            } else {
432                if (hitLo) {
433                    return true;
434                }
435                hitHi = true;
436            }
437            if (tstart >= tend) {
438                break;
439            }
440            tstart = nextVertical(tstart, tend);
441        }
442        if (hitLo) {
443            //c.record(ystart, yend, direction);
444            c.record(ystart, yend, this.getDirection());
445        }
446        return false;
447    }
448
449    public double refineTforY(double t0, double yt0, double y0) {
450        double t1 = 1;
451        while (true) {
452            double th = (t0 + t1) / 2;
453            if (th == t0 || th == t1) {
454                return t1;
455            }
456            double y = YforT(th);
457            if (y < y0) {
458                t0 = th;
459                yt0 = y;
460            } else if (y > y0) {
461                t1 = th;
462            } else {
463                return t1;
464            }
465        }
466    }
467
468    public boolean findIntersect(CurveObject that, double yrange[], double ymin,
469            int slevel, int tlevel,
470            double s0, double xs0, double ys0,
471            double s1, double xs1, double ys1,
472            double t0, double xt0, double yt0,
473            double t1, double xt1, double yt1) {
474        /*
475         String pad = "        ";
476         pad = pad+pad+pad+pad+pad;
477         pad = pad+pad;
478         System.out.println("----------------------------------------------");
479         System.out.println(pad.substring(0, slevel)+ys0);
480         System.out.println(pad.substring(0, slevel)+ys1);
481         System.out.println(pad.substring(0, slevel)+(s1-s0));
482         System.out.println("-------");
483         System.out.println(pad.substring(0, tlevel)+yt0);
484         System.out.println(pad.substring(0, tlevel)+yt1);
485         System.out.println(pad.substring(0, tlevel)+(t1-t0));
486         */
487        if (ys0 > yt1 || yt0 > ys1) {
488            return false;
489        }
490        if (Math.min(xs0, xs1) > Math.max(xt0, xt1)
491                || Math.max(xs0, xs1) < Math.min(xt0, xt1)) {
492            return false;
493        }
494        // Bounding boxes intersect - back off the larger of
495        // the two subcurves by half until they stop intersecting
496        // (or until they get small enough to switch to a more
497        //  intensive algorithm).
498        if (s1 - s0 > Curve.TMIN) {
499            double s = (s0 + s1) / 2;
500            double xs = this.XforT(s);
501            double ys = this.YforT(s);
502            if (s == s0 || s == s1) {
503                System.out.println("s0 = " + s0);
504                System.out.println("s1 = " + s1);
505                throw new InternalError("no s progress!");
506            }
507            if (t1 - t0 > Curve.TMIN) {
508                double t = (t0 + t1) / 2;
509                double xt = that.XforT(t);
510                double yt = that.YforT(t);
511                if (t == t0 || t == t1) {
512                    System.out.println("t0 = " + t0);
513                    System.out.println("t1 = " + t1);
514                    throw new InternalError("no t progress!");
515                }
516                if (ys >= yt0 && yt >= ys0) {
517                    if (findIntersect(that, yrange, ymin, slevel + 1, tlevel + 1,
518                            s0, xs0, ys0, s, xs, ys,
519                            t0, xt0, yt0, t, xt, yt)) {
520                        return true;
521                    }
522                }
523                if (ys >= yt) {
524                    if (findIntersect(that, yrange, ymin, slevel + 1, tlevel + 1,
525                            s0, xs0, ys0, s, xs, ys,
526                            t, xt, yt, t1, xt1, yt1)) {
527                        return true;
528                    }
529                }
530                if (yt >= ys) {
531                    if (findIntersect(that, yrange, ymin, slevel + 1, tlevel + 1,
532                            s, xs, ys, s1, xs1, ys1,
533                            t0, xt0, yt0, t, xt, yt)) {
534                        return true;
535                    }
536                }
537                if (ys1 >= yt && yt1 >= ys) {
538                    if (findIntersect(that, yrange, ymin, slevel + 1, tlevel + 1,
539                            s, xs, ys, s1, xs1, ys1,
540                            t, xt, yt, t1, xt1, yt1)) {
541                        return true;
542                    }
543                }
544            } else {
545                if (ys >= yt0) {
546                    if (findIntersect(that, yrange, ymin, slevel + 1, tlevel,
547                            s0, xs0, ys0, s, xs, ys,
548                            t0, xt0, yt0, t1, xt1, yt1)) {
549                        return true;
550                    }
551                }
552                if (yt1 >= ys) {
553                    if (findIntersect(that, yrange, ymin, slevel + 1, tlevel,
554                            s, xs, ys, s1, xs1, ys1,
555                            t0, xt0, yt0, t1, xt1, yt1)) {
556                        return true;
557                    }
558                }
559            }
560        } else if (t1 - t0 > Curve.TMIN) {
561            double t = (t0 + t1) / 2;
562            double xt = that.XforT(t);
563            double yt = that.YforT(t);
564            if (t == t0 || t == t1) {
565                System.out.println("t0 = " + t0);
566                System.out.println("t1 = " + t1);
567                throw new InternalError("no t progress!");
568            }
569            if (yt >= ys0) {
570                if (findIntersect(that, yrange, ymin, slevel, tlevel + 1,
571                        s0, xs0, ys0, s1, xs1, ys1,
572                        t0, xt0, yt0, t, xt, yt)) {
573                    return true;
574                }
575            }
576            if (ys1 >= yt) {
577                if (findIntersect(that, yrange, ymin, slevel, tlevel + 1,
578                        s0, xs0, ys0, s1, xs1, ys1,
579                        t, xt, yt, t1, xt1, yt1)) {
580                    return true;
581                }
582            }
583        } else {
584            // No more subdivisions
585            double xlk = xs1 - xs0;
586            double ylk = ys1 - ys0;
587            double xnm = xt1 - xt0;
588            double ynm = yt1 - yt0;
589            double xmk = xt0 - xs0;
590            double ymk = yt0 - ys0;
591            double det = xnm * ylk - ynm * xlk;
592            if (det != 0) {
593                double detinv = 1 / det;
594                double s = (xnm * ymk - ynm * xmk) * detinv;
595                double t = (xlk * ymk - ylk * xmk) * detinv;
596                if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
597                    s = s0 + s * (s1 - s0);
598                    t = t0 + t * (t1 - t0);
599                    if (s < 0 || s > 1 || t < 0 || t > 1) {
600                        System.out.println("Uh oh!");
601                    }
602                    double y = (this.YforT(s) + that.YforT(t)) / 2;
603                    if (y <= yrange[1] && y > yrange[0]) {
604                        yrange[1] = y;
605                        return true;
606                    }
607                }
608            }
609            //System.out.println("Testing lines!");
610        }
611        return false;
612    }
613
614    public int compareTo(CurveObject that, double yrange[]) {
615        /*
616         System.out.println(this+".compareTo("+that+")");
617         System.out.println("target range = "+yrange[0]+"=>"+yrange[1]);
618         */
619        if (order == 1) {
620            return order1.compareTo(that, yrange);
621        }
622        double y0 = yrange[0];
623        double y1 = yrange[1];
624        //y1 = Math.min(Math.min(y1, this.getYBot()), that.getYBot());
625        y1 = Math.min(Math.min(y1, this.getYBot()), that.getYBot());
626        if (y1 <= yrange[0]) {
627            System.err.println("this == " + this);
628            System.err.println("that == " + that);
629            System.out.println("target range = " + yrange[0] + "=>" + yrange[1]);
630            throw new InternalError("backstepping from " + yrange[0] + " to " + y1);
631        }
632        yrange[1] = y1;
633        if (this.getXMax() <= that.getXMin()) {
634            if (this.getXMin() == that.getXMax()) {
635                return 0;
636            }
637            return -1;
638        }
639        if (this.getXMin() >= that.getXMax()) {
640            return 1;
641        }
642        // Parameter s for thi(s) curve and t for tha(t) curve
643        // [st]0 = parameters for top of current section of interest
644        // [st]1 = parameters for bottom of valid range
645        // [st]h = parameters for hypothesis point
646        // [d][xy]s = valuations of thi(s) curve at sh
647        // [d][xy]t = valuations of tha(t) curve at th
648        double s0 = this.TforY(y0);
649        double ys0 = this.YforT(s0);
650        if (ys0 < y0) {
651            s0 = refineTforY(s0, ys0, y0);
652            ys0 = this.YforT(s0);
653        }
654        double s1 = this.TforY(y1);
655        if (this.YforT(s1) < y0) {
656            s1 = refineTforY(s1, this.YforT(s1), y0);
657            //System.out.println("s1 problem!");
658        }
659        double t0 = that.TforY(y0);
660        double yt0 = that.YforT(t0);
661        if (yt0 < y0) {
662            t0 = that.refineTforY(t0, yt0, y0);
663            yt0 = that.YforT(t0);
664        }
665        double t1 = that.TforY(y1);
666        if (that.YforT(t1) < y0) {
667            t1 = that.refineTforY(t1, that.YforT(t1), y0);
668        }
669        double xs0 = this.XforT(s0);
670        double xt0 = that.XforT(t0);
671        double scale = Math.max(Math.abs(y0), Math.abs(y1));
672        double ymin = Math.max(scale * 1E-14, 1E-300);
673        if (Curve.fairlyClose(xs0, xt0)) {
674            double bump = ymin;
675            double maxbump = Math.min(ymin * 1E13, (y1 - y0) * .1);
676            double y = y0 + bump;
677            while (y <= y1) {
678                if (Curve.fairlyClose(this.XforY(y), that.XforY(y))) {
679                    if ((bump *= 2) > maxbump) {
680                        bump = maxbump;
681                    }
682                } else {
683                    y -= bump;
684                    while (true) {
685                        bump /= 2;
686                        double newy = y + bump;
687                        if (newy <= y) {
688                            break;
689                        }
690                        if (Curve.fairlyClose(this.XforY(newy), that.XforY(newy))) {
691                            y = newy;
692                        }
693                    }
694                    break;
695                }
696                y += bump;
697            }
698            if (y > y0) {
699                if (y < y1) {
700                    yrange[1] = y;
701                }
702                return 0;
703            }
704        }
705        //double ymin = y1 * 1E-14;
706        if (ymin <= 0) {
707            System.out.println("ymin = " + ymin);
708        }
709        /*
710         System.out.println("s range = "+s0+" to "+s1);
711         System.out.println("t range = "+t0+" to "+t1);
712         */
713        while (s0 < s1 && t0 < t1) {
714            double sh = this.nextVertical(s0, s1);
715            double xsh = this.XforT(sh);
716            double ysh = this.YforT(sh);
717            double th = that.nextVertical(t0, t1);
718            double xth = that.XforT(th);
719            double yth = that.YforT(th);
720            /*
721             System.out.println("sh = "+sh);
722             System.out.println("th = "+th);
723             */
724            try {
725                if (findIntersect(that, yrange, ymin, 0, 0,
726                        s0, xs0, ys0, sh, xsh, ysh,
727                        t0, xt0, yt0, th, xth, yth)) {
728                    break;
729                }
730            } catch (Throwable t) {
731                System.err.println("Error: " + t);
732                System.err.println("y range was " + yrange[0] + "=>" + yrange[1]);
733                System.err.println("s y range is " + ys0 + "=>" + ysh);
734                System.err.println("t y range is " + yt0 + "=>" + yth);
735                System.err.println("ymin is " + ymin);
736                return 0;
737            }
738            if (ysh < yth) {
739                if (ysh > yrange[0]) {
740                    if (ysh < yrange[1]) {
741                        yrange[1] = ysh;
742                    }
743                    break;
744                }
745                s0 = sh;
746                xs0 = xsh;
747                ys0 = ysh;
748            } else {
749                if (yth > yrange[0]) {
750                    if (yth < yrange[1]) {
751                        yrange[1] = yth;
752                    }
753                    break;
754                }
755                t0 = th;
756                xt0 = xth;
757                yt0 = yth;
758            }
759        }
760        double ymid = (yrange[0] + yrange[1]) / 2;
761        /*
762         System.out.println("final this["+s0+", "+sh+", "+s1+"]");
763         System.out.println("final    y["+ys0+", "+ysh+"]");
764         System.out.println("final that["+t0+", "+th+", "+t1+"]");
765         System.out.println("final    y["+yt0+", "+yth+"]");
766         System.out.println("final order = "+orderof(this.XforY(ymid),
767         that.XforY(ymid)));
768         System.out.println("final range = "+yrange[0]+"=>"+yrange[1]);
769         */
770        /*
771         System.out.println("final sx = "+this.XforY(ymid));
772         System.out.println("final tx = "+that.XforY(ymid));
773         System.out.println("final order = "+orderof(this.XforY(ymid),
774         that.XforY(ymid)));
775         */
776        return Curve.orderof(this.XforY(ymid), that.XforY(ymid));
777    }
778
779    public int getSegment(double coords[]) {
780        switch (order) {
781            case 0:
782                return order0.getSegment(coords);
783            case 1:
784                return order1.getSegment(coords);
785            case 2:
786                return order2.getSegment(coords);
787            case 3:
788                return order3.getSegment(coords);
789            default:
790                return -7;
791        }
792
793    }
794
795    public Object getSubCurve(double ystart, double yend, int dir) {    //did return Curve
796        switch (order) {
797            case 0:
798                return order0.getSubCurve(ystart, yend, dir);
799            case 1:
800                return order1.getSubCurve(ystart, yend, dir);
801            case 2:
802                return order2.getSubCurve(ystart, yend, dir);
803            case 3:
804                return order3.getSubCurve(ystart, yend, dir);
805            default:
806                return null;
807        }
808    }
809
810    public void enlarge(Rectangle2D r) {
811        switch (order) {
812            case 0:
813                order0.enlarge(r);
814            case 1:
815                order1.enlarge(r);
816            case 2:
817                order2.enlarge(r);
818            case 3:
819                order3.enlarge(r);
820            default:
821                return;
822        }
823    }
824
825    public Object getWithDirection(int direction) {
826        //return (this.direction == direction ? this : getReversedCurve());
827        //return (this.getDirection() == direction ? this : getReversedCurve());
828        switch (order) {
829            case 0:
830                return order0.getWithDirection(direction);
831            case 1:
832                return order1.getWithDirection(direction);
833            case 2:
834                return order2.getWithDirection(direction);
835            case 3:
836                return order3.getWithDirection(direction);
837            default:
838                return null;
839        }
840    }
841}