A client I work for offers a tool in Flash with which you can draw complex shapes. Each of these shapes represents a “building”. When you draw, the line-tool you draw with automatically snaps to existing lines and nodes so that closed shapes can be created. Each shape receives a fill. This fill is based on the shape that results from scanning each line and their connections other lines. Lines are “connected” by the coordinates of their overlapping edges.

**Implementation A: Scanning the shape of a implicit polygon**

The procedure to scan for connections is as follows:

- Choose a line and set it as “currentLine”
- MAIN CYCLE:
- Store “currentLine” in an Array.
- Get the X/Y coordinates of the start- and end point of line “currentLine”
- Loop through all other lines
- Per line (“myLine”):
- Check if there is an overlap in the X/Y coordinate of “myLine” and “currentLine”
- If so: these lines are connected.
- Store “myLine” in the array.

- Check if “myLine” is also connected to the first line in the Array.
- If so: we have found a closed shape.
- Break loop.
- Stop the main cycle. We are done.

- Set “currentLine” to be “myLine”.
- Break loop and start “Main Cycle”.

- Per line (“myLine”):

In a shape with 5 lines, in 5 cycles finds this is retrieved:

This approach works fine as long as the shape is a single polygon. It fails the moment you “extend” it with another line intersecting two other lines and seperating the “room”, the outcome becomes unpredictable.

With a simple polygon, each node has only two lines and only has one new direction. When shapes are combined, each node can have two or more directions (called “options”) in the drawing to choose as the next path to follow.

Comparing a simple shape wit a more “complex” shape, you will find that dividing that shape in two parts will suddenly introduce choice.

The algorithm that scans the shape is blind. It simply follows the connections between two lines.

When you divide the shape and when you want to follow each path, suddenly a minimum of 3 possible outcomes occur:

- Shape “A” (the left hand side)
- Shape “B” (the right hand side)
- Shape “C” (the total shape according to the outline)

With more dividing lines, the possible options in shapes increase manifold, as any closed path results in a shape.

I have considered scanning all possible shapes and forms of a “complex” shape and then eliminate those shapes which are composed of two or more smaller shapes, but that requires a lot of muscles/processing power. This is the simplefied approach:

- Scan for all possible shapes
- Eliminate all shapes that are composed of 2 or more simple shapes
- Do this for all possible combinations of shapes.

Looking at this approach, and simplyfying it to “what if I use triangles?” I found the key to another strategy.

**Strategy 1: Surface fitting by triangulation**

Instead of following the possible paths, you start by separating the object into the smallest possible parts: triangles. Each triangle is connected to 3 nodes in the polygon. Each triangle is next to at least one other triangle. In case of a more “complex” form, at least two triangles are connected.

Below a step by step depiction of Triangulation from this article:

Once you have the triangles, you also have “clusters” of nodes you can easily cluster into bigger groups as triangle always shares 2 corners with it’s neighbor. The sides of traingles that corresponds with a line drawn by the user are treated as “without a neighbor”.

The scanning / decyphering we use is blind. It has no broader “sight” than the next connected item.

The complexity lies in:

- Defining what is “inside” and “outside” the shape
- Respecting the lines drawn by the user within the combined polygon “complex” shape.
- Avoiding crossing lines / overlapping triangles

Using this strategy, the user is allowed to draw complex shapes any way he or she wants. Crossing lines can be converted to nodes. Polygons can be drawn freehand and with an interrupted work flow, as each polygon is deducted afterwards, based on overlapping corners of the shapes.

To create this solution from scratch would take – including prototyping, testing and cleaning up – approximately 80 hours to 100 hours.

**Strategy 2: Forced single pathways
**

The disadvantage of “Strategy 1” is the complexity in sorting and pattern recognition. A more simple approach is where each node in the polygon does not accept more than one connection to one other line.

- Each line is drawn between a “start” and “end” node
- Each “start” and “end” node holds only one slot and is capable to connect to only one other line.
- A connection is made by drawing or dragging the “end” or “start” node of the new line onto the “start” or “end” node of an existing line.
- A connection between two lines is broken by deleting one of the two lines.

The only way to create a “complex” form of two or more connected polygons is by drawing these polygons separately.

**Strategy 2.a: Maintaining shape consistency when dragging lines and corners
**

Shape consistency is currently maintained by moving all lines and corners connected via the X/Y positions of their corners. This might seem logical but also introduces new problems. For instance: if I reduce the size of one shape by dragging a line, it will automatically deform the other connected shape.

Changing shapes and dragging lines is dealt with as follows:

- Changes due to dragging overlapping corners and overlapping lines will affect both shapes in the same way
- You can snap a line or corner onto another line or corner of another shape to get seamless connections. The shapes will maintain their consistency.

**Strategy 2.b: Converting existing drawings using “Implementation A”**

Using the scanning method with which the polygons of current drawings are defined, the lines connections between lines can be made explicit. By this, drawings created before the implementation of “Strategy 2” will be converted in a proper way.

For drawings containing “complex shapes” the user will have to correct the polygon shape that becomes “broken” by redrawing the shape or adding the line that has been exclusively added to one of the two connected polygons.

Strategy 2 would take approximately 16 hours to prototype, test and clean up.

*Uncategorized*

Posted on July 21, 20090