Need STL implementation of computational geometry problem
berti at ccrl-nece.de
Wed Feb 26 09:29:30 PST 2003
> 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);
> 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;
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
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce