[OctDev] convhulln options. =?iso-8859-15?q?=BFDo=20we=20need=20a=20better?= implementation?

[Pedro T. <pt...@te...>]

This is a post to start discussing the convhulln implementation in octave.

convhulln() is a function that returns the convex hull of a set of points. =
It=20
is based on qhull (http://www.thesa.com/software/qhull/).

Lets start with an example to center the discussion.
I did prepare the following script:

convhulltest.m
************************************
#! /usr/bin/octave -qf

% This is an example of what happens with different versions of convhulln()
% We will first define an easy to visualize polyhedron and after that we wi=
ll=20
% check what happens with the output
% prisma will hold the coordinates of a prisma with pentagonal base. There's
% also one point inside the prisma (just to verify it doesn' appear in the
% hull)

prisma =3D [0,0,0;0,1,0;1,3,0;2,0,0;2,1,0;0,0,1;0,1,1;1,3,1;2,0,1;2,1,1;1,1=
,0.5]

% I have the following commands
% convhulln() , computes the convex hull with QJ option (this is my default)
% convhullnold(), is the old version of convhulln()
% convhullnnew(), is the recently modified (1.5) version of convhulln

ch1 =3D convhulln(prisma)
ch2 =3D convhullnnew(prisma)
ch3 =3D convhullnold(prisma)

% I will run this script and comment the results. I will also comment the=20
% results using command line qhull.
*****************************************

The prisma described in the script has clearly 7 faces, two of which are=20
penthagons and the other five are rectangles. Point #11 is interior to the=
=20
prisma so it should never appear on the hull.

Here are the results... first, what I see on the console (warnings):

******************************************
pedro@linux:~> ./convhulltest.m > result

Output completed.  Verifying that all points are below 1.2e-14 of
all facets.  Will make 176 distance computations.

Output completed.  Verifying that all points are below outer planes of
all facets.  Will make 77 distance computations.
warning: extra vertex 3 of facet 0 =3D 4
warning: extra vertex 4 of facet 0 =3D 1
warning: extra vertex 3 of facet 1 =3D 1
warning: extra vertex 3 of facet 2 =3D 4
warning: extra vertex 3 of facet 3 =3D 3
warning: extra vertex 3 of facet 4 =3D 10
warning: extra vertex 4 of facet 4 =3D 6
warning: extra vertex 3 of facet 5 =3D 1
warning: extra vertex 3 of facet 6 =3D 3

Output completed.  Verifying that all points are below outer planes of
all facets.  Will make 77 distance computations.
panic: Segmentation fault -- stopping myself...
attempting to save variables to `octave-core'...
save to `octave-core' complete
Violaci=F3n de segmento
*****************************************************

As you can see, something terrible happened at the end of the last computat=
ion=20
(with the older version of convhulln). We will come back later on this.

Now the results, I will coment them using { }

******************************************************
prisma =3D

  0.00000  0.00000  0.00000
  0.00000  1.00000  0.00000
  1.00000  3.00000  0.00000
  2.00000  0.00000  0.00000
  2.00000  1.00000  0.00000
  0.00000  0.00000  1.00000
  0.00000  1.00000  1.00000
  1.00000  3.00000  1.00000
  2.00000  0.00000  1.00000
  2.00000  1.00000  1.00000
  1.00000  1.00000  0.50000

{ok... this looks pretty obvious... just to have a visual reference on what=
=20
the index of the points mean}

ch1 =3D {this is what I get with joggled input. I get the prisma constructe=
d=20
with 16 triangles: 3 on the bottom, 3 on top, and 2 for each side. Every=20
point that is a vertex is listed here somehow}

  10   9   7
  10   8   7
   6   9   7
   3   8   7
   3   2   7
   3   5   2
   3  10   8
   3  10   5
   1   2   7
   1   6   7
   4   5   2
   4   1   2
   4  10   9
   4  10   5
   4   6   9
   4   1   6

ch2 =3D {this is what I get with the new convhulln(). Notice that I only ha=
ve a=20
triangle on each face. I can not reconstruct the prisma with this=20
information. Vertex #1 which is part of the hull does not list. It is=20
possible to find it in the warnings we listed before. Notice that the=20
warnings use C enumeration for facets and vertex info; 0 is what we would=20
call 1, etc. Then what comes after the =3D sign is "in our language"}

   5   2   3
   9   6   4
   9   5  10
   8   5  10
   7   8   9
   7   2   6
   7   8   2

******************************************************

Here the results break... the old convhulln couldn't handle something....


If we run qhull (without options) from the command line against a similar=20
prisma, this is what we get:

0 3 4 2 1
5 8 3 0
8 9 4 3
9 7 2 4
6 7 9 8 5
6 5 0 1
7 6 1 2=20

To speak in the same language we should add 1 to every index listed here. A=
s=20
we can see it's not easy for octave to handle this ouput. Not all the rows=
=20
have the same number of elements. Maybe this is the reason for the=20
seg-fault?.

If we run it with QJ or Qt options we get triangulated output, although the=
=20
triangulation is different.


So... after writing this long, long brick.... Should we give some more=20
functionality to the convhulln function? (maybe giving it some other name f=
or=20
compatibility reasons). I don't understand why the new convhulln doesn't gi=
ve=20
also triangulated output (not trimmed rows...).

I hope this can be an starting point for discussion.

Regards,
Pedro