diff --git a/plugins/tools/selectiontools/KisMagneticGraph.h b/plugins/tools/selectiontools/KisMagneticGraph.h index ee93d7bf89..aaf19fb473 100644 --- a/plugins/tools/selectiontools/KisMagneticGraph.h +++ b/plugins/tools/selectiontools/KisMagneticGraph.h @@ -1,202 +1,215 @@ /* * 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 struct VertexDescriptor { long x,y; VertexDescriptor(long _x, long _y): x(_x), y(_y) { } VertexDescriptor(QPoint pt): x(pt.x()), y(pt.y()) { } VertexDescriptor(): x(0), y(0) { } bool operator==(VertexDescriptor const &rhs) const { return rhs.x == x && rhs.y == y; } bool operator==(QPoint const &rhs) const { return rhs.x() == x && rhs.y() == y; } bool operator !=(VertexDescriptor const &rhs) const { return rhs.x != x || rhs.y != y; } bool operator<(VertexDescriptor const &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); } }; +QDebug operator<<(QDebug dbg, const VertexDescriptor &v) { + dbg.nospace() << "(" << v.x << ", " << v.y << ")"; + return dbg.space(); +} + struct neighbour_iterator; struct KisMagneticGraph{ typedef KisMagneticGraph type; KisMagneticGraph() { } KisMagneticGraph(KisPaintDeviceSP dev, QRect graphRect): topLeft(graphRect.topLeft()), bottomRight(graphRect.bottomRight()), m_dev(dev) { outDegree = (bottomRight.y() - topLeft.y()) * (bottomRight.x() - topLeft.x()) - 1; + qDebug() << outDegree; } 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 unsigned long degree_size_type; degree_size_type outDegree; QPoint topLeft, bottomRight; double getIntensity(QPoint pt){ QColor *col = new QColor; m_dev->pixel(pt.x(),pt.y(), col); double intensity = col->blackF(); delete col; return intensity; } private: KisPaintDeviceSP m_dev; }; struct neighbour_iterator : public boost::iterator_facade, boost::forward_traversal_tag, std::pair> { - neighbour_iterator(VertexDescriptor v, KisMagneticGraph g): - graph(g), currentPoint(v) + enum position{ + begin, end + }; + + neighbour_iterator(VertexDescriptor v, KisMagneticGraph g, position p): + graph(g), currentPoint(v), pos(p) { nextPoint = VertexDescriptor(g.topLeft.x(), g.topLeft.y()); if(nextPoint == currentPoint){ - operator++(); + increment(); } } neighbour_iterator() { } std::pair operator*() const { std::pair const result = std::make_pair(currentPoint,nextPoint); return result; } void operator++() { // I am darn sure that Dmitry is wrong, definitely wrong - if(nextPoint == graph.bottomRight) - return; // we are done, no more points - - if(nextPoint.x == graph.bottomRight.x()) // end of a row move to next column - nextPoint = VertexDescriptor(graph.topLeft.x(), nextPoint.y++); - else + if(nextPoint == graph.bottomRight){ + pos = position::end; + return; + } + if(nextPoint.x == graph.bottomRight.x()){ // end of a row move to next column + nextPoint = VertexDescriptor(graph.topLeft.x(), nextPoint.y + 1); + } else { nextPoint.x++; + } + + if(nextPoint == currentPoint){ + increment(); + } + } bool operator==(neighbour_iterator const& that) const { - return currentPoint == that.currentPoint && nextPoint == that.nextPoint; + return pos == that.pos; } bool equal(neighbour_iterator const& that) const { return operator==(that); } void increment() { operator++(); } private: KisMagneticGraph graph; VertexDescriptor currentPoint, nextPoint; + position pos; }; namespace boost{ template<> struct graph_traits { typedef typename KisMagneticGraph::vertex_descriptor vertex_descriptor; typedef typename KisMagneticGraph::edge_descriptor edge_descriptor; typedef typename KisMagneticGraph::out_edge_iterator out_edge_iterator; typedef typename KisMagneticGraph::directed_category directed_category; typedef typename KisMagneticGraph::edge_parallel_category edge_parallel_category; typedef typename KisMagneticGraph::traversal_category traversal_category; typedef typename KisMagneticGraph::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 typename KisMagneticGraph::vertex_descriptor source(typename KisMagneticGraph::edge_descriptor e, KisMagneticGraph g) { Q_UNUSED(g) return e.first; } typename KisMagneticGraph::vertex_descriptor target(typename KisMagneticGraph::edge_descriptor e, KisMagneticGraph g) { Q_UNUSED(g) return e.second; } std::pair out_edges(typename KisMagneticGraph::vertex_descriptor v, KisMagneticGraph g) { return std::make_pair( - KisMagneticGraph::out_edge_iterator(v, g), - KisMagneticGraph::out_edge_iterator(v, g) + KisMagneticGraph::out_edge_iterator(v, g, neighbour_iterator::begin), + KisMagneticGraph::out_edge_iterator(v, g, neighbour_iterator::end) ); } typename KisMagneticGraph::degree_size_type out_degree(typename KisMagneticGraph::vertex_descriptor v, KisMagneticGraph g) { Q_UNUSED(v) return g.outDegree; } -QDebug operator<<(QDebug dbg, const KisMagneticGraph::vertex_descriptor &v) { - dbg.nospace() << "(" << v.x << ", " << v.y << ")"; - return dbg.space(); -} - #endif diff --git a/plugins/tools/selectiontools/KisMagneticWorker.cc b/plugins/tools/selectiontools/KisMagneticWorker.cc index f9d36219f9..3e6d3681f2 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.cc +++ b/plugins/tools/selectiontools/KisMagneticWorker.cc @@ -1,214 +1,220 @@ /* * 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 "KisMagneticGraph.h" struct DistanceMap { typedef VertexDescriptor key_type; typedef double data_type; typedef std::pair value_type; DistanceMap(double const& dval) : m_default(dval) { } data_type &operator[](key_type const& k) { if (m.find(k) == m.end()) m[k] = m_default; return m[k]; } private: std::map m; data_type const m_default; }; struct PredecessorMap{ PredecessorMap() { } PredecessorMap(PredecessorMap const& that): m_map(that.m_map) { } typedef VertexDescriptor key_type; typedef VertexDescriptor value_type; typedef VertexDescriptor & reference_type; typedef boost::read_write_property_map_tag category; VertexDescriptor &operator[](VertexDescriptor v){ return m_map[v]; } std::map m_map; }; VertexDescriptor get(PredecessorMap const &m, VertexDescriptor v){ typename std::map::const_iterator found = m.m_map.find(v); return found != m.m_map.end() ? found->second : v; } void put(PredecessorMap &m, VertexDescriptor key, VertexDescriptor value){ m.m_map[key] = value; } double EuclideanDistance(VertexDescriptor p1, VertexDescriptor p2){ return std::sqrt(std::pow(p1.y-p2.y, 2) + std::pow(p1.x-p2.x, 2)); } class AStarHeuristic : public boost::astar_heuristic { private: PredecessorMap m_pmap; VertexDescriptor m_goal; double coeff_a, coeff_b; public: AStarHeuristic(VertexDescriptor goal, PredecessorMap pmap, double a, double b): m_pmap(pmap), m_goal(goal), coeff_a(a), coeff_b(b) { } AStarHeuristic(VertexDescriptor goal, PredecessorMap 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); double dz = EuclideanDistance(prev, m_goal); di = di/dz; double dm = EuclideanDistance(v, m_goal); return coeff_a * di + coeff_b * (dm - dz); } }; struct GoalFound {}; class AStarGoalVisitor : public boost::default_astar_visitor { public: AStarGoalVisitor(VertexDescriptor goal) : m_goal(goal) { } void examine_vertex(VertexDescriptor u, KisMagneticGraph const &g) { Q_UNUSED(g) if(u == m_goal){ throw GoalFound(); } } private: VertexDescriptor m_goal; }; struct WeightMap{ typedef std::pair key_type; typedef double data_type; typedef std::pair value_type; WeightMap() { } data_type& operator[](key_type const& k) { if (m_map.find(k) == m_map.end()) { m_map[k] = EuclideanDistance(k.first, k.second); } return m_map[k]; } private: std::map m_map; }; QRect KisMagneticWorker::calculateRect(QPoint p1, QPoint p2, int radius) const { // I am sure there is a simpler version of it which exists but well double slope = (p2.y() - p1.y())/(p2.x() - p1.x()); QPoint a,b,c,d; if(slope != 0){ slope = -1/slope; double denom = 2 * std::sqrt(slope*slope+1); double numer = radius/denom; double fac1 = numer/denom; denom = 2 * denom; numer = 3 * slope * numer; double fac2 = numer/denom; a = QPoint(p1.x() - fac1, p1.y() - fac2); b = QPoint(p1.x() + fac1, p1.y() + fac2); c = QPoint(p2.x() - fac1, p2.y() - fac2); d = QPoint(p2.x() + fac1, p2.y() + fac2); }else{ double fac = radius/2; a = QPoint(p1.x() - fac, p1.y() - fac); b = QPoint(p1.x() + fac, p1.y() + fac); c = QPoint(p2.x() - fac, p2.y() - fac); d = QPoint(p2.x() + fac, p2.y() + fac); } QPolygon p(QVector{a,b,c,d}); return p.boundingRect(); } -QVector KisMagneticWorker::computeEdge(KisPaintDeviceSP dev, int radius, QPoint begin, QPoint end) { +QVector KisMagneticWorker::computeEdge(KisPaintDeviceSP dev, int radius, QPoint begin, QPoint end) { QRect rect = calculateRect(begin, end, radius); KisGaussianKernel::applyLoG(dev, rect, 2, -1.0, QBitArray(), 0); VertexDescriptor goal(end); VertexDescriptor start(begin); KisMagneticGraph g(dev, rect); // How many maps does it require? PredecessorMap pmap; DistanceMap dmap(std::numeric_limits::max()); dmap[start] = 0; std::map rmap; std::map cmap; std::map imap; WeightMap wmap; AStarHeuristic heuristic(goal,pmap); - QVector result; + QVector result; try{ boost::astar_search_no_init( g, start, heuristic ,boost::visitor(AStarGoalVisitor(goal)) .distance_map(boost::associative_property_map(dmap)) .predecessor_map(boost::ref(pmap)) .weight_map(boost::associative_property_map(wmap)) .vertex_index_map(boost::associative_property_map>(imap)) .rank_map(boost::associative_property_map>(rmap)) .color_map(boost::associative_property_map>(cmap)) .distance_combine(std::plus()) .distance_compare(std::less()) ); }catch(GoalFound const&){ for(VertexDescriptor u=goal; u!=start; u = pmap[u]){ - result.push_back(QPoint(u.x,u.y)); + result.push_back(QPointF(u.x,u.y)); } } + result.push_back(QPoint(start.x,start.y)); + + for(auto val: result){ + qDebug() << val; + } + return result; } diff --git a/plugins/tools/selectiontools/KisMagneticWorker.h b/plugins/tools/selectiontools/KisMagneticWorker.h index 884b7181de..b4998f067b 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.h +++ b/plugins/tools/selectiontools/KisMagneticWorker.h @@ -1,31 +1,31 @@ /* * 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 KISMAGNETICWORKER_H #define KISMAGNETICWORKER_H #include #include class KRITASELECTIONTOOLS_EXPORT KisMagneticWorker{ public: - QVector computeEdge(KisPaintDeviceSP dev, int radius, QPoint start, QPoint end); + QVector computeEdge(KisPaintDeviceSP dev, int radius, QPoint start, QPoint end); private: QRect calculateRect(QPoint p1, QPoint p2, int radius) const; }; #endif diff --git a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc index e1676b6a86..df9133b9f0 100644 --- a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc +++ b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc @@ -1,51 +1,52 @@ /* * 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 "KisMagneticWorkerTest.h" #include #include #include #include #include #include inline KisPaintDeviceSP loadTestImage(const QString &name, bool convertToAlpha) { QImage image(TestUtil::fetchDataFileLazy(name)); KisPaintDeviceSP dev = new KisPaintDevice(KoColorSpaceRegistry::instance()->rgb8()); dev->convertFromQImage(image, 0); if (convertToAlpha) { dev = KisPainter::convertToAlphaAsAlpha(dev); } return dev; } void KisMagneticWorkerTest::testWorker() { KisPaintDeviceSP dev = loadTestImage("test_main.png", false); const QRect rect = dev->exactBounds(); KisPaintDeviceSP grayscaleDev = KisPainter::convertToAlphaAsGray(dev); KisMagneticWorker worker; - KIS_DUMP_DEVICE_2(grayscaleDev, rect, "main", "dd"); + QVector result = worker.computeEdge(dev, 2, QPoint(10,10), QPoint(20,20)); + KIS_DUMP_DEVICE_2(grayscaleDev, rect, "draw", "dd"); } QTEST_MAIN(KisMagneticWorkerTest)