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
On Sun, 9 Jul 2017 23:35:58 +0200 Mikhail V mikhailwas@gmail.com 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,
On Mon, Jul 10, 2017, at 01:34, Jerome Kieffer wrote:
On Sun, 9 Jul 2017 23:35:58 +0200 Mikhail V mikhailwas@gmail.com 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/_ge...
Stéfan
On 10 July 2017 at 10:34, Jerome Kieffer Jerome.Kieffer@esrf.fr wrote:
On Sun, 9 Jul 2017 23:35:58 +0200 Mikhail V mikhailwas@gmail.com 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 :)
With boxes I mean a bounding box https://en.wikipedia.org/wiki/Minimum_bounding_box
And indeed they are cartesian ranges along all axes by definition. And with general case, did you mean the task of _finding_ this bounding box for a set of arbitrary points (e.g. a polygon)? If so that is definitely a separate task, merely for a graphical/geometry lib.
E.g. if I want to copy-paste arbitrary polygonal area between two arrays I think it is anavoidable to use masks, since there is no polygonal arrays. So i use boolean mask for simple blitting (crisp edges), or grayscale mask for smooth edges (like full alpha blitting).
And this is not condratictory to finding the box intersection. So if my source array needs a mask I use following approach, here using circle as a mask for simplicity:
import numpy import cv2
W = 10; H = 10
DEST = numpy.ones([H,W], dtype = "uint8") SRC = numpy.zeros_like(DEST) SRC[:]=8
SRC_mask = numpy.zeros_like(SRC) cv2.circle(SRC_mask, (H/2,W/2), 3, 1, -1) # draw mask SRC_mask = (SRC_mask == 1) # colorkey = 1 offset = (5,4) d = DEST.shape s = SRC.shape R = box_clip(d,s,offset) DEST_slice = p2slice( R[1], R[1] + R[0] ) SRC_slice = p2slice( R[2], R[2] + R[0] )
mask_tmp = SRC_mask[SRC_slice] # the maks also needs slicing!!! DEST[DEST_slice][mask_tmp] = SRC[SRC_slice][mask_tmp]
print (DEST)
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 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 1] [1 1 1 1 1 1 8 8 8 8] [1 1 1 1 1 1 8 8 8 8] [1 1 1 1 1 8 8 8 8 8]]
So as you see this is all the same code only with mask array added, it copies only the data inside the circle area of the SRC array, that is how for example colorkey blitting works.
That is one of the advantages to having "box_clip" as a separate function in order to be able to combine it with masking for example. So I need the intersection calculation to be able to do this without manual adjustments of the slices for an blit offset. How would you do this without the box_clip or similar function? Just want to note - it is needed not only for imaging software, it can be used for copying any data between arrays.
To find the bounding box of arbitrary polygon - yes one needs another function but that is different task. And if you want to extract the data from SRC within the mask but with an offset then again you'll need to find intersection rectangle first.
The idea is that if I want just to copy data I would need to import one of graphical libraries just for that one function (or roll my own function).
Mikhail