Faster Rectangle Class

Posted: November 15th, 2010 under ActionScript 3.0, Optimization.

“An underlying theme I have discovered with Flash is that you are often better off writing your own code than trusting Adobe’s classes and functions, data structures are no exception.” – taken from my flash particle system article

After the launch and first few patches of Lego Universe, work at NetDevil has calmed down enough that I have the time and energy to explore private projects again. The current project I am working on is large and it is still in the design, test, research phase since it needs to very optimized. I saw that I was going to be doing quite a few rectangle intersects and intersection operations (the function that determines whether two rectangles overlap and the function that returns the overlapping rectangle respectively) so I took a look at the speed of Flash’s native rectangle class. I clocked Flash’s intersects function speed at over 150 simple operations (adds, multiplies, and accessing class members all count as one simple operation from my benchmarking series). I thought to myself “I can do better than that” – I was right, and I managed to write a faster intersection function too (free code).

These speed tests are just from my minimum spec machine “Computer A” (Gateway Desktop, Intel Pentium 4 chip, 2.27 GHz, 1 GB RAM, Windows XP SP3). I am sure that there will be a little variance across different machines, but since my intersects function was over 4 times faster than Adobe’s, I am pretty confident that it will be faster for every machine out there. Relative speed listed here is in comparison to the cost of a simple operation.

Comparing Adobe’s rectangle functions to mine, 1,000,000 executions per trial. Run the benchmarks: Flash’s native rectangle class, My ActionScript 3.0 rectangle class

  Flash’s functions Relative Speed Average Std. Dev.
Computer A intersects (overlap) 162.5 0.6513 0.0246
intersects (containment) 157 0.6269 0.0515
intersection 174 0.6962 0.0124

Flash’s native rectangle intersects function is so slow, and so close to the speed of actually calculating the intersection, there is no point to ever use it. You might as well just ask for the intersection and check to see it if it is null. There is no reason for an intersection test to be running that slowly, here are the results of my implementation:

  My functions Relative Speed Average Std. Dev.
Computer A intersects (overlap) 35.5 0.1410 0.0000
intersects (containment) 35.5 0.1420 0.0040
intersection 157.5 0.6303 0.0095

I had a couple ideas on how to test for intersection before I settled on this implementation – including one very clever one that looked at the union of two rectangles. Ultimately, I went with a very straightforward approach of comparing the two rectangle’s line segments for intersection. I went this route because you don’t need to allocate any additional memory (an increasing trend in my optimized routines), and it compliments the logic for the intersection function (less time spent validating code).

One caveat before I give you the code, my rectangle class is just for integer dimensions because that is what I needed. You will need to make some minor tweaks if you want a custom numeric rectangle class.

package {
   
    //I discovered that Adobe's rectangle class is pretty slow
    //I dont know what they are doing, this rectangle class is faster
    //this is also an integer rectangle, meant to be used with graphics
   
    public class IntegerRectangle{
   
        public var rx:int;
        public var ry:int;
        internal var rwidth:int;//no reason width or height should ever be negitive
        internal var rheight:int;//but making them ints prevents any promotion issues
   
        public function IntegerRectangle(xComponent:int = 0, yComponent:int = 0, widthComponent:int = 0, heightComponent:int = 0):void{
   
            rx = xComponent;
            ry = yComponent;
           
            //take absolute value to make sure width and height are positive
            //there would be bounds issues if parameters coming in were uint getting maped to ints
            rwidth = (widthComponent < 0 ? widthComponent * -1 : widthComponent);
            rheight = (heightComponent < 0 ? heightComponent * -1 : heightComponent);
       
        }//end constructor
       
       
        public function toString():String{
            return "("+rx+", "+ry+"), ("+rwidth+", "+rheight+")";
        }
       
        public function get x():int{
            return rx;
        }
       
        public function get y():int{
            return ry;
        }
       
        public function get width():int{
            return rwidth;
        }
       
        public function get height():int{
            return rheight;
        }
       
       
        public function set x(xComponent:int):void{
            rx = xComponent;
        }
       
        public function set y(yComponent:int):void{
            ry = yComponent;
        }
       
        public function set width(widthComponent:int):void{
            rwidth = (widthComponent < 0 ? widthComponent * -1 : widthComponent);
        }
       
        public function set height(heightComponent:int):void{
            rheight = (heightComponent < 0 ? heightComponent * -1 : heightComponent);
        }
       
        public function copyRectangle(rect:IntegerRectangle):void{
            rx = rect.rx;
            ry = rect.ry;
           
            rwidth = rect.rwidth;
            rheight = rect.rheight;
        }
       
        //bleh, enough getters and setters, lets do some real code
        public function intersects(rect:IntegerRectangle):Boolean{
            //for axis aligned rectangles
            //keep in mind some intersections are at a single point or a line
            //since this class is primarily designed for graphics, a point = a pixel which has area        
            //this is really simple, I have no idea why Adobe's algorithm is so slow
            /*
            A____B       A'___________B'
            |    |        |           |    
            |    |       C'___________D'
            C____D
           
            */

                       
            //line AB or CD (horizontal lines of ABCD) intersecting with A'C' or B'D' (vertical lines of A'B'C'D')
            //line AB is y = ry, CD is y = ry + rheight (in flash coordinates, not cartesian)
            //and the x range of AB == the x range of CD (y = # lines are parallel to x axis)
           
            //line A'C' is x = rect.rx, B'D' is x = rect.rx + rect.rwidth
            //and the y range of A'C' == the y range of B'D' (x = # lines are parallel to y axis)
           
            //A'.x == C'.x, is either in the x range of AB (which is the same as the x range of CD)
            //OR B'.x == D'.x, is either in the x range of AB
            if(    (rx <= rect.rx && rect.rx <= (rx + rwidth))//A'C' check
                || (rx <= (rect.rx + rect.rwidth) && (rect.rx + rect.rwidth) <= (rx + rwidth))){ //B'D' check
               
                //to check line AB intersecting with A'C', B'D'
                //AND A.y == B.y, is A.y in the y range of A'C' AND y range A'C' == B'D'
                if(rect.ry <= ry && ry <= (rect.ry + rect.rheight)){
                    //there is an intersection point
                    //at (rect.rx, ry)               aka (A'.x, A.y)
                    //or (rect.rx + rect.rwidth, ry) aka (B'.x , A.y) - respectively (to initial if statement)
                    return true;
                }                      
                //to check line CD intersecting with A'C', B'D'
                //AND C.y == D.y, is C.y in the y range of A'C' AND y range A'C' == B'D'
                if(rect.ry <= (ry + rheight) && (ry + rheight) <= (rect.ry + rect.rheight)){
                    //there is an intersection point
                    //at (rect.rx, ry + rheight)               aka (A'.x, C.y)
                    //or (rect.rx + rect.rwidth, ry + rheight) aka (B'.x, C.y) - respectively (to initial if statement)
                    return true;
                }      
            }
            /*
            by now we have captured all varieties of:
               ___
             _|___|_____
            | |   |     |
            |_|___|_____|
              |   |
              |___|
             
            and all of the varieties of:
             ____
            |  __|_
            |_|__| |
              |____|
           
            and some varieties of:
                 ___
             ___|___|__
            |   |___|  |
            |__________|
           
            */

            //so, to get the last few cases, we need to check
            //line AC or BD (vertical lines of ABCD) intersecting with A'B' or C'D' (horizontal lines of A'B'C'D')
            //for which, we just need to swap our x and y references
           
            //line AC is x = rx, BD is x = rx + rwidth (in flash coordinates, not cartesian)
            //and the y range of AC == the y range of BD (x = # lines are parallel to y axis)                      
            //A'.y == B'.y, is either in the y range of AC (which is the same as the y range of BD)
            //OR C'.y == D'.y, is either in the y range of AC
            if(    (ry <= rect.ry && rect.ry <= (ry + rheight))  //A'B' check
                || (ry <= (rect.ry + rect.rheight) && (rect.ry + rect.rheight) <= (ry + rheight)) ){
               
                //check line AC intersecting with A'B', C'D'
                //AND A.x == C.x, is A.x in the x range of A'B' AND x range A'B' == C'D'
                if(rect.rx <= rx && rx <= (rect.rx + rect.rwidth)){
                    //there is an intersection point
                    //at (rx, rect.ry)                aka (A.x, A'.y)
                    //or (rx, rect.ry + rect.rheight) aka (A.x , B'.y) - respectively
                    return true;
                }
                //check line BD intersecting with A'B', C'D'
                //AND B.x == D.x, is B.x in the x range of A'B' AND x range A'B' == C'D'
                if(rect.rx <= (rx + rwidth) && (rx + rwidth) <= (rect.rx + rect.rwidth)){
                    //there is an intersection point
                    //at (rx + rwidth, rect.ry)                aka (B.x, A'.y)
                    //or (rx + rwidth, rect.ry + rect.rheight) aka (B.x , B'.y) - respectively
                    return true;
                }
            }
           
            /*
            The only remaining cases deal with containment
             _____
            |  _  |
            | |_| |
            |_____|
           
            */

            //lastly we check for either rectange completely containing the other
            //you need to check rect containing rect' and rect' containing rect
            if(contains(rect) || rect.contains(this)){
                return true;
            }
            //if we havent already returned true...
            return false;
        }
       
        public function contains(rect:IntegerRectangle):Boolean{
            //does 'this' contain the rectangle 'rect'
            //This is really simple since our rectangles are described
            //by a point (A) and positive width and height.
            //we only need to determine if points A' and D' are inside ABCD
            //but we don't even have to do full point inside rect checks
            //just ensure that A <= A'  and D' <= D
            //NOTE: contains does not check for the rectangle being empty
            //however, if the rectangle has no width or height, it equates to the point in rectangle test
            /*
           
            A _________B
             |A'____B' |
             | |    |  |
             | |____|  |
             |C'    D' |           
             |_________|
            C          D
            */

           
            if(   (rx <= rect.rx && ry <= rect.ry) //A <= A'
                &&((rect.rx + rect.rwidth) <= (rx + rwidth)) //D'.x <= D.x
                &&((rect.ry + rect.rheight) <= (ry + rheight))){//D'.y <= D.y
                return true;
            }
           
            return false;
        }
       
        public function containsCoords(px:int, py:int):Boolean{
            //determine if this set of coordinates is on the border or
            //inside of this rectangle
            //just like the contains function,
            //if our coordinates are greater than or equal too A
            //and our coordinates are less than or equal too D
            //it is contained since our rectangles are axis aligned
           
            if(   (rx <= px && ry <= py) //A <= point
                &&(px <= (rx + rwidth) && py <= (ry + rheight))){//point <= D
                return true;
            }
           
            return false;
           
        }
       
        public function intersection(rect:IntegerRectangle):IntegerRectangle{
            //returns the rectangular overlap of two rectangles
            //if there is no overlap, the returned value is null
            //this function can return "empty" rectangles, points and lines are valid results
            //since it is used for graphics a point can be a single pixel and a line a row / column of pixels
            //this is why there is a check for 0 width and 0 height - which would be numerically correct for
            //rectangles over the real numbers, but for pixels and lines width and height are always atleast 1
            //since this class is primarily designed for graphics, a point = a pixel which has area
            /*
            A____B       A'___________B'
            |    |        |           |    
            |    |       C'___________D'
            C____D
           
            */

                       
            //even if one rectangle contains the other we dont want to return
            //one of our parameters because that could cause nasty object sharing bugs.
            //while containment is perhaps the most unlikely case, it is also the least
            //computationally expensive - and greatly simplfies further calculations
            var newRect:IntegerRectangle = new IntegerRectangle();
           
            if(contains(rect)){
                //return a copy of rect
                newRect.copyRectangle(rect);
                return newRect;
            }
            if(rect.contains(this)){
                //return a copy of this
                newRect.copyRectangle(this);
                return newRect;
            }
           
            //ok now the tricky part, we need to find and store the intersection points in some kind of order
            //without adding any overhead of a point class, and trying to avoid the slow Flash array class
            //there is a very finite list of points that would potentially compose an interection rectangle
            //any of the 4 points of ABCD, any of the 4 points of A'B'C'D',
            //and any of the 8 potential line segment intersection points examined in 'intersects()'
            //However, there is no need to find all 4 corners of the newly formed rectangle
            //we just need to find its top left point, and bottom right point - only 4 potential point candidates for each.
           
            //the top left most point must be A, A', the intersection of AB with A'C',
            //or the intersection of AC with A'B' (the pairs of top and left lines)
            //and we must check in that order because the intersections can only be the top
            //left point if A or A' isnt.
            //If all of those cases fail
            //there is not an intersection (assuming your "point in rectangle" test includes borders)
                       
            //rect.containsCoords(rx,ry)
            if(rect.containsCoords(rx,ry)){        
                newRect.rx = rx;
                newRect.ry = ry;
            }
            //containsCoords(rect.rx, rect.ry)
            else if(containsCoords(rect.rx, rect.ry)){             
                newRect.rx = rect.rx;
                newRect.ry = rect.ry;
            }
            //intersection of AB with A'C' - if this is confusing take a look at 'intersects()'
            else if(   (rx <= rect.rx && rect.rx <= (rx + rwidth))
                     &&(rect.ry <= ry && ry <= (rect.ry + rect.rheight))){
                newRect.rx = rect.rx;
                newRect.ry = ry;
            }
            //intersection of AC with A'B'
            else if(   (ry <= rect.ry && rect.ry <= (ry + rheight))
                     &&(rect.rx <= rx && rx <= (rect.rx + rect.rwidth))){              
                newRect.rx = rx;
                newRect.ry = rect.ry;
            }
            else{
                //intersection does not exist
                return null;
            }
           
           
            //the bottom right point must be D, D', intersection of CD with B'D',
            //intersection of C'D' with BD (the pairs of bottom and right lines)
            //and we must check in that order because the intersections can only be the bottom
            //right point if D or D' isnt.
           
            //rect.containsCoords(rx + rwidth, ry + rheight)
            if(rect.containsCoords(rx + rwidth, ry + rheight)){                        
                newRect.rwidth = (rx + rwidth) - newRect.rx;
                newRect.rheight = (ry + rheight) - newRect.ry;
                newRect.rwidth = (newRect.rwidth > 0 ? newRect.rwidth : 1);
                newRect.rheight = (newRect.rheight > 0 ? newRect.rheight : 1);
                return newRect;
            }
            //containsCoords(rect.rx + rect.rwidth, rect.ry + rect.rheight)
            else if(containsCoords(rect.rx + rect.rwidth, rect.ry + rect.rheight)){            
                newRect.rwidth = (rect.rx + rect.rwidth) - newRect.rx;
                newRect.rheight = (rect.ry + rect.rheight) - newRect.ry;
                newRect.rwidth = (newRect.rwidth > 0 ? newRect.rwidth : 1);
                newRect.rheight = (newRect.rheight > 0 ? newRect.rheight : 1);
                return newRect;
            }
            //CD intersecting with B'D'
            else if(   (rx <= (rect.rx + rect.rwidth) && (rect.rx + rect.rwidth) <= (rx + rwidth))
                     &&(rect.ry <= (ry + rheight) && (ry + rheight) <= (rect.ry + rect.rheight))){
                //then there is an intersection at (rect.rx + rect.rwidth, ry + rheight)
                newRect.rwidth = (rect.rx + rect.rwidth) - newRect.rx;
                newRect.rheight = (ry + rheight) - newRect.ry;
                newRect.rwidth = (newRect.rwidth > 0 ? newRect.rwidth : 1);
                newRect.rheight = (newRect.rheight > 0 ? newRect.rheight : 1);
                return newRect;
            }
            //C'D' intersecting with BD
            //I'm fairly confident that this can be an else case
            //but in the unlikely case that I missed something, or my future self edits this
            //and forgets about this little statement, lets just do the whole check
            else if(   (ry <= (rect.ry + rect.rheight) && (rect.ry + rect.rheight) <= (ry + rheight))
                     &&(rect.rx <= (rx + rwidth) && (rx + rwidth) <= (rect.rx + rect.rwidth))){
                //then there is an intersection at (rx + rwidth, rect.ry + rect.rheight)
                newRect.rwidth = (rx + rwidth) - newRect.rx;
                newRect.rheight = (rect.ry + rect.rheight) - newRect.ry;
                newRect.rwidth = (newRect.rwidth > 0 ? newRect.rwidth : 1);
                newRect.rheight = (newRect.rheight > 0 ? newRect.rheight : 1);
                return newRect;
            }
                       
            //I dont think I should ever hit this - you should have already returned something
            //but if you did hit it, the result should be null
            return null;
        }
       
        public function isEmpty():Boolean{
            //are all values 0 - isEmpty doesnt really suit this class well
            if(rx == 0 && ry == 0 && rwidth == 0 && rheight == 0){
                return true;
            }
            return false;
        }
       
        public function area():int{
            return rwidth * rheight;
        }
       
       
        public function clear():void{
            rx = 0;
            ry = 0;
           
            rwidth = 0;
            rheight = 0;
        }
       
        public function destroy():void{
            rx = 0;
            ry = 0;
           
            rwidth = 0;
            rheight = 0;
        }
   
    }//end class
}//end package
   
   
*Special thanks to the Quick Highlighter team for the code embed CSS and HTML I’ll leave it up to you to decide if Adobe = FAIL or if I = WIN. It feels like anytime I start designing a sophisticated project, and find I am going to be doing many of type X calculation or using Y object frequently, I setup some benchmarks and test it out. I have become that untrusting. Stuff like this rectangle discovery are like landmines to developers, unless you took the time to run the benchmarks, you would never expect the intersects function to have the same cost of finding the intersection or realize that you could write a faster implementation. While I was able to write something faster, I don’t feel much like a winner. Having to take the time to think and write classes like this are distractions that interrupt what I am really trying to work on. It also causes a lot of doubt; if Adobe couldn’t get a simple intersection test function right what else did they screw up? Thanks for reading, and remember, we are all in this together.
submit to reddit
Delicious Bookmark this on Delicious

5 Comments »

  • Comment by Todd — November 15, 2010 @ 6:43 am

    1

    It doesn’t surprise me that their code would be clunkier. When dealing with a development team with several hundred coders, I’m guessing not everyone is doing their best to optimize each class.

    Also, I would venture to say they were not focused on this entirely because their target market doesn’t do this type of development much. Kind of like when there were all those companies doing 3d-esque engines with Flash, and Adobe didn’t touch it; after a few years, they built their own into the IDE (if they didn’t just buy one of the companies outright).

    Good stuff!


  • Pingback by Tweets that mention Stephen Calender Programming Blog -- Topsy.com — November 15, 2010 @ 7:58 am

    2

    […] This post was mentioned on Twitter by Snorre Berge, Stephen Calender. Stephen Calender said: Its been a while but the blog is alive again: http://www.stephencalenderblog.com/?p=293 something for the Fellow Flash Developers […]


  • Comment by Kenny — August 11, 2011 @ 7:55 pm

    3

    Is there a reason you omitted the public properties such as ‘left’, ‘top’, etc.?


  • Comment by Stephen Calender — August 12, 2011 @ 1:40 am

    4

    This is a good question. For simple data structure like classes like points, vectors, and in this case rectangles I typically break the encapsulation rule of OOP. Notice that I left the class members rx and ry public and rwidth and rheight as internal. Since Flash is pass by value (you get a copy of the data, not the actual reference to the data) for the simple data types (Boolean, Uint, Int, Number, String) using a getter function is actually a pretty heavy operation since it creates memory. If I wanted to maintain top, bottom, left, and right I would have to either always calculate them on the fly or enforce the use of setter functions for x, y, width, and height (more memory allocations). I provided getters and setters as a courtesy to those that would frown on this practice, I personally avoid using getters and setters if I think I can get away with it. Data structures for basic geometry have a pretty standard implementation, so it felt like it made sense.

    It was a tough call to make, the logic for my intersect and intersection functions would be clearer with those logical reference points. However, I think I clocked the weight of a memory allocation / creating local variables in another post far exceeding the cost of some additional math. Every programmer is different, we all weigh the pros and cons differently, I put a high value on speed, particularly with data structures.


  • Comment by HypoLast — July 2, 2013 @ 12:11 pm

    5

    For your intersection code could you not check it all in one line? Assuming the rectangles are r1 and r2 with an x, y, width and height just use
    return (r1.x < r2.x + r2.width &&
    r2.x < r1.x + r1.width &&
    r1.y < r2.y + r2.height &&
    r2.y < r1.y + r1.height)
    I might be missing something but I'm pretty sure that works.


RSS feed for comments on this post. TrackBack URL

Leave a comment