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

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2007-10-07 13:53:24

Hello Gyuszi,

> 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;
> };
>
OK.

>>
>>> * 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.
>
But how is this a property of the library?
Are the data structures and algorithms specifically optimized for storage 
and/or speed?
If yes, it might be better to state this fact instead, and outline how.

>> 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.
>
You said "none" of the functions. Is that so?
What if I really need to so something on the X or Y etc?

>
> Let's consider the example below.
>
> [really bad code ommitted]
>
> Translating this to gtl isotropic code:
>
> concave += (a.towards(b).left() == b.towards(c));
>
OK. So you are calling isotropic what I know as "coordinate free 
operations".

Notice that I could implement the above as:

concave += ( cross_product((b-a),(c-a)) < 0 ) ;

using basic algebraic stuff (and this would work for non-rectilinear edges 
as well).

So as I said in a previous post I fear this API can be somewhat bloated, but 
anyway, the "idea" of a coordinate free/isotropic approach is certianly 
sound (most geometry libraries I know follow it, in fact).

> 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));
>
Right.
But using basic algebra that becomes:

convex += ( cross_product((b-a),(c-a)) > 0 ) ;

Notice that the lhs expression is the exact same code.
In your case one needs to change ".left()" for ".right()".
That's is what I mean with interface bloat.
But let's not digress until we can see some code and docs.

> 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.
>
How so exactly?
Can you show how this API would handle the case if a==b or b==c and also if 
a==b==c?

> Judging on the developers I'm familiar with, once you start programming
> based on
> isotropy, you'll never write the old-style code again.
>
Right.
I think you should know that this is the approached followed by most modern 
geometry libraries.
But granted, end-users tend to write the sort of code you shown above, so a 
good geometry library is a must.

> There could well be other, more advanced techniques out there, but so
> far this
> served us very well
>
There are even higher level approaches on top of coordinate-free operations 
that are important in a geometry library.
But we can discuss that after I've seen the code and dosc.

Best

-- 
Fernando Cacciola
SciSoft
http://fcacciola.50webs.com