Need STL implementation of computational geometry problem

[Eric Fowler]

I am working on a simple sweepline algo from Computational Geometry, de
Berg, van Kreveld et.al., 2nd Editon, Section 1.2.

The basic idea is to find intersections among a set of line segments by
sweeping a line down and testing at event points, which are segment
endpoints (given) and intersections (discovered as you go).

It is implicit in the problem that you need to be able to find line segments
directly "adjacent" to a given event point. "Adjacent" means if you draw a
horizontal sweepline through that point, the "adjacent" segments are the
ones on either side of the point (if they exist) which intersect the line,
and are closest to the point. You can have at most two, one "smaller" (left
of) and one "larger" (right of) the point. Of course, colinearity is
adjacency also.

So, we have a little problem of ordering segments ....
The book has a type of binary tree structure and expects us to handroll an
implementation - not too hard - but I am anal about using STL as much as I
can. So, I want an STL-ish way to do this. In general, I would like to
extend the set or map template classes to do something like this:

collection_type<LineSegment *,
handrolled_sorting_criteria_or_algorithm_or_something> coll;

//populate c with segments ...

Point point_on_sweepline(x_coord, y_coord);

LineSegment * pS = coll.find_adjacent_upper(point_on_sweepline);

// use pS for something ... blah ...

pS = coll.find_adjacent_lower(point_on_sweepline);

etc.

I am looking for suggestions leading to a CLEAN implementation.

I have tried defining classes as sorting criteria, with operator(), but it
wants two operands of the same type. I need to use a Point& to fish for a
LineSegment*, so that does not work ...

Any ideas?

Eric






-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.