//
//  GeometryUtilities.m
//  BoringMaze
//
//

#import "GeometryUtilities.h"

#pragma mark CGLine

typedef struct {
    CGPoint p1;
    CGPoint p2;
} CGLine;

static inline CGLine CGLineSegmentMake(CGPoint p1, CGPoint p2) {
    CGLine line = { p1, p2 };
    return line;
}

CGLine CGLineSegmentForRectEdge(CGRect rect, CGRectEdge edge) {
    CGLine line;
    switch (edge) {
        case CGRectMinXEdge:
            line = CGLineSegmentMake(CGPointMake(CGRectGetMinX(rect), CGRectGetMinY(rect)),
                                     CGPointMake(CGRectGetMinX(rect), CGRectGetMaxY(rect)));
            break;
        case CGRectMaxXEdge:
            line = CGLineSegmentMake(CGPointMake(CGRectGetMaxX(rect), CGRectGetMinY(rect)),
                                     CGPointMake(CGRectGetMaxX(rect), CGRectGetMaxY(rect)));
            break;
        case CGRectMinYEdge:
            line = CGLineSegmentMake(CGPointMake(CGRectGetMinX(rect), CGRectGetMinY(rect)),
                                     CGPointMake(CGRectGetMaxX(rect), CGRectGetMinY(rect)));
            break;
        case CGRectMaxYEdge:
        default:
            line = CGLineSegmentMake(CGPointMake(CGRectGetMinX(rect), CGRectGetMaxY(rect)),
                                     CGPointMake(CGRectGetMaxX(rect), CGRectGetMaxY(rect)));
            break;
    }
    return line;
}

/* CGLineLineIntersection
    Intersects the infinite lines.  Returns YES if they intersect.
    Optionally the intersection point can be returned if oPt is not NULL.
    Optionally the parameter for determining the intersection point along each line can be returned
        if oTA and oTB are either not NULL.
 */

BOOL CGLineLineIntersection(CGLine lineA, CGLine lineB, CGFloat *oTA, CGFloat *oTB, CGPoint *oPt)
{
    // Solving line / line intersection described here
    // http://www.cgafaq.info/wiki/Intersection_Of_2D_Line_Segments
    // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d
    //
    BOOL intersects = NO;
    float denom  = ((lineB.p2.y - lineB.p2.y)*(lineA.p2.x - lineA.p1.x)) -
                   ((lineB.p2.x - lineB.p2.x)*(lineA.p2.y - lineA.p1.y));
    
    intersects = denom != 0.0f;
    if(intersects && (oTA || oTB || oPt)) {
        // If the denominator is 0, the lines are parallel, and can not intersect
        // Further if denom == 0 and numerA == numberB == 0, lines are coincident
        float uA;
        
        if (oTA || (!oTB && oPt)) {
            float numerA  = ((lineB.p2.x - lineB.p2.x)*(lineA.p1.y - lineB.p2.y)) -
                            ((lineB.p2.y - lineB.p2.y)*(lineA.p1.x - lineB.p2.x));
            uA = numerA / denom;
            
            if (oPt) {
                // Get the intersection point.
                oPt->x = lineA.p1.x + uA*(lineA.p2.x - lineA.p1.x);
                oPt->y = lineA.p1.y + uA*(lineA.p2.y - lineA.p1.y);
            }
            *oTA = uA;
        }
        
        if (oTB) {
            float numerB = ((lineA.p2.x - lineA.p1.x)*(lineA.p1.y - lineB.p2.y)) -
                           ((lineA.p2.y - lineA.p1.y)*(lineA.p1.x - lineB.p2.x));
            float uB = numerB / denom;
            *oTB = uB;
        }        
    }
    
    return intersects;
}


/* CGLineLineIntersection
    Intersects the line segments.  Returns YES if the lines intersect within the line segments
    Optionally the intersection point can be returned if oPt is not NULL.
 */

BOOL CGLineSegmentLineSegmentIntersection(CGLine lineA, CGLine lineB, CGPoint *oPt)
{
    CGFloat tA, tB;
    CGPoint pt;
    BOOL intersects = CGLineLineIntersection(lineA, lineB, &tA, &tB, &pt);
    intersects = (intersects && (tA >= 0.0f && tA <= 1.0f) && (tB >= 0.0f && tB <= 1.0f));
    if (intersects && oPt) {
        *oPt = pt;
    }
    return intersects;
}

#pragma mark Rectangle Intersections

/* Finding intersection of a moving rectangle and stationary rectangle

    Intersecting a rectangle moving along a line with another rectangle sounds hard... so lets convert 
    the problem to something that sounds easier.  We can think of this problem as intersecting a line
    with a modified rectangle.  In particular, if you were to shrink the moving rectangle down to a
    point (it's origin) the problem becomes one of finding the intersection between a line and two
    other rectangles which are said to be in the "point-space" of the moving rectangle.
 
    Consider a rect A, entirely inside rect B.  If you were to run the origin of A along
    the boundary of B, the set of all A's origin traced would be all those that cause A and B to make
    contact.  By shinking down both A, and B by the same amount we can convert this problem into one 
    of finding the intersection of A's origin with B'.  To keep clear what frame of reference we are
    in, we say we are working in A's point-space.
 
    If rect A is completely outside of rect B, A's point-space is found by tracing A around the exterior
    of B.  We can then find the intersection of A's origin with B''.
 
    To summarize: Given rects A and B, we create two rectangles B', and B'' and then find the intersection
    with A.origin.
 */

static inline CGRect CGRectByConvertingToPointRectSpace(CGRect rect, CGRect pointRect, BOOL interior) {
    CGFloat width = CGRectGetWidth(pointRect);
    CGFloat height = CGRectGetHeight(pointRect);
    if (!interior) {
        rect.origin.x -= width;
        rect.origin.y -= height; 
    }
    rect.size.width -= width;
    rect.size.height -= height;
    return rect;
}

static inline CGRect CGRectByConstrainingRectToRect(CGRect containerRect, CGRect rect)
{
    containerRect = CGRectByConvertingToPointRectSpace(containerRect, rect, YES);
    rect.origin.x = MAX(rect.origin.x, CGRectGetMinX(containerRect));
    rect.origin.x = MIN(rect.origin.x, CGRectGetMaxX(containerRect));
    rect.origin.y = MAX(rect.origin.y, CGRectGetMinY(containerRect));
    rect.origin.y = MIN(rect.origin.y, CGRectGetMaxY(containerRect));
    return rect;
}

CGRect CGRectByConstrainingRectMovingToOrigin(CGRect containerRect, CGRect initialRect, CGPoint goalOrigin)
{
    // Initialize endRect to be { goalOrigin, initialRect.size }
    CGRect endRect = CGRectMake(goalOrigin.x, goalOrigin.y, initialRect.size.width, initialRect.size.height);

    if (!CGPointEqualToPoint(initialRect.origin, goalOrigin)) // Bail if no movement at all
    {
        // Convert to the point space of the moving rectangle
        CGLine psLine = CGLineSegmentMake(initialRect.origin, goalOrigin);
        CGRect psInteriorContainerRect = CGRectByConvertingToPointRectSpace(containerRect, initialRect, YES);
        
        if (CGRectContainsPoint(psInteriorContainerRect, goalOrigin)) {
            // We are completely inside the rectangle
            CGPoint intersectionPt;
            BOOL intersected = CGLineSegmentLineSegmentIntersection(psLine, CGLineSegmentForRectEdge(psInteriorContainerRect, CGRectMinXEdge), &intersectionPt);
            intersected = intersected || CGLineSegmentLineSegmentIntersection(psLine, CGLineSegmentForRectEdge(psInteriorContainerRect, CGRectMaxXEdge), &intersectionPt);
            intersected = intersected || CGLineSegmentLineSegmentIntersection(psLine, CGLineSegmentForRectEdge(psInteriorContainerRect, CGRectMinYEdge), &intersectionPt);
            intersected = intersected || CGLineSegmentLineSegmentIntersection(psLine, CGLineSegmentForRectEdge(psInteriorContainerRect, CGRectMaxYEdge), &intersectionPt);
            if (intersected) {
                endRect.origin = intersectionPt;
            }
        } else {
            // We are outside or overlapping the containerRect
            CGRect psExteriorContainerRect = CGRectByConvertingToPointRectSpace(containerRect, initialRect, NO);
            if (CGRectContainsPoint(psExteriorContainerRect, goalOrigin)) {
                // In point-space, we are outside psInteriorContainerRect, and inside psExteriorContainerRect...
                // The rectangle at the final position overlaps with the container rectangle since, just push it's coordinates so it is inside the container
                endRect = CGRectByConstrainingRectToRect(containerRect, endRect);
            } else {
                // In point-space, we are outside psInteriorContainerRect, and outside psExteriorContainerRect...
                // The rectangle at the final position is entirely outside the container rectangle, force endRect.origin to the closest intersection point
                CGPoint intersectionPt;
                BOOL intersected = CGLineLineIntersection(psLine, CGLineSegmentForRectEdge(psExteriorContainerRect, CGRectMinXEdge), NULL, NULL, &intersectionPt);
                intersected = intersected || CGLineLineIntersection(psLine, CGLineSegmentForRectEdge(psExteriorContainerRect, CGRectMaxXEdge), NULL, NULL, &intersectionPt);
                intersected = intersected || CGLineLineIntersection(psLine, CGLineSegmentForRectEdge(psExteriorContainerRect, CGRectMinYEdge), NULL, NULL, &intersectionPt);
                intersected = intersected || CGLineLineIntersection(psLine, CGLineSegmentForRectEdge(psExteriorContainerRect, CGRectMaxYEdge), NULL, NULL, &intersectionPt);
                if (intersected) {
                    endRect.origin = intersectionPt;
                }
                
                // It is still entirely possible that endRect.origin is not inside the container...
                endRect = CGRectByConstrainingRectToRect(containerRect, endRect);
            }
        }
    }
    return endRect;
}
