0

I'm sure somewhere has this question been solved, but after 2 hours of search without finding the solution, I'm desperatly searching for your help.

There is position in an 2d-Array given and I want to search for the same value around this position. Now I dont want to use a double for-loop. I want to search around the position with an increasing circle. Example:

position is 0,0:

  1. search at 0,0;
  2. search at -5, 0;
  3. search at -5, -5;
  4. search at 0, -5;
  5. search at 5, -5;
  6. search at 5, 0;
  7. search at 5, 5;
  8. ....

When the circle is completed i want to increase the search radius from -5, 0; to -10, 5;

Main goal therefor ist not to search in a position, which has already been searched. I tried to implement it with for-loops or booleans but neither worked. Do you have an idea? I need to make it in C++, but any ideas are apreciated!

Thanks for your help and have a good day!

Philipp F.
  • 131
  • 7
  • Why don't you want to do it in a nested loop fashion? Would sound suspiciously like a homework exercise, if you don't have a good answer. – Grimaldi Jul 01 '17 at 11:46
  • 1
    Those coordinates don't look like a circle to me. Do you mean like an outgoing spiral? – meowgoesthedog Jul 01 '17 at 22:58
  • *I tried to implement it with for-loops or booleans but neither worked.* What did you try? And why did you tag this with `[performance]`? What kind of CPU do you want this to run on, and what SIMD extensions can you use? – Peter Cordes Jul 02 '17 at 00:07
  • Also, why don't you need to check `[1,1]` and so on? What kind of data do you have that lets you check for exact matches only every 5 elements, without missing something? If this is something like a video-encoder motion-search, then have a look at some of x264's search algorithms. e.g. [diamond vs hex vs umh vs. exhaustive](https://forum.doom9.org/showthread.php?p=693742). – Peter Cordes Jul 02 '17 at 00:10
  • 1
    @Grimaldi No it's not a homework. I want to write an tracking algorithm to track a person in a video. Therefore I compare two histograms of the known person and the areas around the old position. I want so search around the old position with an increasing circle (or spiral idk how to say it proper in english) – Philipp F. Jul 03 '17 at 08:43
  • I want to make the steps in 5 pixel size because the performance of the drone, where the tracker should run finally, is not that high (@PeterCordes) – Philipp F. Jul 03 '17 at 08:43
  • @PhilippF.: So you're actually comparing whole blocks with a SAD or something, not looking for exact equality? That wasn't what you said in the question. – Peter Cordes Jul 03 '17 at 10:35
  • What you're basically asking for is "feature tracking", check that on Google, read e.g. https://courses.engr.illinois.edu/cs543/sp2012/lectures/Lecture%2008%20-%20Feature%20Tracking%20and%20Optical%20Flow%20-%20Vision_Spring2012.pdf then look up the respective algorithms. – Grimaldi Jul 03 '17 at 17:51

0 Answers0