CGAL users discussion list

[Efraim Fogel <>]

One way to do it is creating a total order of the (unnormalized) 
normals, described below, then adding a sub order for the translation of 
the plane.

In general you need to maintain a lexicographic ordering on the polar 
coordinates u and v of the normals without explicitly computing and 
obtaining them.

Consider the unit sphere parameterized by two parameters u and v as 
follows: $\phi_S(u, v) = (\cos u \cos v, \sin u \cos v, \sin v)$, where 
$\Phi = [-\pi, \pi] \times [-\frac{\pi}{2}, \frac{\pi}{2}]$.

First, assume that the south pole (0,0,-1) is the smallest point of all 
points on the sphere, and the north pole (0,0,1) is the largest point. 
Let's call these 2 points contraction points. Secondly, assume that any 
point on the opposite Prime Meridian (with y = 0, and x < 0) is smaller 
than any point that is not on the opposite Prime Meridian (and, of 
course, smaller than the north pole.) Let's call the opposite Prime 
Meridian the identification arc.

Thirdly, you need a procedure that compares two points $p_1$ and $p_2$ 
by their $u$-coordinates that admits the assumption that the input 
points do not coincide with the contraction points and do not lie on the 
identification arc. Recall, that points are in fact unnormalized vectors 
in R^3. We project $p_1$ and $p_2$ onto the $xy$-plane to obtain 
two-dimensional unnormalized vectors $\hat{p_1}$ and $\hat{p_2}$, 
respectively. We compute the intersection between the identification arc 
and the $xy$-plane to obtain a third two-dimensional unnormalized vector 
$\hat{d}$. Finally, we test whether $\hat{d}$ is reached strictly before 
$\hat{p_2}$ is reached, while rotating counterclockwise starting at 
$\hat{p_1}$. This geometric operation is supported by every geometric 
kernel of \cgal{}.

Forthly, you need a procedure that compares two points $p_1$ and $p_2$ 
lexicographically. It first applies \the procedure above to compare the 
$u$-coordinates of the two points. If the $u$-coordinates are equal, it 
applies a predicate that compares the $v$-coordinates of two points with 
identical $u$-coordinates. This predicate first compares the sign of the 
$z$-coordinates of the two unnormalized input vectors. If they are 
identical, it compares the squares of their normalized $z$-coordinates, 
essentially avoiding the square-root operation.

Amir Vaxman wrote:
> What I need is any total order on planes, as I have a set of planes, and
> want to know efficiently if another input plane is already in the set. The
> planes in the set are not parameterized in any assumed fashion, and neither
> does the input plane parameterized the same way as the plane in the set it
> might fit to, so the only thing given is that the set planes are different.
> New entities are no problem, but normalization is, because I use a gmpq
> kernel.
>
> Amir.
>
> -----Original Message-----
> From: Andreas Fabri [mailto:] 
> Sent: Wednesday, March 18, 2009 2:14 PM
> To: 
>
> Subject: Re: [cgal-discuss] Sorting Planes Lexicographically
>
> Hi Amir,
>
> Isn't the most important question, what do you want to achieve by orderng
> them?
>
> Take the vector which has the same direction as the normal.
> That orders them also in the case they have the same normal.
>
> Is the question if they can be ordered based on the a,b,c,d
> without computing new entities ?
>
> andreas
>
> Amir Vaxman wrote:
>   
> > Yes, but then you have to normalize.. (there is no Direction_3 total 
> > order like in Direction_2).
> >
> >  
> >
> > *From:*  [mailto:] *On 
> > Behalf Of *Ophir Setter
> > *Sent:* Wednesday, March 18, 2009 1:34 PM
> > *To:* 
> >
> > *Subject:* Re: [cgal-discuss] Sorting Planes Lexicographically
> >
> >  
> >
> > I am guessing that you could sort the normals to the planes 
> > (lexicographically).
> >
> > On Mon, Mar 16, 2009 at 3:01 PM, Amir Vaxman < 
> > <mailto:>> wrote:
> >
> > Hello,
> >
> >  
> >
> > Is there a way to sort planes lexicographically in CGAL, in a similar 
> > manner as points are sorted? Of course, I am looking for something 
> > invariant of plane parameterization.
> >
> >  
> >
> > Amir.
> >     
--
 ____  _        ____             _
/_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                       _/