Checking for overlaps of rectangles

[Hans Mayr]

Hello,

I have a problem with checking data integrity if I want to cover a n-
dimensional space with rectangles. I look for a solution which runs on
Oracle.

2-dimensional example: Imagine a bank lending money. The two
parameters determining the interest rate are credit duration and
credit amount. Neither increasing duration nor increasing amount will
necessarily lead to higher interest rates (compare market interest
rates during autumn 2008).

CREATE TABLE interestrates
(
Rate number,
Min_Amount number,
Max_Amount number,
Min_Duration number,
Max_Duration number,
PRIMARY KEY (`Min_Amount`,`Min_Duration`)
);

Through a trigger or a check constraint I will have to make sure that
min_amount < max_amount and min_duration < max_maxduration for all
entries. I assume that the lower borders are not part of the interval
and that all durations are between 1 and 36 and all amounts are
between 0 and 20000.

INSERT INTO interestrates VALUES (0.05, 0, 10000, 1, 12);
INSERT INTO interestrates VALUES (0.06, 0, 10000, 12, 24);
INSERT INTO interestrates VALUES (0.055, 10000, 20000, 1, 24);
INSERT INTO interestrates VALUES (0.053, 0, 20000, 24, 36);

Now the problem is determining if there is any (amount, duration)
which has no defined interest rate or more than one interest rates.

In http://groups.google.de/group/comp.databases.theory/browse_thread/thread/e208bfa769f01abb
I wrote a long message describing my thoughts and a possible but very
complicated solution. But nobody could provide me with an easy
solution or the "standard approach" there. So I try here again with
this simplified version of my problem.

I am looking forward to hearing from you.

Thanks and best,

Hans

[Shakespeare]

Hans Mayr schreef:

Just some thoughts:

You could use Oracle Spatial for this! (if you have licensed it of
course). I don't know if Locator (the free version of Spatial) will
cover this.

Btw: a simple way to check if you don't have holes (after checking there
is no overlap) is to calculate the total area size and compare it to
your total rectangle of values. To FIND the hole is a different story....

The other way around is also possible, if you know the area is covered,
you can check overlap by summing the areas. But both options only work
if one of the conditions is checked on forehand. With spatial, you can
do both checks in one go: summarize your rectangle areas and compare to
the area covered. If they match, your OK! If not, you either have
overlap (sum areas bigger than coverered area) of holes (sum areas
smaller than covered area). By performing a 'minus' over the covered
area and your total rectangle you find the holes.

Another option is the Painter's algorithm: create a rectangle (big 2
dimensional array) and let your rectangles 'paint' the surface of this
rectangle (by adding 1 to the array value). When done, check colors:
white space (value 0) is uncovered. Space with more than one color is
overlap.

And keep in mind: overlap of rectangles means crossing of one (or
actually 2) of their lines, which is much easier to calculate.

Shakespeare

[Hans Mayr]

Hello Shakespeare,

Thanks for your answer. It is nice for me to read that you pointed out
the problems I have seen and wrote about in my original message in the
other group. Thanks for the hints, I will check Locator. And just the
fact that there is something like the "Painter's Algorithm" shows that
a solution is pretty complicated and that there obviously is no easy
standard approach.

Best,

Hans

[Shakespeare]

Hans Mayr schreef:

Well, I think that algrithm is over 25 years old, so there should be
better options available now, since calculation power has grown.
I recall that the algorithm was used to calculate if a graphical object
was in the foreground (visible) or not. In your case, all objects should
be visible, and background should be completely covered.

I checked Locator for you. Locator has 'operators' available to check
whether objects have overlap or not (to be used in a where clause).
Unfortunately, with Locator you can not calculate the actual overlap
(size or shape), just the fact that they DO overlap.

The calculation part is in the SDO_GEOM package, which is licensed with
Spatial. It is installed in each database that has Locator, but you're
just not allowed to use it. Strange enough, it's even in the FREE XE
database, but still: don't touch! If Oracle finds out, you have to bleed....

Shakespeare

Ever seen a car salesman selling a car with 6 speed gear telling you
you're only allowed to shift from 1 up to 5, or you have to pay extra?

[Shakespeare]

Hans Mayr schreef:

Hans,

I suddenly remebered another old algorithm from the Computer Graphics
courses I followed some decades ago. It is an algorithm for which you
fill a 3 by 3 matrix for each combination of rectangles, with values
determined by the position of the corner coordinates (left, right,
above, below). The outcome in the matrix will tell you if the rectangles
overlap. It's fairly simple, but I don't remember the name, nor the
exact way it worked. Maybe one of the readers will remember. I'll try to
find it in one of y (old) books.

Shakespeare

[Hans Mayr]

Hi Shakespeare,

I just discovered your additional answers. Thanks again for your
effort and the valuable answers. I could imagine that the other
algorithm leads to similar results as the one I developed in the
original post. I will work something out from that.

And I wonder what our DB admin says about SDO_GEOM in FREE XE ... And
I wonder if the car salesman could sue if he gives you a car with six
gears, says that you only pay for five, that the sixth one is free and
writes somewhere that the sixth one is free to HAVE but USING it will
be charged ;-)

Best,

Hans