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

[Mikhail V]

On 10 July 2017 at 10:34, Jerome Kieffer <Jerome.Kieffer at esrf.fr> wrote:
> On Sun, 9 Jul 2017 23:35:58 +0200
> Mikhail V <mikhailwas at 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