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: Wed, 22 Dec 2010 08:32:04 +0000 (UTC)
Organization: Hogskolan I Skovde
Lines: 37
Message-ID: <iesd24$idg$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> <ie7pu9$pi1$1@fred.mathworks.com> <ie7rhj$nl3$1@fred.mathworks.com> <ie8n7p$703$1@fred.mathworks.com> <ieag87$n2r$1@fred.mathworks.com> <ieb7ml$idb$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1293006724 18864 172.30.248.38 (22 Dec 2010 08:32:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 22 Dec 2010 08:32:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 2222754
Xref: news.mathworks.com comp.soft-sys.matlab:697465

"Roger Stafford" wrote in message <ieb7ml$idb$1@fred.mathworks.com>...
> "Rikard " <rikard_dot_laxhammar@his.se> wrote in message <ieag87$n2r$1@fred.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie8n7p$703$1@fred.mathworks.com>...
> > > Rikard,
> > > 
> > > I was just thinking more about the problem of determine the directed Hausdorff distance between two polygonal, and the mote I look the more it think it's a not at all a trivial problem. Oddly enough the symmetric one seems to be much more easy to solve.
> > > 
> > > Bruno
> > 
> > Bruno,
> > 
> > Yes indeed it does not seem trivial to calculate the exact directed hausdorff distance between two polygonal curves.
> > It is possible to use the general hausdorff distance (instead of the directed) in my application, so I will stick to it for the time being. Thank you for your feedback!
> > 
> > /Rikard
> - - - - - - - - - - - -
>   I agree that calculating the "directed" hausdorff distance so as to include a polygon's line segments' interiors rather than only its vertex endpoints is a difficult task.  There is a very good reason why the FEX routine you mentioned requires that numerous points be specified along each line segment.  I claim further that the same can be said for the general undirected hausdorff distance for such polygons.
> 
>   Here is a simple example to demonstrate that.  Let the points P, Q, R, S, and T be (2,1), (0,2), (0,0), (0,-2), and (2,-1), respectively.  Define polygon A as PQRSTR and polygon B as RPQRST.  These polygons differ only in that segment RT belongs solely to A and RP only to B.  Both the directed and undirected hausdorff distances occur at interior points of segments RP and RT well away from any of these five vertices.  It would be easy to construct an example of this in which the polygon vertices are disjoint.
> 
>   If the extremes sought by the hausdorff distance were always restricted to vertices of one or the other polygon, the possibilities would be greatly limited, but as we see in the above example they are not limited in this way.  The closest point in a line segment in B to a fixed point in A would be either one of the two B-segment end points or the orthogonal projection of the A point onto the B-segment line.  Assuming we are in three or greater dimensional Euclidean space, as we travel along a segment of A, this closest distance could therefore be expressed as contiguous portions of three possible hyperbolic curves as functions of the distance along the A segment.  This combined function is itself continuous with continuous derivatives even across a transition from one to another of the three types.  For single segment polygons it would therefore be an easy task to find their 
hausdorff 
> distance(s), directed or undirected. 
> 
>   For many segments in B we have a like number of the above curves to consider as we move along a segment of A, and with n of them it would be theoretically possible, (though not likely,) for them to intersect at order(n^2) points.  It is at each of these intersections as well as at the endpoints of A, that we must look for possible hausdorff extreme distances.  It is this necessity to account for all the possible intersections of such hyperbolic curves in a precise calculation of distance that transforms the problem into a difficult one.  Obviously with the usual kinds of graphs a great many of the hypothesized intersections would not be present in reality, but devising an efficient algorithm that makes sure that none are overlooked would require a very considerable effort in my opinion.  As I have said above this statement holds for both the directed and undirected hausdorff 
distances. 
> 
> Roger Stafford

Roger,

Thank you for pointing out and explaining the problem of calculating the general Hausdorff distance - your example has convinced me that it is not enough to only consider distances between vertices and line segments of the two polygonal chains.

I've read some papers related to this problem and it seems that algorithms have been proposed that gives optimal solution in time O((n+m)*log(n+m)) where n and m are number of line segments from each chain resp (H. Alt, "The Computational Geometry of
Comparing Shapes", 2009). Yet I haven't found any available implementation of such algorithms. 

Rikard