File indexing completed on 2024-05-26 04:34:31
0001 /* 0002 * SPDX-FileCopyrightText: 2019 Kuntal Majumder <hellozee@disroot.org> 0003 * 0004 * SPDX-License-Identifier: LGPL-2.1-only 0005 */ 0006 0007 #ifndef KISMAGNETICGRAPH_H 0008 #define KISMAGNETICGRAPH_H 0009 0010 #include <boost/operators.hpp> 0011 #include <boost/graph/graph_traits.hpp> 0012 #include <kis_paint_device.h> 0013 #include <kis_random_accessor_ng.h> 0014 0015 #include <QDebug> 0016 #include <QRect> 0017 #include <QColor> 0018 0019 struct VertexDescriptor { 0020 long x, y; 0021 0022 enum Direction { 0023 MIN = 0, 0024 N = MIN, S, E, W, NW, NE, SW, SE, NONE 0025 }; 0026 0027 VertexDescriptor(long _x, long _y) : 0028 x(_x), y(_y) 0029 { } 0030 0031 VertexDescriptor(QPoint pt) : 0032 x(pt.x()), y(pt.y()) 0033 { } 0034 0035 VertexDescriptor() : 0036 x(0), y(0) 0037 { } 0038 0039 bool operator == (VertexDescriptor const &rhs) const 0040 { 0041 return rhs.x == x && rhs.y == y; 0042 } 0043 0044 bool operator == (QPoint const &rhs) const 0045 { 0046 return rhs.x() == x && rhs.y() == y; 0047 } 0048 0049 bool operator != (VertexDescriptor const &rhs) const 0050 { 0051 return rhs.x != x || rhs.y != y; 0052 } 0053 0054 bool operator < (VertexDescriptor const &rhs) const 0055 { 0056 return x < rhs.x || (x == rhs.x && y < rhs.y); 0057 } 0058 0059 // returns one of the 8 neighboring pixel based on the direction 0060 // it gives out multiple warnings, but I am lazy, sorry 0061 VertexDescriptor neighbor(Direction direction) const 0062 { 0063 int dx = 0, dy = 0; 0064 0065 switch (direction) { 0066 case W: 0067 Q_FALLTHROUGH(); 0068 case SW: 0069 Q_FALLTHROUGH(); 0070 case NW: 0071 dx = -1; 0072 break; 0073 case E: 0074 Q_FALLTHROUGH(); 0075 case SE: 0076 Q_FALLTHROUGH(); 0077 case NE: 0078 dx = 1; 0079 default: 0080 ; 0081 } 0082 0083 switch (direction) { 0084 case N: 0085 Q_FALLTHROUGH(); 0086 case NW: 0087 Q_FALLTHROUGH(); 0088 case NE: 0089 dy = -1; 0090 break; 0091 case S: 0092 Q_FALLTHROUGH(); 0093 case SW: 0094 Q_FALLTHROUGH(); 0095 case SE: 0096 dy = 1; 0097 default: 0098 ; 0099 } 0100 0101 VertexDescriptor const neighbor(x + dx, y + dy); 0102 return neighbor; 0103 } // neighbor 0104 }; 0105 0106 QDebug operator << (QDebug dbg, const VertexDescriptor &v) 0107 { 0108 dbg.nospace() << "(" << v.x << ", " << v.y << ")"; 0109 return dbg.space(); 0110 } 0111 0112 struct neighbour_iterator; 0113 0114 struct KisMagneticGraph { 0115 typedef KisMagneticGraph type; 0116 0117 KisMagneticGraph(){ } 0118 0119 KisMagneticGraph(KisPaintDeviceSP dev) : 0120 m_dev(dev) 0121 { 0122 m_randAccess = m_dev->createRandomAccessorNG(); 0123 } 0124 0125 KisMagneticGraph(KisPaintDeviceSP dev, QRect graphRect) : 0126 m_rect(graphRect), m_dev(dev) 0127 { 0128 m_randAccess = m_dev->createRandomAccessorNG(); 0129 } 0130 0131 typedef VertexDescriptor vertex_descriptor; 0132 typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor; 0133 typedef boost::undirected_tag directed_category; 0134 typedef boost::disallow_parallel_edge_tag edge_parallel_category; 0135 typedef boost::incidence_graph_tag traversal_category; 0136 typedef neighbour_iterator out_edge_iterator; 0137 typedef unsigned degree_size_type; 0138 0139 0140 quint8 getIntensity(VertexDescriptor pt) 0141 { 0142 m_randAccess->moveTo(pt.x, pt.y); 0143 quint8 val = *(m_randAccess->rawData()); 0144 return val; 0145 } 0146 0147 unsigned outDegree(VertexDescriptor pt) 0148 { 0149 // corners 0150 if (pt == m_rect.topLeft() || pt == m_rect.topRight() || 0151 pt == m_rect.bottomLeft() || pt == m_rect.bottomRight()) 0152 { 0153 if (m_rect.width() == 1 || m_rect.height() == 1) 0154 return 1; 0155 0156 return 3; 0157 } 0158 0159 // edges 0160 if (pt.x == m_rect.topLeft().x() || pt.y == m_rect.topLeft().y() || 0161 pt.x == m_rect.bottomRight().x() || pt.y == m_rect.bottomRight().y()) 0162 { 0163 if (m_rect.width() == 1 || m_rect.height() == 1) 0164 return 2; 0165 0166 return 5; 0167 } 0168 return 8; 0169 } 0170 0171 QRect m_rect; 0172 0173 private: 0174 KisPaintDeviceSP m_dev; 0175 KisRandomAccessorSP m_randAccess; 0176 }; 0177 0178 struct neighbour_iterator : public boost::iterator_facade<neighbour_iterator 0179 , std::pair<VertexDescriptor, VertexDescriptor> 0180 , boost::forward_traversal_tag 0181 , std::pair<VertexDescriptor, VertexDescriptor> > { 0182 neighbour_iterator(VertexDescriptor v, KisMagneticGraph g, VertexDescriptor::Direction d) : 0183 m_point(v), m_direction(d), m_graph(g) 0184 { } 0185 0186 neighbour_iterator() 0187 { } 0188 0189 std::pair<VertexDescriptor, VertexDescriptor> operator * () const 0190 { 0191 std::pair<VertexDescriptor, 0192 VertexDescriptor> const result = std::make_pair(m_point, m_point.neighbor(m_direction)); 0193 return result; 0194 } 0195 0196 void operator ++ () 0197 { 0198 m_direction = static_cast<VertexDescriptor::Direction>(int(m_direction) + 1); 0199 VertexDescriptor next = m_point.neighbor(m_direction); 0200 if (m_direction == VertexDescriptor::NONE) { 0201 return; 0202 } 0203 if (!m_graph.m_rect.contains(next.x, next.y)) { 0204 operator ++ (); 0205 } 0206 } 0207 0208 bool operator == (neighbour_iterator const& that) const 0209 { 0210 return m_point == that.m_point && m_direction == that.m_direction; 0211 } 0212 0213 bool equal(neighbour_iterator const& that) const 0214 { 0215 return operator == (that); 0216 } 0217 0218 void increment() 0219 { 0220 operator ++ (); 0221 } 0222 0223 private: 0224 VertexDescriptor m_point; 0225 VertexDescriptor::Direction m_direction {VertexDescriptor::NONE}; 0226 KisMagneticGraph m_graph; 0227 }; 0228 0229 // Requirements for an Incidence Graph, 0230 // https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/IncidenceGraph.html 0231 0232 namespace boost { 0233 template <> 0234 struct graph_traits<KisMagneticGraph> { 0235 typedef typename KisMagneticGraph::vertex_descriptor vertex_descriptor; 0236 typedef typename KisMagneticGraph::edge_descriptor edge_descriptor; 0237 typedef typename KisMagneticGraph::out_edge_iterator out_edge_iterator; 0238 typedef typename KisMagneticGraph::directed_category directed_category; 0239 typedef typename KisMagneticGraph::edge_parallel_category edge_parallel_category; 0240 typedef typename KisMagneticGraph::traversal_category traversal_category; 0241 typedef typename KisMagneticGraph::degree_size_type degree_size_type; 0242 0243 typedef void in_edge_iterator; 0244 typedef void vertex_iterator; 0245 typedef void vertices_size_type; 0246 typedef void edge_iterator; 0247 typedef void edges_size_type; 0248 }; 0249 } 0250 0251 typename KisMagneticGraph::vertex_descriptor source(typename KisMagneticGraph::edge_descriptor e, KisMagneticGraph g) 0252 { 0253 Q_UNUSED(g); 0254 return e.first; 0255 } 0256 0257 typename KisMagneticGraph::vertex_descriptor target(typename KisMagneticGraph::edge_descriptor e, KisMagneticGraph g) 0258 { 0259 Q_UNUSED(g); 0260 return e.second; 0261 } 0262 0263 std::pair<KisMagneticGraph::out_edge_iterator, KisMagneticGraph::out_edge_iterator> out_edges( 0264 typename KisMagneticGraph::vertex_descriptor v, KisMagneticGraph g) 0265 { 0266 return std::make_pair( 0267 KisMagneticGraph::out_edge_iterator(v, g, VertexDescriptor::Direction::MIN), 0268 KisMagneticGraph::out_edge_iterator(v, g, VertexDescriptor::Direction::NONE) 0269 ); 0270 } 0271 0272 typename KisMagneticGraph::degree_size_type out_degree(typename KisMagneticGraph::vertex_descriptor v, 0273 KisMagneticGraph g) 0274 { 0275 return g.outDegree(v); 0276 } 0277 0278 #endif // ifndef KISMAGNETICGRAPH_H