Re: [boost] GTL - geometric template library - determining interest

From: Suto, Gyuszi (gyuszi.suto_at_[hidden])
Date: 2007-10-04 17:34:17

Fernando Cacciola wrote:
> What is parametrized exactly?

Say you have your user data
class UserData{
private:
  int a, b, c;
  int x, y, z;
  float f, g, h;
};
  
and you want to interpret 4 data members as the 4 coordinates of a 
gtl::Rectangl. You would write a few lines of template specialization
to implement 3 basic functoins: get() set() create()

#include <Gtl.h>
template <>
class gtl::RectangleInterface<UserData> {
// need to write 3 functions only !!
};

.then in the user code would look like:

#include <Gtl.h>
typedef gtl::RectangleImpl<UserData> Rectangle; // notice the
specialization of gtl to user data
// from this point on you can use gtl::Rectangle with its full API
Rectangle r1(10, 20, 30, 40);
std::cout << r1.get(gtl::EAST) << std::endl; // prints 20  -  

> 
>> * massive capacity
> 

creating polygons and polygon sets from ~10M rectangles. Doing booleans
on them. Getting the results
back in the form of rectangles, also in the 10M range.

> What does this mean?
> 
>> * isotropic API
> 
> And this?
> 
> I could extrapolate what you mean by "isotropic API" from the examples
> below, but then I'm curious why you call it isotropic?

I'm using the term isotropic denoting the fact that none of the function
names have
any X, Y, Z, horizontal, vertical, etc in them. If that would be the
case, then once you
are using a function
p.getHighXValues() for example, then there is some piece of code that
does similar things
on Y and Z values. This may be trivially bad for the boost audience, but
the fact is that
most of the geometric code I've seen out there was written like that. It
was bad because
of code duplication, code size, readability, inflexibility, lots of if
and switch statements
all over.
In GTL, if a functoin needs to operate on a direction or orientation, it
has a function argument 
for it. The resulting code is much smaller (sometimes 4x smaller) more
readable, more flexible.

Let's consider the example below. 
// Unisotropic example
// counting the concave corners of a rectilinear
// polygon. a,, b, c are 3 adjacent vertices
// iterating clockwise around the polygon
int concave = 0;
...
// trying to find the following pattern:
//    
//    c ------ b
//               |
//               |
//               a
if(
(
a.x == b.x &&
a.y < b.y &&
b.y == c.y &&
b.x < c.x
) ||

// trying to find the following pattern:
//
//     b ---- a
//     |
//     |
//     c
(
a.y == b.y &&
a.x < b.x &&
b.x == c.x &&
b.y > c.y
) ||
// and so on for the other two patterns:
//
//      a
//      |
//      |
//      b -----c
//
// and
//
//               c
//               |
//               |
//    a ------b

This code was present in several code instances that I was exposed to.

Translating this to gtl isotropic code:

concave += (a.towards(b).left() == b.towards(c));

Notice that it's just one line. And more flexible too,
if you want to count the covex instead of concave corners, just
change left to right:

convex += (a.towards(b).right() == b.towards(c));

It also has the advantage of being immune to collinear vertices (assume
that the 
polygon in question does allow them), whereas the non-isotropic code may
have to
account for that specifically.

Judging on the developers I'm familiar with, once you start programming
based on 
isotropy, you'll never write the old-style code again.

There could well be other, more advanced techniques out there, but so
far this
served us very well

Gyuszi