[Numpy-discussion] Generalized rectangle intersection. (Was: Array blitting)

[Mikhail V]

disclaimer: I am not a past contributor to numpy and I don't know
much about github, and what pull request means. So I just put the
examples here.

So in short, the proposal idea is to add a library function which
calculates the intersection
area of two rectangles, generalized for any dimensions.
The need for this function comes quite often so I suppose it would be good
to have such function in the library.

Python function prototype:

def  box_clip(box1, box2, offset):
 -> (box_intersection, offset1, offset2)

Here the rectangle is called "box". The function takes three
equally sized arrays (or tuples) which denote the cartesian
parameters of boxes and their relative position:
 - box1 - destination box size (only positive values)
 - box2 - source box size (only positive values)
 - offset - offset between box2 and box1 the boxes ( any values )

And returns an array (or tuple?) containing 3 arrays :
 - box_intersection : size of the intersection area
 - offset1 : offset in box1' coordinate system
 - offset2 : offset in box2' coordinate system


Following are example of the full  function with comments and
usage examples, all tested with arrays and tuples as input and all seem
to work correctly.

#=====

def box_clip(box1, box2, offset):

    L = len(box1)                    # amount of dimensions
    sizes_equal = ( L == len (box2) == len (offset) )
    if not sizes_equal:
        print ("Error: input arrays must have equal size")
        return

    R = numpy.zeros((3, L))         # init result array

    for i in range (0,L):        # take the  i-th axis
        d = box1[i]                    # dest box size along i-th axis
        s = box2[i]                    # source box size along i-th axis
        o = offset[i]                # offset along i-th axis
        left = max(0, o)            # startpoint of the clipped area
        right = min(d, o+s)            # endpoint of the clipped area
        r = right - left            # size of the clipped area
        if r < 0: r = 0                # clamp negative size values
        R[0,i] = r                    # return the size of the clipped area
        R[1,i] = left                # return the offset in respect to
the destinatition box
        R[2,i] = left-o                # return the offset in respect
to the source box

    return R

#=====

Typical use cases:

Example 1.
Finding the intersection of two rectangles. E.g. for 2D rectangles defined
in the tuple format (coordinate, size):

rect1 = numpy.array ( ( (0, 5), (10, 20) ) )
rect2 = numpy.array ( ( (1, 5), (10, 20) ) )
R = box_clip( rect1[1], rect2[1], rect2[0] - rect1[0] )

> R
[[  9.  20.]        # intersection size
 [  1.   0.]        # coordinate in rect1's origin
 [  0.   0.]]        # coordinate in rect2's origin

E.g. to construct the  rectangle object in the same input format
(global coord, size) just
sum the local rect1's coordinate (R[1]) and global rect1's coordinate:

rect_x = numpy.array ( ( rect1[0] + R[1] , R[0] ) )

> rect_x
[[  1.   5.]
 [  9.  20.]]



Example 2.
Use the function as a helper to find array slices for the array "blit"
operation.
This will need another intermediate function to convert between two
cartesian points and
the slice object:

def p2slice(startpoint, endpoint):            # point to slice conversion
    intervals = numpy.column_stack((startpoint, endpoint))
    slices =  [slice(*i) for i in intervals]
    return slices

# exampe of blitting SRC array into the DEST array at a given offset

W = 6; H = 6
w = 4; h = 1
DEST = numpy.ones([H,W], dtype = "uint8")
SRC = numpy.zeros([h,w], dtype = "uint8")
SRC[:]=8

offset = (5,4)

R = box_clip(DEST.shape, SRC.shape, offset)
DEST_slice = p2slice( R[1], R[1] + R[0] )
SRC_slice = p2slice( R[2], R[2] + R[0] )

DEST[DEST_slice] = SRC[SRC_slice]        # blit

>> DEST
[[1 1 1 1 1 1]
 [1 1 1 1 1 1]
 [1 1 1 1 1 1]
 [1 1 1 1 1 1]
 [1 1 1 1 1 1]
 [1 1 1 1 8 8]]


Notes:
the function should be as general as possible.
The input as box sizes and returning  the intersection area size
and both local offsets  seems to be appropriate, since more often
the rectangle objects are defined as (coordinate, size) tuple and in many
cases the destination box is itself the origin (i.e. it's coordinate is 0,0,..)
But of course there can be various variants for the output format
and order.


Regards,
Mikhail V