6
\$\begingroup\$

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:

enter image description here enter image description here 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<=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>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) & 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...

\$\endgroup\$
2
  • \$\begingroup\$ If those squares were rotated to their normal orientation, the problem becomes a lot simpler. You should perhaps consider treating the problem as if it were oriented normally with a means to translate coordinates. \$\endgroup\$
    – Neil
    Jun 6 '17 at 10:28
  • \$\begingroup\$ @Neil, how does it become simpler than the L1 norm? Generate and check is pretty easy. \$\endgroup\$
    – Krupip
    Jun 6 '17 at 14:34
3
\$\begingroup\$

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] < 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 > y_min_range else y_min_range
    y_max_range = larger_max_range_y if larger_max_range_y < 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 > x_min_range else x_min_range
        x_max_range = larger_max_range_x if larger_max_range_x < 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 < (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

\$\endgroup\$
3
  • \$\begingroup\$ I have a few testcases where this returns incorrect answers though: shape1: [3, 5, -5], shape2: [5, 5, -5] | output = 4 , expected = 13 \$\endgroup\$
    – Ludisposed
    Jun 6 '17 at 18:36
  • \$\begingroup\$ @Ludisposed hmm let me check, that is indeed odd. its clear the first should be inside of the other completely \$\endgroup\$
    – Krupip
    Jun 6 '17 at 18:38
  • \$\begingroup\$ @Ludisposed fixed it, I forgot to make the larger_min_range_y and larger_max_range_y in terms of (0,0), accidentally used source coordinates for the larger diamond in the equation. \$\endgroup\$
    – Krupip
    Jun 6 '17 at 18:44
1
\$\begingroup\$

By setting up a new coorediate system that is the orginal one rotates 45 degrees.

new x = old shape.x - old shape.y ## we do not do scale
new y = old shape.x + old shape.y

now in new x, and new y system, look for the boundary of both shape

lower x bound (inclusive) for each shape is

old shape.x - old shape.y - (shape order - 1)

higher x bound(inclusive) is

old shape.x - old shape.y + (shape order - 1)

so that for intersection shape the low bound must be the maximum of the low bound of the two original shapes.

xmin = max((shape1.x -shape1.y - (shape1.order - 1)), (shape2.x -shape2.y - (shape2.order - 1)))

by doing the same for higher bound and y axis, we have xmin, xmax, ymin and ymax to identify the intersection shape, the problem then is how to count the number of boxes inside.

I made some mistake in final counting. if we do have difficulty how to correctly count the number, we can simply loop through the count.

Now I have an idea how to count correctly. Notice that in the new coordinate system, new x and new y must have the same odds.

new x = old x - old y
new y = old x + old y

as old x and old y must be Whole numbers, so that new x and new y must have the same odds. that is they must be either both even or both odd, no mixing. This makes the process easy for us to get the result. Simply count how many allowed even x and y, odd x and y, and times the numbers respectively.

since different python versions might treat divide differetly, here our division is always truncating division

from __future__ import division

def areaOfIntersection(shape1, shape2):
    xmin = max(shape1[1]+shape1[2]-(shape1[0]-1),shape2[1]+shape2[2]-(shape2[0]-1))
    xmax = min(shape1[1]+shape1[2]+(shape1[0]-1),shape2[1]+shape2[2]+(shape2[0]-1))
    ymin = max(shape1[1]-shape1[2]-(shape1[0]-1),shape2[1]-shape2[2]-(shape2[0]-1))
    ymax = min(shape1[1]-shape1[2]+(shape1[0]-1),shape2[1]-shape2[2]+(shape2[0]-1))
    if(xmin > xmax or ymin > ymax):
        return 0
    else:
        evenX = (xmax-xmin +2) // 2 if (0==xmin%2) else (xmax-xmin+1) // 2
        oddX = (xmax-xmin-evenX+1)
        evenY = (ymax-ymin +2) // 2 if (0==ymin%2) else (ymax-ymin+1) // 2
        oddY = (ymax-ymin-evenY+1)
        return evenX*evenY+oddX*oddY
\$\endgroup\$
4
  • \$\begingroup\$ your current also fails on [3, 0, -1], [5, 4, 0]. Answer should be 4, but you return 4.5. \$\endgroup\$
    – Krupip
    Jun 6 '17 at 19:09
  • \$\begingroup\$ I'm also not sure what you are basing any of your calculations on. why do you calculate xmin and xmax like that? They aren't even the correct values for xmin or xmax. I have no clue why you add 2 or divide or add the same value twice at the end. \$\endgroup\$
    – Krupip
    Jun 6 '17 at 19:21
  • \$\begingroup\$ The basic logic is trying to rotate the whole graph by 45 degree. so that the rectangles are now along the horizontal and vertical direction, and also the intersection rectangle. The difficulty lies in that when you have xmin, xmax, ymin, and ymax, how to correctly calculate how many blocks inside. I think I need consider that whether xmax-xmin and ymax-ymin is odd or even to get the return statement done. \$\endgroup\$
    – phy nju
    Jun 6 '17 at 19:29
  • \$\begingroup\$ you got fraction number b/c of different python version treat division differently, Please refer to the new code for testing. All the division in this code are truncating divisions. \$\endgroup\$
    – phy nju
    Jun 6 '17 at 21:40
0
\$\begingroup\$

I think I figured it out... :)

By only calculating the range where they can possibly meet I lessen the calculationload.

And by checking if that point falls in the range of both shapes I can tell there is a intersection at that point, so no need to map all points which gave me a TLE.

def areaOfIntersection(shape1, shape2):
    k = 0
    # min and max is the range where they can possibly intersect
    x_max = max(shape1[1] - shape1[0], shape2[1] - shape2[0])
    x_min = min(shape1[1] + shape1[0], shape2[1] + shape2[0])
    y_max = max(shape1[2] - shape1[0], shape2[2] - shape2[0])
    y_min = min(shape1[2] + shape1[0], shape2[2] + shape2[0])

for i in range(x_max, x_min):
    for j in range(y_max, y_min):
            # if in range of either
            if abs(i - shape1[1]) + abs(j - shape1[2]) < shape1[0] and abs(i - shape2[1]) + abs(j - shape2[2]) < shape2[0]:
                k += 1

    return k
\$\endgroup\$
1
  • \$\begingroup\$ I believe I've come up with a better way, see my answer. \$\endgroup\$
    – Krupip
    Jun 6 '17 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.