Path: news.mathworks.com!not-for-mail 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$1@fred.mathworks.com> References: <ie5lqf$gd5$1@fred.mathworks.com> <ie5qbs$cbj$1@fred.mathworks.com> <ie7gi9$jqr$1@fred.mathworks.com> <ie7la5$7t9$1@fred.mathworks.com> Reply-To: <HIDDEN> NNTP-Posting-Host: webapp-05-blr.mathworks.com Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: fred.mathworks.com 1292331785 26177 172.30.248.35 (14 Dec 2010 13:03:05 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Tue, 14 Dec 2010 13:03:05 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 2222754 Xref: news.mathworks.com comp.soft-sys.matlab:695349 "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie7la5$7t9$1@fred.mathworks.com>... > "Rikard " <rikard_dot_laxhammar@his.se> wrote in message <ie7gi9$jqr$1@fred.mathworks.com>... > > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie5qbs$cbj$1@fred.mathworks.com>... > > > "Rikard " <rikard_dot_laxhammar@his.se> wrote in message <ie5lqf$gd5$1@fred.mathworks.com>... > > > > 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: > > > http://www.mathworks.com/matlabcentral/fileexchange/28268 > > > > > > 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? Regards Rikard