Hello,
I am trying to determine interest to submit GTL to boost.
History/Background ================== GTL is a geometric library that implements basic rectilinear, fixed point 1D, 2D and 3D types. It was developed over the past decade inside Intel's own EDA CAD department mainly to support advanced physical design tools that create/check/manipulate the massive layout that goes into our microprocessors. GTL comes from a codestream that successfully weathered through several major microprocessor tapeouts. The management agreed to pursue the open-sourcing of GTL via boost (with the boost license) - with all the obvious benefits of doing so.
Comparison to other geometric libraries ============================= We are aware of the various other libraries available. What GTL brings to the table: * parametrized fixed-precision cartesian coordinates * industrial strength code base * directly usable on any user type via template traits - based on C++ concepts * massive capacity * bone-crushing speed * isotropic API * ease of use
Implemented Rectilinear Types ========================================= 1D Types: Interval 2D Types: Point, Segment, Rectangle, Polygon, PolygonSet 3D Types: Point3D, Segment3D, LayeredRectangle, RectangularPrism
Polygons ======== This is by far the most algorithmically advanced type and functionality that we have. 1. full set of boolean operations on polygon sets (or, and, subtract, xor, etc) 2. runtime (all n*log(n) or better) - it is at par or better than other implementations that we're aware of 3. ease of use - simple, intuitive API functions 4. no memory management required by user 5. providing polygon set type that's complete 6. isotropic API // example 1 // construct default empty polygons sets that will be rectangularized // in the given orientation (on demand) gtl::PolygonSet a(VERTICAL), b(HORIZONTAL), c(VERTICAL); a += gtl::Rectangle(4, 5, 60, 70); // add a rectangle to polygon set a a += gtl::Rectangle(gtl::Interval(20, 30), gtl::Interval(40, 100)); // construct a rectangle from 2 intervals, add it to a // .. similar additions to b and c // intersect a with b (with a boolean and) - subtract from it a rectangle, // bloat the north edges of the result by 55 units c += ((a * b) - gtl::Rectangle(10, 10, 2000, 3000)).bloat(NORTH, 55); std::vector<gtl::Rectangle> v; c.get(v); // populate v with the vertical rectangles that make up c
Isotropy ======== A variety of directional types in 1D, 2D, 3D with states like: LOW, HIGH, NORTH, HORIZONTAL, UP, etc A set of operations on these types like: forward(), backward(), toward(), left(), turn(), perpendicular(), etc.
All API functions are isotropic, i.e. they take arguments of directions/orientations. None of the function names contain words like X, Y, Up, deltaX, horizontal, etc. With isotropy, you can do elegant things like:
// example 2 gtl::Rectangle a, b;
// bloat rectangle of a toward rectangle b by b's half delta in that orientation // do nothing if no trivial direction from a to b exists a.bloatInDirection(a.toward(b), b.delta(a.toward(b))/2);
Writing this example in a non-isotropic fashion requires much more lines of code, lots of if statements, four to eight different scenarios, etc. Much more code, much less readable, not flexible at all.
Functionality ============= GTL has pretty much all the functionality that one would expect from these types. You can get/set components, you can do booleans (ands, ors) subtractions, bloats, shrinks. You can construct a rectangle out of 2 points, 2 intervals, 4 coordinates, etc. You can construct a polygon set from n rectangles, from a polgyon or a polygon set. You can get the polygon as a set of rectangles (rectangularized horizontally or vertically), etc.
// example 3 gtl::Rectangle a; gtl::Segment s = a.get(EAST); // returns the right (vertical) edge of the rectangle as a 2D segment. // get the north edge of rectangle a as a segment // get generalized intersection with segment s - as a rectangle // bloat the rectangle's EAST side by 5 // get the center of that rectangle as a point a.get(NORTH).getGeneralizedIntersection(s).bloat(EAST, 5).getCenter();
Data decoupling via template specialization =========================================== GTL can operate on any user data without the need for copying. User will need to write a tiny, template specialization interface to his data, that makes GTL interpret user data as the GTL type of interest. This makes the use of GTL in existing applications trivial.
// example 4 class UserData{ int a, b, c; int x, y, z; };
// if user wants gtl to interpret a, c, x, z // as the coordinates of a rectangle, he will write #include <Gtl.h> template <> class gtl::RectangleInterface<UserData> { // need to write 3 functions only - get(), set(), create() };
typedef gtl::RectangleImpl<UserData> Rectangle; Rectangle r1(10, 20, 30, 40); std::cout << r1.get(gtl::SOUTH) << std::endl; // prints 20 - y low coordinate
David Abrahams suggested to write this description as a brief email. I just realized that I'm past 2 pages already. There's much more to say about GTL. Will do that when/if appropriate. We're eager to get feedback from you. thanks, Gyuszi Suto Intel, Hillsboro, Oregon