Re: Reuse of arrays in DelaunayCustom

>My current method for extracting neighbors has complexity O(num_elms). For
>the dataset in question it takes about 30 seconds and 20Mb while computing,
>and returns an array of 2Mbs. Since I'm not very familiar with the
>implementation if Delaunay I was wondering if any of the public fields
>contained information that I could use to better the performance. I could
>not find in the documentation what is contained in the edges and walk
>arrays. I was hoping that some of this data could reduce my memory
>consumation.

Hi Gunnar,

The four arrays of Delaunay are Tri, Vertices, Walk and Edges.
The samples array, float[dim][num] (where dim is the domain dimension
of the dataset and num is the number of samples in the dataset),
is not stored in the Delaunay object.

Tri is a mapping from triangle number to sample number.  The array
has the form int[ntris][dim+1], where ntris is the number of triangles
in the triangulation and dim is the domain dimension of the dataset.
Each element of the Tri array is an index into the samples array.

Vertices is a mapping from sample number to triangle numbers (the
reverse of the Tri array).  It has the form int[num][x], where num
is the number of samples in the dataset and x is a variable
corresponding to the number of triangles in which the particular
sample is located.  Each element of Vertices is an index into Tri.

Walk is a mapping from triangles to neighboring triangles (triangles
that share an edge with each other).  It has the form
int[ntris][dim+1].  Each element of Walk is an index into Tri.

Edges is a mapping from triangles to edge number (each edge of the
triangulation is assigned a unique edge number).  It has the form
int[ntris][3*(dim-1)].  The total number of unique edges is given
by the NumEdges field.

If by "neighbors" you mean data points that share a triangle, it
should be easy to extract that information from the Delaunay arrays.
If you are looking for neighbors for sample #z, you can get a list
of relevant triangles (an array of indices into Tri) from
Vertices[z].  For each element i of Vertices[z], You can get a list
of samples (an array of indices into samples) from Tri[i].

-Curtis


  • 2001 messages navigation, sorted by:
    1. Thread
    2. Subject
    3. Author
    4. Date
    5. ↑ Table Of Contents
  • Search the visad archives: