Re: [boost] Library Proposal: Boost.Geom 2D and 3D GeometricPrimitives

From: Anis Benyelloul (benyelloul_at_[hidden])
Date: 2005-06-29 03:55:00

Andy Little <andy <at> servocomm.freeserve.co.uk> writes:

>Recently howver I use a struct with x and y members... its less typing  ;-)

Ahhh.. I see :). Well, let's examine why using a "struct point { int x,
y; };" is a bad idea.

-1 Sometimes you aren't even given the choice
---------------------------------------------
Indeed, if you're already using some graphical libraries, the choice
is made for you. Consider this (hypothetical) example about a library
named "trendy_graph" :

<example>
// In header trendy_graph.h

// Rectangles for trendy_graph
typedef struct __TG_RECT {
        TG_COORD left;
        TG_COORD right;
        TG_COORD top;
        TG_COORD bottom;
} TG_RECT;

// Updates a region of the screen
//  re:  A pointer to an array of TG_RECT
//  n:   The number of TG_RECT in re 
TG_Update_Screen(TG_RECT* re, size_t n);
</emaple>

(This is just the kind of ugly C interface I face everyday ..). Look
how TG_Update_Screen needs a TG_RECT*. Now you suggested this :

<your_suggestion>
struct point { int x,y; };
struct rectangle { int x, y, width, height; };
</your_suggestion>

Well, if you insist on using rectangle (instead of TG_RECT) you'll end
up creating an array of rectangle, and converting it into the
corresponding array of TG_RECT that you can pass to
TG_Update_Screen. This is overkill. If you care about performances
you'll just use TG_RECT in your own code.

And when you move to another library (say fast_graph) you'll have to
*learn*  FG_Rectangle because FG_DrawRectandle needs an instance of
FG_Rectangle, and you're not willing to do conversions. Be ready to learn
XRectangle, SDL_Rect, RECT, MAcRect, FuNReCt, HEAVY_Rect, stupid_rect, (??).. :)

-2 Less typing?
---------------
Now if you can choose any point class you want, we may compare
"struct simple_point{ int x, y; }" with "geom::point<>".

- First simple_point is not much less to type. After some suitable
  typedefs (that you'll write once and for all), working with
  Boost.Geom resembles this :
  <example>
  point pt=point_xy(3, 4);
  pt.x()=10;
  pt.rho()=1; // normalizing
  pt.theta()+=3.14159/2; // rotating by 90°
  </example>
  This isn't far of what you can do with simple_point.

- simple_point, is not yet written. You have to do it, you have to
  document it, you have to maintain it, you have to care about it...
  And you'll have to redo that (or to copy/past) for each project!
  because sometimes you'll need 3D points, polar points, "double"
  points, "float" points, "unsigned short" points ...

- geom::point<> has more features ready to use. RHO, THETA, PHI,...

- And finally, simple_point is not faster then geom::point<>. Or
  stated another way, geom::point<> can be as fast as simple_point
 

>Ok.  I understand the use of a common type for cartesian and polar coordinates.
>Alternatively  these two types could be provided as complete useable types, 
with
>a common interface.

I'm not sure I get it, could you name the "types" you're talking
about ?

>A viable alternative to the wrapper is simply to provide a
>conversion from one to the other type.

A as a consequence of traits&wrappers the conversion is already
provided:
<code>
point<point_polar> pt_p=point_polar(1, 3.141592654); // Polar
point<point_xy> pt_c=point_xy(10, 20); // Cartesian

pt_p=pt_c;// Conversion !!!
</code>

>Specialising the traits class looks to be
>nearly the same work as writing  these from scratch with a common
>interface.

I  don't get that either, sorry... Could you explicit your thoughts a
bit ?

>One could provide something similar by overloaded functions:

Humm... do you mean that we should have something like :
<code>
template<class PointImpl>
value_type get_x(const PointImpl&);

template<class PointImpl>
void set_x(const PointImpl&, value_type);
</code>
And then we'll specialize set_x&get_x for point implementations? If
that is what you mean, then yes ! it is the same as traits
classes. But people already know what a traits class is, so I don't
really have to explain the design this way.

>I dont see the advantage in wrapping other libraries point types.

Well, you recall the TG_RECT and FG_Retangle we saw above, and you
remember that we are obliged to use them. Now instead of having to
face the ugliness of TG_RECT everyday you can wrap it in a geom::box
and manipulate it with ease.
<code>
geom::box<TG_RECT> region_to_update[100];

// Here use all nice features of geom::box like center() and corner()
//...

// Now use impl() to get TG_RECT
TG_Update_Screen(&region_to_update[0].impl(), 100);
</code>
Note that :
     - You take benefit of the notaional convinience of geom::box
     - geom::box is a zero cost wrapper, using it does not create
     additional overhead as such.
     - You don't have to convert between geom::box<TG_RECT> and
     TG_RECT, or more precisely, the conversion is zero cost.
And that is not specific to trendy_graph, if you also work with
FastGraph you'll be able to wrap FG_Rectangle in a geom::box  and
enjoy the same interface as with geom::box<TG_RECT>, while still be
able to turn a geom::box<FG_Rectangle> into a FG_Rectangle at no cost
! You learn one interface (that of geom::box) and you keep using it
regardless of the underlying graph API, while not having to pay in
efficiency,  Isn't wrapping other libraries wonderful ? 

>I would want
>precisely defined semantics on the parameters of a point. For example I would
>expect the semantics of float versus integer value_types to be defined
>separately. Allowing use of  user defined point systems would appear to make
>this type of control of the specification much more difficult, if not
>impossible.

Well, putting the exact and precise requirements imposed on
geom::point<>'s template parameter and on the corresponding traits
specialization is hard, very hard, maybe too hard for me. But I'll
give it a try. Thanks for pointing this out.

>Not sure what units angles are in. Is it degrees or radians? radians is my
>preference.

The standard C++ library (std::sin, std::cos, .. etc) speaks in
radians, so I do.

>FWIW I use specific type safee angle types. This allows conversions
>between the two families of angular unit. I also use types representing lengths
>in graphics. IOW I use a point<pqs::length::mm> type  etc. This provides
>graphics data with unit information independent of the device its currently
>being displayed on. Its not a solution for every case but where the units of  
an
>entity is fixed it provides this information with no runtime space
>overhead.

Interesting ... As a first impression, I can say that currently
available point implementations use double for angles, but nothing in
the library design prevents using pqs:: stuff.

>See my site at
>http://www.servocomm.freeserve.co.uk/Cpp/physical_quantity/index.html

What is the connection between your library and boost, do you intend
to have it accepted in Boost ? .. I'll make sure to give it a try ...

>I strongly disagree with the statement in the documentation:
>
>" Indeed, a ``2D point'' is just a 3D point whose implementation doesn't
>actually reserve memory space for a Z attribute."

Ok, maybe you're right. But I think it just a matter of how to express
things. Consider the alternative :

" There is no such a thing as a 2D point, There is even no such a
thing as 2D, the world is 3D, and all points are 3D. Now, some point
are always located on Z=0 plan and don't need to actually store their
Z attribute, we call them 2D points."

>2D space has no notion of another dimension.

Consider this: (let IR be the set of all real numbers)
IRxIR is a 2D space. And IRxIRxIR is a 3D space.
Let U={(x,y,z) in IRxIRxIR such that z=0}
Now we can find an automorphism that maps U to IRxIR. That is, even
though U seems part of IRxIRxIR (3D), it is mathematically
indistinguishable from IRxIR (2D). So U is a part of IRxIRxIR (3D), but
at the same time *it is* IRxIR (which is 2D). See how the "notion of
another dimention" depends on the point of view ...

>Mixing 2D and 3D points doesnt actually happen in my experience.
>They live in separate spaces.
Like I say, 2D points are elements of IRxIR which is U which is part
of IRxIRxIR which is the set of all 3D points.  It just a matter of how you
look at things ..

> 3D points are mapped to 2D points by applying a
>transform(projection).  Some sort of matrix operations on 2D and 3D points
>should also be available(which will require conversion to homogeneous
>coordinates).

For homogeneous stuff, one can easily write a point implementation, say
point_xyzq that stores a forth attribute. But about matrix
transformation,... well,  I'm not sure if there should be somekind of
geom::matrix.. For example, If your're doing 3D games using OpenGL you
already have some matrix manipulation primitives like glMultMatrix(),
do we want to wrap glMultMatrix, to concurrence it or not care about
it at all ? (IMO the latter !)

>The box here is useful for a GUI viewport or window, an attribute of  the
>current output device. IMO Its a mistake for a geometry library to get involved
>with this low level stuff too early. Geometrically a box is a 2D region bounded
>by  geometric *1*  lines, with no guarantee of its attitude. Why not start with
>the most primitive concepts, eg geometric points, lines, circles arcs, curves
>and regions?

Exactly what I was thinking.

>That said, there should be some form of  mechanism for graphical output on
>various platforms/ devices, but again without this affecting the core geometry
>library. generically this requires some means of converting points between
>various coordinate systems.

Humm .... such a mechanism should be, but I doubt it is really up to
Boost.Geom to provide it. The user is free to use any output means
available, for example if [s]he is using fast_graph:
<code>
geom::box<FG_Rectangle> bx;
// Play with bx ....

// Draw bx
FG_DrawRectangle(&bx.impl(), FG_Forground, FG_MAKE_COLOR_RGB(0x2,
                                                0x22, 0x32);
</code>

>Sorry for all the criticism. As you may gather I have my own ideas on what I
>want from a geometry library... looking forward to hearing your views ...

No, don't be sorry. With your suggestions, opinions and criticism
you're helping improve my work (& knowledge), thanks a lot.

>as opposed to  lines which have colour and thickness. These attributes,
>though required for output are not necessary from a geometric viewpoint

I totally agree !

PS: I'll have a look at your library and tell you my impressions. But
where should I send them ? Private mail ? Boost mailing list ?
Anywhere else ?

--Anis Benyelloul