Re: Checking for overlaps of rectangles
Date: Wed, 01 Jul 2009 09:50:29 +0200
Message-ID: <4a4b1545$0$185$e4fe514c_at_news.xs4all.nl>
Hans Mayr schreef:
> 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
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 Received on Wed Jul 01 2009 - 02:50:29 CDT