-namespace {
-
-bool compare_z(const Marklin::Point &p1, const Marklin::Point &p2)
-{
- return p1.z<p2.z;
-}
-
-template<typename Iter>
-Iter graham_scan(Iter begin, Iter end)
-{
- // http://en.wikipedia.org/wiki/Graham_scan
-
- // Find point with lowest X coordinate
- Marklin::Point lowest = *begin;
- for(Iter i=begin; i!=end; ++i)
- if(i->x<lowest.x || (i->x==lowest.x && i->y>lowest.y))
- lowest = *i;
-
- // Compute tangents and sort points
- for(Iter i=begin; i!=end; ++i)
- i->z = (i->x==lowest.x ? 1e5/(i->y-lowest.y-1) : (i->y-lowest.y)/(i->x-lowest.x));
- sort(begin, end, compare_z);
-
- for(Iter k=begin, i=k++, j=k++;; )
- {
- // Compute winding by cross product
- float turn = (j->x-i->x)*(k->y-j->y) - (k->x-j->x)*(j->y-i->y);
-
- if(turn<1e-5)
- {
- // Right turn - throw the middle point away
- // Special case for collinear vertices in the beginning
- if(i==begin)
- j = k++;
- else
- j = i--;
- }
- else
- {
- // Left turn - store the middle point and advance
- if(++i!=j)
- *i = *j;
- j = k++;
- }
-
- // Cycle back to beginning and terminate after checking the last point
- if(k==end)
- k = begin;
- else if(j==begin)
- return ++i;
- }
-}
-
-}
-
-namespace Marklin {