# Generalized rectangle intersection. (Was: Array blitting)

4 messages
Open this post in threaded view
|
Report Content as Inappropriate

## Generalized rectangle intersection. (Was: Array blitting)

 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 _______________________________________________ NumPy-Discussion mailing list [hidden email] https://mail.python.org/mailman/listinfo/numpy-discussion
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Generalized rectangle intersection. (Was: Array blitting)

 On Sun, 9 Jul 2017 23:35:58 +0200 Mikhail V <[hidden email]> wrote: > 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. I am using this kind of clipping as well but in the case you are suggesting the boxes looks aligned to the axis which is limiting to me. The general case is much more complicated (and interesting to me :) Moreover the scikit-image may be more interested for this algorithm. Cheers, -- Jérôme Kieffer tel +33 476 882 445 _______________________________________________ NumPy-Discussion mailing list [hidden email] https://mail.python.org/mailman/listinfo/numpy-discussion
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Generalized rectangle intersection. (Was: Array blitting)

 On Mon, Jul 10, 2017, at 01:34, Jerome Kieffer wrote: > On Sun, 9 Jul 2017 23:35:58 +0200 > Mikhail V <[hidden email]> wrote: > > > 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. > > I am using this kind of clipping as well but in the case you are > suggesting the boxes looks aligned to the axis which is limiting to me. > The general case is much more complicated (and interesting to me :) > > Moreover the scikit-image may be more interested for this algorithm. We use rectangular clipping in scikit-image, but general polygon clipping is easy thanks to Matplotlib's wrapping of the AGG library. Here's how to do it: https://github.com/scikit-image/scikit-image/blob/master/skimage/_shared/_geometry.py#L6Stéfan _______________________________________________ NumPy-Discussion mailing list [hidden email] https://mail.python.org/mailman/listinfo/numpy-discussion