[Tutor] Triangle structure for triangulation
Dear All,
I have written a Delaunay triangulation 10 years ago
in C based on triangle structure.
It was 400 lines, so it seems to be a fine task to turn into python.
My problem is the translation of the C structure and the OO thinking.
I tried to draft it so.
/*
The triangle, its neighbours,
sides and rotations.
0
VTOP
/\
/ t r \
LEFT/ oo \RIGHT 1
/ r t \
/ act\
1 VLEFTVRIGHT 2
BOTTOM
0
*/
typedef struct{
TRIINDEXneighbour[3]; // triangles: bottom, right, left
POINTINDEX vertex[3]; // vertex: top, left, right
float height;// elevation
} TRIANGLE;
Each triangle has three vertices and three neighbours.
To calculate the elvation on the triangulation at a given point,
it is important to find the coresponding triangle as fast as possible,
so the triangles had directions. But it was important in the update
process too.
So I had an array with the triangles, but the neighbours were
directed triangles not simple triangle (TRIINDEX).
There were C macros to get the neighbours of the triangles.
To get the left triangle tleft = LEFT(t), tright = RIGHT(t), tbottom =
BOTTOM(t)
ROT(t) was the same triangle as t, but rotated ccw.
so t = ROT(ROT(ROT(t)))
TOR(t) was the same triangle as t, but rotated cw.
t = TOR(TOR(TOR(t)))
In C, I have used
typedef unsigned intTRIINDEX;
to identify a triangle, where the last two bites were used to handle the
directions.
## I can translate it into python in this way
class Triangle:
def __init__(self, points, neighbours):
self.points = points
self.neighbours = neighbours
def TOR(self, direction):
return (self, (direction+1)%3)
def ROT(self, direction):
return (self, (direction+2)%3)
def RIGHT(self, direction):
return (self.neighbours[(direction+2)%3])
I would ask your opinions to encapsulate a triangle into a directed
triangle.
I made my first trial on the way to keep a directed triangle as a tuple
(triangle, direction)
and register it in that way.
I would like to use directed triangles, but wouldn't like to use too much
memory.
Yours sincerely,
Janos Juhasz
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Triangle structure for triangulation
János Juhász [EMAIL PROTECTED] wrote ## I can translate it into python in this way class Triangle: def __init__(self, points, neighbours): self.points = points self.neighbours = neighbours def TOR(self, direction): return (self, (direction+1)%3) def ROT(self, direction): return (self, (direction+2)%3) def RIGHT(self, direction): return (self.neighbours[(direction+2)%3]) I would ask your opinions to encapsulate a triangle into a directed triangle. I'm not totally sure what you are looking for but my first guess would be to add a direction argument to the init and store it as an attribute. But it sounds like you need to add some methods too. What do you do with these triangles? From your descriptionI'd expect to see some methods taking other triangles as arguments? For example you store the points but never use them. Attributes in a class shjould be thee to support the metjods. If the atrributes are not used by any method that implies that they are not needed or that you are accessing them from some function outside the class, which is probably an indication of bad OO design. I made my first trial on the way to keep a directed triangle as a tuple (triangle, direction) and register it in that way. I would like to use directed triangles, but wouldn't like to use too much memory. How much memory would be too much? If you don't know, then go with the best design and optimise the memory only when you know that there is a need. Prematurely optimising memory is just as bad as prematurely optimising speed. It usually leads to bad code when there is no need. -- Alan Gauld Author of the Learn to Program web site http://www.freenetpages.co.uk/hp/alan.gauld ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
[Tutor] Triangle structure for triangulation
Dear Allan, thanks for your coments. ## I can translate it into python in this way class Triangle: def __init__(self, points, neighbours): self.points = points self.neighbours = neighbours def TOR(self, direction): return (self, (direction+1)%3) def ROT(self, direction): return (self, (direction+2)%3) def RIGHT(self, direction): return (self.neighbours[(direction+2)%3]) I would ask your opinions to encapsulate a triangle into a directed triangle. I'm not totally sure what you are looking for but my first guess would be to add a direction argument to the init and store it as an attribute. But it sounds like you need to add some methods too. What do you do with these triangles? From your descriptionI'd expect to see some methods taking other triangles as arguments? The triangulation would be used for surface modelling. The most important function is CalcZ(point(x, y)), that interpolates the elevation on the surface of a triangle. For this interpolation I have to find the corresponding triangle of the point, that can be made the fastest by walking from triangle to triangle. This is the first reason I need the neighbours. I also need to extend and update the triangulation, when a new point inserted into it. For example you store the points but never use them. Attributes in a class shjould be thee to support the metjods. If the atrributes are not used by any method that implies that they are not needed or that you are accessing them from some function outside the class, which is probably an indication of bad OO design. I feel that, the best would be to strore 3 separate triangles for A,B,C points, Triangulation.Append(Triangle(A,B,C)) Triangulation.Append(Triangle(B,C,A)) Triangulation.Append(Triangle(C,A,B)) And register the topological relations after it. It could be OO, and simple. As I wrote, I made it in C with structures, so it wasn't OO, but fast. I can translate a C iteration over C structures into python, to iterate over class objects, and usually I don't miss the pointers. Except now, when the algorithm based strongly on pointers and indeces :( Yours sincerely, Janos Juhasz ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Triangle structure for triangulation
János Juhász [EMAIL PROTECTED] wrote ## I can translate it into python in this way class Triangle: def __init__(self, points, neighbours): def TOR(self, direction): def ROT(self, direction): def RIGHT(self, direction): and store it as an attribute. But it sounds like you need to add some methods too. What do you do with these triangles? The most important function is CalcZ(point(x, y)), that interpolates the elevation on the surface of a triangle. For this interpolation I have to find the corresponding triangle of the point, that can be made the fastest by walking from triangle to triangle. This is the first reason I need the neighbours. OK, That suggests to me that your triangle should have a predicate method contains(aPoint) where aPoint is a tuple of x,y coords and it returns a boolean. The iteration could then become a list comprehension: candidates = [t for t in triangles if t.contains(myPoint)] candidates will be a list of all triangles containing the point (hopefully a very short list!!) And the calcZ function could be a method of the collection of triangles if the collection were made into a class - a TriangualtedSurface maybe? I also need to extend and update the triangulation, when a new point inserted into it. OK That sounds like a job for the Surface class too, but with a fairt bit of help from, the triangles within it. A lot of the adoption of OOP is about rethinking how procedural style functionscan be split up with the various responsibilities parceled out between the various objects. The end result tends to be a lot of small methods within the various classes. And the top level method either simply orchestrates the execution of the helper methods in the component classes or starts a cascade of method calls as each component does something then delegates to its components (this is usually how GUIs work). I suspect your surface model would be a candidate for the orchestration technique. I feel that, the best would be to strore 3 separate triangles for A,B,C points, Triangulation.Append(Triangle(A,B,C)) Triangulation.Append(Triangle(B,C,A)) Triangulation.Append(Triangle(C,A,B)) And register the topological relations after it. It could be OO, and simple. OO is usually simpler that traditiona;l procedural once you get the knack. Its because you delegate the functions to where the data is so all processing tends to be simplified. The big down side is that you can end up with very deep call stacks, but in practice this is rarely as big a problem as traditionalists expected when OOP was introduced. As I wrote, I made it in C with structures, so it wasn't OO, but fast. OO doesn't need to be slow, especially in C++ where some OOP programs have been shown to be faster than their non OOP equiva;lents. But in Python speed of execution is almost never the primary aim, fast enough and easy to build and maintain are the usual goals. Except now, when the algorithm based strongly on pointers and indeces :( Real low level pointer arithmetic can be tricky to convert pythonically but normal array indexing is nt usually an issue. Either a while loop or a for loop will do the job. But an OOP approach can often render both unnecessary, or at least greatly simplify things. HTH, -- Alan Gauld Author of the Learn to Program web site http://www.freenetpages.co.uk/hp/alan.gauld ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
