Adding upstream version 1.2.2.upstream/1.2.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 472 insertions, 0 deletions

diff --git a/src/3rdparty/libdepixelize/priv/homogeneoussplines.h b/src/3rdparty/libdepixelize/priv/homogeneoussplines.h
new file mode 100644
index 0000000..6c4894d
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/homogeneoussplines.h
@@ -0,0 +1,472 @@
+/*  This file is part of the libdepixelize project
+    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+    GNU Lesser General Public License Usage
+    This library is free software; you can redistribute it and/or modify it
+    under the terms of the GNU Lesser General Public License as published by the
+    Free Software Foundation; either version 2.1 of the License, or (at your
+    option) any later version.
+    You should have received a copy of the GNU Lesser General Public License
+    along with this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    GNU General Public License Usage
+    Alternatively, this library may be used under the terms of the GNU General
+    Public License as published by the Free Software Foundation, either version
+    2 of the License, or (at your option) any later version.
+    You should have received a copy of the GNU General Public License along with
+    this library.  If not, see <http://www.gnu.org/licenses/>.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+#define LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+
+#include "simplifiedvoronoi.h"
+#include "point.h"
+#include <algorithm>
+#include <utility>
+
+namespace Tracer {
+
+template<typename T>
+class HomogeneousSplines
+{
+public:
+    struct Polygon
+    {
+        typedef std::vector< Point<T> > Points;
+        typedef typename Points::iterator points_iter;
+        typedef typename Points::const_iterator const_points_iter;
+        typedef typename std::vector<Points>::iterator holes_iter;
+        typedef typename std::vector<Points>::const_iterator const_holes_iter;
+
+        Polygon() {}
+        Polygon(const guint8 (&rgba)[4])
+        {
+            for ( int i = 0 ; i != 4 ; ++i )
+                this->rgba[i] = rgba[i];
+        }
+
+        std::vector< Point<T> > vertices;
+
+        /**
+         * It may be benefited from C++11 move references.
+         */
+        std::vector< std::vector< Point<T> > > holes;
+
+        guint8 rgba[4];
+    };
+
+    typedef typename std::vector<Polygon>::iterator iterator;
+    typedef typename std::vector<Polygon>::const_iterator const_iterator;
+    typedef typename std::vector<Polygon>::size_type size_type;
+
+    template<bool adjust_splines>
+    HomogeneousSplines(const SimplifiedVoronoi<T, adjust_splines> &voronoi);
+
+    // Iterators
+    iterator begin()
+    {
+        return _polygons.begin();
+    }
+
+    const_iterator begin() const
+    {
+        return _polygons.begin();
+    }
+
+    iterator end()
+    {
+        return _polygons.end();
+    }
+
+    const_iterator end() const
+    {
+        return _polygons.end();
+    }
+
+    size_type size() const
+    {
+        return _polygons.size();
+    }
+
+    int width() const
+    {
+        return _width;
+    }
+
+    int height() const
+    {
+        return _height;
+    }
+
+private:
+    typedef std::vector< Point<T> > Points;
+    typedef typename Points::iterator points_iter;
+    typedef typename Points::const_iterator points_citer;
+    typedef typename Points::reverse_iterator points_riter;
+    typedef typename Points::const_reverse_iterator points_criter;
+
+    typedef std::pair<points_iter, points_iter> points_range;
+    typedef std::pair<points_citer, points_citer> points_crange;
+
+    struct CommonEdge
+    {
+        bool ok; //< share an edge
+        Points *dst;
+        const Points *src;
+
+        // the interval is closed on both ends
+        // different from [begin, end) STL style
+        points_iter dst_begin, dst_end;
+        points_citer src_begin, src_end;
+    };
+
+    struct SelfCommonEdge
+    {
+        bool ok; //< share an edge
+
+        // Greater range. The one that should be erased from the vector.
+        points_riter grt_begin, grt_end;
+
+        // Smaller range. The one that should be used to create a new vector.
+        points_riter sml_begin, sml_end;
+    };
+
+    /**
+     * Return ok == true if they share an edge (more than one point).
+     */
+    CommonEdge _common_edge(Points &dst, const Points &src);
+
+    /**
+     * Return ok == true if they share an edge (more than one point).
+     *
+     *  - [dst_begin, dst_end) will contain the hole polygon
+     *  - [src_begin, src_end) will contain the range to be erased
+     *
+     * It's required to do the search in backward order.
+     */
+    SelfCommonEdge _common_edge(Points &points, points_riter it);
+
+    /*!
+     * Add polygon represented by \p common_edge.src to \p common_edge.dst.
+     */
+    void _polygon_union(CommonEdge common_edge);
+
+    /**
+     * Weird recursive function created to solve the complex problem to fill
+     * polygons holes without the need to store temporaries on the heap nor
+     * changing requirements to some data type that don't invalidate iterators
+     * that point before the current element (maybe I'll write some poetry about
+     * the problem someday).
+     */
+    void _fill_holes(std::vector<Points> &holes, points_iter region_begin,
+                     points_iter region_end);
+
+    std::vector<Polygon> _polygons;
+    int _width;
+    int _height;
+};
+
+template<class T>
+template<bool adjust_splines>
+HomogeneousSplines<T>::HomogeneousSplines(const SimplifiedVoronoi<T,
+                                          adjust_splines> &voronoi) :
+    _width(voronoi.width()),
+    _height(voronoi.height())
+{
+    //if (!voronoi.size())
+    //    return;
+    using colorspace::same_color;
+
+    typedef typename SimplifiedVoronoi<T, adjust_splines>::const_iterator
+        voronoi_citer;
+
+    // Identify visible edges (group polygons with the same color)
+    for ( voronoi_citer cell_it = voronoi.begin(), cell_end = voronoi.end()
+              ; cell_it != cell_end ; ++cell_it ) {
+        bool found = false;
+        for ( iterator polygon_it = _polygons.begin(),
+                  polygon_end = _polygons.end()
+                  ; polygon_it != polygon_end ; ++polygon_it ) {
+            if ( same_color(polygon_it->rgba, cell_it->rgba) ) {
+                CommonEdge common_edge = _common_edge(polygon_it->vertices,
+                                                      cell_it->vertices);
+                if ( common_edge.ok ) {
+                    _polygon_union(common_edge);
+                    found = true;
+
+                    for ( iterator polygon2_it = polygon_it + 1
+                              ; polygon2_it != polygon_end ; ++polygon2_it ) {
+                        if ( same_color(polygon_it->rgba, polygon2_it->rgba) ) {
+                            CommonEdge common_edge2
+                                = _common_edge(polygon_it->vertices,
+                                               polygon2_it->vertices);
+                            if ( common_edge2.ok ) {
+                                _polygon_union(common_edge2);
+                                _polygons.erase(polygon2_it);
+                                break;
+                            }
+                        }
+                    }
+
+                    break;
+                }
+            }
+        }
+        if ( !found ) {
+            Polygon polygon(cell_it->rgba);
+            polygon.vertices = cell_it->vertices;
+            _polygons.insert(_polygons.end(), polygon);
+        }
+    }
+
+    // Find polygons with holes and fix them
+    // This iteration runs such complex time-consuming algorithm, but each
+    // polygon has an independent result. They wouldn't even need to share/sync
+    // results and the only waste would be a join at the end of the for.
+    for ( typename std::vector<Polygon>::iterator it = _polygons.begin(),
+              end = _polygons.end() ; it != end ; ++it ) {
+        SelfCommonEdge ce = _common_edge(it->vertices, it->vertices.rbegin());
+        while ( ce.ok ) {
+            _fill_holes(it->holes, ce.sml_end.base(), ce.sml_begin.base());
+            it->vertices.erase(ce.grt_end.base() + 1, ce.grt_begin.base());
+            ce = _common_edge(it->vertices, ce.grt_end);
+        }
+    }
+}
+
+// it can infinite loop if points of both entities are equal,
+// but this shouldn't happen if user has only access to Kopf2011 interface
+template<class T>
+typename HomogeneousSplines<T>::CommonEdge
+HomogeneousSplines<T>::_common_edge(Points &dst, const Points &src)
+{
+    // It's an edge, then the points are closer together. After we find the
+    // first point, there is no need for check against all points of the src
+    // a second time
+
+    const points_iter dst_begin = dst.begin();
+    const points_iter dst_end = dst.end();
+
+    const points_citer src_begin = src.begin();
+    const points_citer src_end = src.end();
+
+    for ( points_iter it = dst_begin ; it != dst_end ; ++it ) {
+        points_citer src_it = std::find(src_begin, src_end, *it);
+
+        if ( src_it == src_end )
+            continue;
+
+        points_iter dst_common_edge_begin = it;
+        points_citer src_common_edge_end = src_it;
+
+        // iterate until find the beginning of the common edge range
+        while ( *dst_common_edge_begin == *src_common_edge_end ) {
+            if ( dst_common_edge_begin == dst_begin )
+                dst_common_edge_begin = dst_end - 1;
+            else
+                --dst_common_edge_begin;
+
+            ++src_common_edge_end;
+            if ( src_common_edge_end == src_end )
+                src_common_edge_end = src_begin;
+        }
+
+        // fix {dst_begin, src_end} range
+        ++dst_common_edge_begin;
+        if ( dst_common_edge_begin == dst_end )
+            dst_common_edge_begin = dst_begin;
+
+        if ( src_common_edge_end == src_begin )
+            src_common_edge_end = src_end - 1;
+        else
+            --src_common_edge_end;
+
+        points_iter dst_common_edge_end = it;
+        points_citer src_common_edge_begin = src_it;
+
+        // find the end of the common edge range
+        while ( *dst_common_edge_end == *src_common_edge_begin ) {
+            ++dst_common_edge_end;
+            if ( dst_common_edge_end == dst_end )
+                dst_common_edge_end = dst_begin;
+
+            if ( src_common_edge_begin == src_begin )
+                src_common_edge_begin = src_end - 1;
+            else
+                --src_common_edge_begin;
+        }
+
+        // fix {dst_end, src_begin} range
+        if ( dst_common_edge_end == dst_begin )
+            dst_common_edge_end = dst_end - 1;
+        else
+            --dst_common_edge_end;
+
+        ++src_common_edge_begin;
+        if ( src_common_edge_begin == src_end )
+            src_common_edge_begin = src_begin;
+
+        CommonEdge ret;
+
+        // if only one point in common
+        if ( dst_common_edge_begin == dst_common_edge_end )
+            continue;
+
+        ret.ok = true;
+
+        ret.dst = &dst;
+        ret.dst_begin = dst_common_edge_begin;
+        ret.dst_end = dst_common_edge_end;
+
+        ret.src = &src;
+        ret.src_begin = src_common_edge_begin;
+        ret.src_end = src_common_edge_end;
+
+        return ret;
+    }
+
+    CommonEdge ret;
+    ret.ok = false;
+    return ret;
+}
+
+template<class T>
+typename HomogeneousSplines<T>::SelfCommonEdge
+HomogeneousSplines<T>::_common_edge(Points &points, points_riter it)
+{
+    SelfCommonEdge ret;
+
+    ret.grt_end = points.rend();
+
+    for ( ; it != ret.grt_end ; ++it ) {
+        ret.sml_end = std::find(it + 1, ret.grt_end, *it);
+
+        if ( ret.sml_end == ret.grt_end )
+            continue;
+
+        ret.grt_begin = it;
+        ret.grt_end = ret.sml_end + 1;
+
+        ret.sml_begin = it;
+
+        while ( *ret.sml_begin == *ret.sml_end ) {
+            ++ret.sml_begin;
+            --ret.sml_end;
+        }
+
+        --ret.sml_begin;
+        ++ret.sml_end;
+        ++ret.sml_end;
+
+        ret.ok = true;
+        return ret;
+    }
+
+    ret.ok = false;
+    return ret;
+}
+
+template<class T>
+void HomogeneousSplines<T>::_polygon_union(CommonEdge common_edge)
+{
+    Points &dst = *common_edge.dst;
+    const Points &src = *common_edge.src;
+
+    // the rotated cell must be inserted before (dst.begin() + index)
+    typename Points::difference_type index;
+
+    // first, we remove the common edge in dst
+    if ( common_edge.dst_begin < common_edge.dst_end ) {
+        // common edge is in the middle of dst
+
+        index = dst.erase(common_edge.dst_begin,
+                          common_edge.dst_end + 1) - dst.begin();
+    } else {
+        // common edge cross the end of dst
+
+        dst.erase(common_edge.dst_begin, dst.end());
+        dst.erase(dst.begin(), common_edge.dst_end);
+        index = dst.end() - dst.begin();
+    }
+
+    // second, we copy src points to polygon
+    if ( common_edge.src_begin < common_edge.src_end ) {
+        // common edge is in the middle of src
+
+        const typename Points::difference_type nfirstinserted
+            = src.end() - common_edge.src_end;
+        const typename Points::difference_type nsecondinserted
+            = 1 + (common_edge.src_begin - src.begin());
+
+        dst.reserve(dst.size() + nfirstinserted + nsecondinserted);
+
+        dst.insert(dst.begin() + index, common_edge.src_end, src.end());
+
+        dst.insert(dst.begin() + index + nfirstinserted,
+                   src.begin(), common_edge.src_begin + 1);
+    } else {
+        // common edge cross the end of src
+
+        dst.reserve(dst.size() + 1
+                    + (common_edge.src_begin - common_edge.src_end));
+
+        dst.insert(dst.begin() + index,
+                   common_edge.src_end, common_edge.src_begin + 1);
+    }
+}
+
+// The following piece of code is so evil that you could end up invoking an
+// ancient beast if you proceed to read it, but I'll be able to explain it in
+// the form of some video (text is not so representative as an image).
+template<class T>
+void HomogeneousSplines<T>::_fill_holes(std::vector<Points> &holes,
+                                        points_iter region_begin,
+                                        points_iter region_end)
+{
+    // the exact location might not always be back and iterators will be
+    // invalidated after some insertions, then the index is required
+    const typename std::vector<Points>::size_type hole_index = holes.size();
+    holes.resize(hole_index + 1);
+
+    for ( points_iter it = region_begin + 1 ; it != region_end ; ++it ) {
+        points_iter res = std::find(it + 1, region_end, *it);
+        if ( res == region_end )
+            continue;
+
+        holes[hole_index].insert(holes[hole_index].end(), region_begin,
+                                 it);
+        region_begin = res;
+
+        do {
+            ++it;
+            --res;
+        } while ( *it == *res );
+        _fill_holes(holes, it - 1, res + 2);
+
+        it = region_begin;
+    }
+
+    holes[hole_index].insert(holes[hole_index].end(), region_begin,
+                             region_end - 1);
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :