Detecting insideness of a rectangle to an arbitrary polygon

Abstract

There is described a method for determining the relative location between a rectangle and a polygon. First, a box that bounds the polygon is created. An outside indicator is returned if the rectangle is outside the box. An intersect indicator is returned if the box is entirely inside the rectangle. If an odd/even fill process is in use then first the intersect indicator is returned if the rectangle intersects with the polygon or if a subpath bounding box is entirely inside the rectangle. Finally, if the location of the rectangle has not yet been returned, the location of a single point of the rectangle is returned. If a non-zero winding fill process is in use, first, the intersect indicator is returned if at least one corner of the rectangle is in a different side of the polygon than remaining corners of the rectangle. Next, the intersect indictor is returned if an edge of the rectangle starts outside the polygon and intersects with the polygon or if an edge of the rectangle intersects with the polygon and transitions outside the polygon. A subpath bounding box that bounds any subpaths is created. The location of a corner of the rectangle is returned if a point inside the subpath is equal to the corner of the rectangle. In the alternative, where the corner and subpath's points are different, the intersect indicator is returned. Finally, if the location of the rectangle has not yet been returned, the location of a center point of the rectangle is returned.