Java > Open Source Codes > org > apache > batik > gvt > text > GlyphLayout


1 /*
2
3    Copyright 2001-2004 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.gvt.text;
19
20 import java.awt.BasicStroke ;
21 import java.awt.Graphics2D ;
22 import java.awt.Shape ;
23 import java.awt.Stroke ;
24 import java.awt.font.FontRenderContext ;
25 import java.awt.font.TextAttribute ;
26 import java.awt.geom.AffineTransform ;
27 import java.awt.geom.Area ;
28 import java.awt.geom.GeneralPath ;
29 import java.awt.geom.PathIterator ;
30 import java.awt.geom.Point2D ;
31 import java.awt.geom.Rectangle2D ;
32 import java.text.AttributedCharacterIterator ;
33 import java.text.CharacterIterator ;
34 import java.util.HashSet ;
35 import java.util.List ;
36 import java.util.Set ;
37
38 import org.apache.batik.gvt.font.AWTGVTFont;
39 import org.apache.batik.gvt.font.AltGlyphHandler;
40 import org.apache.batik.gvt.font.GVTFont;
41 import org.apache.batik.gvt.font.GVTGlyphMetrics;
42 import org.apache.batik.gvt.font.GVTGlyphVector;
43 import org.apache.batik.gvt.font.GVTLineMetrics;
44 import org.apache.batik.gvt.TextNode;
45 import org.apache.batik.gvt.text.GVTAttributedCharacterIterator;
46 import org.apache.batik.gvt.text.TextHit;
47 import org.apache.batik.gvt.text.TextSpanLayout;
48
49 /**
50  * Implementation of TextSpanLayout which uses java.awt.font.GlyphVector.
51  * @see org.apache.batik.gvt.text.TextSpanLayout
52  *
53  * @author <a HREF="mailto:bill.haneman@ireland.sun.com">Bill Haneman</a>
54  * @version $Id: GlyphLayout.java,v 1.63 2005/03/27 08:58:35 cam Exp $
55  */
56 public class GlyphLayout implements TextSpanLayout {
57
58     public static final char SOFT_HYPHEN = 0x00AD;
59     public static final char ZERO_WIDTH_SPACE = 0x200B;
60     public static final char ZERO_WIDTH_JOINER = 0x200D;
61     public static final char SPACE = ' ';
62
63     private GVTGlyphVector gv;
64     private GVTFont font;
65     private GVTLineMetrics metrics;
66     private AttributedCharacterIterator aci;
67     private FontRenderContext frc;
68     private Point2D advance;
69     private Point2D offset;
70     private float xScale=1;
71     private float yScale=1;
72     private Point2D prevCharPosition;
73     private TextPath textPath;
74     private Point2D textPathAdvance;
75     private int [] charMap;
76     private boolean vertical, adjSpacing=true;
77     private float [] glyphAdvances;
78     private boolean isAltGlyph; //false
79
80     // When layoutApplied is false it means that the glyph positions
81 // are different from where they would be if you did
82 // doExplicitGlyphLayout().
83 private boolean layoutApplied = false;
84     // When spacingApplied is false it means that xScale, yScale and
85 // kerning/wordspacing stuff haven't been applied. This can
86 // be rectified by calling adjustTextSpacing(). Note that when
87 // spacing is actually used layoutApplied will be cleared it
88 // is not garunteed that applying text spacing will cause it to
89 // be cleared (it will only be cleared if the glyphs move).
90 private boolean spacingApplied = false;
91     // When pathApplied is false it means that the text has not been
92 // layed out on the associated text path (if any). If there is an
93 // associated text path then this will clear both layoutApplied
94 // and spacing applied but neither will be touched if no text path
95 // is present.
96 private boolean pathApplied = false;
97
98
99     public static final AttributedCharacterIterator.Attribute FLOW_LINE_BREAK
100         = GVTAttributedCharacterIterator.TextAttribute.FLOW_LINE_BREAK;
101
102     public static final AttributedCharacterIterator.Attribute FLOW_PARAGRAPH
103         = GVTAttributedCharacterIterator.TextAttribute.FLOW_PARAGRAPH;
104
105     public static final AttributedCharacterIterator.Attribute
106         FLOW_EMPTY_PARAGRAPH
107         = GVTAttributedCharacterIterator.TextAttribute.FLOW_EMPTY_PARAGRAPH;
108
109     public static final AttributedCharacterIterator.Attribute LINE_HEIGHT
110         = GVTAttributedCharacterIterator.TextAttribute.LINE_HEIGHT;
111
112     public static final AttributedCharacterIterator.Attribute
113         TEXT_COMPOUND_DELIMITER
114         = GVTAttributedCharacterIterator.TextAttribute.TEXT_COMPOUND_DELIMITER;
115
116     public static final AttributedCharacterIterator.Attribute
117         VERTICAL_ORIENTATION
118         = GVTAttributedCharacterIterator.TextAttribute.VERTICAL_ORIENTATION;
119
120     public static final
121         AttributedCharacterIterator.Attribute VERTICAL_ORIENTATION_ANGLE =
122        GVTAttributedCharacterIterator.TextAttribute.VERTICAL_ORIENTATION_ANGLE;
123
124     public static final
125         AttributedCharacterIterator.Attribute HORIZONTAL_ORIENTATION_ANGLE =
126      GVTAttributedCharacterIterator.TextAttribute.HORIZONTAL_ORIENTATION_ANGLE;
127
128     private static final AttributedCharacterIterator.Attribute X
129         = GVTAttributedCharacterIterator.TextAttribute.X;
130
131     private static final AttributedCharacterIterator.Attribute Y
132         = GVTAttributedCharacterIterator.TextAttribute.Y;
133
134     private static final AttributedCharacterIterator.Attribute DX
135         = GVTAttributedCharacterIterator.TextAttribute.DX;
136
137     private static final AttributedCharacterIterator.Attribute DY
138         = GVTAttributedCharacterIterator.TextAttribute.DY;
139
140     private static final AttributedCharacterIterator.Attribute ROTATION
141         = GVTAttributedCharacterIterator.TextAttribute.ROTATION;
142
143     private static final AttributedCharacterIterator.Attribute BASELINE_SHIFT
144         = GVTAttributedCharacterIterator.TextAttribute.BASELINE_SHIFT;
145
146     private static final AttributedCharacterIterator.Attribute WRITING_MODE
147         = GVTAttributedCharacterIterator.TextAttribute.WRITING_MODE;
148
149     private static final Integer WRITING_MODE_TTB
150         = GVTAttributedCharacterIterator.TextAttribute.WRITING_MODE_TTB;
151
152     private static final Integer ORIENTATION_AUTO
153         = GVTAttributedCharacterIterator.TextAttribute.ORIENTATION_AUTO;
154
155     public static final AttributedCharacterIterator.Attribute GVT_FONT
156         = GVTAttributedCharacterIterator.TextAttribute.GVT_FONT;
157
158     static protected Set runAtts = new HashSet ();
159
160     static {
161         runAtts.add(X);
162         runAtts.add(Y);
163         runAtts.add(DX);
164         runAtts.add(DY);
165         runAtts.add(ROTATION);
166         runAtts.add(BASELINE_SHIFT);
167     }
168
169     static protected Set szAtts = new HashSet ();
170
171     static {
172         szAtts.add(TextAttribute.SIZE);
173         szAtts.add(GVT_FONT);
174         szAtts.add(LINE_HEIGHT);
175     }
176
177
178     /**
179      * Creates the specified text layout using the
180      * specified AttributedCharacterIterator and rendering context.
181      *
182      * @param aci the AttributedCharacterIterator whose text is to
183      * be laid out
184      * @param charMap Indicates how chars in aci map to original
185      * text char array.
186      * @param offset The offset position of this text layout
187      * @param frc the FontRenderContext to use for generating glyphs.
188      */
189     public GlyphLayout(AttributedCharacterIterator aci,
190                        int [] charMap,
191                        Point2D offset,
192                        FontRenderContext frc) {
193
194         this.aci = aci;
195         this.frc = frc;
196         this.offset = offset;
197         this.font = getFont();
198         this.charMap = charMap;
199
200         this.metrics = font.getLineMetrics
201             (aci, aci.getBeginIndex(), aci.getEndIndex(), frc);
202
203         // create the glyph vector
204 this.gv = null;
205         this.aci.first();
206         this.vertical = (aci.getAttribute(WRITING_MODE) == WRITING_MODE_TTB);
207         this.textPath = (TextPath) aci.getAttribute
208             (GVTAttributedCharacterIterator.TextAttribute.TEXTPATH);
209
210         AltGlyphHandler altGlyphHandler
211             = (AltGlyphHandler)this.aci.getAttribute
212             (GVTAttributedCharacterIterator.TextAttribute.ALT_GLYPH_HANDLER);
213         if (altGlyphHandler != null) {
214             // this must be an altGlyph text element, try and create
215 // the alternate glyphs
216 this.gv = altGlyphHandler.createGlyphVector
217                 (frc, this.font.getSize(), this.aci);
218             if ( this.gv != null ){
219                 this.isAltGlyph = true;
220             }
221         }
222         if (this.gv == null) {
223             // either not an altGlyph or the altGlyphHandler failed to
224 // create a glyph vector
225 this.gv = font.createGlyphVector(frc, this.aci);
226         }
227     }
228
229
230     public GVTGlyphVector getGlyphVector() {
231         return this.gv;
232     }
233
234
235     /**
236      * Returns the current text position at the beginning
237      * of glyph layout, before the application of explicit
238      * glyph positioning attributes.
239      */
240     public Point2D getOffset() {
241         return offset;
242     }
243
244     /**
245      * Sets the scaling factor to use for string. if ajdSpacing is
246      * true then only the spacing between glyphs will be adjusted
247      * otherwise the glyphs and the spaces between them will be
248      * adjusted. Only the scale factor in the progression direction
249      * is used (x for horizontal text, y for vertical text
250      * ).
251      * @param xScale Scale factor to apply in X direction.
252      * @param yScale Scale factor to apply in Y direction.
253      * @param adjSpacing True if only spaces should be adjusted.
254      */
255     public void setScale(float xScale, float yScale, boolean adjSpacing) {
256         // Fix the off axis scale factor.
257 if (vertical) xScale = 1;
258         else yScale = 1;
259
260         if ((xScale != this.xScale) ||
261             (yScale != this.yScale) ||
262             (adjSpacing != this.adjSpacing)) {
263             this.xScale = xScale;
264             this.yScale = yScale;
265             this.adjSpacing = adjSpacing;
266
267             // We don't affect layoutApplied directly...
268 // System.out.println("layoutApplied: " + layoutApplied);
269
270             // However if we did path layout or spacing it's all junk now...
271 spacingApplied = false;
272             glyphAdvances = null;
273             pathApplied = false;
274         }
275     }
276
277     /**
278      * Sets the text position used for the implicit origin
279      * of glyph layout. Ignored if multiple explicit glyph
280      * positioning attributes are present in ACI
281      * (e.g. if the aci has multiple X or Y values).
282      */
283     public void setOffset(Point2D offset) {
284         // System.err.println("SetOffset: " + offset + " - " + this.offset);
285 if ((offset.getX() != this.offset.getX()) ||
286             (offset.getY() != this.offset.getY())) {
287             if ((layoutApplied)||(spacingApplied)) {
288                 // Already layed out need to shift glyph positions to
289 // account for new offset.
290 float dx = (float)(offset.getX()-this.offset.getX());
291                 float dy = (float)(offset.getY()-this.offset.getY());
292                 int numGlyphs = gv.getNumGlyphs();
293
294                 // System.out.println("DXY: [" + dx +","+dy+"]");
295 float [] gp = gv.getGlyphPositions(0, numGlyphs+1, null);
296                 Point2D.Float pos = new Point2D.Float ();
297                 for (int i=0; i<=numGlyphs; i++) {
298                     pos.x = gp[2*i ]+dx;
299                     pos.y = gp[2*i+1]+dy;
300                     gv.setGlyphPosition(i, pos);
301                 }
302             }
303
304             // When not layed out (or after updating) just set the new
305 // offset this will be factored in for any future layout
306 // operations.
307 this.offset = offset;
308
309             // We don't affect layoutApplied or spacingApplied since
310 // they both work off the offset value.
311
312             // However if we did path layout it's all junk now...
313 pathApplied = false;
314         }
315     }
316
317     public GVTGlyphMetrics getGlyphMetrics(int glyphIndex) {
318         return gv.getGlyphMetrics(glyphIndex);
319     }
320
321     /**
322      * Returns true if the advance direction of this text is vertical.
323      */
324     public boolean isVertical() {
325         return vertical;
326     }
327
328     /**
329      * Returns true if this layout in on a text path.
330      */
331     public boolean isOnATextPath() {
332         return (textPath != null);
333     }
334
335
336     /**
337      * Returns the number of glyphs in this layout.
338      */
339     public int getGlyphCount() {
340         return gv.getNumGlyphs();
341     }
342
343
344     /**
345      * Returns the number of chars represented by the glyphs within the
346      * specified range.
347      *
348      * @param startGlyphIndex The index of the first glyph in the range.
349      * @param endGlyphIndex The index of the last glyph in the range.
350      *
351      * @return The number of chars.
352      */
353     public int getCharacterCount(int startGlyphIndex, int endGlyphIndex) {
354         return gv.getCharacterCount(startGlyphIndex, endGlyphIndex);
355     }
356
357     /**
358      * Returns true if the text direction in this layout is from left to right.
359      */
360     public boolean isLeftToRight() {
361         aci.first();
362         int bidiLevel =
363             ((Integer )aci.getAttribute
364              (GVTAttributedCharacterIterator.TextAttribute.BIDI_LEVEL))
365             .intValue();
366
367         // Check if low bit is set if not then we are left to right
368 // (even bidi level).
369 return ((bidiLevel&0x01) == 0);
370     }
371
372
373     /**
374      * This method makes certain that the layout has been
375      * completed at this point (much of the layout is done lazily).
376      */
377     private final void syncLayout() {
378         if (!pathApplied) {
379             // System.out.println("Doing Path Layout: " + this);
380 doPathLayout();
381         }
382     }
383
384     /**
385      * Paints the text layout using the
386      * specified Graphics2D and rendering context.
387      * @param g2d the Graphics2D to use
388      */
389     public void draw(Graphics2D g2d) {
390         syncLayout();
391         gv.draw(g2d, aci);
392     }
393
394     /**
395      * Returns the current text position at the completion
396      * of glyph layout.
397      */
398     public Point2D getAdvance2D() {
399         adjustTextSpacing();
400         return advance;
401     }
402
403
404     /**
405      * Returns the outline of the completed glyph layout.
406      */
407     public Shape getOutline() {
408         syncLayout();
409
410         return gv.getOutline();
411     }
412
413     public float [] getGlyphAdvances() {
414         if (glyphAdvances != null)
415             return glyphAdvances;
416
417         if (!spacingApplied)
418             // This will layout the text if needed.
419 adjustTextSpacing();
420
421         int numGlyphs = gv.getNumGlyphs();
422         float [] glyphPos = gv.getGlyphPositions(0, numGlyphs+1, null);
423         glyphAdvances = new float[numGlyphs+1];
424         int off = 0;
425         if (isVertical())
426             off = 1;
427
428         float start = glyphPos[off];
429         for (int i=0; i<numGlyphs+1; i++) {
430             glyphAdvances[i] = glyphPos[i+i+off]-start;
431         }
432         return glyphAdvances;
433     }
434
435     /**
436      * Returns the outline of the specified decorations on the glyphs,
437      * @param decorationType an integer indicating the type(s) of decorations
438      * included in this shape. May be the result of "OR-ing" several
439      * values together:
440      * e.g. <tt>DECORATION_UNDERLINE | DECORATION_STRIKETHROUGH</tt>
441      */
442     public Shape getDecorationOutline(int decorationType) {
443         syncLayout();
444
445         Shape g = new GeneralPath ();
446         if ((decorationType & DECORATION_UNDERLINE) != 0) {
447              ((GeneralPath ) g).append(getUnderlineShape(), false);
448         }
449         if ((decorationType & DECORATION_STRIKETHROUGH) != 0) {
450              ((GeneralPath ) g).append(getStrikethroughShape(), false);
451         }
452         if ((decorationType & DECORATION_OVERLINE) != 0) {
453              ((GeneralPath ) g).append(getOverlineShape(), false);
454         }
455         return g;
456     }
457
458     /**
459      * Returns the rectangular bounds of the completed glyph layout.
460      */
461     public Rectangle2D getBounds2D() {
462         syncLayout();
463         return gv.getBounds2D(aci);
464     }
465
466     /**
467      * Returns the rectangular bounds of the completed glyph layout,
468      * inclusive of "decoration" (underline, overline, etc.)
469      */
470     public Rectangle2D getGeometricBounds() {
471         syncLayout();
472         Rectangle2D gvB, decB;
473         gvB = gv.getGeometricBounds();
474         decB = getDecorationOutline(DECORATION_ALL).getBounds2D();
475         return gvB.createUnion(decB);
476     }
477
478     /**
479      * Returns the position to used when drawing a text run after this one.
480      * It takes into account the text path layout if there is one.
481      */
482     public Point2D getTextPathAdvance() {
483         syncLayout();
484         if (textPath != null) {
485             return textPathAdvance;
486         } else {
487             return getAdvance2D();
488         }
489     }
490
491
492     /**
493      * Returns the index of the first glyph that has the specified char index.
494      *
495      * @param charIndex The original index of the character in the text node's
496      * text string.
497      * @return The index of the matching glyph in this layout's glyph vector,
498      * or -1 if a matching glyph could not be found.
499      */
500     public int getGlyphIndex(int charIndex) {
501         int numGlyphs = getGlyphCount();
502         int j=0;
503         for (int i = 0; i < numGlyphs; i++) {
504             int count = getCharacterCount(i, i);
505             for (int n=0; n<count; n++) {
506                 int glyphCharIndex = charMap[j++];
507                 if (charIndex == glyphCharIndex)
508                     return i;
509                 if (j >= charMap.length)
510                     return -1;
511             }
512         }
513         return -1;
514     }
515
516     /**
517      * Returns the index of the last glyph that has the specified char index.
518      *
519      * @param charIndex The original index of the character in the text node's
520      * text string.
521      * @return The index of the matching glyph in this layout's glyph vector,
522      * or -1 if a matching glyph could not be found.
523      */
524     public int getLastGlyphIndex(int charIndex) {
525         int numGlyphs = getGlyphCount();
526         int j=charMap.length-1;
527         for (int i = numGlyphs-1; i >= 0; --i) {
528             int count = getCharacterCount(i, i);
529             for (int n=0; n<count; n++) {
530                 int glyphCharIndex = charMap[j--];
531                 if (charIndex == glyphCharIndex) return i;
532                 if (j < 0) return -1;
533             }
534         }
535         return -1;
536     }
537
538
539     /**
540      * Return the angle value according to the orientation
541      * of the character.
542      */
543     public double getComputedOrientationAngle(int index){
544
545         if ( isGlyphOrientationAuto() ){
546             if (isVertical()) {
547                 char ch = aci.setIndex(index);
548                 if (isLatinChar(ch))
549                     return 90.0;
550                 else
551                     return 0.0;
552             }
553             return 0.0;
554         }
555         else{
556             return getGlyphOrientationAngle();
557         }
558     }
559
560    /**
561      * Returns a Shape which encloses the currently selected glyphs
562      * as specified by the character indices.
563      *
564      * @param beginCharIndex the index of the first char in the
565      * contiguous selection.
566      * @param endCharIndex the index of the last char in the
567      * contiguous selection.
568      * @return The highlight shape or null if the spacified char range
569      * does not overlap with the chars in this layout. */
570     public Shape getHighlightShape(int beginCharIndex, int endCharIndex) {
571         syncLayout();
572
573         if (beginCharIndex > endCharIndex) {
574             int temp = beginCharIndex;
575             beginCharIndex = endCharIndex;
576             endCharIndex = temp;
577         }
578         GeneralPath shape = null;
579         int numGlyphs = getGlyphCount();
580
581         Point2D.Float [] topPts = new Point2D.Float [2*numGlyphs];
582         Point2D.Float [] botPts = new Point2D.Float [2*numGlyphs];
583
584         int ptIdx = 0;
585
586         int currentChar = 0;
587         for (int i = 0; i < numGlyphs; i++) {
588             int glyphCharIndex = charMap[currentChar];
589             if ((glyphCharIndex >= beginCharIndex) &&
590                 (glyphCharIndex <= endCharIndex) &&
591                 gv.isGlyphVisible(i)) {
592                     
593                 Shape gbounds = gv.getGlyphLogicalBounds(i);
594                 if (gbounds != null) {
595                     // We got something...
596 if (shape == null)
597                         shape = new GeneralPath ();
598
599                     // We are pretty dumb here we assume that we always
600 // get back polygons with four sides to them if
601 // isn't met we are SOL.
602 float [] pts = new float[6];
603                     int count = 0;
604                     int type = -1;
605
606                     PathIterator pi = gbounds.getPathIterator(null);
607                     Point2D.Float firstPt = null;
608
609                     while (!pi.isDone()) {
610                         type = pi.currentSegment(pts);
611                         if ((type == PathIterator.SEG_MOVETO) ||
612                             (type == PathIterator.SEG_LINETO)) {
613                             // LINETO or MOVETO
614 if (count > 4) break; // too many lines...
615 if (count == 4) {
616                                 // make sure we are just closing it..
617 if ((firstPt == null) ||
618                                     (firstPt.x != pts[0]) ||
619                                     (firstPt.y != pts[1]))
620                                     break;
621                             } else {
622                                 Point2D.Float pt;
623                                 pt = new Point2D.Float (pts[0], pts[1]);
624                                 if (count == 0) firstPt = pt;
625                                 // Use sides of rectangle...
626 switch (count) {
627                                 case 0: botPts[ptIdx] = pt; break;
628                                 case 1: topPts[ptIdx] = pt; break;
629                                 case 2: topPts[ptIdx+1] = pt; break;
630                                 case 3: botPts[ptIdx+1] = pt; break;
631                                 }
632                             }
633                         } else if (type == PathIterator.SEG_CLOSE) {
634                                 // Close in the wrong spot?
635 if ((count < 4) || (count > 5)) break;
636                         } else {
637                             // QUADTO or CUBETO
638 break;
639                         }
640
641                         count++;
642                         pi.next();
643                     }
644                     if (pi.isDone()) {
645                         // Sucessfully Expressed as a quadralateral...
646 if ((botPts[ptIdx]!=null) &&
647                             ((topPts[ptIdx].x != topPts[ptIdx+1].x) ||
648                              (topPts[ptIdx].y != topPts[ptIdx+1].y)))
649                             // box isn't empty so use it's points...
650 ptIdx += 2;
651                     } else {
652                         // System.out.println("Type: " + type +
653 // " count: " + count);
654 // Wasn't a quadralateral so just add it don't try
655 // and merge it...
656 addPtsToPath(shape, topPts, botPts, ptIdx);
657                         ptIdx = 0;
658                         shape.append(gbounds, false);
659                     }
660                 }
661             }
662             currentChar += getCharacterCount(i, i);
663             if (currentChar >= charMap.length)
664                 currentChar = charMap.length-1;
665         }
666         addPtsToPath(shape, topPts, botPts, ptIdx);
667
668         return shape;
669     }
670
671     public static final float eps = 0.00001f;
672     public static boolean epsEQ(double a, double b) {
673         return ((a+eps > b) && (a-eps < b));
674     }
675
676     public static int makeConvexHull(Point2D.Float [] pts, int numPts) {
677         // Sort the Pts in X...
678 Point2D.Float tmp;
679         // System.out.print("Sorting...");
680 for (int i=1; i<numPts; i++) {
681             // Simple bubble sort (numPts should be small so shouldn't
682 // be too bad.).
683 if ((pts[i].x < pts[i-1].x) ||
684                 ((pts[i].x == pts[i-1].x) && (pts[i].y < pts[i-1].y))) {
685                 tmp = pts[i];
686                 pts[i] = pts[i-1];
687                 pts[i-1] = tmp;
688                 i=0;
689                 continue;
690             }
691         }
692
693         // System.out.println("Sorted");
694
695         Point2D.Float pt0 = pts[0];
696         Point2D.Float pt1 = pts[numPts-1];
697         Point2D.Float dxdy = new Point2D.Float (pt1.x-pt0.x, pt1.y-pt0.y);
698         float soln, c = dxdy.y*pt0.x-dxdy.x*pt0.y;
699
700         Point2D.Float [] topList = new Point2D.Float [numPts];
701         Point2D.Float [] botList = new Point2D.Float [numPts];
702         botList[0] = topList[0] = pts[0];
703         int nTopPts=1;
704         int nBotPts=1;
705         for (int i=1; i<numPts-1; i++) {
706             Point2D.Float pt = pts[i];
707             soln = dxdy.x*pt.y-dxdy.y*pt.x+c;
708             if (soln < 0) {
709                 // Below line goes into bot pt list...
710 while (nBotPts >= 2) {
711                     pt0 = botList[nBotPts-2];
712                     pt1 = botList[nBotPts-1];
713                     float dx = pt1.x-pt0.x;
714                     float dy = pt1.y-pt0.y;
715                     float c0 = dy*pt0.x-dx*pt0.y;
716                     soln = dx*pt.y-dy*pt.x+c0;
717                     if (soln > eps) // Left turn add and we are done..
718 break;
719                     if (soln > -eps) {
720                         // On line take lowest Y of two and keep going
721 if (pt1.y < pt.y) pt = pt1;
722                         nBotPts--;
723                         break;
724                     }
725                     // right turn drop prev pt;
726 nBotPts--;
727                 }
728                 botList[nBotPts++] = pt;
729             } else {
730                 // Above line goes into top pt list...
731 while (nTopPts >= 2) {
732                     pt0 = topList[nTopPts-2];
733                     pt1 = topList[nTopPts-1];
734                     float dx = pt1.x-pt0.x;
735                     float dy = pt1.y-pt0.y;
736                     float c0 = dy*pt0.x-dx*pt0.y;
737                     soln = dx*pt.y-dy*pt.x+c0;
738                     if (soln < -eps) // Right turn add and check next point.
739 break;
740                     if (soln < eps) {
741                         // On line take greatest Y of two and keep going
742 if (pt1.y > pt.y) pt = pt1;
743                         nTopPts--;
744                         break;
745                     }
746                     // left turn drop prev pt;
747 nTopPts--;
748                 }
749                 topList[nTopPts++] = pt;
750             }
751         }
752
753         // Check last point in both sets...
754 Point2D.Float pt = pts[numPts-1];
755         while (nBotPts >= 2) {
756             pt0 = botList[nBotPts-2];
757             pt1 = botList[nBotPts-1];
758             float dx = pt1.x-pt0.x;
759             float dy = pt1.y-pt0.y;
760             float c0 = dy*pt0.x-dx*pt0.y;
761             soln = dx*pt.y-dy*pt.x+c0;
762             if (soln > eps)
763                 // Left turn add and we are done..
764 break;
765             if (soln > -eps) {
766                 // On line take lowest Y of two and keep going
767 if (pt1.y >= pt.y) nBotPts--;
768                 break;
769             }
770             // right turn drop prev pt;
771 nBotPts--;
772         }
773
774         while (nTopPts >= 2) {
775             pt0 = topList[nTopPts-2];
776             pt1 = topList[nTopPts-1];
777             float dx = pt1.x-pt0.x;
778             float dy = pt1.y-pt0.y;
779             float c0 = dy*pt0.x-dx*pt0.y;
780             soln = dx*pt.y-dy*pt.x+c0;
781             if (soln < -eps)
782                 // Right turn done...
783 break;
784             if (soln < eps) {
785