Thread Subject: Avoiding for-loop

Hi all!

I have a list of coordinates (u,v) that I want to be mapped
to a matrix (in this case an image). I have 2 mesh matrices
(x,y) that contain a grid of u,v coordinates. Now I want to
find the element in x,y which is the nearest.

So far I'm using a for-loop which takes too long for a list
with 10000 coordinates and a grid of (100x100)

Anyone has an idea?

Example:
My coordinates u and v:
u1,v1 = 1.3, 3.6

My grid looks like this:
u-grid: 0 1 2
        0 1 2
        0 1 2

v-grid: 2 2 2
        3 3 3
        4 4 4

So I want my coordinates u1,v1 should be mapped to [3,1]

anyone has an idea how to avoid the for-loop?

Thanks in advance!
Volker

"Volker K" <klinkv.NOSPAM@yahoo.de> wrote in message
<fpedv5$gu6$1@fred.mathworks.com>...
> Hi all!
>
> I have a list of coordinates (u,v) that I want to be
mapped
> to a matrix (in this case an image). I have 2 mesh
matrices
> (x,y) that contain a grid of u,v coordinates. Now I want
to
> find the element in x,y which is the nearest.
>
> So far I'm using a for-loop which takes too long for a
list
> with 10000 coordinates and a grid of (100x100)
>
> Anyone has an idea?
>
> Example:
> My coordinates u and v:
> u1,v1 = 1.3, 3.6
>
> My grid looks like this:
> u-grid: 0 1 2
> 0 1 2
> 0 1 2
>
> v-grid: 2 2 2
> 3 3 3
> 4 4 4
>
> So I want my coordinates u1,v1 should be mapped to [3,1]
>
> anyone has an idea how to avoid the for-loop?
>
> Thanks in advance!
> Volker
>
>

this may be faster:

>> % set it up like you
>> u1 = 1.3;
>> v1 = 3.6;
>> u = repmat([0 1 2],[3 1]);
>> v = repmat([2 3 4]',[1 3]);

>> % subtract the value you're searching for
>> subU = abs(u-u1);
>> subV = abs(v-v1);

>> % find the minimum
>> [minU indexU] = min(subU(:));
>> [minV indexV] = min(subV(:));

>> % output the values
>> u(indexU)
ans =
     1
>> v(indexV)
ans =
     4

"Volker K" <klinkv.NOSPAM@yahoo.de> wrote in message
<fpedv5$gu6$1@fred.mathworks.com>...
> Hi all!
>
> I have a list of coordinates (u,v) that I want to be
mapped
> to a matrix (in this case an image). I have 2 mesh
matrices
> (x,y) that contain a grid of u,v coordinates. Now I want
to
> find the element in x,y which is the nearest.
>
> So far I'm using a for-loop which takes too long for a
list
> with 10000 coordinates and a grid of (100x100)
>
> Anyone has an idea?
>
> Example:
> My coordinates u and v:
> u1,v1 = 1.3, 3.6
>
> My grid looks like this:
> u-grid: 0 1 2
> 0 1 2
> 0 1 2
>
> v-grid: 2 2 2
> 3 3 3
> 4 4 4
>
> So I want my coordinates u1,v1 should be mapped to [3,1]
>
> anyone has an idea how to avoid the for-loop?
>
> Thanks in advance!
> Volker
>
>

keep in mind, though, that if your mapping is linear as
you've shown, it'd probably be even better to just write a
mex file to do the loop in C and just break out of the loop
as soon as you've found the first index that has an
increasing difference.

Hi Ian!
I had the same idea...but:
I have ~10000 uv coordinates pairs.
Which means I have to use "repmat" and create 10000 uv-grids
as well. The UV grid is not linear...I only have one GB RAM

Is there a way to subtract a single m-n from a m-n-p matrix
array?
That would help a lot...

But thanks for you thoughts!
Volker

Volker K <klinkv.NOSPAM@yahoo.de> wrote:
> Hi all!
>
> I have a list of coordinates (u,v) that I want to be mapped
> to a matrix (in this case an image). I have 2 mesh matrices
> (x,y) that contain a grid of u,v coordinates. Now I want to
> find the element in x,y which is the nearest.
>
[snip]

I assume your x and y grids are formed e.g from meshgrid.
If that is the case, then you can find the appropriate elements using
interp1, and avoid the for loop.

x = (0:2:200)';
y = (0:5:500)';
[X,Y] = meshgrid(x,y);
xi = (1:length(x))';
yi = (1:length(y))';
u = 100 * rand(1000,1);
v = 200 * rand(1000,1);
ui = interp1(x,xi,u,'nearest');
vi = interp1(y,yi,v,'nearest');
un = x(ui);
vn = y(vi);



--
Dr Tristram J. Scott
Energy Consultant

Unfortunately the x and y grid are not made with meshgrid...
Maybe I should explain what I'm trying to:
I have georeferenced image so that every pixel has an earth
coordinate (Latitude and Longitude) assigned. Therefore I
have 2 arrays (LatArray,LonArray)with the resolution of the
image (100x100) but containing the earth coordinates for
each pixel.

Now I have a list of coordinates, also given in Lat/Lon. I
want to find these coordinates within the georeferenced
image, but as the coordinates do not perfectly match I need
to find the nearest one.
Right now I'm using a for-loop to calculate the euclidean
distance for each coordinate.

Thanks so much guys for your time and help!






tristram.scott@ntlworld.com (Tristram Scott) wrote in
message <ccCuj.2055$ab5.1911@newsfe1-win.ntli.net>...
> Volker K <klinkv.NOSPAM@yahoo.de> wrote:
> > Hi all!
> >
> > I have a list of coordinates (u,v) that I want to be mapped
> > to a matrix (in this case an image). I have 2 mesh matrices
> > (x,y) that contain a grid of u,v coordinates. Now I want to
> > find the element in x,y which is the nearest.
> >
> [snip]
>
> I assume your x and y grids are formed e.g from meshgrid.
> If that is the case, then you can find the appropriate
elements using
> interp1, and avoid the for loop.
>
> x = (0:2:200)';
> y = (0:5:500)';
> [X,Y] = meshgrid(x,y);
> xi = (1:length(x))';
> yi = (1:length(y))';
> u = 100 * rand(1000,1);
> v = 200 * rand(1000,1);
> ui = interp1(x,xi,u,'nearest');
> vi = interp1(y,yi,v,'nearest');
> un = x(ui);
> vn = y(vi);
>
>
>
> --
> Dr Tristram J. Scott
> Energy Consultant

"Volker K" <klinkv.NOSPAM@yahoo.de> writes:

> Hi all!
>
> I have a list of coordinates (u,v) that I want to be mapped
> to a matrix (in this case an image). I have 2 mesh matrices
> (x,y) that contain a grid of u,v coordinates. Now I want to
> find the element in x,y which is the nearest.
>
> So far I'm using a for-loop which takes too long for a list
> with 10000 coordinates and a grid of (100x100)
>
> Anyone has an idea?
>
> Example:
> My coordinates u and v:
> u1,v1 = 1.3, 3.6
>
> My grid looks like this:
> u-grid: 0 1 2
> 0 1 2
> 0 1 2
>
> v-grid: 2 2 2
> 3 3 3
> 4 4 4
>
> So I want my coordinates u1,v1 should be mapped to [3,1]

I can't quite follow your example, but it sounds like "interp2" should
do what you want. Specify 'nearest' for interpolation method to keep
the rouding behavior, or leave the default 'linear' option for bilinear
interpolation.

-Peter

"Volker K" <klinkv.NOSPAM@yahoo.de> writes:

> Unfortunately the x and y grid are not made with meshgrid...
> Maybe I should explain what I'm trying to:
> I have georeferenced image so that every pixel has an earth
> coordinate (Latitude and Longitude) assigned. Therefore I
> have 2 arrays (LatArray,LonArray)with the resolution of the
> image (100x100) but containing the earth coordinates for
> each pixel.
>
> Now I have a list of coordinates, also given in Lat/Lon. I
> want to find these coordinates within the georeferenced
> image, but as the coordinates do not perfectly match I need
> to find the nearest one.
> Right now I'm using a for-loop to calculate the euclidean
> distance for each coordinate.
>
> Thanks so much guys for your time and help!

Ah. That is indeed a job for interp2.

newimage = interp2(latarray, lonarray, geo_image, new_lat, new_lon);


As a note, if this image is over a relatively small area (less than a
few degrees of longitude), you might consider converting things over to
UTM coordinates. This produces even grids, equal x-y coordinates, and
distances in meters.

-Peter

well, it's a bit different: my aim is to create a m-by-n
binary coastline image from a set of coordinates.

Therefore I have:

LatArray, m-by-n, containing the Latitudes for each pixel
LonArray, m-by-n, containing the Longitudes for each pixel
m and n = 101

LatVector, q-by-1
LonVector, q-by-1
q is about 10000

The coordinates given by Lat/LonVector need to be found
within Lat/LonArray, even if the values given do not
perfectly match the values stored in the arrays. I will need
the subscripts of the array elements that matched the vector
coordinates.

Finally a new m-n blank image is created and a pixel is set
to 1, if it contains a coord. of the vector...





> Ah. That is indeed a job for interp2.
>
> newimage = interp2(latarray, lonarray, geo_image, new_lat,
new_lon);
>
>
> As a note, if this image is over a relatively small area
(less than a
> few degrees of longitude), you might consider converting
things over to
> UTM coordinates. This produces even grids, equal x-y
coordinates, and
> distances in meters.
>
> -Peter

I'm really running out of ideas...

"Volker K" <klinkv.NOSPAM@yahoo.de> wrote in message
<fpf0hi$lut$1@fred.mathworks.com>...
> well, it's a bit different: my aim is to create a m-by-n
> binary coastline image from a set of coordinates.
>
> Therefore I have:
>
> LatArray, m-by-n, containing the Latitudes for each pixel
> LonArray, m-by-n, containing the Longitudes for each pixel
> m and n = 101
>
> LatVector, q-by-1
> LonVector, q-by-1
> q is about 10000
>
> The coordinates given by Lat/LonVector need to be found
> within Lat/LonArray, even if the values given do not
> perfectly match the values stored in the arrays. I will need
> the subscripts of the array elements that matched the vector
> coordinates.
>
> Finally a new m-n blank image is created and a pixel is set
> to 1, if it contains a coord. of the vector...
>
>
>
>
>
> > Ah. That is indeed a job for interp2.
> >
> > newimage = interp2(latarray, lonarray, geo_image, new_lat,
> new_lon);
> >
> >
> > As a note, if this image is over a relatively small area
> (less than a
> > few degrees of longitude), you might consider converting
> things over to
> > UTM coordinates. This produces even grids, equal x-y
> coordinates, and
> > distances in meters.
> >
> > -Peter
>

[re-ordering top-post]

"Volker K" <klinkv.NOSPAM@yahoo.de> writes:

>> Ah. That is indeed a job for interp2.
>>
>> newimage = interp2(latarray, lonarray, geo_image, new_lat,
>> new_lon);
>>
>> As a note, if this image is over a relatively small area (less than a
>> few degrees of longitude), you might consider converting things over
>> to UTM coordinates. This produces even grids, equal x-y coordinates,
>> and distances in meters.
>
> well, it's a bit different: my aim is to create a m-by-n
> binary coastline image from a set of coordinates.
>
> Therefore I have:
>
> LatArray, m-by-n, containing the Latitudes for each pixel
> LonArray, m-by-n, containing the Longitudes for each pixel
> m and n = 101
>
> LatVector, q-by-1
> LonVector, q-by-1
> q is about 10000
>
> The coordinates given by Lat/LonVector need to be found
> within Lat/LonArray, even if the values given do not
> perfectly match the values stored in the arrays. I will need
> the subscripts of the array elements that matched the vector
> coordinates.
>
> Finally a new m-n blank image is created and a pixel is set
> to 1, if it contains a coord. of the vector...

OK, so instead of looking up values from the image, look up values from
a specially constructed array of the values you want to find. Also, use
the 'nearest' argument to interp2. Maybe something like:

[LatIndices LonIndices] = meshgrid(1:m, 1:n);

Lat = interp2(LatArray, LongArray, LatIndices, LatVector, LonVector, 'nearest');
Lon = interp2(LatArray, LongArray, LonIndices, LatVector, LonVector, 'nearest');


It is quite possible I have some of these reversed.

-Peter

why did you not provide the for loop for better
understanding of your problem?
hmm for me it looks just like filling appropriate positions
of LatArray and LonArray of an matrix.

% i like column vectors more
% as the points should be put in a Matrix they must be
% integer
LatArray = round(LatArray(:));
LonArray = round(LonArray(:));

minlat = min(LatArray);
minlon = min(LonArray);
% points should be placed in a matrix, smallest coordinate
% must be 1
LatArray = LatArray-minlat+1;
LonArray = LonArray-minlon+1;
maxlat = max(LatArray);
maxlon = max(LonArray);
% so first create the matrix
%maybe i exchange lat with lon..
outimg = zeros(maxlon, maxlat);
% then get the coordinates in linear form
linidx = sub2ind(size(outimg), LonArray, LatArray);
%now set the coordinates to 1
outimg(linidx) = 1;

hth
kinor




"Volker K" <klinkv.NOSPAM@yahoo.de> wrote in message
<fpf0hi$lut$1@fred.mathworks.com>...
> well, it's a bit different: my aim is to create a m-by-n
> binary coastline image from a set of coordinates.
>
> Therefore I have:
>
> LatArray, m-by-n, containing the Latitudes for each pixel
> LonArray, m-by-n, containing the Longitudes for each pixel
> m and n = 101
>
> LatVector, q-by-1
> LonVector, q-by-1
> q is about 10000
>
> The coordinates given by Lat/LonVector need to be found
> within Lat/LonArray, even if the values given do not
> perfectly match the values stored in the arrays. I will need
> the subscripts of the array elements that matched the vector
> coordinates.
>
> Finally a new m-n blank image is created and a pixel is set
> to 1, if it contains a coord. of the vector...
>
>
>
>
>
> > Ah. That is indeed a job for interp2.
> >
> > newimage = interp2(latarray, lonarray, geo_image, new_lat,
> new_lon);
> >
> >
> > As a note, if this image is over a relatively small area
> (less than a
> > few degrees of longitude), you might consider converting
> things over to
> > UTM coordinates. This produces even grids, equal x-y
> coordinates, and
> > distances in meters.
> >
> > -Peter
>

Hey Peter!

Thanks a lot! That was EXACTLY what I needed! You saved my
butt! The computing time is now ~1.4 seconds while it was up
to 20 seconds before!

And thanks to all the others who spent their time on my
problem as well!

I just love this forum, without you guys I probably wouldn't
accomplish my master thesis!

Volker

...but I used griddata instead of interp2.