| //////////////////////////////////////////////////////////////////////////////// |
| // |
| // Licensed to the Apache Software Foundation (ASF) under one or more |
| // contributor license agreements. See the NOTICE file distributed with |
| // this work for additional information regarding copyright ownership. |
| // The ASF licenses this file to You under the Apache License, Version 2.0 |
| // (the "License"); you may not use this file except in compliance with |
| // the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| //////////////////////////////////////////////////////////////////////////////// |
| package flashx.textLayout.utils |
| { |
| import flash.geom.Rectangle; |
| |
| import flashx.textLayout.debug.Debugging; |
| import flashx.textLayout.debug.assert; |
| import flashx.textLayout.elements.FlowElement; |
| import flashx.textLayout.elements.FlowLeafElement; |
| import flashx.textLayout.tlf_internal; |
| |
| use namespace tlf_internal; |
| |
| [ExcludeClass] |
| /** |
| * The HitTestArea class is a lightweight implementation of the Warnock |
| * algorithm for rectangles. It is used for hit-testing in FlowElements, which |
| * may contain multiple child elements. The algorithm attempts to set the logical |
| * midpoint to be outside of a bounding rectangle to avoid having to split too many rectangles. |
| * Note that the code is optimized for non-overlapping rectangles; |
| * the determination of the logical midpoint does not work well for overlapping |
| * rectangles because the algorithm breaks once it found a rectangle that contains |
| * the geometric midpoint. |
| * |
| * The pseudocode for this algorithm is: |
| * |
| * if !(point in this rectangle) return false; |
| * if !(hasKids) return true; |
| * determine the quadrant where the point is in (top left "tl", top right "tr", |
| * bottom left "bl", or bottom right "br"); |
| * if this[quadrant] == null, return false; // no rectangle covers this area |
| * else return this[quadrant].hitTest(x,y); |
| * |
| * To avoid having to create a 4-element array for the four quadrants, the code |
| * constructs the property name and accesses the property with dynamic lookup. |
| */ |
| public class HitTestArea |
| { |
| private var tl:HitTestArea = null; // top left quadrant // NO PMD |
| private var tr:HitTestArea = null; // top right quadrant // NO PMD |
| private var bl:HitTestArea = null; // bottom left quadrant // NO PMD |
| private var br:HitTestArea = null; // bottom right quadrant // NO PMD |
| |
| private var _rect:Rectangle; // the bounding rectangle |
| private var _xm:Number; // logical midpoint |
| private var _ym:Number; |
| |
| /** |
| * The owning FlowElement is the element whose area this HitTestArea |
| * covers. This variable is set for a rectangle if the structure passed |
| * in to the constructor contains an "owner" property. If it is null, |
| * the instance has child quadrants. |
| */ |
| private var _owner:FlowElement = null; |
| |
| CONFIG::debug |
| { |
| static private var _depth:int = 0; |
| /** |
| * This array takes the counts for recursion depths on hit testing. |
| */ |
| static public const depths:Array = []; |
| } |
| /** |
| * Create a HitTestArea with an object containing enumerable property objects as a rectangle |
| * in a "rect" property, and a a FlowElement in its "owner" property. First, |
| * determine the bounding rectangle; then, determine the midpoint, and fill |
| * in each quadrant with the intersecting rectangles. |
| * @param obj An object containing {rect:Rectangle, owner:FlowElement} objects as property values. |
| */ |
| public function HitTestArea(objects:Object) |
| { |
| initialize(objects); |
| } |
| |
| /** @private */ |
| tlf_internal function initialize(objects:Object):void |
| { |
| var obj:Object; |
| // determine the number of objects; all we need to know is 0, 1, or more |
| var count:int = 0; |
| if (objects) |
| { |
| for (obj in objects) |
| { |
| if (++count > 1) |
| break; |
| } |
| } |
| |
| if (count == 0) |
| { |
| _rect = new Rectangle(); |
| _xm = _ym = 0; |
| return; |
| } |
| |
| // Determine the bounding rectangle |
| // if the object only has one element, it is easy |
| if (count == 1) |
| { |
| for each (obj in objects) |
| { |
| _rect = obj.rect; |
| _xm = _rect.left; |
| _ym = _rect.top; |
| _owner = obj.owner; |
| CONFIG::debug { assert(_owner != null, "No owner given"); } |
| return; |
| } |
| } |
| |
| var r:Rectangle; |
| // if more than one element, we need to calulate and fill |
| for each (obj in objects) |
| { |
| r = obj.rect; |
| if (!_rect) |
| _rect = r; |
| else |
| _rect = _rect.union(r); |
| } |
| |
| // Set the geometric midpoint |
| _xm = Math.ceil(_rect.left + _rect.width / 2); |
| _ym = Math.ceil(_rect.top + _rect.height / 2); |
| |
| // Hard stop here: if the bounding rectangle is < 3 pixels in any direction, |
| // we consider it to be a single rectangle. |
| if (_rect.width <= 3 || _rect.height <= 3) |
| { |
| // Here, we set the owner to the first element's owner |
| for each (obj in objects) |
| { |
| _owner = obj.owner; |
| CONFIG::debug { assert(_owner != null, "No owner given"); } |
| return; |
| } |
| } |
| |
| // Determine the logical midpoint. This point is as close to |
| // the geometric midpoint as possible. If the midpoint is inside |
| // a rectangle, the midpoint is adjusted to the nearest point |
| // outside of the rectangle if possible to avoid excessive |
| // splitting of rectangles. The first point is used as the new |
| // midpoint to avoid having to deal with overlapping rectangles, |
| // which should usually not appear at all. |
| for each (obj in objects) |
| { |
| r = obj.rect; |
| if (r.equals(_rect)) |
| continue; |
| |
| if (r.contains(_xm, _ym)) |
| { |
| // The midpoint is over a rectangle; find the closest |
| // rectangle boundary and move the midpoint there |
| var dxLower:Number = _xm - r.left; |
| var dxUpper:Number = r.right - _xm; |
| var dyLower:Number = _ym - r.top; |
| var dyUpper:Number = r.bottom - _ym; |
| // this may lead to _xm and/or _ym being equal to left/top |
| _xm = (dxLower > dxUpper) ? _xm + dxUpper : _xm - dxLower; |
| _ym = (dyLower > dyUpper) ? _ym + dyUpper : _ym - dyLower; |
| // this should be changed if overlapping rectangles need to be supported |
| // in that case, all rectangles that have a hit shouldd be checked to |
| // determine the closest boundary |
| break; |
| } |
| } |
| |
| // Insert all rectangles into the respective quadrants |
| var quadrant:Rectangle = new Rectangle(_rect.left, _rect.top, _xm - _rect.left, _ym - _rect.top); |
| addQuadrant(objects, "tl", quadrant); |
| quadrant.left = _xm; |
| quadrant.right = _rect.right; |
| addQuadrant(objects, "tr", quadrant); |
| quadrant.left = _rect.left; |
| quadrant.top = _ym; |
| quadrant.right = _xm; |
| quadrant.bottom = _rect.bottom; |
| addQuadrant(objects, "bl", quadrant); |
| quadrant.left = _xm; |
| quadrant.right = _rect.right; |
| addQuadrant(objects, "br", quadrant); |
| } |
| |
| /** |
| * Do a hit test. If the point is within this rectangle, determine |
| * the quadrant of the point. If the quadrant is empty, the hit test |
| * is true. If not, recurse into that quadrant. |
| * @param x the X coordinate |
| * @param y the Y coordinate |
| * @return the owner if the hit test succeeds, null otherwise |
| */ |
| public function hitTest(x:Number, y:Number):FlowElement |
| { |
| if (!_rect.contains(x, y)) |
| return null; |
| // if there are no kids (the owner is set), the rectangle has been hit |
| // no need to attempt to retrieve the quadrant |
| if (_owner) |
| return _owner; |
| // determine quadrant |
| var quadrantName:String = (y < _ym) ? "t" : "b"; |
| quadrantName += (x < _xm) ? "l" : "r"; |
| var quadrant:HitTestArea = this[quadrantName]; |
| // there is no child rectangle here: no hit |
| if (quadrant == null) |
| return null; |
| // ask the child |
| return quadrant.hitTest(x, y); |
| } |
| |
| /* Use this version to track hit testing in debug code |
| public function hitTest(x:Number, y:Number, depth:int=1):FlowElement |
| { |
| if (!_rect.contains(x, y)) |
| { |
| trace("Depth " + depth + ": " + x + "," + y); |
| return null; |
| } |
| // if there are no kids (the owner is set), the rectangle has been hit |
| // no need to attempt to retrieve the quadrant |
| if (_owner) |
| { |
| trace("Depth " + depth + ": " + x + "," + y + ": " + _owner); |
| if (depths[depth] == undefined) |
| depths[depth] = 0; |
| depths[depth]++; |
| return _owner; |
| } |
| // determine quadrant |
| var quadrantName:String = (y < _ym) ? "t" : "b"; |
| quadrantName += (x < _xm) ? "l" : "r"; |
| var quadrant:HitTestArea = this[quadrantName]; |
| // there is no child rectangle here: no hit |
| if (quadrant == null) |
| { |
| trace("Depth " + depth + ": " + x + "," + y); |
| return null; |
| } |
| // ask the child |
| return quadrant.hitTest(x, y, depth+1); |
| } |
| */ |
| /** @private |
| * Add the given objects of rectangles to the given quadrant. Create an array of |
| * intersecting rectangles, and, if that array if not empty, create a new |
| * HitTestArea covering these rectangles, and store it into the quadrant |
| * property. Note that this method is recursive. |
| * @param arr An object of rectangle objects. |
| * @param propName The name of the quadrant property (tl, tr, bl, br). |
| * @param quadrant The bounding rectangle for this quadrant. |
| */ |
| private function addQuadrant(objects:Object, propName:String, quadrant:Rectangle):void |
| { |
| if (quadrant.isEmpty()) |
| return; |
| |
| // Collect the objects of intersecting rectangles |
| var qrects:Object = {}; |
| var i:int = 0; |
| for each (var obj:Object in objects) |
| { |
| var intersect:Rectangle = obj.rect.intersection(quadrant); |
| if (!intersect.isEmpty()) |
| qrects[i++] = {owner:obj.owner, rect:intersect}; |
| } |
| if (i > 0) |
| this[propName] = new HitTestArea(qrects); |
| } |
| } |
| } |