Return to Snippet

Revision: 61474
at December 15, 2012 08:33 by GeorgeCross


Initial Code
public function isPointInsideShape(_point:Vector3D, _shapeVerices:Vector.<Vector3D>):Boolean
{
	var _numberOfSides:int = shapeVertices.length;
	var _i:int = 0;
	var _leftOrRightSide:Boolean = false;
	var _firstEdgePoint:Vector3D = null;
	var _secondEdgePoint:Vector3D = null;
			 
	while(_i < _numberOfSides)
	{
		_firstEdgePoint = _shapeVertices[_i];
		_secondEdgePoint = _shapeVertices[(_i + 1) % _numberOfSides];
				 
		if(_i == 0){
			// Determining if the point is to the left or to the right of first edge true for left, false for right
			_leftOrRightSide = ((_point.y - _firstEdgePoint.y) * (_secondEdgePoint.x - _firstEdgePoint.x)) - ((_point.x - _firstEdgePoint.x) * (_secondEdgePoint.y - _firstEdgePoint.y)) > 0;
		}
		else
		{
			// Now all edges must be on the same side
			if(_leftOrRightSide && ((_point.y - _firstEdgePoint.y) * (_secondEdgePoint.x - _firstEdgePoint.x)) - ((_point.x - _firstEdgePoint.x) * (_secondEdgePoint.y - _firstEdgePoint.y)) < 0)
			{
				// Not all edges are on the same side! 
				return false;
			}
			else if(!_leftOrRightSide && ((_point.y - _firstEdgePoint.y) * (_secondEdgePoint.x - _firstEdgePoint.x)) - ((_point.x - _firstEdgePoint.x) * (_secondEdgePoint.y - _firstEdgePoint.y)) > 0)
			{
				// Not all edges are on the same side!
				return false;
			}
		}
		_i++;
	}
	
	// We looped through all vertices and didn't detect different sides
	return true;
}

Initial URL


Initial Description
The convex polygon algorithm, which, as the name says, only works for convex polygons and is based on whether or not a point is on a certain “side” of every edge of the polygon.

Initial Title
Is point inside a convex shape?

Initial Tags


Initial Language
ActionScript 3