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:
Shortest distance from Matrix to a line segment

Subject: Shortest distance from Matrix to a line segment

From: James D

Date: 15 Aug, 2011 20:03:28

Message: 1 of 4

Dear all,
I have a problem that I am trying to solve.

I have a matrix of 600 x 840 different positions of latitude and longitude and I am trying to find and output the shortest distance to a line segment.

I have created the following for the distance to a point and vectorised it so that it works faster than a for statement.

I was wondering how I would code the shortest distance to a particular line segment for each of the 600 x 840 points in the matrix.

distancematrix=sqrt( bsxfun(@plus, ((yllcorner+600*spacing-0.020833333:-spacing:yllcorner+0.020833333).'-centrallat).^2 ,...
    ((xllcorner+0.020833333:spacing:xllcorner+840*spacing-0.020833333)-centrallong).^2 ) );

I hope that you can help!
Many thanks in advance,
James.

Subject: Shortest distance from Matrix to a line segment

From: James D

Date: 15 Aug, 2011 20:11:28

Message: 2 of 4

I forgot to say that
yllcorner = 22
xllcorner = 121
spacing = 0.041666666

and the line segment is from (27.222,128.111) to (32.111, 133.222).

Cheers.


"James D" <j.e.daniell@gmail.com> wrote in message <j2bu2g$ghi$1@newscl01ah.mathworks.com>...
> Dear all,
> I have a problem that I am trying to solve.
>
> I have a matrix of 600 x 840 different positions of latitude and longitude and I am trying to find and output the shortest distance to a line segment.
>
> I have created the following for the distance to a point and vectorised it so that it works faster than a for statement.
>
> I was wondering how I would code the shortest distance to a particular line segment for each of the 600 x 840 points in the matrix.
>
> distancematrix=sqrt( bsxfun(@plus, ((yllcorner+600*spacing-0.020833333:-spacing:yllcorner+0.020833333).'-centrallat).^2 ,...
> ((xllcorner+0.020833333:spacing:xllcorner+840*spacing-0.020833333)-centrallong).^2 ) );
>
> I hope that you can help!
> Many thanks in advance,
> James.

Subject: Shortest distance from Matrix to a line segment

From: Roger Stafford

Date: 15 Aug, 2011 20:56:26

Message: 3 of 4

"James D" <j.e.daniell@gmail.com> wrote in message <j2bu2g$ghi$1@newscl01ah.mathworks.com>...
> Dear all,
> I have a problem that I am trying to solve.
>
> I have a matrix of 600 x 840 different positions of latitude and longitude and I am trying to find and output the shortest distance to a line segment.
>
> I have created the following for the distance to a point and vectorised it so that it works faster than a for statement.
>
> I was wondering how I would code the shortest distance to a particular line segment for each of the 600 x 840 points in the matrix.
>
> distancematrix=sqrt( bsxfun(@plus, ((yllcorner+600*spacing-0.020833333:-spacing:yllcorner+0.020833333).'-centrallat).^2 ,...
> ((xllcorner+0.020833333:spacing:xllcorner+840*spacing-0.020833333)-centrallong).^2 ) );
>
> I hope that you can help!
> Many thanks in advance,
> James.
- - - - - - - - - -
  That seems a remarkably inefficient way of finding the minimum distance from an evenly-spaced rectangular gridwork of points to a given point. You are having to compute 600*840 = 504,000 distances that way. It's very easy to find the gridwork coordinates of the four corners of a square (rectangle?) that immediately surrounds your given point. It just takes one subtraction, followed by one division, and then a call on 'ceil' and 'floor', for each of the two dimensions. Then you only have to find the minimum among four distances.

  Finding the minimum distance to a line segment is more complicated but I think the above reasoning can be applied in an analogous manner to greatly reduce the total number of distances that need to be computed. Of course you will have to decide precisely what you mean by the distance to a line segment. The usual definition is the distance to the orthogonal projection of a point onto the line of the line segment if the projected point lies within the segment, and otherwise the distance to the closer of the segment's two endpoints.

Roger Stafford

Subject: Shortest distance from Matrix to a line segment

From: Bruno Luong

Date: 15 Aug, 2011 21:45:29

Message: 4 of 4

"James D" <j.e.daniell@gmail.com> wrote in message <j2bu2g$ghi$1@newscl01ah.mathworks.com>...
> Dear all,
> I have a problem that I am trying to solve.
>
> I have a matrix of 600 x 840 different positions of latitude and longitude and I am trying to find and output the shortest distance to a line segment.
>
> I have created the following for the distance to a point and vectorised it so that it works faster than a for statement.
>
> I was wondering how I would code the shortest distance to a particular line segment for each of the 600 x 840 points in the matrix.
>
> distancematrix=sqrt( bsxfun(@plus, ((yllcorner+600*spacing-0.020833333:-spacing:yllcorner+0.020833333).'-centrallat).^2 ,...
> ((xllcorner+0.020833333:spacing:xllcorner+840*spacing-0.020833333)-centrallong).^2 ) );
>
> I hope that you can help!
> Many thanks in advance,
> James.

I assume the rectangle is (long, lat) such that
left <= long <=right (eqt1)
bottom <= lat <=top (eqt2).

The line segment in its parametric form is (x,t)
x(t) = x1 + t*(x2-x1)
y(t) = y1 + t*(y2-y1)
0 <= t <= 1 (eqt3).

The distance squared is d2
d2 = (x(t)-long)^2 + (y(t)-lat)^2.

It is clear that d2 is a quadratic form with respect to (3 x 1) vector [long,lat,t]'.

The problem is minimize
d2 such that box constraints (1-3).

This can be solved with QUADPROG. There may be some function in FEX that can solve such problem.

Bruno

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