Menu
▾
▴
octave-dev
|
From: Rafael L. <rla...@us...> - 2003-12-18 10:46:41
|
* Pedro Tarrafeta <pt...@te...> [2003-12-18 11:05]:
> This is what Qt is supposed to do. QJ also does it although using some other
> method (joggling vertices until only simplicial facets are found). Anyway Qt
> option is not working under octave. Is it just my case?
I also noticed that Qt is not working and I have no clue about where the
problem is. I will try to investigate further when I will have some time.
> I think so.
> In fact. Maybe we should use convhulln for matlab compatibility if this is an
> issue. Some of the important info that I think should be accesible from
> octave is stored in qh struct in qhull. What I mean is:
> - A polyhedron is just an ordered list of facets.
> - A facet should contain:
> - id number
> - normals and offset (hyperplane supporting the facet)
> - area
> - set of vertices (n if simplicial, >n if non-simplicial)
> - set of neighbours (again n if simplicial...). Here's the need for the id.
> - set of ridges. (?)
>
> I don't know how difficult this is but it looks like in the same
> FORALLfacets{} loop the above can be retrieved and written to octave.
This means a total redesign of the qhull functions and facilities for
Octave, with the old API (delaunay, convhull, and voronoi) being wrappers to
them. I would like to see this happening. Could someone make a complete
design proposal?
--
Rafael
|
|
From: Pedro T. <pt...@te...> - 2003-12-19 09:22:18
|
El Jueves, 18 de Diciembre de 2003 11:43, a Rafael Laboissiere se le ocurr= i=F3=20 decir lo siguiente: > I also noticed that Qt is not working and I have no clue about where the > problem is. I will try to investigate further when I will have some time. It works adding the Q0 option. According to QHull manual Q0: "do not pre-me= rge=20 facets with 'C-0' and Qx". C-0 and Qx options are by default used by qhull = to=20 avoid precission errors. This errors can be avoided pre-merging coplanar=20 facets (C-0 & Qx) or using QJ option.=20 Again reading qhull manual: "Use option 'Qt' to triangulate all non-simplic= ial=20 facets before generating results". So... Qt uses C-0 and Qx and only later = it=20 "breaks" non-simplicial facets. Maybe this is why, since we read the qh=20 struct on memory rather than the final result of qhull this isn't working..= =2E=20 It looks like there's a missing step. This is as far as I've got... Regards, Pedro |
|
From: Paul K. <pki...@us...> - 2003-12-19 05:32:06
|
On Dec 18, 2003, at 5:05 AM, Pedro Tarrafeta wrote:
>
>> Are these two cases different enough that we need different functions?
>>
>> I think you are going to need an interface layer above the QHull
>> options
>> so that users can ask for them nicely:
>>
>> [X,Y,Z] = convhulln(cube,'output',{'simplicial','ideal','geomview'})
>>
>> This says that X will contain the simplicial output (as a full
>> matrix),
>> Y will contain a cell array of facet sizes, and Z will contain a
>> string
>> used to control geomview. The default for output must be 'simplicial'
>> for compatibility.
>>
>> That means you will need other options for controlling the QHull
>> algorithm,
>> such as 'qhull','QJ' to feed a raw option string, or if you are
>> feeling
>> creative, meaningful names for all the options.
>
> I think so.
> In fact. Maybe we should use convhulln for matlab compatibility if
> this is an
> issue. Some of the important info that I think should be accesible from
> octave is stored in qh struct in qhull. What I mean is:
> - A polyhedron is just an ordered list of facets.
> - A facet should contain:
> - id number
> - normals and offset (hyperplane supporting the facet)
> - area
> - set of vertices (n if simplicial, >n if non-simplicial)
> - set of neighbours (again n if simplicial...). Here's the need for
> the id.
> - set of ridges. (?)
Maybe you want a structure array?
x(id).normal = <normal>
x(id).offset = <offset>
x(id).area = <area>
x(id).vertices = [v1,...,vn]
x(id).neighbors = [id1,...,idn]
x(id).ridges = <?>
My only question is, are there relevant vector operations you want to
do on the returned information? Or do you need a for loop to process
each id? Since the octave interpreter is slow, I prefer to avoid for
loops
as much as possible.
Paul Kienzle
pki...@us...
|
|
From: Pedro T. <pt...@te...> - 2003-12-19 08:47:56
|
El Viernes, 19 de Diciembre de 2003 06:31, a Paul Kienzle se le ocurri=F3 = decir=20 lo siguiente: > > - A polyhedron is just an ordered list of facets. > > - A facet should contain: > > - id number > > - normals and offset (hyperplane supporting the facet) > > - area > > - set of vertices (n if simplicial, >n if non-simplicial) > > - set of neighbours (again n if simplicial...). Here's the need for > > the id. > > - set of ridges. (?) > > Maybe you want a structure array? > > x(id).normal =3D <normal> > x(id).offset =3D <offset> > x(id).area =3D <area> > x(id).vertices =3D [v1,...,vn] > x(id).neighbors =3D [id1,...,idn] > x(id).ridges =3D <?> > > My only question is, are there relevant vector operations you want to > do on the returned information? Or do you need a for loop to process > each id? Since the octave interpreter is slow, I prefer to avoid for > loops > as much as possible. Let me give you some ideas of what I'm doing. My hull belongs to an economi= c=20 simulation model. Each facet has an economic interpretation in terms of=20 prices of different inputs. I do perform computations on every facet to get= a=20 set of points that will give me the shape of a demand function. So... I do= =20 loop around all facets. I also have to study the equilibrium conditions=20 around the "optimal" facet and that's where the neighbors set becomes=20 specially important (neighbours for those of us who learnt english with a B= BC=20 method ;) ). Regards, Pedro |
|
From: Paul K. <pki...@us...> - 2003-12-19 05:42:16
|
On Dec 18, 2003, at 3:53 AM, Rafael Laboissiere wrote:
> * Paul Kienzle <pki...@us...> [2003-12-17 20:07]:
>
>>
>> On Dec 17, 2003, at 7:00 PM, Rafael Laboissiere wrote:
>>
>> [...]
>>> would be represented in Octave like this:
>>>
>>> A = {[3 4 2 1],
>>> [7 4 3],
>>> [5 7 3 1],
>>> [4 6 2],
>>> [6 7 5],
>>> [7 6 4],
>>> [6 5 1 2]}
>>>
>>>
>>> (Notice that vertex indices in Octave start at 1 instead of zero.)
>>>
>>> I do not know how backward incompatible would be such a change.
>>
>> I think the most convenient would be to return a cell-array of
>> matrices,
>> one for each dimension of returned facet.
>
> Sorry, I did not understand the above statement. Could you give an
> example,
> please?
A = { [7 4 3; 4 6 2; 6 7 5; 7 6 4], [5 7 3 1; 6 5 1 2] }
This is the same information as above but you can process it with
"for i=1:2" rather than "for i=1:6".
>> I think it would also be convenient if the default were to arbitrarily
>> split those facets that are non-simplicial so that those who just want
>> triangles don't have to deal with the occasional square. I'm
>> guessing that
>> this is what matlab does --- convhulln returns this for the cube:
>>
>>>> convhulln(cube)
>>
>> ans =
>>
>> 3 4 1
>> 4 2 1
>> 2 4 6
>> 2 5 1
>> 5 2 6
>> 7 5 6
>> 4 7 6
>> 7 4 3
>> 7 3 1
>> 5 7 1
>
> This is the case in Octave with the "QJ" option:
>
> octave:3> convhulln(cube,"QJ")
> qhull warning: joggle ('QJ') always produces simplicial output.
> Triangulated output ('Qt') does nothing.
> ans =
>
> 7 8 6
> 4 8 6
> 5 7 1
> 5 7 6
> 2 4 1
> 2 4 6
> 2 5 1
> 2 5 6
> 3 7 8
> 3 4 8
> 3 7 1
> 3 4 1
Okay. But aren't we supposed to be avoiding QJ? Is there a way to
break up a non-simplicial facet which doesn't introduce errors?
>
>> So long as the default all-simplicial case is returned as a matrix,
>> backward compatibility doesn't matter. The user will need special
>> code to
>> handle the non-simplicial facets anyway.
>>
>> Are these two cases different enough that we need different functions?
>
> I do not think so, since the output format will be dependent on the
> data
> and, in general, cannot be determined beforehand by the user.
>
> I have already an idea on how to implement this change (i.e.,
> returning a
> cell array instead of a matrix in the non-simplicial case. Should I go
> ahead?
The output needs to be predictable so that users can code for it.
Also, the
default output must be simplicial only for compatibility --- same named
functions should give the same results for the same input.
>
>> I think you are going to need an interface layer above the QHull
>> options so
>> that users can ask for them nicely:
>>
>> [X,Y,Z] = convhulln(cube,'output',{'simplicial','ideal','geomview'})
>>
>> This says that X will contain the simplicial output (as a full
>> matrix),
>> Y will contain a cell array of facet sizes, and Z will contain a
>> string
>> used to control geomview. The default for output must be 'simplicial'
>> for compatibility.
>>
>> That means you will need other options for controlling the QHull
>> algorithm, such as 'qhull','QJ' to feed a raw option string, or if
>> you are
>> feeling creative, meaningful names for all the options.
>
> That looks like a quite nice idea. Two questions:
>
> * Is the option passing format you described above standard in
> Matlab/Octave/octave-forge?
Matlab uses 'option',value pairs frequently (e.g., for all of their
handle
graphics functions and for their optimization functions). Many
functions
also accept structures where x.option=value. I wrote some code a
couple of years ago to sort out options --- I'll update it and send it
along.
Matlab also uses fn(...,'option','option','option') and fn(...,parms),
where
parms is an array of integers, but these are less common.
>
> * Can I consider your suggestion as a final design or is it just a
> sketch? If it is the later, could you please propose a complete
> design (so that implementation can follows easily)?
I can't propose a final design because I don't know how to use
QHull effectively. You tell me what options you want to control
and what they mean, and I can suggest an interface.
- Paul
|
|
From: Pedro T. <pt...@te...> - 2003-12-19 08:58:57
|
El Viernes, 19 de Diciembre de 2003 06:24, a Paul Kienzle se le ocurri=F3 =
decir=20
lo siguiente:
> >> I think the most convenient would be to return a cell-array of
> >> matrices,
> >> one for each dimension of returned facet.
> >
> > Sorry, I did not understand the above statement. Could you give an
> > example,
> > please?
>
> A =3D { [7 4 3; 4 6 2; 6 7 5; 7 6 4], [5 7 3 1; 6 5 1 2] }
>
> This is the same information as above but you can process it with
> "for i=3D1:2" rather than "for i=3D1:6".
Be carefull... if we are returning more things from qhull the order is=20
important, unless you also return the facet ID.
> Okay. But aren't we supposed to be avoiding QJ? Is there a way to
> break up a non-simplicial facet which doesn't introduce errors?
That's what Qt is supposed to do, but as Rafael also noticed, this option i=
s=20
not working under octave properly.
> I can't propose a final design because I don't know how to use
> QHull effectively. You tell me what options you want to control
> and what they mean, and I can suggest an interface.
QHull has many, many options. In fact delaunay* and voronoi* are just QHull=
=20
with parameters. I can prepare a list of the options I think are most=20
important. I'll mail them to the list as soon as I prepare it.
Regards,
Pedro
|
|
From: Pedro T. <pt...@te...> - 2003-12-19 10:53:58
|
QHull provides a very complete set of options. This options come in different
families:
- Format options
- Print options
- Geomview options
- Trace options
- precision options
- Q control options.
I think the most important issue to decide is what output will be handled back
to octave and what won't. For example we've been running qhull with the s
option (for a summary on stderr) and we didn't make use of it.
As it was said in another post I think the struct array proposed by Paul is
correct. (We'll need to see the format of the ridges element, probably a
matrix containing the vertices of each ridge, always with the same dimension
and varying length depending on the facet been simplicial or not).
x(id).normal = <normal>
x(id).offset = <offset>
x(id).area = <area>
x(id).vertices = [v1,...,vn]
x(id).neighbors = [id1,...,idn]
x(id).ridges = <?>
Some other kind of output like OFF file for Geomview or summary can be sent to
a file. For this second purpose it is important to get the "TO file" option
working. Right know it does nothing.
I gues the most used options for qhull could be the subset presented by qhull
on the command line:
d : 'delaunay', Delaunay triangulation lifting the points to a paraboloid
d Qu : 'furthest delaunay'. Furthest site Delaunay triangulation.
v : 'voronoi'. Voronoi diagram
v Qu: 'furthest voronoi'. Furthest site Voronoi diagram
H1,1: 'halfspace intersection' about [1,1,0,0...]
Qt: 'triangulated output'
QJ: 'joggled input'
Tv: 'verify results'
s: 'output summary'
i: 'vertices in facets' (This is what we actually get returned to octave)
n:'normals'. Normals with offset for each facet (This is what I also want to
have ;).)
p: 'vertex coordinates'. We already have that since we parse a matrix with
this to the function.
Fp: 'halfspace intersections'
Fx: 'extreme points'
FA: 'total area and volume'
o: 'OFF format'
G: 'Geomview output'
m: 'Mathematica output'
QVn: 'print facets that include point n'
TO file: 'output file'
As you see QVn is an "option with options" so I would eliminate it from the
list and pass it as a string like it is done now. The same for Hn,n and all
the other options not listed here.
Regards,
Pedro
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X