Tessellate a Polygon-with-hole without tessellating a polygon-with-hole

So there is a problem of geometry…. how do you “do stuff” with a polygon? For example – cover it with triangles?

This is in general called ‘tessellation’ or ’tiling’, although we dont necessarily need “regular” tilings here in computer-mathistan and in specific called “tessellating with triangles” or ‘triangulation’.

So. By googling those words and ‘algorithm’ and ‘C++’ or ‘python’ you can find algorithms that do this sort of thing.

However, that answer is not so simple. First, one must ask, (as questions tend to be the beginning of many fruitful endeavors), what is a polygon?

Is this a polygon?

8

Is this a polygon?7

What about this?

6

And this?

5

The answer, in the end, can be all sorts of bizarre things. When you want to ‘triangulate’ a polygon, though, many a good, free algorithm out there stops at the simplest sorts of polygons. In fact, they tend to call these types of polygons ‘Simple’ polygons.

That is, Polygons that dont have edges overlapping, intersecting, self-touching, etc etc etc. Also, Simple Polygons don’t tend to have holes.

And that is where this blog post begins.

—————

Consider the polygon with one hole.

Consider an algorithm that can cover with triangles a simple polygon, with no holes.

Can the algorithm be used on the polygon with one hole? How?

The answer is yes, it can! There are many ways. Let us use an example.

2

A first, simple way is this:

Break up the polygon-with-hole into two separate polygons, each of which does not have a hole.

9

Now, triangulate each one, and then combine them back together. Tada! A triangulated polygon-with-hole.

1

 

OK. Not bad. And there is another way. It’s called by various names, including the “keyhole” method of making a ‘keyhole’ polygon. You basically take the polygon-with-hole, then pretend you slice down from the top of the polygon into the hole, straight down.

11

Now, you still have ‘one’ polygon, it’s just that one of its edges touches another one of it’s edges …. that’s what your knife kerf represents. Those two touching edges.

You can then pass this polygon to some of the triangulation algorithms and, tada, you have covered the original polygon-with-hole with triangles.

12

OK.

But then there is a funky method. It’s probably already been discovered but I don’t know what to call it.

————————

The idea is that you ‘project’ the polygon-with-hole onto a 3d object so that it no longer has a hole. For example, the ’round’ part of a cylinder. Then you do the tessellation within the ‘geometry’ of the three-d object. Then, you ‘un project’ the triangles back down to your original shape. Tada!

But how does it work? What is all this? Well, imagine what they have to do to perform triangulations in hyperbolic geometry. They do it somehow, right? There are entire books filled with tessellations in hyperbolic geometry.

But what is hyperbolic geometry? It can be seen as an ‘alternative 2d universe’, sort of like the book Flatland, but the 2d-universe is within a 3d hyperbola shape.

And you can, imagine, that you ‘project’ triangles down from the hyperbolic space down to 2d-space. If you want. It’s sort of how MC Escher did his paintings of hyperbolic tessellations. You can see Norman Wildberger describing this on his awesome youtube channel, here

Wikipedia has a nice page:

http://en.wikipedia.org/wiki/Uniform_tilings_in_hyperbolic_plane

Uniform tiling 63-t2.png

Uniform tiling 37-t0.png

 

 

So that’s sort of what I’m describing here. But imagine that instead of starting in the hyperbolic plane, tessellating, and projecting down, instead we start out in the ‘normal’ plane, project some shape up to the hyperbola (or cylinder, or whatever), THEN do the tessellation,and THEN project back down to the normal plane where we started.

FOR example:

Consider this polygon-with-hole. It’s a rectangle, abcd, and then a hole in the middle, efg.

2

Now, let’s pretend we are playing Graph Theory. In the Graph Theory game, you call points “vertexes” and you call the lines between the points “edges”. So we have points and edges. A-C is an edge, C-D is an edge, and so on.

Now let’s take our shape twist and wrap it around a cylinder. Like it was pizza dough or something.

4

OK. So why did we play in graph theory? To see that our ‘polygon’ that has been stretched around this cylinder, is still the same good old polygon. It’s got the same number of points, and the same edges. The edges are just funny looking because now they are curves instead of straight lines, at least to us looking on the Cylinder-Land from the outside.

This is where the imagination comes in. Imagine the cylinder is a world of it’s own. There are people living there. In fact, Imagine the Science Fiction theme called the O’Neill Cylinder

Image: Rick Guidice, NASA Ames Research Center; color-corrector unknown, via Wikipedia

To tiny ants living on the cylinder wall, it looks flat enough. If you made it big enough, even the people living on the cylinder wall would think roads looked flat. Just like on Earth we see roads and they look flat.

(Photo: User SriMesh from Wikimedia Commons)

 

Now, let’s triangulate the polygon that forms the ’round’ face of the cylinder

3

Note that in our ‘cylindrical’ geometry here, the ‘lines’ between triangles are actually ‘curves’ viewed from our 3d alien being perspective. But for the creatures living on Cylinder World, the lines are pretty much ‘straight looking’ enough.

Now, if we again pretend we are playing Graph Theory, we don’t even care. We are making ‘Edges’, which are essentially just connections between points. We don’t even care what shape the ‘edges’ are.

 

OK. So. Now we have triangulated our cylindrical polygon-with-no-hole

How do we get it back to the ‘Flatland’, of the normal 2d plane? We ‘unproject’ it down.

1

Yay!

But what’s this? We also have the edges of the ‘triangulation’ recorded…. there’s F-D, F-C, G-C, etc etc etc. They are all there!

Wait… so we actually just created a triangulation of the polygon-with-hole, without actually having to deal with the hole itself in the triangulation algorithm! All we had to do was get a triangulation algorithm that works on a Simple Polygon in Cylindrical Geometry.

Wow. Weird. Cool?

Useful? I don’t know. Probably not. But it seems interesting.

 

Advertisements

About donbright

don bright http://github.com/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s