Thread Subject:

Maximum distance from a polygonal chain to another polygonal chain

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.

/Rikard

"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

"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?

Regards
Rikard

"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

"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

"Rikard " <rikard_dot_laxhammar@his.se> wrote in message <ie7pu9$pi1$1@fred.mathworks.com>...
> "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?
>

Sorry but because you introduce the notion "directed" Hausdorff in post #3, after I propose my solution, which I initially reasoning on symmetric Hausdorff (the property of vertexes applied for symmetric one). I might still be valid for directed Hausdorff, but I haven't though that much right now and your example does not convince me either.

I'll leave the thread as it is and let you think about it.

Bruno

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 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

"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 Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ieb7ml$idb$1@fred.mathworks.com>...

>
> 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.

Good example Roger.

Bruno

"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