Need STL implementation of computational geometry problem

[Guntram Berti]

Hi Eric,

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


Couldn't you just do:

LineSegment Lp(Point(x+epsilon, y), Point(x-epsilon,y));
coll_type::iterator  pS_after  = coll.upper_bound(Lp);
 // ...
coll_type::iterator  pS_before = --pS_after;


HTH
--guntram


-- 
============================================================
Guntram Berti -- NEC C&C Research Labs              O__  ==
Rathausallee 10, D-53757 St. Augustin, Germany     c/ /'_ == 
++49 +2241 92 52  -32(voice) -99(fax)             (*) \(*) ==
                                                  ------------ 
http://www.ccrl-nece.de/~berti - berti at ccrl-nece.de
============================================================

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