# Tree Search documentation

## Introduction

The basic concept is very simple: just answer a number of question about the pattern you wish to locate and you will be presented with a small number of patterns satisfying those criteria from which you can see if the pattern is in the collection.
If you make a mistake, then you will be lead along the wrong set of questions so that you will not find the pattern you are after. There are a number of mistakes which are easy to make, but this documentation should enable you to use the tree search effectively.

The patterns themselves usually appear coloured, but the colour is ignored as is how the lines appear - they could be thick or thin or with interlacing which goes up and down at cross-over points.

## Basic method

A simple example of a page in the tree search is when only two options are offerred.
For instance, a pattern may or may not have a line of reflection. In this case, examples will be shown with a line of reflection with a link to the next page. Similarly, examples with be shown without a line of reflection, with another link to a subsequent page.
Many selection points are more complex with more than just yes/no for a characteristic of a pattern. In such cases, it is important to consider the cases on offer in the order presented and to take to first one which is satisfied by the pattern being searched for.
(If you do make a mistake, the selection can be considered again by using the link at the bottom of the page to go back a step.)

## Searching issues

When using the tree search, some problems may arise which are addressed here. Some specific terms are used which may not be familiar to you.
### Repeat pattern

By this term, we mean that there is a rectangular area which is repeated in the obvious way to fill any desired area. Such patterns are shown here with a repeating rectangle a bit smaller that the displayed area. There is a compromise in the area displayed which implies that some detail will only be visible by selecting the high-quality image (rather than the smaller bit-map).
It has been shown that repeat patterns are one of 17 types, but you do not need to know about this.

### Kites

A kite is a four-sided polygon whose edge lengths in cyclic order are AABB, where A and B are not equal. (If they were equal, the four-sided polygon would be a diamond (or a square) which are treated differently by the system.)
Kites appear many times in Islamic patterns and therefore the present or absence is taken as a characteristic in the tree search. Many stars are surrounded by kites.

### Edge-to-edge

A pattern has this property if one straight edge of the polygon is connected to just one other polygon. Most Islamic patterns have this property.
### Two coloured

Most Islamic patterns can be coloured with just two colours so that all neighbouring polygons have a different colour. This property is *not* dependent on how the pattern is actually displayed here. For this property to hold, the pattern must be edge-to-edge.
### Regular polygons

The presence or otherwise of such polygons is a frequent property used in the tree search. However, it can be the case that a specific pattern appears to have a regular pentagon (say), but it is not exactly regular and therefore can mislead you. There is no simple way round this problem, so beware!
Note also that star polygons are not necessarily concave. For instance, see here, where the 4-pointed star could be an octagon, but has a vertex angle of 120 degrees to match the hexagon.

### Two-level patterns

There are two potentially distinct patterns here, but the tree search logic can only handle one. This is the underlying low-level pattern. If you are searching for a two-level pattern then is would be simpler to look at the collection at here.
### Reflections

There is a problem with reflections when a pattern has been drawn using interlacing, see
here. The small display of this pattern appears to show white lines, but clicking on the image to give the more detailed display show the lines are actually interlaced. From this detailed display you can see that the interlacing prevents a true reflection (say along the middle vertical line).
To partly avoid these problems, the interlacing is ignored in decided if the pattern has reflections. For another example see here which is regarded as having a reflection.