diff --git a/plugins/tools/selectiontools/KisMagneticGraph.h b/plugins/tools/selectiontools/KisMagneticGraph.h index 1a2b8ade11..7d4c2cb79a 100644 --- a/plugins/tools/selectiontools/KisMagneticGraph.h +++ b/plugins/tools/selectiontools/KisMagneticGraph.h @@ -1,215 +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 #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(VertexDescriptor pt){ - QColor *col = new QColor; - m_dev->pixel(pt.x, pt.y, col); - double intensity = col->blackF(); - delete col; - return intensity; + KisRandomAccessorSP randAccess = m_dev->createRandomAccessorNG(m_dev->exactBounds().x(),m_dev->exactBounds().y()); + randAccess->moveTo(pt.x, pt.y); + qint8 val = *(randAccess->rawData()); + return std::abs(val); } private: KisPaintDeviceSP m_dev; }; struct neighbour_iterator : public boost::iterator_facade, boost::forward_traversal_tag, std::pair> { 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){ 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){ 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 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, 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; } #endif diff --git a/plugins/tools/selectiontools/KisMagneticWorker.cc b/plugins/tools/selectiontools/KisMagneticWorker.cc index 8eb542cabe..c3cd988f2a 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.cc +++ b/plugins/tools/selectiontools/KisMagneticWorker.cc @@ -1,227 +1,222 @@ /* * 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); - qDebug() << v << prev; 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() { } 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 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); + KisGaussianKernel::applyLoG(dev, rect, 2, -10.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(g); AStarHeuristic heuristic(goal, pmap); 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)); } } result.push_back(QPoint(start.x,start.y)); - for(auto val: result){ - qDebug() << val; - } - return result; } diff --git a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc index 2a4637b5c0..8833a12899 100644 --- a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc +++ b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc @@ -1,77 +1,77 @@ /* * 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 QPointF startPos(30, 10); - const QPointF endPos(50, 65); + const QPoint startPos(40, 10); + const QPoint endPos(50, 65); - auto points = worker.computeEdge(grayscaleDev, 10, QPoint(30,10), QPoint(50,65)); + auto points = worker.computeEdge(grayscaleDev, 10, startPos, endPos); KIS_DUMP_DEVICE_2(grayscaleDev, rect, "draw", "dd"); QImage img = grayscaleDev->convertToQImage(0, rect); img = img.convertToFormat(QImage::Format_ARGB32); QPainter gc(&img); - QPainterPath path; - path.moveTo(points[0]); + QPainterPath path(points[0]); for (int i = 1; i < points.size(); i++) { path.lineTo(points[i]); + qDebug() << points[i]; } - gc.setPen(Qt::white); + 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"); } QTEST_MAIN(KisMagneticWorkerTest)