1

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.

Community
  • 1
  • 1
Sohaib
  • 4,556
  • 8
  • 40
  • 68
  • Is there any extra information/knowledge about the rectangles? (are they overlapping, axis-alligned, ...) – Emond Oct 08 '13 at 17:16
  • Also, might it not be a better idea to use a bounding circle instead of a rectangle? (easier to calculate) – Emond Oct 08 '13 at 17:17
  • Axis aligned. Always. – Sohaib Oct 08 '13 at 17:17
  • I can use a circle yes. Rectangle because c++ already provides an implemented rectangle. – Sohaib Oct 08 '13 at 17:18
  • 1
    Don't you already know which rectangles each point *is supposed* to be inside? Can't you use that knowledge? Do you really have to know if the marker has moved to a completely different rectangle? – Lasse V. Karlsen Oct 08 '13 at 17:36
  • Umm I can guess yes. 80 percent it would be the same as the point which was detected last time around. The rest of the times I must search. – Sohaib Oct 08 '13 at 17:39
  • 1
    Have you *tried* this yet? It seems to me that unless you have a *bunch* of markers, you should still be able to get a good framerate even if you went with an exhaustive search. Not that I'm advocating that. I think Lasse's idea is best, but how much time is it actually taking currently? – Geobits Oct 08 '13 at 18:02
  • No I haven't tried this as of yet. There are around 65 markers and hence 65 rectangles. Do you say it wont have much effect on my processing time even if I use brute force? – Sohaib Oct 08 '13 at 18:04
  • I don't know. My point is, you should try it and see. – Geobits Oct 08 '13 at 18:14
  • Thanks, Ill try. I hope it works cause the answers I am seeing below are really hopping over me ;) – Sohaib Oct 08 '13 at 18:17

4 Answers4

2

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
Ben P
  • 129
  • 9
  • Did you read that question in the link attached? I am trying to understand this its something a little new. – Sohaib Oct 08 '13 at 17:57
  • Think of the grid as a pixelization of your image. Create a grid as a 2D array of (flags, integers. lists of rectangle identifieres). Place all of your rectangles into the grid (turn on the flag, or or the integer into the grid[x,y], or add to list). Now you can check inclusion into a rectangle in O(1). – ChuckCottrill Oct 08 '13 at 18:01
  • Is their some resource that explains this approach better? – Sohaib Oct 08 '13 at 18:15
  • What if half of my rectangle lies in one part of the grid and another half in another part of the grid? – Sohaib Oct 08 '13 at 18:16
  • @SohaibI After reading your background info, I think you may be jumping the gun a bit by trying to track these markers yourself. The problem of tracking blobs over time is tricky, and there are lots of articles out there to read up on. Google for things like feature tracking and blob tracking. As for this algorithm I gave you, it will accomplish what you asked for in this question, but I don't think it will serve you tell in your larger goal of tracking features in a video, or in any case this algorithm will serve only a very small piece of the overall solution. – Ben P Oct 10 '13 at 19:36
  • @SohaibI If half a rectangle is in one grid cell and another half in another cell, this algorithm will still work. You are thinking from a "rectangles -> cells -> check against point" direction. Think in terms of a "find cell for point -> check rectangles intersecting that cell" direction. Good luck! – Ben P Oct 10 '13 at 19:37
  • @BenP Thanks Ben for the time being my brute force seems to be working although finally I think I have been able to grasp this algorithm. – Sohaib Oct 11 '13 at 14:44
  • If every cell is almost equal to a pixel don't you think `pt_cell = grid.get_cell_for_pt(pt)` would end being a little tedious? – Sohaib Oct 11 '13 at 14:47
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

Community
  • 1
  • 1
Slimen Belhajali
  • 48
  • 1
  • 9
1

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.

taxeeta
  • 1,188
  • 1
  • 12
  • 25
  • Memory is not a problem. Time complexity should be better cause a lot of frames need to be processed. This is not a game but still required efficiency in terms of time. – Sohaib Oct 08 '13 at 17:26
  • I do not completely understand you solution does it state that I should run a brute force in the background? – Sohaib Oct 08 '13 at 17:26
  • Yes, before you load your game, do all the processing and keep the boolean arrays ready for O(1) – taxeeta Oct 08 '13 at 17:27
  • I have done this before for a few games. Lightening fast.. :) – taxeeta Oct 08 '13 at 17:27
  • My rectangles do change with every frame unfortunately. That's the crux of my algorithm. – Sohaib Oct 08 '13 at 17:31
0

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.

ElKamina
  • 7,747
  • 28
  • 43
  • Thing is in most cases in fact 99 percent of the cases only one point would end up in a rectangle. So its more like n rectangles and n points. – Sohaib Oct 08 '13 at 17:34
  • That is the worst case complexity. It happens when most of the points are in xrange or yrange, but none in the rectangle. That is rare IMO. – ElKamina Oct 08 '13 at 21:07