1

I have N Non-Intersecting Rectangles. Every Rectangle has a name/number associated with it.

Now I am Given Some point (x,y) as a query. I have to answer the name of the rectangle inside which the point lies or -1 if there is no such rectangle.

There are Q such queries. And we get the next query only when we display the results of the current query.

1<=N,Q<=1000000
-1000000<=x,y<=1000000
How do we go about doing such question?
Do we need some good datastructure for such a problem? Please Help me out.
Please keep it as simple as possible. Thanks in advance.

Dhruv Chandhok
  • 780
  • 7
  • 18
  • Do you want to do this in code and could you do it in a database. All the major databases, both commercial and open source, support a spatial datatype, with spatial indexing, which makes this sort of query really easy to answer. You can also do this with the java.awt.Polygon class and contains method. You tagged the question with C++ and there is an answer for point in polygon here: http://stackoverflow.com/questions/11716268/point-in-polygon-algorithm – John Powell Mar 26 '14 at 08:02
  • I want to do this in code. And I have upto 10^6 queries and 10^6 rectangles , so it requires a highly optimised algorithm. Every query requires to be answered in O(log n). – Dhruv Chandhok Mar 26 '14 at 08:29
  • Point in polygon is a pretty efficient algorithm. Do you know about the kd-tree data structure. It is very efficient for searching and might suite your purposes. http://en.wikipedia.org/wiki/K-d_tree – John Powell Mar 26 '14 at 08:37
  • Yeah but this is different, we are not just searching whether a point in in a polygon or not. We have upto 10^6 rectangles(or polygons). – Dhruv Chandhok Mar 26 '14 at 12:26
  • No I don't know KD-tree data structure, I will read it. Hope it serves the purpose. – Dhruv Chandhok Mar 26 '14 at 12:27
  • 1
    Point in polygon is reasonably efficient, although point in rectangle is a better solution. Even so, you don't want to do a million point in rectangle operations for every query. The k-d tree is definitely the way to go here. – Jim Mischel Mar 26 '14 at 12:56

0 Answers0