[cairo] Finding minimum distance to a stroke or fill

[Ashwin Bharambe]

Hi all,

Attached is a patch which adds two new functions to the cairo API. The
functions provide functionality for finding the closest point to a
stroke/fill from a given point (x, y). The function returns the
distance as well as the co-ordinates of the closest point (px, py).
Note that returning the distance is redundant and this need not be
done. The actual signatures of the functions are:

<code>
double
cairo_min_distance_stroke (cairo_t *cr, double x, double y, double
*px, double *py);

double
cairo_min_distance_fill (cairo_t *cr, double x, double y, double *px,
double *py);
</code>

These functions are counterparts to cairo_in_stroke and cairo_in_fill,
respectively and work along similar lines. i.e., they look at each of
the tesselated trapezoids and find the minimum distant point to the
trapezoid from the given point (x, y). In the worst case, a test for
each trapezoid may require computing 8 dot-products. Perhaps, this can
be made much more efficient, however, at this point I am happy that it
works. :)

Also attached is a modified version of cairo-spline.c from
cairo-demos/X11 which demonstrates the above two functions. Clicking
anywhere on the canvas constructs line-segments to the nearest points
of the stroked spline as well as the filled circles around the control
points.

I am hoping this extension to the API fills a need and would be
accepted in some way or another.

Thanks,
Ashwin

PS: Also, I must say the cairo API and code is so amazingly clean that
it was a pleasure hacking this up! Kudos!

On Fri, 11 Feb 2005 19:58:48 -0500, mental at rydia.net <mental at rydia.net> wrote:
> Quoting Ashwin Bharambe <ashwinb at gmail.com>:
> 
> > Hi,
> >
> > I know that cairo_in_stroke (cairo_in_fill) would answer me if a
> > point
> > P was inside the stroke (fill), respectively. However, how would
> > I go
> > about finding the distance of the point in the stroke/fill which
> > is
> > closest to a certain point P?
> 
> Knowing roughly what you want this for, perhaps you would do better
> to use a different approach...
> 
> For example, testing whether the stroke/fill overlaps a filled
> circle with radius n centered on the given point?
> 
> Cairo does not do that for you any more than it does
> closest-point-on-path, but it is a significantly more tractable
> problem than trying to find the closest point on a bezier curve
> (which is relatively difficult).
> 
> The overlapping-circle approach can be approximated using a regular
> polygon (for a proof-of-concept a square with sides of length n
> should be sufficient).
> 
> For testing against the fill, just use either cairo_current_path or
> the locally cached pre-cairo path, and return true if:
> 
>   the center point falls within the path ||
>   the first point of any subpath falls within the polygon ||
>   any path segment intersects the polygon
> 
> (if you use cairo_current_path, I'm not sure whether using that and
> subdividing yourself, or using cairo_current_path_flat would be
> more/less efficient)
> 
> For testing against the stroke, increase the polygon's radius by the
> stroke width and return true if:
> 
>   the first point of any subpath falls within the polygon ||
>   any path segment intersects the polygon
> 
> (admittedly that will miss the miter part of miter-joined strokes)
> 
> You can probably combine both tests into a single pass.
> 
> Longer-term, perhaps cairo can add versions of cairo_in_stroke and
> cairo_in_fill that take a radius and center coordinates?
> 
> Comments?  Other ideas?
> 
> -mental
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mindist.patch
Type: text/x-patch
Size: 11065 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050212/ece747c0/mindist.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cairo-spline.c
Type: text/x-csrc
Size: 13889 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050212/ece747c0/cairo-spline.c