how to generate tessellation cells using the Poincare disk model?

I'm a computer programmer, and while I like math, this is an area where my understanding of math falls short of what I need in order to apply it successfully.

I've been looking at M.C. Escher's "Circle Limit" drawings, which use a Poincare disk model to illustrate tilings of the hyperbolic plane. What I want to do is generate the coordinates (in the Cartesian plane, for a graphics display) of vertices in such a tiling. But I'm not even sure where to start. It seems like I need two things:

1. a way to generate the coordinates in the hyperbolic plane, for each vertex of several cells (polygons) in such a tiling; and
2. the formula to convert those coordinates to the Cartesian plane, using the Poincare Disk model.

For example, in Circle Limit I, each fish seems equivalent to a quadrilateral (four other fish touch its edges), and each vertex is surrounded by either 4 or 6 fish. I don't need to generate fish, just quadrilaterals. But I don't know how to do it.

Do you know of software to do this? Or can someone help me with an algorithm?

I want to generate a finite area of the plane (of course?). If an algorithm could help me generate $k$ rings of cells around the origin, that would be most convenient.

Thanks for any suggestions.

P.S. I'd also be interested in hyperbolic tilings besides Escher's, e.g. http://en.wikipedia.org/wiki/Heptagonal_tiling

P.P.S. I just found some source code for drawing hyperbolic tilings (see bottom of the page), which includes generating locations of vertices. I can extract these vertex coordinates by putting in print statements. But they're grouped by line segment rather than by cell, and converting from the former to the latter does not seem easy.

Solution 1:

The most helpful solution I've found for my need -- cranking out the locations of vertices of each polygon -- is David Joyce's Hyperbolic Tessellations applet and its source code. This applet draws regular and quasiregular tessellations organized by polygons, so it's easy to put print statements into the update() method and output the locations of vertices of each polygon as the polygon is drawn. It's much less efficient than Hatch's code, but efficiency is not one of my requirements at this point. Clarity is much more important.

I found the explanations in Ajit Datar's master's thesis the most helpful for learning how the process of generating the tessellations works. There is also code that goes with it, which I have not yet looked at. Datar's program offers more flexibility than Joyce's applet: e.g. Datar's can build tessellations either with a polygon centered at the origin, or with a vertex at the origin; and can also tessellate "motifs" (polygons or polylines such as Escher's fish).