Eric Broug in his book Islamic Geometric Patterns gives straightedge and compass construction of some simpler patterns. It is clear his techniques will provide constructions for many Islamic patterns.
Looking at formal constructibility, the Wikipedia pages gives Gauss' result that 7, 9, 11, 13, 14, 18... etc sided polygons are not constructible. Hence the pattern
is not constructible since it contains a regular 9-pointed star polygon.
I have over 800 Islamic patterns on my web site but I use a computer and trigonometry to produce my images. It seems that about 40 Islamic patterns on my site are not constructible.
Given an Islamic pattern that is not excluded from construction by Gauss' result, it is almost certainly constructible if the following is true:
Given two points on the plane, a polygon ($n$ sides) can be constructed with the two points as an edge, provided $n$ is not equal to 7, 9, 11, 13, 14, 18... etc.
This result would allow patterns to be built up piece-by-piece.
EDIT, Will Jagy: from his profile page, the OP's website, in this address preset to display the tilings in a slideshow format on a web browser, is at