Wednesday, December 4, 2013

Ubuntu Precise, QGIS, GRASS and r.denoise

If you are interested in making your own shaded relief in QGIS, you may want to know about a GRASS module called r.denoise.

r.denoise (as explained more at length here), removes the random noise from a digital elevation model. As a result, when you generate a shaded relief image from the DEM it doesn't show as many small texture features.

Shaded relief of a portion of Canadian topographic map 093L14 (Smithers) generated with GRASS's module r.shaded.relief. At left, shaded relief from regular CDED DEM, and, at right, from CDED DEM denoised with r.denoise. Denoising parameters in this case were 5 iterations at a tolerance of 0.93.
The trick is that, although under Ubuntu Precise it's easy to install QGIS and GRASS (packages qgis and qgis-plugin-grass), r.denoise is not a standard module in GRASS. It's an addon. There are many wonderful GRASS addons (see a list here), but installing a GRASS addon when you did not compile GRASS yourself (i.e., you installed it through a precompiled package, as one tends to do under Ubuntu), requires a few extra steps. It can be done, however!

I recently struggled through installing r.denoise, and I was unable to find complete instructions on the web, so I thought I would explain here how I did it.

I'll assume that you are running Ubuntu Precise, and that you already have QGIS 2 and the GRASS plugin installed, and that you know how to use them.

Preparation

There are four things you will need before you can install r.denoise:
  • package grass-dev (which will in turn require package grass)
  • package subversion
  • the mdenoise utility
  • a patch in a makefile that comes as part of grass-dev (apparently you will not need this if you have grass version >=6.4.2, but at this point Ubuntu has 6.4.1)
Phase 1: The packages grass-dev and subversion you can install through the synaptic package manager.

Phase 2: To install mdenoise,
  1. go to the Cardiff University site on the Filtering and Processing of Irregular Meshes with Uncertainties  and downlaod mdsource.zip
  2. unzip it into a temporary folder, e.g., on your desktop
  3. open a terminal in that folder and compile mdenoise with:
  4. $ g++ -o mdenoise mdenoise.cpp triangle.c
  5. move (as root or using sudo)  the new file that appears, "mdenoise," into /usr/bin:
$ sudo mv mdenoise /usr/bin/

Phase 3: to patch Platform.make file in /usr/lib/grass64/include/Make, run the following command:

$ sudo sed -i -e 's+^\(GRASS_HOME[ ]*=\) /build/.*+\1 ${INST_DIR}+' \
-e 's+^\(RUN_GISBASE[ ]*=\) /build/.*+\1 ${INST_DIR}+' \
/usr/lib/grass64/include/Make/Platform.make
 
OK, now you're ready to install the addon r.denoise.

Installing r.denoise itself

1. Start QGIS and make sure the GRASS plugin in loaded. If you haven't already discovered it, the GRASS menu is under the "Plugins" menu.

2. Open a GRASS mapset, so that the GRASS toolbox will be available: Plugins>GRASS>Open mapset, or the corresponding button on the GRASS toolbar. (If you need to create a GRASS mapset first, a set of getting-started-with-GRASS instructions are here.)

3. Open the GRASS Tools: Plugins>GRASS>Open GRASS Tools, or the corresponding button on the GRASS toolbar.

4. Open a GRASS shell. You can find this at the top of the Modules Tree ("Modules Tree " tab), or search for it ("shell") on the Modules List tab. A GRASS shell opens as a fourth tab in the GRASS window. In this shell window, Ctrl-Shift-C and Ctrl-Shft-V act as Copy and Paste, just as in a regular terminal window.

5. In the GRASS shell, type:
$ g.extension extension=r.denoise svnurl=http://svn.osgeo.org/grass/grass-addons/grass6/
This will launch a process of downloading the source code for the addon via subversion, compiling it, and then installing the executable.

Unfortunately, if you're like me, you will get this:

Fetching from GRASS-Addons SVN (be patient)...
A    r.denoise/description.html
A    r.denoise/r.denoise
A    r.denoise/Makefile
 U   r.denoise
Checked out revision 58345.
Compiling ...
mkdir -p /usr/lib/grass64/bin.x86_64-pc-linux-gnu
mkdir: cannot create directory `/usr/lib/grass64/bin.x86_64-pc-linux-gnu': Permission denied
make: *** [/usr/lib/grass64/bin.x86_64-pc-linux-gnu] Error 1
ERROR: Compilation failed, sorry. Please check above error messages.

In short, GRASS does not have permission to create this directory it wants (/usr/lib/grass64/bin.x86_64-pc-linux-gnu). I tried a number of workarounds. Running GRASS as root does not help. Attempting to 'sudo' this g.extension command does not work. Finally, I simply created the directory myself from within the GRASS shell by typing:

 $ sudo mkdir /usr/lib/grass64/bin.x86_64-pc-linux-gnu

I know this looks an ugly and desperate act, but it leads to success just down the road, so bear with me.


Note that all I had to do was copy the mkdir line from the output above (with Ctrl-Shift-C), paste it in as the next command (Ctrl-Shift-V), hit the Home key to jump to the front of the command line, type 'sudo' and hit Enter.

Now run the g.extension command again (tap up-arrow until it reappears as you entered it before), and get a similar error for another directory it can't create:

Fetching from GRASS-Addons SVN (be patient)...
A    r.denoise/description.html
A    r.denoise/r.denoise
A    r.denoise/Makefile
 U   r.denoise
Checked out revision 58345.
Compiling ...
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/include/grass
mkdir: cannot create directory `/usr/lib/grass64/dist.x86_64-pc-linux-gnu': Permission denied
make: *** [/usr/lib/grass64/dist.x86_64-pc-linux-gnu/include/grass] Error 1
ERROR: Compilation failed, sorry. Please check above error messages.

Repeat the process of creating the new subdir by hand.

$ sudo mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/include/grass

However, this time change the permissions to world-writeable on this new subdir. g.extension is going to want to create six more sub-directories under it, so this will save you significant time:
$ sudo chmod -R 777 /usr/lib/grass64/dist.x86_64-pc-linux-gnu/

Running the g.extension command a third time you will now get a long output:

Fetching from GRASS-Addons SVN (be patient)...
A    r.denoise/description.html
A    r.denoise/r.denoise
A    r.denoise/Makefile
 U   r.denoise
Checked out revision 58345.
Compiling ...
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/lib
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/bin
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/etc
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/driver
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/driver/db
mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/fonts
if [ ! -d /usr/lib/grass64/dist.x86_64-pc-linux-gnu/scripts ]; then mkdir -p /usr/lib/grass64/dist.x86_64-pc-linux-gnu/scripts; fi
/usr/bin/install -c  r.denoise /usr/lib/grass64/dist.x86_64-pc-linux-gnu/scripts/r.denoise
make htmlscript scriptstrings
[...and a whole lot of other stuff, including errors...]

This is good news: your script has been created and it's at /usr/lib/grass64/dist.x86_64-pc-linux-gnu/scripts/r.denoise. (Note: we're not going to get the documentation for the module. That's what all the final errors are about. Haven't been able to solve this part yet.)


As a final step, it's up to you (using sudo) to move it to /usr/lib/grass64/scripts:

$ sudo mv /usr/lib/grass64/dist.x86_64-pc-linux-gnu/scripts/r.denoise /usr/lib/grass64/scripts/

Make sure it's executable, and if it's not you can make it that way with

$ sudo chmod +x /usr/lib/grass64/scripts/r.denoise

r.denoise is now accessible to you through the GRASS shell by typing:
$ r.denoise

It'll open a nice little GUI and let you get started denoising.


One final note, probably unnecessary to seasoned GRASS users. When r.denoise asks you for a raster input map, you can pick from the current mapset using the dropdown. It'll insert the name of the map with an @ sign and then the mapset name, something like "mymap@mymapset". But when it asks for "Denoised raster output map," put in a new filename without the "@mymapset".

Happy denoising!





Friday, November 22, 2013

Galera Division

Galera division is a technique used in the late Medieval and early Renaissance periods in southern Europe. It was a technique of the abbaco schools, popular schools of reckoning that developed to serve the needs of merchants and navigators. For more about abbaco schools I would recommend two excellent articles in Loci: Randy Schwartz's article on the Pamiers Manuscript, and William Branson's article on solving a cubic equation the way Girolamo Cardano would have done it in the 1500s.


For a bit of background, you must understand that the people doing arithmetic at this time (the 1300s and 1400s) were doing so without the equals sign (=), the plus sign (+), the minus sign (-),  the multiplication sign (x), the division sign (\(\div\)) or the decimal point (.). These were all yet to be invented! Problems were expressed in words. Numbers that were not whole numbers were always expressed in fractions.  (It's somehow comforting to know that they already did use the fraction notation we  use today, a numerator and denominator separated by a bar).  Money and weights involved complex non-decimal fractions, like 24 grossi to a ducat and 32 pizoli to the grosso (Venetian coinage), or 12 ounces to the pound and 6 sazi to the ounce.

For example, here's a problem from the Treviso Arithmetic, a how-to manual of arithmetic written in 1478 in Venetian (rather than Latin -- indicating to us that it was intended for a wide audience outside of universities):

Se lire.100.e \(\frac{1}{4}\) de seda valisseno ducati 42 g 2.e\(\frac{1}{5}\) che valerano lire 9816 onze.3.e \(\frac{1}{6}\)[F. 36, v.] 

If 100 and \(\frac{1}{4}\) pounds of silk are valued at 42 ducats, 7 and \(\frac{1}{5}\) grossi, what will 9816 pounds, 3 and \(\frac{1}{6}\) ounces be valued at?

But reckoners had tools to navigate these complicated numbers and get the right results. They were not afraid of big numbers, and indeed they regularly did calculations that would choke a modern hand calculator. Here's the author of the Treviso Arithmetic dividing 12,030 into 14,350,278,384 in the process of showing us how to solve the problem above.

Treviso Arithmetic, 1478, F. 38, r.


It's called galera division because the mass of cancelled digits that proliferates above and below the dividend and divisor in the completed problem resembles a galley (galera) sailing directly at you: narrowing to the waterline below, narrowing to the top sails above. In the Treviso Arithmetic it is called batello or "boat" division.

As Frank Swetz points out in his book Capitalism and Arithmetic, galera division had the advantage, in an age when paper was expensive, of filling a smaller, more compact space on paper than our modern long division technique would.


1607 divided by 42: long division (left) and galera division (right)

Galera is intriguing because it's a lost technique used by people centuries ago, but it's also worth noting that it involves acts of multiplication and subtraction that are frequently smaller than those you'll do in long division. In long division, one multiplies the new quotient digit by the whole divisor, and then subtracts the result, however big it is, from the relevant part of the dividend. In galera division, as I'll show below, one multiplies the new quotient digit by each digit of the divisor in turn, subtracting these smaller results individually from the relevant piece of the dividend above.

Galera division can get away with this because its process is one of constantly adjusting the dividend, crossing out digits and replacing them with others. So, to know your way around a galera division problem, notice that at any given time the current dividend can be assembled from the uncrossed-out digits at the tops of the columns of figures. Similarly, the divisor is crossed out and re-written at the bottom of the columns. Learn to find these with your eye, and you'll be looking at the problem the way a galera divider did.

At this stage in the problem the dividend is 347.


So let's get started. We'll divide 42 into 1607.

Setup

Write the divisor under the dividend, much like a fraction, and place a vertical bar to the right of them.  Align them so that the first digits of the divisor go into the first digits of the dividend. 


Let's say however that the problem was 38 into 699. We would observe that 38 is less than 69 – it can go into it –  so it would be lined up like this:

When the first digits of the dividend and divisor are the same, you have to look at the next digit. So, 18 into 1274 would be aligned like this:

Now, back to dividing 42 into 1607.

Step 1

Consider how many times the divisor (42) will go into just those digits of the dividend that are immediately above and to the left of it (160).  The answer is 3 times, so write a 3 to the right of the vertical line. This is the beginning of the quotient.

Step 2

Multiply this new quotient digit by the leftmost, that is, most significant, digit in the divisor, and hold that number in your head. (3 times 4 makes 12. Hold 12 in your head.)   Strike out the portion of the dividend that is above and to the left of this leftmost divisor digit (16), and over it write the difference between it and the number in your head (12 from 16 leaves 4). Also strike out leftmost digit of the divisor (4), to indicate we've “used” it.

(Notice that the dividend has been changed now 407, but not all the digits are on the same line.)

Step 3

Now multiply the new quotient digit by the next most significant digit of the divisor, and hold that number in your head. (3 times 2 makes 6. Hold 6 in your head.)  Strike out the portion of the dividend that is above and to the left of this digit of the divisor (40), and over it write the difference between it and the number in your head (6 from 40 leaves 34). Also strike out this digit of the divisor (2), to indicate we've “used” it. (The dividend is now 347, with all three digits on different lines.)

Step 4

Write in a fresh copy of the divisor, but shifted one column right. (The 4 will go under the original 2, and the 2 will go to the left of the original 2.)

Now we're ready to guess the next digit of the quotient, and repeat those four steps again.

Step 1

Consider how many times the divisor (42) will go into just those digits of the dividend that are immediately above and to the left of it (347).  The answer is 8 times, so write an 8 to the right of the vertical line.

Step 2

Multiply this new quotient digit by the leftmost, that is, most significant, digit in the divisor, and hold that number in your head. (8 times 4 makes 32. Hold 32 in your head.)  Strike out the portion of the dividend that is above and to the left of this leftmost digit of the divisor (34), and over it write the difference between it and the number in your head (32 from 34 leaves 2). Also strike out leftmost digit of the divisor (4), to indicate we've “used” it. (Notice that the dividend has been changed now to 27, but not all the digits are on the same line.)

Step 3

Now multiply the new quotient digit by the next most significant digit of the divisor, and hold that number in your head. (8 times 2 makes 16. Hold 16 in your head.)  Strike out the portion of the dividend that is above and to the left of this digit of the divisor (27), and over it write the difference between it and the number in your head (16 from 27 makes 11). Also strike out this digit of the divisor (2), to indicate we've “used” it. (The dividend is now 11, with digits on different lines.)

We can't move the divisor any further right, so we're done.  We don't have to write the divisor again. The answer is 38 with a remainder of 11. Done!

10's-complement Subtraction

In doing that galera division we performed a lot of subtraction. It's easy to assume that people in the 1400s did subtraction as we do today, but they did not!  In the Treviso Arithmetic, subtraction did not employ the "borrowing" method we use, but used a technique we can call 10's-complement subtraction.

Today, when faced with subtracting a larger digit from a smaller digit, we "borrow." Let's say we are subtracting 16 from 41. We begin with the one's place, and faced with taking 6 from 1 we "borrow" from the ten's place to make 11, decrement the 4 to a 3, take 6 from 11 to get 5, and then move on.

In 10's-complement subtraction you also begin with the one's place, but faced with taking 6 from 1, you pause and note the 10's complement of 6, that is, the number you would add to 6 to get 10. It's 4.

This 4 you add to the number above that you were trying to subtract 6 from. Four plus 1 is 5, so you write a 5 below the line as your answer digit for this column. (Note that this means you don't have to have memorized the subtraction tables for numbers larger than 9!)

Finally, instead of decrementing the next digit of the minuend (upper number), we add one to the next digit of the subtrahend (the lower number). Same result.



Wednesday, September 18, 2013

Quick and Dirty Mapping with Geographic Data

Barely a day goes by without seeing a map on the web. And the more eye-catching maps are usually fairly involved productions. Consider, for example, Bomb Sight, or the World Water Risk Atlas.  These maps can be quite beautiful, and offer all sorts of capabilities to explore data. But they aren't the kind of mapping I want to talk about here.

I'm interested in a much lower-end question: what can a person do to quickly post his or her geographic data onto a map? Let's say I have a couple of KML files (or GPX, or shapefiles... we'll get to discussing formats in a bit): if I just need to visualize them, what's my best place to go? Let's say that I'm not making a presentation and I don't need to be able to share the data, or let others edit it. Nor do I need visitors to be able to draw on the map.

For the moment I'll also assume that I don't even want to be able to customize how the data looks, or be able to direct others to this quick and dirty map. I'll cover that in a later post.

The user should not have to know anything about the world of GIS. He or she should not have to re-project the data, or convert formats. There shouldn't be a need to understand map projections. There is a broad range of people who receive data -- maybe it's downloaded from the web, handed over by a collaborator, sent by a friend or produced by the company -- and they just want to see it.

GPSVisualizer

GPSVisualizer is probably your best single bet for a quick and dirty map, whether your geographic data is KML, KMZ, CSV or XLS.



On the home page, where it says "Get started now," browse for your data file and click "Go!"
You'll get a small inset map of your data over a Google maps background. If your data included lines, these are summarized in the box in the upper right side of the map.

There are several nice features available to you now:
  • With one click you can go to a full page view of your map. (Click on "view" in the fine print at the top where it says your map is "also temporarily available to view.")
  • You can click on your points or lines and see the data embedded within them.
  • You can change the background of your map, with over 20 backgrounds to choose from. These include Yahoo maps, OpenStreet map, and topographic maps for the US and Canada
  • You can copy that address for the full-page view of your map and send it to others to visit -- at least for a few hours. (GPSVisualizer says the map is there "temporarily". It's probably good for the rest of the day unless use of the site is heavy.)
If you go back a page, back to that "Get started now" box, you can re-generate the map and, instead of getting a Google maps mash-up, receive:
  • a Google Earth (KMZ) version of your data
  • a JPEG image
  • a PNG image
  • an SVG image
  • an elevation profile
  • a GPX version of your data
  • a plain-text
Nice. Simple. Effective.

Hillmap

If the data you have is in the GPX format, GPSVisualizer will still work just fine. (GPX is a format that usually comes out of GPS devices, or software people use to manage their GPSs.) However if you have GPX data, in many ways Hillmap is a more delightful site, and even easier to use.



With Hillmap, you can drag and drop that GPX file right onto either of their double maps. It will upload the file and move the map to view your data. By default the maps a show "map" and "satellite" views, but there are 14 different backgrounds to choose from.
Now you can:
  • Switch to the Input and Output tab, and use the Link To button to get a link to this map, or an iframe tag to paste into a blog post (example below). (Note: set you preferred background before you get the link or iframe code.)
  • Also on the Input and Output tab, you can print your map. 
Hillmap is very clever: they've thought about how awkward most things printed out of web browsers look, and they've created an interface where you can get a decent looking map. You choose the dimensions of the printed map you want, and the dpi. It will then tell you what scaling to apply when sending it to the printer, and open a new tab with just the map image on it.
In Firefox, for example, you go File - Print Preview, set the scale to the given percentage, and hit Print. Very nice results, and, as a real bonus, it has a scale bar on it!


A short digression on formats

There are six common formats that geographic data comes in:
  • KML This is the original Google Earth data format. (KML stands for "Keyhole Markup Language".) You might have a KML file if you drew some points, lines or areas in Google Earth. Or you might have downloaded a KML file from the web. KML files can contain points, lines and areas.
  • KMZ This is a zipped version of KML.
  • GPX  A format for sharing data among GPSs, as discussed above. GPX files can contain points (which they call "waypoints") and lines (which they call "tracks").
  • shapefile This is a format originally created by a company called ESRI, but now used by most GIS software. It's common in academic and scientific circles. Note that a "shapefile" is actually a set of four files. These files all share the same name but have different extensions, like trail.shp, trail.dbx, trail.shx, and trail.prj. When sites ask you to upload a shapefile, they usually want you to zip the four files together into a .ZIP file first. A shapefile can only contain one kind of data: points, lines OR areas.
  • CSV or "Comma Separated Values." This is a plain text file with columns of data separated by, well, commas. Other variants of this format use tabs or semicolons to separate the fields. These files are generated by spreadsheet programs like Excel or OpenOffice Calc, and they can be displayed by those programs. When a CSV file contains geographic data it typically has columns named latitude and longitude. (It's also possible that instead the columns are northing and easting. This means the data is in a UTM projection, which I won't go into that here.) CSV data is usually just the locations of points.
  • XLS Microsoft Excel's spreadsheet format. Like CSV data, it will have latitude and longitude columns, and represent the locations of points.
There are also more obscure ones, like GeoRSS, GeoJSON, and GML, but if you have data in one of those formats you're probably beyond the scope of this post already.

CartoDB 

The format we haven't covered yet is shapefile. If you have this kind of data, neither of the two sites above will work, but CartoDB will. 

Like other sites that can accept shapefiles (such as ArcGIS Online and GeoCommons), CartoDB requires you to get a free account and insists that data you upload be publicly discoverable by other users. But it is simpler and more intuitive than those other services.  

Do note the limitations of the free CartoDB account. It will only let you have five uploaded shapefiles (which it calls "tables") at once, 5 MB of data total, and ten thousand views of your map. For our purposes this is not particularly onerous, but note that because a single shapefile can only hold a single kind of geographic data (points, lines or areas), you will be uploading more than one shapefile if, for example, you have both line and points to view.

Once you have your free account, log in and upload your shapefile by clicking on the large "New Table" button with the plus sign on it. Click select a file, locate your zipped shapefile, and when the progress bar finishes you're looking at a table of data for the geographic objects in your shapefile. Click on Map View. and you see the map. From upload to map is pretty fast.


Notice that you can change among the seven background maps (Nokia Day;  Google terrain, roads, satellite, hybrid, grey roadmap, or dark).

If you click on one of your features  you don't see the data yet, but a select fields link is offered, which pulls a set of toggle switches out from the right side of the map. Toggle "on" all the fields you want to see displayed.

To add a second shapefile to the map, you have to first convert it to a "Visualization." (Use the "Visualize" button in the upper right.) Once you give your visualization a name, the Visualize button becomes a "Publish" button. Right below it is a small "+" button which will allow you to add another shapefile (that you've already uploaded) to the map.

Next post: websites of choice for quick styling and sharing of maps.

 

Saturday, September 14, 2013

A Geometry Puzzle: Alternating Hexagons and Squares In a Ring


Background

This intriguing pattern is an alternating sequence of six hexagons and six squares. Both basic shapes have the same edge length, and they pack perfectly around a centre.

Furthermore, this fairly complex construction can be done with only a ruler and straightedge. Typically, you start with a circle, within which you construct what will be the dodecagonal centre of the figure above. The alternating hexagons and squares then sit on the sides of this dodecagon.

Because we will have to create other hexagons along the way, I'll call the hexagons in the final pattern around the outside ring hexagons.

The construction goes like this. (I will assume you know how to construct a hexagon within a circle, and how to bisect a line segment.)
1. Draw a circle.

2. Construct a hexagon within it.
3. Bisect one of the sides of the hexagon and draw a ray from the circle's centre through it. Construct another hexagon beginning with a vertex that falls where this ray intersects the circle.
4. Connect the successive vertices of the two hexagons to make a dodecagon, a 12-sided regular polygon.
5. Using the side length of the dodecagon as radius, draw circles around each vertex of the dodecagon.
6. Using every other intersection of these circles as a centre, draw six more circles of the same radius.
7. Construct hexagons within these last six circles. One side of each will coincide with a side of the dodecagon.
8. Connect hexagons to form squares.
9. The final figure without the construction lines. Rotating it 15° counterclockwise will make it look like the one at the very top of the post.

The Puzzle

OK, now for the puzzle. If we connect the centres of the six hexagons in the ring, we get another, larger hexagon.

This hexagon, which I'll call the master hexagon, can be used as the repeating frame for tiling a larger area with the pattern.

But if you were to do this, you would draw the pattern of master hexagons first, and would then construct the ring pattern based on it.

So here's the puzzle: how do you construct the ring pattern of hexagons and squares, given only the master hexagon?

Solution

The basic problem is to locate the dodecagon that forms the inside of the ring. Once we have that, we can construct  the ring, as above. But how do we get from the master hexagon to the dodecagon? 
10. Begin with the master hexagon.
11. Locate its centre by connecting vertices, and construct the circumscribing circle.
12. Bisect one side of the hexagon, and construct a second hexagon, much as you did in step 3 above, starting from the point where this bisector meets the circle.
13. Connect vertices of one hexagon to make a six pointed star.
14. Connect the vertices of the other hexagon in a similar fashion.
15. Connect the intersections of those two six-pointed stars, to make a dodecagon. This is the dodecagon that will form the inside of the ring.
16. Using steps 5, 6 and 7 above, construct ring hexagons from the sides of the dodecagon.
17. And, as in step 8 above, connect the ring hexagons to form squares.
It's interesting to compare the construction lines one uses when beginning with a circle to those drawn when beginning with the master hexagon.
18. "Forward" construction lines (that is, those beginning from the circle that circumscribes the dodecagon) are black. "Reverse" construction lines (beginning with the master hexagon) are blue.

Commentary

Why does using this method to construct the dodecagon within the master hexagon work?

Well, we know the master hexagon has a concentric dodecagon within it somewhere. But which dodecagon?

Because each dodecagon has a different edge length, each implies a different size of hexagons arrayed around it. We want the dodecagon where the hexagon's centre will fall at a vertex of the master hexagon (the red one, below, in this case).


The "right" dodecagon will have vertices that are 60° apart when viewed from a vertex of the master hexagon. Necessarily then, these dodecagon vertices will fall somewhere on the sides of equilateral triangles drawn within the master hexagon.
Drawing the other equilateral triangle within this hexagon gives us a general idea of where these dodecagon vertices will fall, but nothing precise. As well, this pattern so far only has 6-fold rotational symmetry.
If we add another master hexagon, rotated 15°, and its inner triangles, we get a pattern with the necessary 12-fold rotational symmetry.

The set of four equilateral triangles has 3 sets of common intersections, all of which will make dodecagons (red, orange and yellow, below). But only the outermost set (red) creates dodecagon sides that subtend a 60° angle when viewed from the vertices of the master hexagon.