diff --git a/plugins/tools/selectiontools/KisMagneticGraph.h b/plugins/tools/selectiontools/KisMagneticGraph.h index d22ca468a5..aef6f6936b 100644 --- a/plugins/tools/selectiontools/KisMagneticGraph.h +++ b/plugins/tools/selectiontools/KisMagneticGraph.h @@ -1,255 +1,255 @@ /* * 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 struct VertexDescriptor { long x,y; enum Direction { MIN = 0, N = MIN, S, E, W, NW, NE, SW, SE, NONE }; 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); } + // returns one of the 8 neighboring pixel based on the direction + // it gives out multiple warnings, but I am lazy, sorry VertexDescriptor neighbor(Direction direction) const { int dx = 0, dy = 0; switch (direction){ case W: case SW: case NW: dx = -1; break; case E: case SE: case NE: dx = 1; } switch(direction){ case N: case NW: case NE: dy = -1; break; case S: case SW: case SE: dy = 1; } VertexDescriptor const neighbor(x + dx, y + dy); return neighbor; } }; 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): m_rect(graphRect), m_dev(dev) { } 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 degree_size_type; double getIntensity(VertexDescriptor pt){ KisRandomAccessorSP randAccess = m_dev->createRandomAccessorNG(m_dev->exactBounds().x(),m_dev->exactBounds().y()); randAccess->moveTo(pt.x, pt.y); qint8 val = *(randAccess->rawData()); //offsetting the value, so we don't get negatives return val + 255; } unsigned outDegree(VertexDescriptor pt){ //corners if(pt == m_rect.topLeft() || pt == m_rect.topRight() || pt == m_rect.bottomLeft() || pt == m_rect.bottomRight()){ if(m_rect.width() == 1 || m_rect.height() == 1) return 1; return 3; } //edges if(pt.x == m_rect.topLeft().x() || pt.y == m_rect.topLeft().y() || pt.x == m_rect.bottomRight().x() || pt.y == m_rect.bottomRight().y()){ if(m_rect.width() == 1 || m_rect.height() == 1) return 2; return 5; } - return 8; - } QRect m_rect; private: KisPaintDeviceSP m_dev; }; struct neighbour_iterator : public boost::iterator_facade, boost::forward_traversal_tag, std::pair> { neighbour_iterator(VertexDescriptor v, KisMagneticGraph g, VertexDescriptor::Direction d): m_point(v), m_direction(d), m_graph(g) { } neighbour_iterator() { } std::pair operator*() const { std::pair const result = std::make_pair(m_point, m_point.neighbor(m_direction)); return result; } void operator++() { m_direction = static_cast(int(m_direction)+1); VertexDescriptor next = m_point.neighbor(m_direction); if(m_direction == VertexDescriptor::NONE){ return; } if(!m_graph.m_rect.contains(next.x, next.y)){ operator++(); } } bool operator==(neighbour_iterator const& that) const { return m_point == that.m_point && m_direction == that.m_direction; } bool equal(neighbour_iterator const& that) const { return operator==(that); } void increment() { operator++(); } private: VertexDescriptor m_point; VertexDescriptor::Direction m_direction; KisMagneticGraph m_graph; }; +// Requirements for an Incidence Graph, +// https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/IncidenceGraph.html + 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, VertexDescriptor::Direction::MIN), KisMagneticGraph::out_edge_iterator(v, g, VertexDescriptor::Direction::NONE) ); } typename KisMagneticGraph::degree_size_type out_degree(typename KisMagneticGraph::vertex_descriptor v, KisMagneticGraph g) { return g.outDegree(v); } #endif diff --git a/plugins/tools/selectiontools/KisMagneticWorker.cc b/plugins/tools/selectiontools/KisMagneticWorker.cc index 98d9f14452..b12a867723 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.cc +++ b/plugins/tools/selectiontools/KisMagneticWorker.cc @@ -1,218 +1,227 @@ /* * 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 #include #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: VertexDescriptor m_goal; double coeff_a, coeff_b; public: AStarHeuristic(VertexDescriptor goal, double a, double b): m_goal(goal), coeff_a(a), coeff_b(b) { } AStarHeuristic(VertexDescriptor goal): m_goal(goal), coeff_a(0.5), coeff_b(0.5) { } double operator()(VertexDescriptor v){ return EuclideanDistance(v,m_goal); } }; 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() { } WeightMap(KisMagneticGraph g): m_graph(g) { } data_type& operator[](key_type const& k) { if (m_map.find(k) == m_map.end()) { double edge_gradient = (m_graph.getIntensity(k.first) + m_graph.getIntensity(k.second))/2; m_map[k] = EuclideanDistance(k.first, k.second) * (edge_gradient + 1); } return m_map[k]; } private: std::map m_map; KisMagneticGraph m_graph; }; QRect KisMagneticWorker::calculateRect(QPoint p1, QPoint p2, int radius) const { + // I am sure there is a simpler version of it which exists but well + // Calculates a bounding rectangle based on the radius, + // -------------------------------- + // | ------------------- | + // | | A* | | + // | | | | + // | | *B| | + // | ------------------- | + // -------------------------------- 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) { QRect rect = calculateRect(begin, end, radius); KisGaussianKernel::applyLoG(dev, rect, 2, 1.0, QBitArray(), 0); KisLazyFillTools::normalizeAndInvertAlpha8Device(dev, rect); VertexDescriptor goal(end); VertexDescriptor start(begin); KisMagneticGraph g(dev, rect); // How many maps does it require? + // Take a look here, if it doesn't make sense, https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/astar_search.html PredecessorMap pmap; DistanceMap dmap(std::numeric_limits::max()); dmap[start] = 0; std::map rmap; std::map cmap; std::map imap; WeightMap wmap(g); AStarHeuristic heuristic(goal); 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(QPointF(u.x,u.y)); - //qDebug() << g.getIntensity(u); } } result.push_back(QPoint(start.x,start.y)); return result; } diff --git a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc index 80cc21e89c..0a3a44030d 100644 --- a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc +++ b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc @@ -1,77 +1,117 @@ /* * 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(dev, rect, "main", "dd"); const QPoint startPos(40, 10); const QPoint endPos(50, 65); auto points = worker.computeEdge(grayscaleDev, 10, startPos, endPos); KIS_DUMP_DEVICE_2(grayscaleDev, rect, "draw", "dd"); - QImage img = dev->convertToQImage(0, rect); - img = img.convertToFormat(QImage::Format_ARGB32); - QPainter gc(&img); - - QPainterPath path(points[0]); - for (int i = 1; i < points.size(); i++) { - path.lineTo(points[i]); - qDebug() << points[i]; - } - - gc.setPen(Qt::blue); - gc.drawPath(path); - - gc.setPen(Qt::green); - gc.drawEllipse(startPos, 3, 3); - gc.setPen(Qt::red); - gc.drawEllipse(endPos, 2, 2); - - img.save("result.png"); + QVector result = { QPointF(50,65), + QPointF(49,64), + QPointF(48,63), + QPointF(47,62), + QPointF(46,61), + QPointF(45,60), + QPointF(44,59), + QPointF(44,58), + QPointF(44,57), + QPointF(44,56), + QPointF(44,55), + QPointF(44,54), + QPointF(44,53), + QPointF(44,52), + QPointF(44,51), + QPointF(44,50), + QPointF(44,49), + QPointF(44,48), + QPointF(44,47), + QPointF(44,46), + QPointF(44,45), + QPointF(44,44), + QPointF(44,43), + QPointF(44,42), + QPointF(43,41), + QPointF(43,40), + QPointF(43,39), + QPointF(44,38), + QPointF(44,37), + QPointF(44,36), + QPointF(44,35), + QPointF(44,34), + QPointF(44,33), + QPointF(44,32), + QPointF(44,31), + QPointF(44,30), + QPointF(44,29), + QPointF(44,28), + QPointF(44,27), + QPointF(44,26), + QPointF(44,25), + QPointF(44,24), + QPointF(44,23), + QPointF(44,22), + QPointF(44,21), + QPointF(44,20), + QPointF(44,19), + QPointF(44,18), + QPointF(43,17), + QPointF(44,16), + QPointF(44,15), + QPointF(44,14), + QPointF(44,13), + QPointF(43,12), + QPointF(42,11), + QPointF(41,11), + QPointF(40,10)}; + + QCOMPARE(result, points); } QTEST_MAIN(KisMagneticWorkerTest)