|  | look up table for the overlapping rectangle | | |
| | | Guest |  |
|  Posted: Tue Aug 19, 2008 9:57 am Post subject: look up table for the overlapping rectangle |  |
| |  | |
I am writing a c++ program about extracting rectangles. I have a
overlapping coefficient which is between 0 and 1. If two rectangles
are given, I can find the overlapping coefficient wihout any problem.
My problem is this:
My program is an iterative program which iterates for 3000 times, and
in each iteration it has to find the overlapping coefficient for each
rectangle in the current configuration. At the very first iterations,
there are like 2000 rectangles, which consumes a lot of time for
finding the overlapping coefficient for each rectangle. That's why I
decided to write each overlapping scenario to an array for two
rectangles. It is like this:
Consider the program will extract the rectangles between the range of
W:[90 100] and L:[60 80] pixels. So if I consider a rectangle in this
range I will have a 4D array four the dimensions like array[10][20][10]
[20](10 means the range 90-100 and 20 means the range 60-80) and also
there will be a rotation for each rectangle which makes 4D to 6D like
(If we think that the discretization step will be 10 degrees than it
will be [10][20][10][20][18][18]).Ok.Then there should be distance
between the centers of the rectangles like x dim= 2sqrt(2)*(max(W,L))
and y dim= 2sqrt(2)*(max(W,L)).It can easily be calculated
intuitively. so 6D array will be 8D [10][20][10][20][18][18][280]
[280]. The first 4D is for the dimensions of each rectangle, 5th and
6th dimensions for the angle, and the last 2D is for the x and y
distances...
So this array will be , on the condition that I use 4bit type, it will
be 4000 gb:(
So my problem is to recompress the array, which I will use for look up
table for 2 rectangles.
Another example: I did this for circle overlapping which is very
trivial like if there is two rectangles of which R is between 40 and
50, it will be like [10][10] for the radiuses of each circle and [100]
for the distance so it is [100][10][10]. If I reach the element
array[38][4][6], it will mean that "give me the overlapping
coefficient for the scenario which first circle is 44 and second
circle is 46 and the distance between the centers is 38".So that is...
PS:The second example is given for better understanding because circle
is easier to understand the design... |
| |
| | | Pascal J. Bourguignon | |
| | Posted: Tue Aug 19, 2008 9:51 pm Post subject: Re: look up table for the overlapping rectangle | |
| | | |
fatih.arslan.koc@gmail.com writes:
| Quote: | I am writing a c++ program about extracting rectangles. I have a
overlapping coefficient which is between 0 and 1. If two rectangles
are given, I can find the overlapping coefficient wihout any problem.
My problem is this:
|
If you have a time complexity problem, indeed sometimes it can be
solved by trading space for time, but obviously your approach is not
the good one, since you'd need more memory than available (and using
too much memory takes time too, since RAM is much much slower than
L2-cache).
| Quote: | My program is an iterative program which iterates for 3000 times, and
in each iteration it has to find the overlapping coefficient for each
rectangle in the current configuration. At the very first iterations,
there are like 2000 rectangles, which consumes a lot of time for
finding the overlapping coefficient for each rectangle.
|
Where are you consuming this time? I don't understand exactly your
problem, but it seems to be that computing the "overlapping
coefficient" of two given rectangles would be a O(1) operation.
So I assume that you are computing it for every couple of rectangles,
thus having a O(n^2) loop.
One way to avoid useless comparisons between unrelated rectangles
would be to use a quad-tree structure. This is similar to a binary
tree, only since rectangles have 2D coordinates, you cut each nodes in
four childens, (x<m;y<n), (x>=m;y<n), (x<m;y>=n), (x>=m;y>=n).
(Rectangles that would cross a boundary would be attached to the
parent node). You build this quad-tree down to the depth where only a
small number of rectangles remains attached to the node.
With such a structure you don't need to compare rectangles that are
not in the same node, since they won't overlap.
LINK
--
__Pascal Bourguignon__ LINK
IMPORTANT NOTICE TO PURCHASERS: The entire physical universe,
including this product, may one day collapse back into an
infinitesimally small space. Should another universe subsequently
re-emerge, the existence of this product in that universe cannot be
guaranteed. |
| |
| | | Guest | |
| | Posted: Wed Aug 20, 2008 9:30 am Post subject: Re: look up table for the overlapping rectangle | |
| | | |
First of all, thank you for help...I am not a computer scientist, that
s why I need to improve my programming skills.
As far as I understand from your reply, it looks I could not explain
my problem in a good way. Because you recommended me a way to prevent
me from comparing rectangles that they do not overlap.
But my problem is not this....
It is like this....I have a current configuration of rectangles.
Imagine that it is a 800*800 image and there are 40 rectangles in the
configuration. I need to assign a overlapping coefficient to EACH
rectangle. It means that if overlapping coefficient is 0 for a
rectangle, it does not overlap any other rectangle. If it is 0.5, half
of the rectangle is in overlap with other rectangle and so on...
So As I said, consider 40 rectangles in 800*800 image. I will scan all
the rectangles.
For Rect 1:
it would be located in (200,200) and W is 40 L is 40, That s why I
need to search for any rectangle in a region [80sqrt(2)][80sqrt(2)],
which is like 112*112 so the other rectangles can be in [200-56,200+56]
[200-56,200+56] so I have the search for the region "from 144 to 256 X
from 144 to 256". And if there is another rectangle(s) in this area, I
have to find a overlapping coefficient between these two rectangles.
For Rect 2: ............and so on till the last rectangle.
As a conclusion, I need to find a way to calculate the overlap
percentage(which means overlapping pixels/ area of first rectangle).
In my first post, I considereded about making a look up table, which
is very very big and inefficient.
Quadtree looks like a way to give me the answer if they overlap or
not...Like a detector, moreover I need to assign a value indicating
the overlapping percentage instead if 'yes it overlaps' or 'no'...
Thank you
On Aug 20, 1:51 am, p...@informatimago.com (Pascal J. Bourguignon)
wrote:
| Quote: | fatih.arslan....@gmail.com writes:
I am writing a c++ program about extracting rectangles. I have a
overlapping coefficient which is between 0 and 1. If two rectangles
are given, I can find the overlapping coefficient wihout any problem.
My problem is this:
If you have a time complexity problem, indeed sometimes it can be
solved by trading space for time, but obviously your approach is not
the good one, since you'd need more memory than available (and using
too much memory takes time too, since RAM is much much slower than
L2-cache).
My program is an iterative program which iterates for 3000 times, and
in each iteration it has to find the overlapping coefficient for each
rectangle in the current configuration. At the very first iterations,
there are like 2000 rectangles, which consumes a lot of time for
finding the overlapping coefficient for each rectangle.
Where are you consuming this time? I don't understand exactly your
problem, but it seems to be that computing the "overlapping
coefficient" of two given rectangles would be a O(1) operation.
So I assume that you are computing it for every couple of rectangles,
thus having a O(n^2) loop.
One way to avoid useless comparisons between unrelated rectangles
would be to use a quad-tree structure. This is similar to a binary
tree, only since rectangles have 2D coordinates, you cut each nodes in
four childens, (x<m;y<n), (x>=m;y<n), (x<m;y>=n), (x>=m;y>=n).
(Rectangles that would cross a boundary would be attached to the
parent node). You build this quad-tree down to the depth where only a
small number of rectangles remains attached to the node.
With such a structure you don't need to compare rectangles that are
not in the same node, since they won't overlap.http://en.wikipedia.org/wiki/Quadtree
--
__Pascal Bourguignon__ LINK
IMPORTANT NOTICE TO PURCHASERS: The entire physical universe,
including this product, may one day collapse back into an
infinitesimally small space. Should another universe subsequently
re-emerge, the existence of this product in that universe cannot be
guaranteed. |
|
| |
|
|
