newbie question about dictionnary ?

[Bengt Richter]

On Fri, 5 Sep 2003 08:37:01 +0200, "Sophie Alléon" <alleon at club-internet.fr> wrote:

>Hi,
>
>CONTEXT
>I do numerical simulation for which I have to process mesh. A mesh is made
>of
>triangle which are made of points.
>I want from this information to create edges and build triangle from edges
>rather
>than from points.
>
>PROBLEM
>An edge is shared by possibly more than one triangle.
>
>ALGORITHM
>
>have a triangle class  (made of 3 edges)
>have an edge   class   (made of 2 points and embeding a triangle list (those
>connected to the edge)
Is that a straigt line edge, or a concatenation of possibly non-co-linear triangle
edges? And does the direction imply anything, e.g., a counter-clock-wise edge walk
with surface to the left and outside to the right? (and up being defined as the direction
of the cross product of two successive edge vectors of the same triangle).

>
>for each triangle construct its edges but I have to check if the edge
>already exists
>
>for doing this I thought the dictionary was excellent but the key is a
>string while I want it
>to be the 2 points forming the edge ? How to do it ?
You can do it with points, with a couple of caveats:
Dicts don't have to have strings as keys. Numbers and tuples are ok as keys too.
So if you have an edge, you could represent it as ((x1,y1,z1), (x2,y2,z2)) and use that
as a key. unless you are differentiating edges according to direction (which can be very
useful for some purposes), you would want to normalize the point order one way or another, IWT.

Besides order, it is important to consider floating point accuracy when/if using them
as keys of part of tuple keys, because two different expressions for the same mathematical
value may be calculated with different roundoff, and can lead to a key error if both floats
are used in keys in a dict, expecting equivalence.

Once past the floating point FUD, you can consider whether it will really affect you or not
in the specifics of what you are doing. If you convert ascii string number literal representations
to float, those should map 1:1 to consistent nearest-available-floating-point values. If you then
use those unchanged in keys, you should be ok. OTOH, if e.g. you calculate some line/surface
intersection for an end point, or subdivide an edge, etc., there might be roundoff, and you'd
have to decide how to generate key values that will actually be equal (to each other or to converted
literals) when they're "equal" according to your rules of "close enough."

One way to deal with this is to use scaled integers instead of floats, and be careful
how/when you convert. Or rounding to a given precision may work also. For fine mesh graphic
end output, you may want to think about whether whether you are rounding in a way that gives
the same end image, independent of intermediate coordinate system translations. (E.g., rounding
signed relative local pixel dimensions of a figure before adding a center-of-figure pixel offset
might look different from just rounding the final all-positive pixel coordinates, especially if
amplified by Moire effects).

>
>Have you a better idea ?
>
I have to understand better first, and then it would only be a maybe ;-)

I think a lot depends on the topology of the surface your mesh covers,
and whether it varies in resolution (i.e., are some triangles subdivided
into smaller triangles), and how the edges of the whole and of regular subregions
are defined. I.e., what does the data represent, and how did it come into being?

E.g., a sphere can be covered with 60 triangles made five per pentagonal face of the
included docdecahedron, projected, and those 60 triangles can be regularly subdivided.
Implicit in that is that you could cook up an algorithm to walk the triangles by some
indexing scheme and/or map from indices to spatial info re triangles and the sphere.

For a flat rectangular space (or topological equivalent), you might index triangles
much more easily.

Once you have your model represented, what kinds of access walks will you need to do?
Will you be iterating over the entire set of triangles and wanting to access the
neighbors of each (in which case it should be cheap to find neighbors), or are you
doing something like making countour maps, or what? Designing with the future access
patterns in mind is likely to help in making the end use faster, IWT.

Regards,
Bengt Richter