newbie question about dictionnary ?

[Sophie Alléon]

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)

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 ?

Have you a better idea ?

Thanks

Guillaume

 

[Michael Geary]

...
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)

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 ?

Sophie, dictionary keys can be just about any immutable value. They can be
tuples, if the tuples contain only strings, numbers, or other tuples:

d = { (1,2): 'one two', (3,4): 'three four' }
d {(1, 2): 'one two', (3, 4): 'three four'}
d[(1,2)] 'one two'
d[(3,4)] 'three four'

For more information, see the Dictionaries section in the Python tutorial:

http://www.python.org/doc/current/tut/

-Mike

 

[Michael Peuser]

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 ?

Luckily you are wrong! Keys can be numbers, strings, AND tuples of immutable
data!!!

Example:

a="first"
b=2
x={}
x[(a,b)]="hi"
print x

However it will not work when assigning objects or lists to a or b.

So you can use it when you store your objects in a list and refer to them by
indexes. This is old fashioned stuff but may be really efficient.

Kindly
Michael P

 

[Alex Martelli]

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)

OK, so, say for example (for 2-D meshes):

import operator

class Point(tuple):
"""
a convenience class Point, basically just a 2-items (x,y) tuple
with handy constructor, accessors, representation
"""
__slots__ = ()
def __new__(cls, x, y):
# assert operator.isNumberType(x) and operator.isNumberType(y)
return tuple.__new__(cls, (x,y))
def getx(self): return self[0]
def gety(self): return self[1]
x = property(getx)
y = property(gety)
def __repr__(self): return "Point(%r,%r)" % self


class Edge(tuple):
"""
basically a 2-items tuple of points (NB: sorted, since we do
NOT deal with DIRECTED edges here!!!) with convenience
constructor, accessors, representation, + list of triangles
"""
def __new__(cls, p1, p2):
pts = [Point(*p1), Point(*p2)]
pts.sort()
return tuple.__new__(cls, pts)
def __init__(self, p1, p2):
self.triangles = []
def __repr__(self):
return 'Edge((%r,%r),(%r,%r))' % (self[0]+self[1])

The Triangle class may of course be made along very similar lines.

A slightly more efficient representation of Edge might use containment
of and delegation to tuple rather than inheriting from it (problem is
that inheriting from tuple impedes using a non-empty __slots__, so in
this code each Edge instance carries around an instance dictionary).

An even more clever approach might be to keep the edge->triangle data
NOT as per-instance data of edges but as a class-level attribute and
use a property for edge.triangles access, but that would violate the
explicit specs you give for the edge class.

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 ?

Have you a better idea ?

Strings just don't enter the picture here: edges are perfectly
acceptable keys into dictionaries, since they ARE tuples.

I do think that not having each edge 'embeding a triangle list',
as you put it, is an even better idea. But, although a bit more
complicated and less efficient, your idea can also work fine.
And, yes, of course you need a dictionary (in fact that is why
it's better to not ALSO have the triangle list IN the edge
instance -- it might as well be in the dictionary anyway... !!!).


Alex

 

[Ganesan R]

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 ?

The key can be any immutable object. So key can be a tuple. For example you
can do

------------------------------
mydict = {}

mydict[((1,2),(2,3))] = ...
------------------------------

You can even use your own class as a key. So to make it more readable, you
can do something like

---------------------------------------
class Edge:
def __init__(self, point1, point2):
self.point1 = point1
self.point2 = point2

p1 = (1,2)
p2 = (2,3)
e = Edge(p1, p2)
mydict[e] = ...

 

[Michael Peuser]

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 ?

Luckily you are wrong! Keys can be numbers, strings, AND tuples of immutable
data!!!

Example:

a="first"
b=2
x={}
x[(a,b)]="hi"
print x

However it will not work when assigning objects or lists to a or b.

.... and so I had been wrong as well ;-)
Instances ARE immutables so it WILL work smoothly as others have already
posted.

MP

 

[Mark Carter]

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 ?

Good keys don't have to be strings. So this is perfectly valid code:
d={}
d[((1,2), (3,4))] = 'whatever'

 

[Andrew Eland]

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 ?

Unlike perl, the keys used for a Python dictionary can be arbitary
objects. You're not forced to use strings. If you represent edges as a
tuple of the form (startPoint,endPoint), you can do the following:

start=(1,1)
end=(2,2)
edges={}
edges[(start,end)]=1
if (start,end) in edges:

.... print "Edge exists"
....
Edge exists

If you're using Python 2.3, you can use the new sets module, which
will give you an object repesenting a set, which is a little neater
than just using a dictionary.

-- Andrew (http://www.andreweland.org)

 

[johnagianis]

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)

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 ?

Have you a better idea ?

Thanks

Guillaume

Dictionary keys are not necessarily strings. It can be even class
instances!! You can have the following:

class edge:
def __init__(self,x,y):
self.a=x
self.b=y
def ...
....


pointA=(3,1)
pointB=(5,2)
edgeA=edge(pointA,pointB)

triangle={}

triangle[edgeA]=something

Well i think that a list would be ok. The use of a dictionary is for
making a relation (key->value).In this case i dont know what the value
could be.

John

 

[Bengt Richter]

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