Hi,
I need to hash a set of regions. Each region is a set of "start" and "end" coordinates.
class Region
{
int posStart;
int posEnd;
}
Now the task is to find all regions that contain coordinate "pos" in log time. Regions in the set may intersect.
Does anyone have an idea how to do it?
Thanks in advance,
Pavel.
Hashing is not really appropriate for regions.
Consider creating a new set of intervals that form a partition of your space. Each of the new intervals should have a pointer back to a list of the original intervals that intersect in that region. For example, if you have:
x1x2
r1:|-|
r2:|--|
x3x4
Form the partition:
x1 x3
R1:||x2
R2:||x4
R3:|-|
R1 would have a pointer to r1, R2 has a pointer to (r1, r2) and R3 has a pointer to r2.
Now throw your partition into a set, sorted by the initial value and you're done.