jdan/isomer — pull request #39 by Mysterix (2014-05-08 20:57:03+00:00)
Title: Path and multiple shapes ordering (solves #9)

First, good news : it can't break anything, as I only added functions (for the moment), and changed none.
The function to use is addOrdered, you can see examples here http://rdelav.fr/isomer/isomer3.html (and the following numbers)
addOrdered takes as input as list of {shape:yourShape, color:yourColor}, and display all the path of all the shapes of the input and display them in the correct order, according to their relative positions.

The algorithm used is the following :
We put all the paths of every shape in a big array
For every couple of path, we considerer their projection on the canvas (which are two 2D-polygons).
If their intesection is non-empty [see note 1], we add the rule that the one which is in front [see note 2] must be drawn after the other one.
To match all those rules, we sort the path using a topological sort.

Note1 : to know if the intesection is not empty, we compute if one edge of the first cuts an edge of the other, or if a vertex of one is contained in the other
Note2 : to know which one is is front of the other between two intesecting paths, we look at the percentage of vertices of one which are one the same side of the plane defined by the other than the observer. (I will show a drawing for that)
Note3 : we need to check that the projection of the paths is intersecting, otherwise you have common situation where A is in front of B which is in front of C which is in front of A (I will show a drawing for that too)
Note 4 : other problems I didn't think of initially : rounding approximations, and the exact position of the observer.
Note 5 : I found so many special cases and exceptions during my tests (that work in this version) that there may be cases I didn't think of, sorry for that.

In the future, instead of a function addOrdered, we can also have two functions, one to add a shape, and one to flush and draw all the added shapes.