Re: Possible (summer of code) projects for Octave

[Jaroslav Hajek]

On Tue, Jan 4, 2011 at 7:49 PM, Daniel Kraft <address@hidden> wrote:
> Jaroslav Hajek wrote:
>>
>> On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <address@hidden> wrote:
>>>
>>> Hi all,
>>>
>>> I'm interested to apply for Google Summer of Code with Octave next year
>>> (provided there will be another GSoC and GNU is again accepted as
>>> mentoring
>>> organization, but I guess both will be true) and in general to look into
>>> contributing to Octave (although I don't know how much spare time I can
>>> spend on it outside of something like GSoC at the moment).
>>>
>>
>> IIRC, mentors from Google itself are also acceptable under some
>> conditions. If that's still true, I could volunteer as a mentor. I
>> used to be a very active Octave developer not so long ago :)
>
> I think that's true -- however, I guess that an application for the GNU
> project (in case it is again accepted) would also do and you (or someone
> else from Octave) could mentor for it.  This is how I worked on GNU Guile
> two years ago.
>

OK, if that works even if I'm not a member of FSF, why not. Unless
there's some kind of restriction for Google employees applicable here.

>> If you compiled with (almost) all dependencies, that's already a minor
>> achivement :)
>
> Well, I did with what I need -- and this in several steps, but now I have at
> least SuiteSparse, QHull and ARPACK working; maybe something else, but if so
> I just forgot that. :)

Add FFTW and that's pretty much all the computational stuff. Then
there's a bunch of other libs for other stuff.

>
>>> Ok, sorry so far for the off-topic description of myself.  What I wanted
>>> to
>>> ask is whether there are some ideas for projects to work on that could
>>> fit
>>> for GSoC or in general something which is possibly not "fixing bugs" or
>>> doing a lot of "minor" improvements but seperate "new" things to work on
>>> and
>>> getting started.
>>
>> My favorite is implementing the OOP versions of delaunay triangulation
>> and interpolation functions. See
>> http://www.mathworks.ch/help/techdoc/ref/delaunaytriclass.html
>> http://www.mathworks.ch/help/techdoc/ref/trirepclass.html
>> http://www.mathworks.ch/help/techdoc/ref/triscatteredinterpclass.html
>>
>> in contrast to the existing delaunay et al. functions, the OOP
>> approach is not only fancy, it allows you encapsulate & reuse more
>> important topological data to make things like lookup & interpolation
>> way faster.
>> For instance, if you want to triangulate an area nad then lookup
>> enclosing triangles for a set of points, you'd use delaunay & tsearch
>> in Octave; the problem is that the latter is sadly inefficient because
>> it's not able to accept any more information than a plain list of
>> triangles from the delaunay triangulation (it can't even assume the
>> triangulation is delaunay).
>
> This actually sounds quite interesting!  Although I did not yet work at all
> with OOP in Octave (or Matlab), but I guess this would make it even more
> interesting and beneficial and should not be too hard to get into.
>

Yes, and it's quite suitable for incremental progress, something like

1. get just the interface working, wrapping the existing delaunay et
al. functions
1a. write tests
2. Wrap topology structs used by Qhull, store them in the objects and
use this to do lookups & interpolation more efficiently
3. Consider using other free libraries than qhull. If possible, make
it a configure-time choice.
4a. Consider special-cases optimizations for lookups & interpolation,
e.g. target pointset is a regular grid or another triangulation
4b. Consider special-cases optimizations for the triangulation itself
(may be already handled by some libraries)
5. Do benchmarks (incl. with Matlab if you can legally do so).

+ unless tired, do all this for 3D or even n-D :D


> I'm just not sure how "important" this would be for Octave itself --
> delaunay triangulation and related stuff seems like a more or less specific
> topic; although there was also a reply that this could help OOP in Octave in
> general (but at the moment I do not know how).
>

Well, I can't speak for others, but I consider it important.
Triangulation & piecewise interpolation is typically the approach of
choice if you have lots of source and target data, because it can be
done fast and has very simple and stable properties.
AFAIK, there are currently no Octave packages that can even do nearest
neighbor lookup in sublinear time. This means that real-life
high-resolution scattered interpolation (face reconstruction etc) is
simply not feasible to do in Octave.

> Are you aware of more cases like this?  Then one could think about a more
> general project to implement some OOP interfaces to functions.
>

Nothing from the top of my head, but I daresay this would turn out to
be a big enough project :)