diff --git a/plugins/tools/selectiontools/KisMagneticGraph.h b/plugins/tools/selectiontools/KisMagneticGraph.h index d2640e3941..5641e51ecc 100644 --- a/plugins/tools/selectiontools/KisMagneticGraph.h +++ b/plugins/tools/selectiontools/KisMagneticGraph.h @@ -1,210 +1,171 @@ /* * Copyright (c) 2019 Kuntal Majumder * * 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; version 2.1 of the License. * * 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. * * You should have received a copy of the GNU Lesser General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KISMAGNETICGRAPH_H #define KISMAGNETICGRAPH_H -#include #include #include -#include -#include -#include #include +#include +struct VertexDescriptor : public boost::equality_comparable{ -// vertex_at -template -struct magnetic_graph_vertex_at { + long x,y; - typedef typename boost::graph_traits::vertex_descriptor result_type; - - magnetic_graph_vertex_at() : m_graph(0) {} - - magnetic_graph_vertex_at(const Graph* graph) : - m_graph(graph) { } - - result_type - operator() (typename boost::graph_traits::vertices_size_type vertex_index) const { - return (vertex(vertex_index, *m_graph)); - } - -private: - const Graph* m_graph; -}; - -// out_edge_at -template -struct magnetic_graph_out_edge_at { - -private: - typedef typename boost::graph_traits::vertex_descriptor vertex_descriptor; - -public: - typedef typename boost::graph_traits::edge_descriptor result_type; + VertexDescriptor(long _x, long _y): + x(_x), y(_y) + { } - magnetic_graph_out_edge_at() : - m_vertex(), m_graph(0) + VertexDescriptor(QPoint pt): + x(pt.x()), y(pt.y()) { } - magnetic_graph_out_edge_at(vertex_descriptor source_vertex, const Graph* graph) : - m_vertex(source_vertex), m_graph(graph) + VertexDescriptor(): + x(0), y(0) { } - result_type - operator() (typename boost::graph_traits::degree_size_type out_edge_index) const { - return (out_edge_at(m_vertex, out_edge_index, *m_graph)); + bool operator ==(const VertexDescriptor &rhs) const { + return rhs.x == x && rhs.y == y; } -private: - vertex_descriptor m_vertex; - const Graph* m_graph; + bool operator ==(const QPoint &rhs) const { + return rhs.x() == x && rhs.y() == y; + } }; -// in_edge_at -template -struct magnetic_graph_in_edge_at { +struct neighbour_iterator; -private: - typedef typename boost::graph_traits::vertex_descriptor vertex_descriptor; +struct KisMagneticGraph{ -public: - typedef typename boost::graph_traits::edge_descriptor result_type; - - magnetic_graph_in_edge_at() : - m_vertex(), m_graph(0) - { } - - magnetic_graph_in_edge_at(vertex_descriptor target_vertex, const Graph* graph) : - m_vertex(target_vertex), m_graph(graph) + KisMagneticGraph() { } + KisMagneticGraph(long _outDegree, QRect graphRect): + outDegree(_outDegree), topLeft(graphRect.topLeft()), bottomRight(graphRect.bottomRight()) { } - result_type - operator() (typename boost::graph_traits::degree_size_type in_edge_index) const { - return (in_edge_at(m_vertex, in_edge_index, *m_graph)); - } - -private: - vertex_descriptor m_vertex; - const Graph* m_graph; + typedef VertexDescriptor vertex_descriptor; + typedef std::pair edge_descriptor; + typedef boost::undirected_tag directed_category; + typedef boost::disallow_parallel_edge_tag edge_parallel_category; + typedef boost::incidence_graph_tag traversal_category; + typedef neighbour_iterator out_edge_iterator; + typedef long degree_size_type; + + degree_size_type outDegree; + QPoint topLeft, bottomRight; }; -// edge_at -template -struct magnetic_graph_edge_at { - - typedef typename boost::graph_traits::edge_descriptor result_type; - - magnetic_graph_edge_at () : - m_graph(0) - { } - - magnetic_graph_edge_at (const Graph* graph) : - m_graph(graph) - { } +struct neighbour_iterator : public boost::iterator_facade, + boost::forward_traversal_tag, + std::pair> +{ + neighbour_iterator(VertexDescriptor v, KisMagneticGraph g): + currentPoint(v), graph(g) + { + nextPoint = VertexDescriptor(g.topLeft.x(), g.topLeft.y()); + if(nextPoint == currentPoint){ + operator++(); + } + } - result_type operator() - (typename boost::graph_traits::edges_size_type edge_index) const { - return (edge_at(edge_index, *m_graph)); + std::pair + operator*() const { + std::pair const result = std::make_pair(currentPoint,nextPoint); + return result; } -private: - const Graph* m_graph; -}; + void operator++() { + if(nextPoint == graph.bottomRight) + return; // we are done, no more points -// adjacent_vertex_at -template -struct magnetic_graph_adjacent_vertex_at { + if(nextPoint.x == graph.bottomRight.x()) // end of a row move to next column + nextPoint = VertexDescriptor(graph.topLeft.x(), nextPoint.y++); + else + nextPoint.x++; + } -public: - typedef typename boost::graph_traits::vertex_descriptor result_type; + bool operator==(neighbour_iterator const& that) const { + return point == that.point; + } - magnetic_graph_adjacent_vertex_at - (result_type source_vertex, const Graph* graph) : - m_vertex(source_vertex), m_graph(graph) - { } + bool equal(neighbour_iterator const& that) const { + return operator==(that); + } - result_type operator() - (typename boost::graph_traits::degree_size_type adjacent_index) const { - return (target(out_edge_at(m_vertex, adjacent_index, *m_graph), *m_graph)); + void increment() { + operator++(); } private: - result_type m_vertex; - const Graph* m_graph; + KisMagneticGraph graph; + VertexDescriptor currentPoint, nextPoint; }; - -class KisMagneticGraph{ -public: +namespace boost{ +template<> +struct graph_traits { typedef KisMagneticGraph type; + typedef typename type::vertex_descriptor vertex_descriptor; + typedef typename type::edge_descriptor edge_descriptor; + typedef typename type::out_edge_iterator out_edge_iterator; + typedef typename type::directed_category directed_category; + typedef typename type::edge_parallel_category edge_parallel_category; + typedef typename type::traversal_category traversal_category; + typedef typename type::degree_size_type degree_size_type; + + typedef void in_edge_iterator; + typedef void vertex_iterator; + typedef void vertices_size_type; + typedef void edge_iterator; + typedef void edges_size_type; +}; +} +// Requirements for an Incidence Graph, +// https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/IncidenceGraph.html - typedef long VertexIndex; - typedef long EdgeIndex; - - typedef VertexIndex vertices_size_type; - typedef EdgeIndex edges_size_type; - typedef EdgeIndex degree_size_type; - - struct VertexDescriptor : public boost::equality_comparable{ - vertices_size_type x,y; - - VertexDescriptor(vertices_size_type _x, vertices_size_type _y): - x(_x),y(_y) - { } - - VertexDescriptor(): - x(0),y(0) - { } - - bool operator ==(const VertexDescriptor &rhs) const { - return rhs.x == x && rhs.y == y; - } - }; - - typedef VertexDescriptor vertex_descriptor; - typedef std::pair edge_descriptor; +typename KisMagneticGraph::vertex_descriptor +source(typename KisMagneticGraph::edge_descriptor e, KisMagneticGraph g) { + return e.first; +} - friend QDebug operator<<(QDebug dbg, const KisMagneticGraph::edge_descriptor &e); - friend QDebug operator<<(QDebug dbg, const KisMagneticGraph::vertex_descriptor &v); +typename KisMagneticGraph::vertex_descriptor +target(typename KisMagneticGraph::edge_descriptor e, KisMagneticGraph g) { + return e.second; +} - typedef boost::directed_tag directed_category; - typedef boost::disallow_parallel_edge_tag edge_parallel_category; - struct traversal_category : virtual public boost::incidence_graph_tag, - virtual public boost::vertex_list_graph_tag - { }; +std::pair +out_edges(typename KisMagneticGraph::vertex_descriptor v, KisMagneticGraph g) { + return std::make_pair( + KisMagneticGraph::out_edge_iterator(v), + KisMagneticGraph::out_edge_iterator(v) + ); +} - KisMagneticGraph() { } -}; +typename KisMagneticGraph::degree_size_type +out_degree(typename KisMagneticGraph::vertex_descriptor v, KisMagneticGraph g) { + return g.outDegree; +} QDebug operator<<(QDebug dbg, const KisMagneticGraph::vertex_descriptor &v) { - dbg.nospace() << "(" << v.x << ", " << v.y << ")"; return dbg.space(); } -QDebug operator<<(QDebug dbg, const KisMagneticGraph::edge_descriptor &e) { - KisMagneticGraph::vertex_descriptor src = e.first; - KisMagneticGraph::vertex_descriptor dst = e.second; - - dbg.nospace() << "(" << src << " -> " << dst << ")"; - return dbg.space(); -} - #endif diff --git a/plugins/tools/selectiontools/KisMagneticWorker.cc b/plugins/tools/selectiontools/KisMagneticWorker.cc index 9460163c88..e76a67a406 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.cc +++ b/plugins/tools/selectiontools/KisMagneticWorker.cc @@ -1,89 +1,87 @@ /* * Copyright (c) 2019 Kuntal Majumder * * 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; version 2.1 of the License. * * 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. * * You should have received a copy of the GNU Lesser General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "KisMagneticWorker.h" #include "kis_gaussian_kernel.h" #include #include #include #include #include "KisMagneticGraph.h" -typedef KisMagneticGraph::VertexDescriptor VertexDescriptor; - struct VertexHash : std::unary_function { std::size_t operator()(VertexDescriptor const& u) const { std::size_t seed = 0; boost::hash_combine(seed, u.x); boost::hash_combine(seed, u.y); return seed; } }; typedef boost::unordered_map PredMap; typedef boost::associative_property_map APredMap; class AstarHeuristic : public boost::astar_heuristic { private: APredMap m_pmap; VertexDescriptor m_goal; double coeff_a, coeff_b; public: AstarHeuristic(VertexDescriptor goal, APredMap pmap, double a, double b): m_pmap(pmap), m_goal(goal), coeff_a(a), coeff_b(b) { } AstarHeuristic(VertexDescriptor goal, APredMap pmap): m_pmap(pmap), m_goal(goal), coeff_a(0.5), coeff_b(0.5) { } double operator()(VertexDescriptor v){ auto prev = m_pmap[v]; double di = (m_goal.y - prev.y) * v.x + (m_goal.x - prev.x) * v.y; di = std::abs(di + prev.x * m_goal.y + prev.y * m_goal.x); auto dist = [](VertexDescriptor p1, VertexDescriptor p2){ return std::sqrt(std::pow(p1.y-p2.y, 2) + std::pow(p1.x-p2.x, 2)); }; double dz = dist(prev, m_goal); di = di/dz; double dm = dist(v, m_goal); return coeff_a * di + coeff_b * (dm - dz); } }; KisMagneticWorker::KisMagneticWorker(): m_dev(0), m_rect(QRect()) { } KisMagneticWorker::KisMagneticWorker(KisPaintDeviceSP dev, const QRect &rect): m_dev(dev), m_rect(rect) { } void KisMagneticWorker::run(KisPaintDeviceSP dev, const QRect &rect) { KisGaussianKernel::applyLoG(dev, rect, 2, -1.0, QBitArray(), 0); } void KisMagneticWorker::computeEdge(QPoint start, QPoint end) { Q_UNUSED(start) Q_UNUSED(end) KisGaussianKernel::applyLoG(m_dev, m_rect, 2, -1.0, QBitArray(), 0); }