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

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2007-10-08 13:36:51

François Duranleau wrote:
> On Sun, 7 Oct 2007, Fernando Cacciola wrote:
>
> [...]
>>> 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).
> [...]
>>> convex += (a.towards(b).right() == b.towards(c));
>>>
>> Right.
>> But using basic algebra that becomes:
>>
>> convex += ( cross_product((b-a),(c-a)) > 0 ) ;
> [...]
>
> Just one thing: in linear algebra, cross product returns a vector.
> Then how can you compare that result with a scalar?

OK, OK, you are right.
This is such an old trick that I often forget it is formally incorrect ;)
(it even appears in the CGA FAQ)

The cross product, as you now, is defined in 3D, not in 2D, but these are 2D 
vectors.

Since the cross product doesn't actually exist at all in 2D, there's an 
old-school trick:

1.pretend these vectors are in 3D (adding z=0)
2.take their cross product. The result is a vector of the form (0,0,z)
3.return z alone (a scalar)

Many geometry toolboxes define such a 2D pseudo-cross-product that returns 
the z component of the actual product.
But this is formally wrong... old habits die hard I guess.

But we don't want to perpetuate this blasfemy here in boost :)
So, the correct "orientation test" is to use the determinant of a matrix 
formed with those two vectors (which works in 3D too).
So I shoud have wrote that as:

( determinant((b-a),(c-a)) > 0 )

Best

Fernando Cacciola