textLayout/src/flashx/textLayout/utils/HitTestArea.as - flex-tlf - Git at Google

 ////////////////////////////////////////////////////////////////////////////////
 //
 //  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);
 		}
 	}
 }
	////////////////////////////////////////////////////////////////////////////////
	//
	// 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);
	}
	}
	}