Following on from the post introducing this series, and the last post focused on generating simple hyperbolic geometry, this post looks at generating hyperbolic tessellations inside AutoCAD.
Having “borrowed” some C++ code, last time, today we’re going to borrow some Java. That’s one of the great things about the C family of languages: the relatively small amount of work that’s often needed to move code between environments. :-)
This article, written by David E. Joyce, Professor of Mathematics and Computer Science at Clark University, has provided the best information I could find with regards to a hyperbolic tiling algorithm (especially thanks to its posted source code).
The algorithm works by creating a central polygon of the specified number of sides, and then – based on the other primary parameter into the algorithm, the number of polygons that meet at each vertex – it mirrors this polygon again and again in the hyperbolic plane (which means it gets smaller and a bit squished as it gets mirrored out towards the edge of the circle) in order to make up our pattern. The number of mirroring operations – and the number of resultant polygons – will depend on the number of levels (or layers): 0 means we have just the central polygon, 1 means we have that plus the layer around it, etc.
The number of levels needed to effectively fill a circle depends on the resolution needed but also greatly on the pattern. Interestingly the more even patterns (such as 7-sided polygons meeting 3 per vertex) create fewer polygons per level, but need more levels to fill a circle adequately. The patterns with larger central polygons create many more polygons per level (which is probably not that surprising, thinking about it), and so need fewer levels to fill a circle.
Rather than ask the user for the number of levels, this implementation has a coded limit on the number of polygons (which, of course, could also be asked of the user, if needed). The code starts with a default level of 6 (which is pretty high for most patterns), but quickly reduces the level by one if it finds it would result in more than 1000 polygons being created. Once it has found a level number that creates a small enough of set of polygons, it goes ahead and uses that.
In addition to the HyperbolicEngine we saw in the last post, we’re now introducing a PolygonEngine to generate polygons for a particular pattern. Here’s the C# file:
using Autodesk.AutoCAD.Geometry;
using System;
namespace HyperbolicGeometry
{
public class Polygon
{
public Point2dCollection Vertices = new Point2dCollection();
}
public class PolygonEngine
{
// The list of polygons
Polygon[] _polys;
// Previously created neighbors for the polygons
int[] _rules;
// The total number of polygons in all the layers
int _totalPolygons;
// The number through one less layer
int _innerPolygons;
public Polygon[] GetPolygons(
int n, int k, ref int layNum, int max
)
{
do
{
CountPolygons(layNum, n, k, max);
if (_totalPolygons > max)
layNum--;
}
while (_totalPolygons > max);
DeterminePolygons(n, k);
return _polys;
}
private static Polygon ConstructCenterPolygon(int n, int k)
{
// Initialize P as the center polygon in an n-k regular tiling
// Let ABC be a triangle in a regular (n,k0-tiling, where
// A is the center of an n-gon (also center of the disk),
// B is a vertex of the n-gon, and
// C is the midpoint of a side of the n-gon adjacent to B
double angleA = Math.PI / n;
double angleB = Math.PI / k;
double angleC = Math.PI / 2.0;
// For a regular tiling, we need to compute the distance s
// from A to B
double sinA = Math.Sin(angleA);
double sinB = Math.Sin(angleB);
double s =
Math.Sin(angleC - angleB - angleA) /
Math.Sqrt(1.0 - sinB * sinB - sinA * sinA);
// Determine the coordinates of the n vertices of the n-gon.
// They're all at distance s from center of the Poincare disk
Polygon p = new Polygon();
for (int i = 0; i < n; ++i)
{
p.Vertices.Add(
new Point2d(
s * Math.Cos((3 + 2 * i) * angleA),
s * Math.Sin((3 + 2 * i) * angleA)
)
);
}
return p;
}
private void CountPolygons(int layer, int n, int k, int max)
{
// Determine
// totalPolygons: the number of polygons there are through
// that many layers
// innerPolygons: the number through one less layer
_totalPolygons = 1; // count the central polygon
_innerPolygons = 0;
int a = n * (k - 3); // polygons in 1st layer joined by vertex
int b = n; // polygons in 1st layer joined by edge
int next_a, next_b;
for (int l = 1; l <= layer; ++l)
{
_innerPolygons = _totalPolygons;
if (k == 3)
{
next_a = a + b;
next_b = (n - 6) * a + (n - 5) * b;
}
else
{ // k > 3
next_a =
((n - 2) * (k - 3) - 1) * a +
((n - 3) * (k - 3) - 1) * b;
next_b = (n - 2) * a + (n - 3) * b;
}
_totalPolygons += a + b;
// If we've reached our maximum threshold, just return,
// as we won't be using this layer, anyway
if (_totalPolygons > max)
break;
a = next_a;
b = next_b;
}
}
/* Rule codes
* 0: initial polygon. Needs neighbors on all n sides
* 1: polygon already has 2 neighbors, but one less
* around corner needed
* 2: polygon already has 2 neighbors
* 3: polygon already has 3 neighbors
* 4: polygon already has 4 neighbors
*/
private void DeterminePolygons(int n, int k)
{
_polys = new Polygon[_totalPolygons];
_rules = new int[_totalPolygons];
_polys[0] = ConstructCenterPolygon(n, k);
_rules[0] = 0;
int j = 1; // index of the next polygon to create
for (int i = 0; i < _innerPolygons; ++i)
{
j = ApplyRule(i, j, n, k);
}
}
private int ApplyRule(int i, int j, int n, int k)
{
int r = _rules[i];
bool special = (r == 1);
if (special) r = 2;
int start = (r == 4) ? 3 : 2;
int quantity = (k == 3 && r != 0) ? n - r - 1 : n - r;
for (int s = start; s < start + quantity; ++s)
{
// Create a polygon adjacent to P[i]
_polys[j] = CreateNextPolygon(_polys[i], s % n, n, k);
_rules[j] = (k == 3 && s == start && r != 0) ? 4 : 3;
j++;
int m;
if (special) m = 2;
else if (s == 2 && r != 0) m = 1;
else m = 0;
for (; m < k - 3; ++m)
{
// Create a polygon adjacent to P[j-1]
_polys[j] = CreateNextPolygon(_polys[j - 1], 1, n, k);
_rules[j] = (n == 3 && m == k - 4) ? 1 : 2;
j++;
}
}
return j;
}
// Reflect P thru the point or the side indicated by the side s
// to produce the resulting polygon Q
private Polygon CreateNextPolygon(
Polygon P, int s, int n, int k
)
{
Point2d start = P.Vertices[s],
end = P.Vertices[(s + 1) % n];
Polygon Q = new Polygon();
for (int i = 0; i < n; i++)
Q.Vertices.Add(Point2d.Origin);
for (int i = 0; i < n; ++i)
{
// Reflect P[i] thru C to get Q[j]}
int j = (n + s - i + 1) % n;
Q.Vertices[j] = Reflect(start, end, P.Vertices[i]);
}
return Q;
}
// Reflect the point R across the line through A to B
public Point2d Reflect(Point2d A, Point2d B, Point2d R)
{
// Find a unit vector D in the direction of the line
double den = A.X * B.Y - B.X * A.Y;
bool straight = Math.Abs(den) < Tolerance.Global.EqualPoint;
if (straight)
{
// The less interesting case - we could do this less
// manually using AcGe
Point2d P = A;
den =
Math.Sqrt(
(A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y)
);
Point2d D =
new Point2d(
(B.X - A.X) / den,
(B.Y - A.Y) / den
);
// Reflect method
double factor =
2.0 * ((R.X - P.X) * D.X + (R.Y - P.Y) * D.Y);
return
new Point2d(
2.0 * P.X + factor * D.X - R.X,
2.0 * P.Y + factor * D.Y - R.Y
);
}
else
{
// Find the center of the circle through these points
// (this is what we really need to use this for)
double s1 = (1.0 + A.X * A.X + A.Y * A.Y) / 2.0;
double s2 = (1.0 + B.X * B.X + B.Y * B.Y) / 2.0;
Point2d C =
new Point2d(
(s1 * B.Y - s2 * A.Y) / den,
(A.X * s2 - B.X * s1) / den
);
double r = Math.Sqrt(C.X * C.X + C.Y * C.Y - 1.0);
// Reflect method
double factor =
r * r / (
(R.X - C.X) * (R.X - C.X) + (R.Y - C.Y) * (R.Y - C.Y)
);
return
new Point2d(
C.X + factor * (R.X - C.X),
C.Y + factor * (R.Y - C.Y)
);
}
}
}
}
Here’s the updated command class that includes a new command, HT, to generate polygons for a hyperbolic tessellation with a given set of parameters:
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.Colors;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System;
namespace HyperbolicGeometry
{
public class Commands
{
[CommandMethod("HT")]
public static void CreateHyperbolicTiles()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;
PromptEntityOptions peo =
new PromptEntityOptions("\nSelect circle: ");
peo.AllowNone = true;
peo.SetRejectMessage("\nMust be a circle.");
peo.AddAllowedClass(typeof(Circle), false);
PromptEntityResult per = ed.GetEntity(peo);
if (per.Status != PromptStatus.OK &&
per.Status != PromptStatus.None
)
return;
int n, k;
bool done;
do
{
PromptIntegerOptions pio =
new PromptIntegerOptions(
"\nNumber of sides for polygons"
);
pio.AllowZero = false;
pio.AllowNegative = false;
pio.AllowNone = true;
pio.DefaultValue = 7;
pio.UseDefaultValue = true;
pio.LowerLimit = 3;
pio.UpperLimit = 20;
PromptIntegerResult pir = ed.GetInteger(pio);
if (pir.Status != PromptStatus.None &&
pir.Status != PromptStatus.OK)
return;
n = pio.DefaultValue;
if (pir.Status == PromptStatus.OK)
n = pir.Value;
pio.Message =
"\nNumber of polygons meeting at each vertex";
pio.DefaultValue = 3;
pir = ed.GetInteger(pio);
if (pir.Status != PromptStatus.None &&
pir.Status != PromptStatus.OK)
return;
k = pio.DefaultValue;
if (pir.Status == PromptStatus.OK)
k = pir.Value;
done = ((n - 2) * (k - 2) > 4);
if (!done)
{
ed.WriteMessage(
"\nPlease increase values for a successful tiling."
);
}
}
while (!done);
PromptKeywordOptions pko =
new PromptKeywordOptions(
"\nUse curved or straight segments"
);
pko.Keywords.Add("Curved");
pko.Keywords.Add("Straight");
pko.Keywords.Default = "Straight";
PromptResult pr = ed.GetKeywords(pko);
if (pr.Status != PromptStatus.Keyword &&
pr.Status != PromptStatus.OK)
return;
bool straight = pr.StringResult == "Straight";
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
Circle cir = null;
if (per.Status == PromptStatus.OK)
{
cir =
tr.GetObject(per.ObjectId, OpenMode.ForRead) as Circle;
}
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, cir, straight, ptLay, lnLay, htLay
);
PolygonEngine pe = new PolygonEngine();
if (cir == null)
{
he.DrawUnitCircle();
}
// We'll default to level 6, but this will get reduced
// if resulting in > 1000 polygons
int level = 6;
Polygon[] polys = pe.GetPolygons(n, k, ref level, 1000);
if (HostApplicationServices.Current.UserBreak())
return;
ed.WriteMessage(
"\n{{{0} {1}}} (level {2}) => {3} polygons.",
n, k, level, polys.Length
);
foreach (Polygon p in polys)
{
he.DrawPolygon(p.Vertices.ToArray());
p.Vertices.Clear();
p.Vertices.Capacity = 0;
}
tr.Commit();
}
}
[CommandMethod("HGT")]
public static void CreateHyperbolicTriangles()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, null, false, ptLay, lnLay, htLay
);
he.DrawUnitCircle();
he.DrawTriangle(
new Point2d(0.8, -0.3),
new Point2d(0.2, -0.6),
new Point2d(-0.61, -0.6),
true, true
);
tr.Commit();
}
}
[CommandMethod("HGS")]
public static void CreateHyperbolicSpiro()
{
Document doc =
Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Transaction tr =
doc.TransactionManager.StartTransaction();
using (tr)
{
LayerTable lt =
(LayerTable)tr.GetObject(
db.LayerTableId, OpenMode.ForWrite
);
// Points and supporting lines will be on layers that
// are grey and initially frozen
ObjectId ptLay = CreateLayer(tr, lt, "HG_PTS", 9, false);
ObjectId lnLay = CreateLayer(tr, lt, "HG_LNS", 9, false);
ObjectId htLay = CreateLayer(tr, lt, "HG_CNT", 6, true);
// Create our hyperbolic engine
HyperbolicEngine he =
new HyperbolicEngine(
tr, db, null, false, ptLay, lnLay, htLay
);
he.DrawUnitCircle();
int max = 13;
for (int k = 0; k < (max - 1); k++)
{
he.DrawTriangle(
new Point2d(1, 0),
new Point2d(
Math.Cos(k * 134 / (double)max),
Math.Sin(k * 134 / (double)max)
),
new Point2d(
Math.Cos((k + 1) * 134 / (double)max),
Math.Sin((k + 1) * 134 / (double)max)
),
true, true
);
}
tr.Commit();
}
}
private static ObjectId CreateLayer(
Transaction tr, LayerTable lt,
string lname, short col, bool on
)
{
if (lt.Has(lname))
return lt[lname];
LayerTableRecord ltr = new LayerTableRecord();
ltr.Color = Color.FromColorIndex(ColorMethod.ByAci, col);
ltr.Name = lname;
ltr.IsFrozen = !on;
ObjectId layId = lt.Add(ltr);
tr.AddNewlyCreatedDBObject(ltr, true);
return layId;
}
}
}
When we run the HT command we have a number of options. We can either select a circle to fill, or hit Enter to have it create a standard circle at the origin, and then are asked to enter the number of sides of the polygons, the number meeting at each vertex, and the number of levels. We’re also asked whether to straight or curved segments (and it’s in the case of curved segments that the code we showed in the last post gets exercised).
Let’s see the results of running the HT command with the default option values selected:
Command: HT
Select circle:
Number of sides for polygons <7>:
Number of polygons meeting at each vertex <3>:
Use curved or straight segments [Curved/Straight] <Straight>:
{7 3} (level 5) => 617 polygons.
We can see that our {7 3} tessellation has resulted in 617 polygons being created. The various patterns generated by this algorithm have a single, central polygon. Other algorithms can also generate a group of polygons centered on the circle – this shouldn’t be overly difficult to implement, but has been left as an exercise for the engaged reader. :-)
Just to see, we can try the same operation with curved segments instead of straight, which will exercise the code in the last post but not actually make a very noticeable difference to the results (the resultant arcs mostly have very low curvature).
I’ll follow up with one more post in this series, to script the HT command to create a varied range of the patterns that can be created with the current implementation.
Also, if people are interested in thinking about how this might be taken to the next dimension (i.e. 3D), then this document should be interesting: it even looks at the possibilities around printing 3D hyperbolic tessellations, although it tends to do so more from an artistic – rather than structural – perspective.
