Shortest distance from a point to a sampled surface?

I have a 2-D matrix of sampled values on a regular, uniform grid of x and y. 
The data can be analogied to being vertical height at every point.

I then have an arbitrary point (a,b,c) and I want to know the shortest 
distance from that point to the sampled surface.  The x and y coordinates of 
the point (a,b,c) will coincide with those on the sampled grid (so it's not 
completely arbitrary).

I know I can find the distance to every point on the surface and find a 
minimum, but that doesn't acount for when the shortest distance is to a face 
or edge of the surface rather than a point.  And if possible I'd like to 
find the shortest distance to a smoothly interpolated (cubic spline or 
similar) of the surface.

Are there any fast algorithms for doing this?  I'm working in MATLAB mostly 
if that helps.

It needs to be as fast as possible because in practice I have an entire 
surface of points (a,b,c) and i need to find the shortest disatance for each 
one.  i.e. I have two surfaces and at a whole bunch of points x,y I need to 
find the shortest distance between the two planes.

The planes will be about 200x300 in size mostly.

Any help muchly appreciated.

-- 
Ian Cowley
Bishop's Stortford/Cambridge, UK

www.iancowley.co.uk/contact 


0
me3 (245)
7/26/2005 11:23:54 AM
comp.soft-sys.matlab 206993 articles. 0 followers. lunamoonmoon (258) is leader. Post Follow

8 Replies
281 Views

Similar Articles

[PageSpeed] 24
In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
"Ian Cowley" <me3@privacy.net> writes:
|> 
|> I have a 2-D matrix of sampled values on a regular, uniform grid of x and y. 
|> The data can be analogied to being vertical height at every point.
|> 
|> I then have an arbitrary point (a,b,c) and I want to know the shortest 
|> distance from that point to the sampled surface.  The x and y coordinates of 
|> the point (a,b,c) will coincide with those on the sampled grid (so it's not 
|> completely arbitrary).
|> 
|> I know I can find the distance to every point on the surface and find a 
|> minimum, but that doesn't acount for when the shortest distance is to a face 
|> or edge of the surface rather than a point.  And if possible I'd like to 
|> find the shortest distance to a smoothly interpolated (cubic spline or 
|> similar) of the surface.
|> 
|> Are there any fast algorithms for doing this?  I'm working in MATLAB mostly 
|> if that helps.

No.  You need to specify the problem more precisely before it is
answerable.  There are two aspects:

1) You need to specify the interpolation, because the properties
will affect the search very considerably.  There are several
variants of cubic splines, and most of those will produce a
surface that can extend beyond the extrema of your points.

2) If you have a single point per surface, you will clearly not
do better than a fairly simple search, as the cost of setting up
a data structure will be more than it's worth.  If you have many
of them, the problem is different.

For a single point, start at the closest point on the grid plane
to the point and work outwards, maintaining the closest distance
so far.  When you have reached that distance away on the plane,
you can stop, as no subsequent point can be closer.

Even then, you may be able to optimise that if you can make
assumptions about the properties of the surface.


Regards,
Nick Maclaren.
0
nmm1 (190)
7/26/2005 11:44:52 AM
In message dc57nk$ju3$1@gemini.csx.cam.ac.uk, Nick Maclaren burbled:
> In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
> "Ian Cowley" <me3@privacy.net> writes:
>>>
>>> I have a 2-D matrix of sampled values on a regular, uniform grid of
>>> x and y. The data can be analogied to being vertical height at
>>> every point.
>>>
>>> I then have an arbitrary point (a,b,c) and I want to know the
>>> shortest distance from that point to the sampled surface.  The x
>>> and y coordinates of the point (a,b,c) will coincide with those on
>>> the sampled grid (so it's not completely arbitrary).
>
> No.  You need to specify the problem more precisely before it is
> answerable.  There are two aspects:
>
> 1) You need to specify the interpolation, because the properties
> will affect the search very considerably.  There are several
> variants of cubic splines, and most of those will produce a
> surface that can extend beyond the extrema of your points.

OK, we'll ignore interpolation for now, I should get good enough answers 
without.
Assuming then that I can take each square (in the x,y plane) and divide it 
into two triangles, I'm looking for an algorithm that'll give me the 
shortest distance from an arbitrary point in to a triangle in 3D.  I've 
found algorithms for distance from a point to an infinite planes, but I 
can't find out the more specific point-to-triangle.

So, can anyone point me in the direction of a point-to-triangle distance 
algorithm?

-- 
Ian Cowley
Bishop's Stortford/Cambridge, UK

www.iancowley.co.uk/contact 


0
me3 (245)
7/26/2005 12:46:21 PM
In article <dc5b8d$rm5$1@gemini.csx.cam.ac.uk>,
"Ian Cowley" <me3@privacy.net> writes:
|> 
|> OK, we'll ignore interpolation for now, I should get good enough answers 
|> without.
|> Assuming then that I can take each square (in the x,y plane) and divide it 
|> into two triangles, I'm looking for an algorithm that'll give me the 
|> shortest distance from an arbitrary point in to a triangle in 3D.  I've 
|> found algorithms for distance from a point to an infinite planes, but I 
|> can't find out the more specific point-to-triangle.

That's linear interpolation :-)

|> So, can anyone point me in the direction of a point-to-triangle distance 
|> algorithm?

You work out the nearest point on the plane, check if it is within
the triangle, and use it if so.  If not, you find where the point
is relative to the sides and do the similar task for the nearest
side.  If the nearest point on that side is within the side, use
it if so.  If not, use the distance to the nearest point.

It isn't hard, can be optimised tolerably well by ensuring that
your calculations deliver information in a form that can be used
for both the distance and the selection, but is messy and it is
a hell of a long time since I did it.  Sorry I can't help more.


Regards,
Nick Maclaren.
0
nmm1 (190)
7/26/2005 12:54:06 PM
Ian Cowley wrote:
> In message dc57nk$ju3$1@gemini.csx.cam.ac.uk, Nick Maclaren burbled:
> > In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
> > "Ian Cowley" <me3@privacy.net> writes:
> >>>
> >>> I have a 2-D matrix of sampled values on a regular, uniform grid of
> >>> x and y. The data can be analogied to being vertical height at
> >>> every point.
> >>>
> >>> I then have an arbitrary point (a,b,c) and I want to know the
> >>> shortest distance from that point to the sampled surface.  The x
> >>> and y coordinates of the point (a,b,c) will coincide with those on
> >>> the sampled grid (so it's not completely arbitrary).
> >
> > No.  You need to specify the problem more precisely before it is
> > answerable.  There are two aspects:
> >
> > 1) You need to specify the interpolation, because the properties
> > will affect the search very considerably.  There are several
> > variants of cubic splines, and most of those will produce a
> > surface that can extend beyond the extrema of your points.
>
> OK, we'll ignore interpolation for now, I should get good enough answers
> without.
> Assuming then that I can take each square (in the x,y plane) and divide it
> into two triangles, I'm looking for an algorithm that'll give me the
> shortest distance from an arbitrary point in to a triangle in 3D.  I've
> found algorithms for distance from a point to an infinite planes, but I
> can't find out the more specific point-to-triangle.
>
> So, can anyone point me in the direction of a point-to-triangle distance
> algorithm?

A (non-degenerate) triangle determines a plane, so you can find the
distance from your point to that plane. Then find the projection of
your point onto that plane. If that projection is in the triangle, you
are done. Otherwse, find the shortest distance to the perimeter of the
triangle by any method you like (I suggest parametrizing the sides, and
finding the minimum of each edge. This is a simple problem)

0
qurqirishd (16)
7/26/2005 1:14:30 PM
In article <dc5b8d$rm5$1@gemini.csx.cam.ac.uk>,
 "Ian Cowley" <me3@privacy.net> wrote:

> In message dc57nk$ju3$1@gemini.csx.cam.ac.uk, Nick Maclaren burbled:
> > In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
> > "Ian Cowley" <me3@privacy.net> writes:
> >>>
> >>> I have a 2-D matrix of sampled values on a regular, uniform grid of
> >>> x and y. The data can be analogied to being vertical height at
> >>> every point.
> >>>
> >>> I then have an arbitrary point (a,b,c) and I want to know the
> >>> shortest distance from that point to the sampled surface.  The x
> >>> and y coordinates of the point (a,b,c) will coincide with those on
> >>> the sampled grid (so it's not completely arbitrary).
> >
> > No.  You need to specify the problem more precisely before it is
> > answerable.  There are two aspects:
> >
> > 1) You need to specify the interpolation, because the properties
> > will affect the search very considerably.  There are several
> > variants of cubic splines, and most of those will produce a
> > surface that can extend beyond the extrema of your points.
> 
> OK, we'll ignore interpolation for now, I should get good enough answers 
> without.
> Assuming then that I can take each square (in the x,y plane) and divide it 
> into two triangles, I'm looking for an algorithm that'll give me the 
> shortest distance from an arbitrary point in to a triangle in 3D.  I've 
> found algorithms for distance from a point to an infinite planes, but I 
> can't find out the more specific point-to-triangle.
> 
> So, can anyone point me in the direction of a point-to-triangle distance 
> algorithm?

I can tell you what I used.

Given a point x0, and a triangulation in a 3d space:

0. Compute the "in-plane" circumspheres for each triangle.
You would only do this once for many points, so its not
that bad, and its fast anyway. A circumsphere is the sphere
that contains each point on its circumference. In this case,
it will have the additional feature that the centrer of the
sphere must lie in the plane of the triangle. It can be
done by solving a linear system of equations.

I. Find the closest vertex on the triangulation to x0.
Compute that distance.

2. Find the distances from x0 to each circumcenter. Use
these distances with the radii of the corresponding spheres
to compare to the closest point we found so far. This
allows you to eliminate most of the triangles. (Note that
all points on a triangle must lie inside its circumsphere.)

3. For those few triangles which remain, use algorithm
LDP to find the closest point to x0.

What is LDP? Its from a book by Lawson & Hanson, "Solving
Least Squares Problems". LDP finds the closest point to
the origin of the set of points which satisfies a set of
convex inequalities. (LDP stands for Least Distance
Programming.) You can describe a triangle as such a set.
One inequality is defined by the normal to the plane of
the triangle, the rest by the 3 sides of the triangle.

Lawson and Hanson also show how to convert the LDP problem
into a non-negative least squares problem, as is solved
in matlab by lsqnonneg (nnls for older versions of matlab.)

HTH,
John D'Errico


-- 
The best material model of a cat is another, or
preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945
0
woodchips (7942)
7/26/2005 3:42:53 PM
In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
Ian Cowley <me3@privacy.net> wrote:

>I have a 2-D matrix of sampled values on a regular, uniform grid of x and y. 
>The data can be analogied to being vertical height at every point.
>
>I then have an arbitrary point (a,b,c) and I want to know the shortest 
>distance from that point to the sampled surface. 

Just to add to the things you want to think about: if your height data read:

   x y z=f(x,y)
   ------------
   0 0   0
   0 1   1
   1 0   1
   1 1   0

then you can put a polyhedral surface to these data which looks like a
valley between  (0,0) and (1,1), with two hills on the sides, or which
looks like a mountain ridge between (0,1) and (1,0), with two valleys
off to the sides. 

Lesson learned: that the sampling data do not specify a unique surface
in the same way that a 1-D array of sampled values specifies a unique
piecewise-linear curve. This can, obviously, affect decisions about
where on "the surface" is the nearest point to any given  (x,y,z) in R^3.

dave
0
rusin (29)
7/26/2005 8:20:41 PM
In article <dc5bpe$sre$1@gemini.csx.cam.ac.uk>, nmm1@cus.cam.ac.uk 
says...
> |> So, can anyone point me in the direction of a point-to-triangle distance 
> |> algorithm?
> 
> You work out the nearest point on the plane, check if it is within
> the triangle, and use it if so.  If not, you find where the point
> is relative to the sides and do the similar task for the nearest
> side.  If the nearest point on that side is within the side, use
> it if so.  If not, use the distance to the nearest point.

That'll work, but it's not very efficient.  The most efficient
method considers the Voronoi feature regions defined by the
triangle: 3 vertex regions, 3 edge regions, and 1 triangle
interior.  You classify the query point to the first 6
regions, and if it is found residing in one of them, you
project the query point onto the feature (the vertex or
edge).  The projection is the closest point on the triangle
to the query point (which trivially gives the distance).
If the query point is not in one of the first 6 regions,
the projection onto the triangle plane is the nearest point.

If Q is the query point and ABC is the triangle, you can test
if Q is in the Voronoi region of, say, A by testing if
Dot(Q - A, B - A) < 0 and Dot(Q - A, C - A) < 0.  The
other regions are tested in a similarly simple fashion.
You can find all the tests in my SIGGRAPH'04 slides on
GJK as available here:

http://realtimecollisiondetection.net/pubs/

The math for the edge Voronoi regions can be simplified
using the Lagrange identity so that the 6 dot products
for testing the vertex Voronoi regions are being reused.

It doesn't get faster than that.

-- 
Christer Ericson
http://realtimecollisiondetection.net/
0
7/27/2005 5:56:18 AM
In article <MPG.1d50c1dce7942e10989822@news.verizon.net>,
Christer Ericson  <christer_ericson@NOTplayTHISstationBIT.sony.com> wrote:
>In article <dc5bpe$sre$1@gemini.csx.cam.ac.uk>, nmm1@cus.cam.ac.uk 
>says...
>> |> So, can anyone point me in the direction of a point-to-triangle distance 
>> |> algorithm?
>> 
>> You work out the nearest point on the plane, check if it is within
>> the triangle, and use it if so.  If not, you find where the point
>> is relative to the sides and do the similar task for the nearest
>> side.  If the nearest point on that side is within the side, use
>> it if so.  If not, use the distance to the nearest point.
>
>That'll work, but it's not very efficient.  The most efficient
>method considers the Voronoi feature regions defined by the
>triangle: 3 vertex regions, 3 edge regions, and 1 triangle
>interior.  You classify the query point to the first 6
>regions, and if it is found residing in one of them, you
>project the query point onto the feature (the vertex or
>edge).  The projection is the closest point on the triangle
>to the query point (which trivially gives the distance).
>If the query point is not in one of the first 6 regions,
>the projection onto the triangle plane is the nearest point.

I was simplifying.  If you optimise the operation I suggested, you
end up with doing approximately the same calculation in a slightly
different order.  My experience is that all ways of doing this are
a pain, because a lot of the performance comes from not recalculating
things - and adding data structures to manage that costs too much.

>The math for the edge Voronoi regions can be simplified
>using the Lagrange identity so that the 6 dot products
>for testing the vertex Voronoi regions are being reused.
>
>It doesn't get faster than that.

Only by a small constant factor, which depends on the detail of the
coding and not the mathematics.


Regards,
Nick Maclaren.
0
nmm1 (190)
7/27/2005 9:22:18 AM
Reply:
Similar Artilces:

Finding distance
Set A={y1,y2,y3} How can i find set B={y2-y1,y3-y2,y3-y1} in a fast way? Thanks! -Bob Bob Jenkins wrote: > Set A={y1,y2,y3} > How can i find set B={y2-y1,y3-y2,y3-y1} in a fast way? Perhaps you could tell us what 'yN' is and what you consider "fast". By "Set" or "set" do you mean 'std::set' or something else? Is your question about C++ language or about a general programming technique? Bob Jenkins wrote: > Set A={y1,y2,y3} > How can i find set B={y2-y1,y3-y2,y3-y1} in a fast way? > Thanks! > > -Bob How fast does it n...

shortest distance
i want to measure the shortest distance between cities in java island,one of my friend already used dijkstra,so i need to use another method.could you please advice me? appreciate you'r help. sekolah dimana? hendra wrote: > > > i want to measure the shortest distance between cities in java > island,one of my friend already used dijkstra,so i need to use > another method.could you please advice me? > > appreciate you'r help. ...

Re: Hotelling's 2-Sample Test for Correlation #4
Regarding Hotelling's test, look at a post I wrote several months ago: http://www.listserv.uga.edu/cgi-bin/wa?A2=ind0904D&L=sas-l&P=R50242 A reasonably good summary for the correlation question is found on pages 23-25 of "Correlation", by Chen and Popovich (Sage QASS series vol 139) which refers to an article by Steiger "Tests for comparing elements of a correlation matrix" from Psychological Bulletin, (1980), pp. 245-251. I also recall that PROC CALIS can make a similar test, so you might want to check the archives for it. Robin High UNMC OR Stats &l...

Elements of distance matrix into a long list
Hi all : I have a rather simple question : I have a distance matrix from SAS proc distance for 1000 variables which have exotic but meaningful names. The sas dataset has 1001 variables and 1000 rows, the upper half is missing. The first variable is named type and contains the names of the variables, say, V1 to V1000 (in reality there is no easy naming scheme in these names!). The varibles No. 2 to No. 1001 are also named V1 to V1000. This is standard SAS. What I need is a new dataset with 3 variables from | to | and DIST . DIST is the numeric value of all non-missing and non-null dis...

meshgrid plot only some points
Hi all, Here is my problem: I have 3 functions (of 2 variables) to draw on the same graph: f1(x1,x2), f2(x1,x2), f3(x1,x2) with x1 and x2 in [xmin,xmax] .... with the meshgrid ... it is very simple BUT the trouble is that i have 3 inequality constraints that have to be satisfied: g1(x1,x2) <0 g2(x1,x2) <0 g3(x1,x2) <0 and i want to see on the graph, only the value of f1, f2, and f3 that correspond ton feasible points (meaning satisfying the 3 constraints) How can I do that ? Here it is the drawing of my unconstraint problem: n=100 x1=linspace(-4,4,n); x2=linspace(-4,4,n); [...

pgsql-server: Mark as done: < * Point-in-time data recovery using
Log Message: ----------- Mark as done: < * Point-in-time data recovery using backup and write-ahead log, < * Create native Win32 port, http://momjian.postgresql.org/main/writings/pgsql/project/win32.html > * -Point-in-time data recovery using backup and write-ahead log > * -Create native Win32 port 470c470 < o Fix PL/pgSQL RENAME to work on variables other than OLD/NEW > o Fix PL/pgSQL RENAME to work on variables other than OLD/NEW Modified Files: -------------- pgsql-server/doc: TODO (r1.1351 -> r1.1352) (http://developer.postgre...

paired-samples anova
I have results for 250 people who were solving three different tests. All of my subjects solved all three tests and now I want to compare means of those three tests. I know that I should do analysis of variance for paired samples, but I don't know how to do it in SPSS (I have version 11.01), so can anyone help me? miroslav.rajter@gmail.com wrote: > I have results for 250 people who were solving three different tests. > All of my subjects solved all three tests and now I want to compare > means of those three tests. I know that I should do analysis of > variance fo...

Shortest Path
Hi Everyone, Can you guide me through the following problem: in the shortest path problem if we have vertex costs in addition to edge lengths how is the algorithm changed! I am trying to modify the Dijkstra and Bellman_ford algorithm to answer this but i am stuck!!! any Hints thx On Feb 27, 12:02 pm, "Ez_Alg" <virtualreal...@gmail.com> wrote: > Hi Everyone, > Can you guide me through the following problem: > in the shortest path problem if we have vertex costs in addition to > edge lengths how is the algorithm changed! I am trying to modify the > Dijkstra a...

Finidin the nodes of the shortest path
Hi all, I am trying to find all possible shortest paths ( the path itself not the distance) for a undirected graph for which all weights are equal. The function "graphshortestpath" gives only one possible shortest path between any two nodes while there may be many. How can I find the rest?? For my data, I have 64-node undirected graph for which the shortest path between nodes 1 and 3: [dist,path,pred] = graphshortestpath(UG,1,3,'directed',false); path path = 1 7 55 3 and funny enough if you try to exchange the nodes you get another possible root for the s...

US-PA: West Point-Summer Internship 2009
************************************************************** JobCircle.com is the largest regional job board in the Mid-Atlantic region, with tens of thousands of job offerings in PA, NJ, DE, MD, NY, and Washington D.C. To learn more, visit http://www.jobcircle.com?source=ng ************************************************************** Job Title: Summer Internship 2009 - Developer, Technology... Job Location: PA: West Point Pay Rate: Open Job Length: full time Start Date: 2009-02-07 Company Name: Merck Contact: HR Phone: email only please ...

No. of Sample Size < No. of weights
Hi, Dear all, I am using feedforward neural networks to develop time series prediction (one step). There are few data points (sample points), 15. I construct a network, small, but have weights larger than the sample no. Generaltion / regulation is used for training. THe prediction is good/acceptable. But it seems this is not right, for No. of Sample Size < No. of weights. How to validate/justify my predictions? Thanks Regards, Qingpei The problem is the number of data points. 15 is really small to get good result with NN. My advice is to use other method. Hope that helps. ...

Re: OT: Ramblin's about distance perception
My brother and I picked up a hitch hiker about a hundred years ago (ok, maybe it was 25 to 30 years) ago. He had a backpack, and was from England. We picked him up at the East end of Arizona (on I-40) and he was hitch hiking his way across America for the summer. We had several laughs about him and with him. Some of his thoughts were: No one in Europe could ever even begin to conceive just how hot Arizona is (it was well into June and well over a 100 degrees), after working his way across California and Arizona, he was stupefied by the sheer size and magnitude of the two states and was alr...

smoothing 3d point cloud
I have created mesh and surface files from a 3d laser scan of a surface, point cloud of (x,y,z). I have used linear and cubic interpolants with the griddata function and i am finding that the output mesh and surface have a relative amount of noise, spikes at radom intervals. It is clear that the input 3d point cloud has noisy data, or overlapping data. I would like to smooth the data by taking some sort of average of near points or even eliminating some of the data??? I see that there is a 3d smoothing function, but i am not sure how to get my 3d point cloud data into the necessary 3d nxn vec...

Help with post-increment and sequence points
#include <iostream> int main() { int i =3D 1; std::cout << i << i++ << i << "\n"; } Compiling this code in g++ prints out 212 . Is this correct? If so, I don't= understand why.=20 Shouldn't this actually be equivalent to f(f(f(f(std::cout,i),i++),i),"\n")= where f is operator<< ? In that case, each time a function is entered, the= re should be a sequence point which makes the side effects happen. So I'd e= xpect the output to be 112 instead.=20 % g++ --version g++ (Debian 4.6.1-4) 4.6.1 Best regards, Laird Breyer On...

Point lights in PhotoWorks
Does anyone know how to control the size of a point light source in photoworks. I am wanting light a neon bulb in an assembly but the point light is larger than the bulb it self. Martin The size of the graphic is only a reference it shouldn't make any difference when rendered. All the light is emited from the center of the ball. I'm assuming you mean the size of the light beam. Where do you want to control it? At the source of the light? Or at the surface where it is being projected onto? Richard "Martin Scottorn" <marty@spam.co.nz> wrote in message new...

Airport connection speed vs. distance
Does the connection speed slow down as you move further from the AirPort base stationand the signal level drops? It may be my imagination but this apears to be hapening to me. Entity Dennis spoke thus: > Does the connection speed slow down as you move further from the > AirPort base stationand the signal level drops? Yes. -- Gnarlie ...

Re: How to plot individual 2D data points, where each must have its own color.
Chrisantha, It always helps if a poster can supply some actual sample data. Then a responder doesn't have to make up data that may not reflect your actual form of data. In any case, here is some sample data where the third item is a Hue color. data = Table[{x, Sin[x], Hue[x/(2Pi)]}, {x, 0.0, 2Pi, 2Pi/20}] Show[Graphics[ {AbsolutePointSize[6], {Part[#, 3], Point[Take[#, 2]]} & /@ data}], Frame -> True, ImageSize -> 450]; What I did was use a pure function, {Part[#, 3], Point[Take[#, 2]]} &, that extracted the third part of the data list...

How to boot to Linux when MBR points to Win partition?
Hello, I copied an old HD with Linux RH8.0 and Win98 to a bigger disk. On my all HD Linux had 3 pimary partitions - one for /boot, one for / and one for swap and Win98 had another primary partition. On a new disk I made one extended partition for Linux - with 3 logical partitions. I had problem with booting, so I put in MBR original boot record by issuing command: FDISK /MBR. I have Partition Magic 5.0 on my Win98 partition, so I thought with help of this software I could correct Lilo problem. Now I can boot Win, PM is seeing Linux partitions, but PQ Boot (multi boot part of Partit...

finding ALL shortest paths from i to j (not All pair shortest paths)
Hi, I have an undirected and unweighted graph. I can easily compute the shortest path between a node i and j. However, often there are more than one shortest paths between i and j and I would like to find all of them. Is there an algorithm/implementation out there that can compute this? many thanks Hi, May be the following would work : While using Dijkstra's algorithm we maintain a set of nodes L , one whose shortest distance from the node u has already been found out and let d[] denote the array/storage of all values. what we do in the algorithm is that we find the node A which is the ...

What is the shortest path...?
Hi, Can any one show me the shortest path to become lisp guru... Sorry if it is a faq. (hope not waste than ad's posted) Thanks lboard1947@gmail.com writes: > Can any one show me the shortest path to become lisp guru... > > Sorry if it is a faq. (hope not waste than ad's posted) A man from AI walked across the mountains to SAIL to see the Master, Knuth. When he arrived, the Master was nowhere to be found. "Where is the wise one named Knuth?", he asked a passing student. "Ah," said the student," you have not heard. He has gone on a pilgrimage a...

Distance between a Line Segment and a triangle in 3D
Hello, I need to calculate the distance between a line segment and a triangle. Unfortunately Google was no good helper this time. So i thought of something like that: (When speaking of plane i mean the plane defined by the triangles points and when speaking of line its the infinite line defined by the line segment) First test if the endpoints of this given Line Segment are on opposite sides of the plane. If so calculate the intersection point between this plane and test if its inside the triangle. In this case the distance would be zero. If not: project both endpoints orthogonally ont...

Sampling by means of Matlab
Hi to all, I'd like to know if there exists some readily available function in Matlab which can be used to generate samples of data out of a given list of data points? Thanks a lot in advance and good day. - Fiona "Fiona Sammut" <fionasammut@yahoo.com> wrote in message news:eeef33f.-1@webx.raydaftYaTP... > Hi to all, > > I'd like to know if there exists some readily available function in > Matlab which can be used to generate samples of data out of a given > list of data points? > > Thanks a lot in advance and good day. > > - Fiona help r...

Re: Points sampled by FindMinimum
On 11/8/06 at 6:06 AM, andrew.j.moylan@gmail.com (Andrew Moylan) wrote: >Please consider the following code, which asks FindMinimum to >minimise a simple parabolic function while tracking at which which >points FindMinimum evaluates the function: >func[x_?NumericQ] := (Print[x]; 1 + (x - 1)^2) FindMinimum[func[x], >{x, 0.1}] >The output is: >0.1 0.1 0.1 0.6 0.6 0.6 1. 1. 1. 1. 1. 1. >But I would have expected output more like: >0.1 0.6 1. 1. >Can anyone explain why FindMinimum evaluates func three times at >each test point, instead of ...

How do I get the pointed to bit of memory into a character variable?
I have an integer, IPTR which holds the address of a bit of memory in which resides some character data. I want to capture that character data in a character variable, but not sure how to do that. I tried the old equivalence but that didn't work. Can anyone help? ferrad <acfer@hotmail.com> wrote: > I have an integer, IPTR which holds the address of a bit of memory in > which resides some character data. I want to capture that character > data in a character variable, but not sure how to do that. I tried the > old equivalence but that didn't work. Can anyone h...

(610) US-PA-WEST POINT: Recruiter
********************************************************************** This job posting is brought to you by ISHUNTER.COM, offering computer jobs for programmers, engineers, systems analysts, network administrators and other high technology professionals. Search over 3,000 IS/IT jobs in the United States by clicking on http://www.ISHunter.com ********************************************************************** Title ...... Recruiter - Scientific Skills ..... COMMUNICATION Location ... WEST POINT, PA Area Code .. 610 Term ....... Contract Length ..... PERM Pay ....