newbie question about dictionnary ?

Discussion in 'Python' started by Sophie Alléon, Sep 5, 2003.

  1. 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
     
    Sophie Alléon, Sep 5, 2003
    #1
    1. Advertising

  2. Sophie Alléon wrote:
    >...
    > 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 Geary, Sep 5, 2003
    #2
    1. Advertising

  3. "Sophie Alléon" <> schrieb im Newsbeitrag
    news:3f582f90$0$20952$-internet.fr...


    > 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
     
    Michael Peuser, Sep 5, 2003
    #3
  4. Sophie Alléon 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)



    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
     
    Alex Martelli, Sep 5, 2003
    #4
  5. Sophie Alléon

    Ganesan R Guest

    >>>>> "Sophie" == Sophie Alléon <> writes:

    > 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] = ...
    ---------------------------------------

    You get the idea :)

    Ganesan

    --
    Ganesan R
     
    Ganesan R, Sep 5, 2003
    #5
  6. "Michael Peuser" <> schrieb im Newsbeitrag
    news:bj9h99$btm$02$-online.com...
    >
    > "Sophie Alléon" <> schrieb im Newsbeitrag
    > news:3f582f90$0$20952$-internet.fr...
    >
    >
    > > 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
     
    Michael Peuser, Sep 5, 2003
    #6
  7. Sophie Alléon

    Mark Carter Guest

    > 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 news: keys don't have to be strings. So this is perfectly valid code:
    d={}
    d[((1,2), (3,4))] = 'whatever'
     
    Mark Carter, Sep 5, 2003
    #7
  8. Sophie Alléon

    Andrew Eland Guest

    "Sophie Alléon" <> wrote in message news:<3f582f90$0$20952$-internet.fr>...

    > 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)
     
    Andrew Eland, Sep 5, 2003
    #8
  9. Sophie Alléon

    johnagianis Guest

    "Sophie Alléon" <> wrote in message news:<3f582f90$0$20952$-internet.fr>...
    > 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
     
    johnagianis, Sep 5, 2003
    #9
  10. On Fri, 5 Sep 2003 08:37:01 +0200, "Sophie Alléon" <> 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
     
    Bengt Richter, Sep 5, 2003
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. NOBODY
    Replies:
    2
    Views:
    830
    Thomas Weidenfeller
    Oct 17, 2003
  2. Bob Ippolito

    Re: Identity dictionnary

    Bob Ippolito, Feb 29, 2004, in forum: Python
    Replies:
    1
    Views:
    318
    Jean-Sebastien Roy
    Feb 29, 2004
  3. Famille Delorme

    Dictionnary vs Class for configuration

    Famille Delorme, Apr 30, 2004, in forum: Python
    Replies:
    7
    Views:
    344
  4. Sigfried
    Replies:
    9
    Views:
    482
    Tom Anderson
    Dec 2, 2008
  5. Jerry C.
    Replies:
    8
    Views:
    278
    Uri Guttman
    Nov 23, 2003
Loading...

Share This Page