Field of view/ convexity map

Question

On a shape from a logical image, I am trying to extract the field of view from any point inside the shape on matlab :

I tried something involving to test each line going through the point but it is really really long.(I hope to do it for each points of the shape or at least each point of it's contour wich is quite a few times)

I think a faster method would be working iteratively by the expansion of a disk from the considered point but I am not sure how to do it.

How can I find this field of view in an efficient way?

Any ideas or solution would be appreciated, thanks.

Answer 1

Here is a possible approach (the principle behind the function I wrote, available on Matlab Central):

I created this test image and an arbitrary point of view:

testscene=zeros(500);
testscene(80:120,80:120)=1;
testscene(200:250,400:450)=1;
testscene(380:450,200:270)=1;

viewpoint=[250, 300]; 
imsize=size(testscene); % checks the size of the image

It looks like this (the circle marks the view point I chose):

The next line computes the longest distance to the edge of the image from the viewpoint:

maxdist=max([norm(viewpoint), norm(viewpoint-[1 imsize(2)]), norm(viewpoint-[imsize(1) 1]), norm(viewpoint-imsize)]);

angles=1:360; % use smaller increment to increase resolution

Then generate a set of points uniformly distributed around the viewpoint.:

endpoints=bsxfun(@plus, maxdist*[cosd(angles)' sind(angles)'], viewpoint);

for k=1:numel(angles)
        [CX,CY,C] = improfile(testscene,[viewpoint(1), endpoints(k,1)],[viewpoint(2), endpoints(k,2)]);
        idx=find(C);
        intersec(k,:)=[CX(idx(1)), CY(idx(1))];
end

What this does is drawing lines from the view point to each directions specified in the array angles and look for the position of the intersection with an obstacle or the edge of the image.

This should help visualizing the process:

Finally, let's use the built-in roipoly function to create a binary mask from a set of coordinates:

FieldofView = roipoly(testscene,intersec(:,1),intersec(:,2));

Here is how it looks like (obstacles in white, visible field in gray, viewpoint in red):