CGAL users discussion list

[Ben Supnik <>]

Thanks Efi!

As usual, there is a whole literature and it was only the name of one 
mathematician away. :-)

Follow-up for anyone who cares: the most useful paper I found was one 
that argues for why spatial indexing can be legal for calculating the 
Hausdorff between poly-lines.  Basically once we know the worst case 
error, we can limit or spatial queries to only a closer range.

In my case, I can use my silly "variance" measurement and still do this 
as long as there is a maximum distance beyond which I just want to bail 
out.  (In my case there is, because if the error between two curves is 
large enough my algorithm is going to bail out.)  Indexing the curve 
comparison improved algorithm performance by about 7.5x - it would be 
more if the polylines weren't so short.

cheers
Ben

On 8/28/11 11:40 AM, 

 wrote:
> Quoting "Ben Supnik" 
> <>:
>
> > Hi Y'all,
> >
> > I have two poly-lines and I am trying to find their - that is, the
> > error of one poly-line as a set of points in terms of distance to the
> > other.
> >
> > What I do now is pretty terrible: for each poly-line in 1, I find its
> > distance to the other poly-line (which requires looking at every
> > segment) and then I sum the squares of those error-distances. The
> > result is O(N^2).
> >
> > Does anyone know of a better way to measure how similar one poly-line
> > is to another?
> >
> > The two poly-lines share end points so I tried taking the signed area
> > of the polygon they form, but I get a lot of false low errors - often
> > the two poly-lines will form one large positive and one large negative
> > area, which makes the error seem artificially low.
>
> Then why not take the sum of the absolute areas?
>
> Look for Hausdorff distance
> (http://en.wikipedia.org/wiki/Hausdorff_distance) and related subjects
> within.
>
> > cheers
> > ben
> >
> >
> > --
> > Scenery Home Page: http://scenery.x-plane.com/
> > Scenery blog: http://www.x-plane.com/blog/
> > Plugin SDK: http://www.xsquawkbox.net/xpsdk/
> > X-Plane Wiki: http://wiki.x-plane.com/
> > Scenery mailing list: 
> >
> > Developer mailing list: 
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://www.x-plane.com/blog/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: