-1

The problem statement bit related to this one.

There is a list of rectangles that has 2 points given.

Each Rectangle is represented by x0,y0,x1,y1.

  1. x0,y0 - Represents top left or starting point
  2. x1,y1 - Represents bottom right or ending point

Note: We can sort the list in any format. Assume (can be changed) the list is sorted based on starting point.

Need to find given best rectangle where point X,Y lies in completely.

If more than one rectangle is overlapping, one can choose the rectangle with the smallest area.

This can be improved later to the shortest distance from any rectangle corner.

Input:

Point: (X, Y) = (1450,380)

List of rectangles :

[
  {
    "x0": 1797,
    "x1": 1854,
    "y0": 333,
    "y1": 434
  },
  {
    "x0": 1671,
    "x1": 1688,
    "y0": 423,
    "y1": 434
  },
  {
    "x0": 1565,
    "x1": 1594,
    "y0": 366,
    "y1": 378
  },
  {
    "x0": 1547,
    "x1": 1552,
    "y0": 112,
    "y1": 146
  },
  {
    "x0": 1439,
    "x1": 1457,
    "y0": 373,
    "y1": 396
  }
]

Output:

  {
    "x0": 1439,
    "x1": 1457,
    "y0": 373,
    "y1": 396
  }

One simple way to find is to iterate through all rectangles and find the smallest rectangle where the point lies. This is possible O(n) in complexity.

Is there a better solution for getting the best rectangle resolving overlapping scenarios in less complexity than O(n)?

Vaibhav More
  • 212
  • 1
  • 14

1 Answers1

2

A binary search won't work because you can only partition on one axis, but a spatial partitioning algorithm should work. For example, a quadtree data structure can trivially reduce the complexity of your search to O(logn) in a non-degenerate success case.

One can easily build a degenerate case that requires a linear scan however, where you have all elements of your array as the same rectangle. It's really up to how your data is coming in and how pedantic you want to be with labels.

Blindy
  • 65,249
  • 10
  • 91
  • 131
  • 1
    I agree that this is the right way to do things, but if each instance of the problem starts off with a fresh array of rectangles, I think we're still stuck with a linear search. – Pointy Feb 15 '23 at 19:28
  • The list is created once and is possible to transform into the expected format before proceeding to find the best one. – Vaibhav More Feb 16 '23 at 04:25
  • 1
    @VaibhavMore: the time needed to build the search data structure must be balanced by a sufficient number of accelerated queries. –  Feb 16 '23 at 08:31
  • @YvesDaoust There is no limit on queries. It can range from 1K to 10K at a time. As per code execution flow I can take a hit of processing data for faster retrieval. – Vaibhav More Feb 16 '23 at 10:05
  • @VaibhavMore: for how many rectangles ? –  Feb 16 '23 at 10:24
  • @YvesDaoust 200-1000 rectangles could be present at a given time. – Vaibhav More Feb 16 '23 at 10:40
  • Quadtree's your answer right there! – Blindy Feb 16 '23 at 15:11