CGAL users discussion list

[cheshirekow <>]

Hello CGAL users/devs, 

I'm trying to use CGAL to save myself some time in a simple 2D robot
motion planning demo. What I would like is a data structure to perform
nearest-obstacle queries: I give the data structure a point, and I want
to know what is the distance to the nearest obstacle, and whether or not
the query point is within that obstacle. In my simple case study, I'll
be using convex polygons to represent the obstacles. 

I'd like to get the advice of experienced users of CGAL on what is the
best way to approach this. After reading the docs for a couple of days,
this is what I have come up with:

First, there is no implementation of such a data structure already in
CGAL. However, there is an implemenation of 2d Segment Delaunay
hierarchy, and a voronoi diagram adapter (which may or may not be
necessary for my needs), which may be extended to provide me with what I
want.

In particular, I suspect that the following will be the easiest way to
implement what I want: I will have to provide a customized geometric
traits class which is a model of SegmentDelaunayGraphTraits_2, where the
data structure of the different sites are extended so that they contain
a pointer to which obstacle they are a member of. Then I can use the
current 2d Segment API to perform distance queries, and use the
additional pointer to determine which obstacle a site is from. If I use
that pointer to reference a Polygon_2 object, I can then answer the
collision query using the Polygon_2 API.

Does this sound like a reasonable way to implement this data structure,
or will is it likely to be difficult to customize / create new site
classes and a customized geometric traits class? Are there other
approaches that would be better for this which I have overlooked as a
CGAL novice?

Thanks in advance!