algorithm - Check if a point lies inside a rectangle

Question

I am doing a project in openCV. However the language is not a concern in this.

I have an array of rectangles, say. And I have a an array of points with coordinates x and y. My question is apart from using the brute force technique and check a point with every rectangle I have is there a better and more elegant solution.

I saw a similar question at this link but did not understand the solution:

Check if an array of points is inside an array of rectangles?

Background Information (For people who know image processing)

Please have a look at this question: Detecting Markers in a video Sequence The reason I require the above in a better time limit is because of this. The algorithm that I have thought for the same is to make a rectangle around each marker and in the next frame search for a marker inside a rectangle. If it lies inside a rectangle then it is likely that it was the same marker which has moved from the previous frame, then realign the rectangle to now fit the new marker position and so on. With so many frames the problem is likely to make processing slow hence this question. Thanks and cheers.

Answer 1

A common way to improve on the naive approach to this is to use Spatial Indexing. There are a couple of data structures that specialize in this. I bet OpenCV has some of these data structures available to you already.

One simple example of how to index your scene spatially is to break your scene down into a grid, and then for each rectangle, determine which grid cells the rectangle either contains or intersects with. Then you determine which cell your point lies in, and voila, you can now do your expensive hit test on a list of rectangles that is hopefully smaller than the naive method.

This algorithm is known as spatial hashing, and is used a lot for speeding up collision detection in 2D games. Note that the worst case of this algorithm occurs when all the rectangles are in every cell, or when all the rectangles and your point are in the same cell. Here's some rough pseudo code for how it applies to you. I would read up on spatial hashing though, there are whole articles that will describe the best way to do this.

rects = array of rectangles
grid = divide scene into n x m grid

for each cell in grid do
    cell.m_rects = determine_which_rects_intersect(cell, rects)
end

...

pt = some point in scene
pt_cell = grid.get_cell_for_pt(pt)

hits = empty array
for each rect in pt_cell.m_rects do
    if expensive_hit_test(pt, rect) then
        hits.append(rect)
    end
end

return hits

Answer 2

This is an explication how to check a point inside a rectangle

https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle

Answer 3

The question falls under 2 categories.

• Space Complexity
• Time Complexity

Which one is more important to you ? If its a game, then time complexity is more important to you. You want to make sure that your response time for this algorithm is not only fast, but also deterministic. Fast is easy to understand, so I wont explain it. Deterministic, means that every time you run this algo it will return back in a deterministic time, else your game will slow down and could get worse with time. Memory build ups to be avoided. Which means that you cannot allocate / decallocate memory while running this algorithm.

If space complexity is your issue, then you have to compromise on time and deterministic'ism.

The only solution for a algorithm is based on one assumption. The rectangles dont change with time. In that case you can create a array of boolean for "every point" on the resolution and determine in a background algorithm (bruteforce) if any point lies within the rectangle. That way your algo is O(1). Fast and Deterministic.

If your rectangles change with time, then you need a background process to know the rectangles before hand, and process it before the search takes place with your points.

This is not a solution, just a hint for your problem. I hope this helps.

Answer 4

Step 1: Sort the points according to x and y axis (so you have two sorted lists)

Step 2: For every rectangle do a binary search on these lists and calculate the candidate sets.

Step 3: Pick the smaller candidate set and verify if the other axis also contain each of these points.

Worst case complexity of this solution is pretty bad ( O(mn) ), but for most real cases this should work just fine.