From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Maximum distance from a polygonal chain to another polygonal chain
Date: Tue, 14 Dec 2010 13:03:05 +0000 (UTC)
Organization: Hogskolan I Skovde
Lines: 37
Message-ID: <ie7pu9$pi1$>
References: <ie5lqf$gd5$> <ie5qbs$cbj$> <ie7gi9$jqr$> <ie7la5$7t9$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1292331785 26177 (14 Dec 2010 13:03:05 GMT)
NNTP-Posting-Date: Tue, 14 Dec 2010 13:03:05 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 2222754
Xref: comp.soft-sys.matlab:695349

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie7la5$7t9$>...
> "Rikard " <> wrote in message <ie7gi9$jqr$>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie5qbs$cbj$>...
> > > "Rikard " <> wrote in message <ie5lqf$gd5$>...
> > > > Hi,
> > > > I'm looking for fast yet accurate Matlab code that calculates the Hausdorff distance from a polygonal chain A (aka polyline, piecewise linear curve etc) to another polygonal chain B, i.e. the maximum distance from any point along A to the corresponding closest point along B (note that these points are not necessarily vertices of the chains). 
> > > > Any ideas how to implement such as distance measure?
> > > > There is a function for calculating Hausdorff distance at the FEX but it operates on sets of points -  it requires all points along each straight line of the chain as input which makes it rather inaccurate/inefficient? Moreover, there is a function "Distance from a point to polygon", but obviously it takes a point instead of a polygon chain as input.
> > > 
> > > Unless if I'm mistaken but the Hausdorff distance is always reached by a vertexes on either set (you can show this by contradiction trick: it cannot be reach by the middle of two segments, using the line derivative).
> > > 
> > > So all we need is a procedure to compute the distance of a vertex VA of either polygonal A to the other polygonal B. Then take the max on all vertexes VA. Do the opposite and take the max of both results.
> > > 
> > > Such function, e.g., this one on FEX seems to be the right building block:
> > >
> > > 
> > > Bruno
> > 
> > Thank you for your response Bruno.
> > 
> > Yes, I believe you are right that the Hausdorff distance between two polygonal chains A and B correspond to the shortest distance from a vertex from A or B to a line segment from B resp. A. 
> > However, I want to calculate the *directed* Hausdorff distance from A to B which is less or equal to the "general" Haussdorff distance between the chains? In this case I'm not sure that Haussdorff distance must correspond to distance between a vertex and a line segment. And I'm not sure how the function you proposed could be used for calculating the directed haussdorff distance from chain A to chain B? 
> > 
> Don't you want to compute:
> d(A,B) := max over VA { min over EB { D(VA,EB) }}
> Just use the above function (note that I haven't use it), put the distances in matrix D, for example first dimension corresponds to VA, second dimension corresponds to EB 
> then call max(min(D,[],2),[],1)
> Bruno

Please correct me if I'm wrong, but I believe that d(A,B) as you defined it above does not calculate the directed Hausdorff distance from polygonal chain A to B. To give a counter example, assume A is a single line segment: {(0,1),(1,1)} and B two line segments: {(0,0),(0.5,-1),(1,0)}. The point from A having the largest distance to any edge from B is *not* a vertex of A; it is in fact the point (0.5,1) in between the vertices of A?