diff --git a/plugins/tools/selectiontools/KisMagneticWorker.cc b/plugins/tools/selectiontools/KisMagneticWorker.cc index 3e6d3681f2..f58f1c5ef7 100644 --- a/plugins/tools/selectiontools/KisMagneticWorker.cc +++ b/plugins/tools/selectiontools/KisMagneticWorker.cc @@ -1,220 +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; + KisMagneticGraph m_graph; 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, double a, double b, KisMagneticGraph g): + m_pmap(pmap), m_goal(goal), coeff_a(a), coeff_b(b), m_graph(g) { } - AStarHeuristic(VertexDescriptor goal, PredecessorMap pmap): - m_pmap(pmap), m_goal(goal), coeff_a(0.5), coeff_b(0.5) + AStarHeuristic(VertexDescriptor goal, PredecessorMap pmap, KisMagneticGraph g): + m_pmap(pmap), m_goal(goal), coeff_a(0.5), coeff_b(0.5), m_graph(g) { } 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); + double i = m_graph.getIntensity(QPoint(v.x,v.y)); + return (coeff_a * di + coeff_b * (dm - dz)) * (i+1) ; } }; 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) { 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); + AStarHeuristic heuristic(goal, pmap, g); 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 df9133b9f0..13d31f00c0 100644 --- a/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc +++ b/plugins/tools/selectiontools/tests/KisMagneticWorkerTest.cc @@ -1,52 +1,54 @@ /* * 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(dev, rect, "main", "dd"); + auto points = worker.computeEdge(grayscaleDev, 2, QPoint(30,10), QPoint(50,65)); + KIS_DUMP_DEVICE_2(grayscaleDev, rect, "draw", "dd"); + KisPainter p(grayscaleDev); KIS_DUMP_DEVICE_2(grayscaleDev, rect, "draw", "dd"); } QTEST_MAIN(KisMagneticWorkerTest)