Generalized rectangle intersection. (Was: Array blitting)

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

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

Jerome Kieffer
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Stefan van der Walt
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#L6

Stéfan
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Mikhail V
In reply to this post by Jerome Kieffer
On 10 July 2017 at 10:34, Jerome Kieffer <[hidden email]> 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 :)

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
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/numpy-discussion
Loading...