Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Find adjacent points

Subject: Find adjacent points

From: Brian Flemming

Date: 11 Nov, 2010 22:25:05

Message: 1 of 4

Given two contiguous disjoint sets Ai & Aj of (x,y) coordinates, is there an efficient method of determining which points (xi,yi) in Ai and (xj,yj) in Aj are adjacent; i.e. such that |xi-xj|<=1 and |yi-yj|<=1? I'm currently using a for...end loop to test the kth coordinate in one set against the vectorised representation of the other in a find statement. This seems inefficient, especially for large sets. Is there a fully vectorised method of achieving the same end?

Subject: Find adjacent points

From: Sean

Date: 11 Nov, 2010 22:40:06

Message: 2 of 4

"Brian Flemming" <qzxj37@googlemail.com> wrote in message <ibhqg1$a4o$1@fred.mathworks.com>...
> Given two contiguous disjoint sets Ai & Aj of (x,y) coordinates, is there an efficient method of determining which points (xi,yi) in Ai and (xj,yj) in Aj are adjacent; i.e. such that |xi-xj|<=1 and |yi-yj|<=1? I'm currently using a for...end loop to test the kth coordinate in one set against the vectorised representation of the other in a find statement. This seems inefficient, especially for large sets. Is there a fully vectorised method of achieving the same end?

I would use bsxfun to test equality of both x and y, and when it's in both then it's a neighbor, something like this:
xi = 3; %mid point one we care about
yi = 3;
[x5,y5] = meshgrid(1:5); %grid of indices 5x5

xnear = bsxfun(@(x,y)abs(x-y)<=1,x5(:),xi); %linear indices of close x's
ynear = bsxfun(@(x,y)abs(x-y)<=1,y5(:),yi); %linear indices of close y's

nearidx = xnear&ynear; %both close

[xnear ynear] = ind2sub(size(x5),find(nearidx)); %turn it back to x,y coordinates

Subject: Find adjacent points

From: Sean

Date: 11 Nov, 2010 22:53:04

Message: 3 of 4

"Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <ibhrc6$5hf$1@fred.mathworks.com>...
> "Brian Flemming" <qzxj37@googlemail.com> wrote in message <ibhqg1$a4o$1@fred.mathworks.com>...
> > Given two contiguous disjoint sets Ai & Aj of (x,y) coordinates, is there an efficient method of determining which points (xi,yi) in Ai and (xj,yj) in Aj are adjacent; i.e. such that |xi-xj|<=1 and |yi-yj|<=1? I'm currently using a for...end loop to test the kth coordinate in one set against the vectorised representation of the other in a find statement. This seems inefficient, especially for large sets. Is there a fully vectorised method of achieving the same end?
>
> I would use bsxfun to test equality of both x and y, and when it's in both then it's a neighbor, something like this:
> xi = 3; %mid point one we care about
> yi = 3;
> [x5,y5] = meshgrid(1:5); %grid of indices 5x5
>
> xnear = bsxfun(@(x,y)abs(x-y)<=1,x5(:),xi); %linear indices of close x's
> ynear = bsxfun(@(x,y)abs(x-y)<=1,y5(:),yi); %linear indices of close y's
>
> nearidx = xnear&ynear; %both close
>
> [xnear ynear] = ind2sub(size(x5),find(nearidx)); %turn it back to x,y coordinates

this can be multiple points too, otherwise there would be no reason for bsxfun
xi = [1 5]
yi = [1 5]

I did miss an any in this line though:
nearidx = any(xnear&ynear,2); %touching either point

If you wanted to find out which points are touching which you could do so by skipping the 'any' and running ind2sub every column of nearidx. The columns of nearidx correspond to the columns in xi,yi before the call to 'any'

Subject: Find adjacent points

From: ImageAnalyst

Date: 11 Nov, 2010 23:47:40

Message: 4 of 4

Brian Flemming:
What are you calculating this for? Because believe it or not the
distance between two polygons is not so straightforward. It sounds
like you want the "minimin" distance. But there are other distances
that may be more relevant depending on what you want to do. For
example, look at this tutorial page on the Hausdorf distance:

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

Now, for your problem the way you suggest is the most obvious and
straightforward. So what kind of speeds are you getting? How many
vertices? If you have only a few thousand and computation imes less
than a second or so, who cares? No sense turning an obvious intuitive
algorithm into a compact cryptic one just to beat down the time from 2
microseconds to 1 microsecond.
ImageAnalyst

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us