Find area of intersection between 2 squares rotated 45 degrees Ok so I am trying this task on a Code Challenge website, but I can't figure this out to do this fast enough. Because my current solutions has Time Limit Exceded Errors

This is the stated problem see images:



This is my current code:

def areaOfIntersection(shape1, shape2):
    def calc_points(shape):
        # shape = ["order(range)" , "x_center", "y_center"]
        points = []
        k = -1

        # k = Number of points in row-i in shape
        for i in range(shape[0]*2-1):
            if(i&lt;=shape[0]-1):
                k += 2
            else:
                k -= 2

            # Add point to collection of points (x, y)
            for x in range(k):
                current_X = shape[1] + x - (k-1)/2
                current_Y = shape[2] + abs(shape[0] - i - 1) if i&gt;shape[0]-1 else shape[2] - abs(shape[0] - i - 1)
                points.append( ( current_X , current_Y ) )
        return points

    p1 = calc_points(shape1)
    p2 = calc_points(shape2)

    # Return the length of the lists intersection
    return len(list(set(p1) &amp; set(p2)))


Thus my Question is: How can above program complete faster?

I tried to add some logic to lessen the points to calculate but I am stuck...

My guess is I'm missing some simple math...
You can further reduce the time spent via taking advantage of the l1norm. The l1norm is the sum of the absolute values of a vector.  We represent our coordinates as a 2d vector, the l1norm of that is the absolute value of x and y.  Using this we can use the l1norm like distance (which happens to be the l2norm) for a diamond.  Calculating the l1 norm and comparing it against the order-1 of the diamond will give us whether or not the point is inside the diamond, provided the point the diamond we are trying to figure out if the point is inside of or not is centered at 0,0. 

Utilizing the l1 norm we only need to look at one diamonds xy points, not two.  Because we only need to look at one, we can pick the smallest diamond to use to check overlap and translating the coordinates of the smaller one to a system where the center of the larger one is at (0,0). 

This saves a lot of time, but if both of our diamonds are larger, and are nowhere close to each other we will still have to do a lot of work.  To avoid this we can use broad phase collision techniques to reduce computational time in these scenarios, using something akin to sweep and prune.  If we accomplish this via creating a range() that at first is our new translated smaller diamonds y - (order -1) and y + (order + 1).  We then conditionally swap these values if the max y values of the larger diamond are in smaller more convenient ranges, so if the furthest upward y point on the larger one is at a shorter distance than what we use as our max y range, the we will use that instead, or with the furthest downward y point on the larger one is larger than what we use for our min y range, we will use that instead.  If our smaller diamond isn't even in range of either of the larger diamonds y min and max values, our counting loop terminates as soon as it starts. 

But we can go further with this idea.   We will do something similar with the x values, except we don't need to use the bounding box version of x cutoff values.  We can actually figure out the range of x on a per larger diamond y axis value.  Since our smaller x y coordinates are with respect to the larger diamond being at (0,0) y actually corresponds to the same y location relative to the center of the larger diamond is.  In fact because of the l1norm formula, we now know how to know the width (or half width) of a (0,0) centered diamond given one of its y coordinates.  We know that our y is within the larger diamonds y range from before, so the formula is (larger_order - 1) - abs(our_calculated_y_for_smaller) since abs(x) + abs(y) = order -1 we simply do algebra to figure out that abs(x) = order - 1 - abs(y) and since we only need to know the half width, we are actually looking for abs(x).

Now that we know the half width, we can use the same method above to figure out the range we should be looking at for this y level with respect to the larger diamond, instead of niavely looking within the bounding box. 

But wait a second.  Now that we both know that we are only looking at values with that match the same y level on both our smaller and larger diamond, and we've been able to make sure we don't look at x's outside of the same x level why would we still need to check for each l1norm intersection?

What we can actually do is just sum up the difference between the max x range and min x range instead of using the l1norm, since we know exactly the range of values that overlap now!  

now I doubt this is necessarily the fastest for very small diamond sizes, but I think this is the fastest no parallel asymptotic time algorithm for this specific problem that I could think of.  You could theoretically do this for N dimensional diamonds as well, but you'd have to include broad phase at each dimension. This should certainly be faster than both of your solutions for any large diamonds no matter the situation. 

The time complexity is now bounded by only the order of the smallest diamond, as in O((smallest diamond order*2)-1). 

Here is the implementation in python   

def areaOfIntersection(shape1, shape2):
    # find smaller diamond
    (smaller, larger) = (shape1, shape2) if shape1[0] &lt; shape2[0] else (shape2, shape1)

    # use the variables for the l1norm comparison for each point
    larger_offset_order = larger[0] - 1
    x_translate = -larger[1]
    y_translate = -larger[2]

    # use these variables to create each index in the diamond
    order = smaller[0]
    smaller_offset_order = order - 1
    # making relative to larger being at (0,0) instead of (shape2[1], shape2[2])
    x = smaller[1] + x_translate
    y = smaller[2] + y_translate

    # using comp order instead of larger[0] to work with logic below, since the number will represent the actual max
    # or min x or y value possible instead of one past it.
    larger_min_range_y = -larger_offset_order
    larger_max_range_y = larger_offset_order

    # overlap number
    k = 0

    # makes sure that the calculations at least take place in the same y coordinate intersection
    y_min_range = y + (-smaller_offset_order)
    y_max_range = y + (smaller_offset_order)
    y_min_range = larger_min_range_y if larger_min_range_y &gt; y_min_range else y_min_range
    y_max_range = larger_max_range_y if larger_max_range_y &lt; y_max_range else y_max_range

    for nmy in range(y_min_range, y_max_range + 1):
        half_width = smaller_offset_order - abs(nmy - y)
        # the difference from the y axis to the furthest diamond point, since it is already "centered"
        # no offset math is needed
        # equation abs(x) + abs(y) = order - 1, un normalized l1 norm equation, we only are about abs(x) so
        # it becomes x + abs(y) = order or x = order - 1 - abs(y), which is what we have here
        larger_half_width_at_current_y = larger_offset_order - abs(nmy)
        larger_min_range_x = -larger_half_width_at_current_y
        larger_max_range_x = larger_half_width_at_current_y
        x_min_range = (x + (-half_width))
        x_max_range = (x + half_width)  # max value in range, since exclusive
        # sets the range to make sure only iterating over possible subsection of x that could actually contain
        # a value from both
        x_min_range = larger_min_range_x if larger_min_range_x &gt; x_min_range else x_min_range
        x_max_range = larger_max_range_x if larger_max_range_x &lt; x_max_range else x_max_range
        # check if possible generated x offsets are out of range.
        # no longer need l1norm, since we can just sum up values in range
        if x_min_range &lt; (x_max_range + 1):
            k += (x_max_range + 1) - x_min_range
    return k


print(areaOfIntersection([3, 0, -1], [5, 3, 0]))
# 8


The only faster method I can think of is some how accurately transforming these diamonds into AABB (Axis Aligned Bounding Boxes) and then computing the area overlap, but I'm  not sure how one would do so with out loosing out on the exact number of pixel overlap. In floating point however, I suspect this to be the correct method to measure area overlap since you aren't going to be losing out on discrete value precision. In a floating point scenario one could also use the generalized quadrilateral intersection