I have a raster image with a number of arbitrary shapes (blobs). I am interested to find, for every blob, its immediate neighbors, i.e. those that are visible from it in a straight line. The search can stop after a few neighbors (say 3) have been found, by decreasing closeness.

I imagine that a growing process around every shape (i.e. constructing offset curves of the boundary with increasing offset size) could work, excluding shadow areas created by the obstacles.

I allow myself a computing budget proportional to the image size (number of pixels), not more. So the above procedure will probably not achieve that goal, as the shapes will have "zones of influence" that overlap each other, and the total workload risks to be proportional to the number of shapes as well.

I am looking for suggestions on ways to reduce the processing time. Vectorizing the scene and working with discrete segments is allowed. Approximate solutions are allowed. In particular exact distance computation is not required. The exact visible area on the neighbors is not required, only mutual visibility matters.

enter image description here

  • $\begingroup$ I would suggest looking into ray casting: en.wikipedia.org/wiki/Ray_casting. Wolfenstein 3D ran smoothly on 1992 hardware! $\endgroup$ – j_random_hacker Nov 19 '17 at 17:36
  • $\begingroup$ Do you have some constraints about the size of the objects? Anything about approximate position? Or this is purely: look at the new, unknown raster and return k-nn (here k = 3)? By the processing time proportional to the number of pixels, (and vectorization) do you mean that one can read all pixels, return edges and check what is available for all objects? It would be quite inefficient or does the vectorization time does not count (e.g. is preprocessed?). $\endgroup$ – Evil Nov 21 '17 at 3:35
  • $\begingroup$ Flood fill with "boundary angles"? $\endgroup$ – greybeard Nov 21 '17 at 7:25
  • $\begingroup$ @evil: no, there is no constraint on size (except the images size < 1 megapixel). If that helps, centers, bounding boxes, moments... can be computed (as this is done in linear time). No preprocessing is allowed, this is a "one shot" question. If vectorization is done in linear time, you achieve very good compression of the data and can use algorithms working on geometric primitives. $\endgroup$ – Yves Daoust Nov 21 '17 at 9:15
  • $\begingroup$ I haven't tested it fully, but if you sparsely probe pixels (say one per k by k pixels, with finer grid than the smallest object) then when hit the primitive look for the border, find it's hull, processing the lines to vectors and if it is ellipse recovering it from two principal axis, and then sparsely casting rays, starting at center and ending in other centers, then if it hit something else discarding this object (it is not nearest anymore) otherwise uniformly probing by rays that are cast from vertices found, it will not read every pixel. The tricky part is to convert the geometric $\endgroup$ – Evil Nov 23 '17 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.