KiCad PCB EDA Suite
poly_grid_partition.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KICAD, a free EDA CAD application.
3  *
4  * Copyright (C) 2016-2017 CERN
5  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #ifndef __POLY_GRID_PARTITION_H
27 #define __POLY_GRID_PARTITION_H
28 
29 
30 #include <algorithm>
31 #include <functional>
32 #include <set>
33 #include <unordered_map>
34 #include <vector>
35 
36 #include <geometry/seg.h>
38 #include <geometry/shape_rect.h>
39 #include <math/vector2d.h>
40 
68 {
69 public:
70  POLY_GRID_PARTITION( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize );
71 
72  int ContainsPoint( const VECTOR2I& aP, int aClearance = 0 );
73 
74  const BOX2I& BBox() const
75  {
76  return m_bbox;
77  }
78 
79 private:
80  enum HASH_FLAG
81  {
82  LEAD_EDGE = 1,
84  };
85 
86  using EDGE_LIST = std::vector<int>;
87 
88  template <class T>
89  inline void hash_combine( std::size_t& seed, const T& v )
90  {
91  std::hash<T> hasher;
92  seed ^= hasher( v ) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
93  }
94 
95  struct segsEqual
96  {
97  bool operator()( const SEG& a, const SEG& b ) const
98  {
99  return (a.A == b.A && a.B == b.B) || (a.A == b.B && a.B == b.A);
100  }
101  };
102 
103  struct segHash
104  {
105  std::size_t operator()( const SEG& a ) const
106  {
107  return a.A.x + a.B.x + a.A.y + a.B.y;
108  }
109  };
110 
111  int containsPoint( const VECTOR2I& aP, bool debug = false ) const;
112 
113  bool checkClearance( const VECTOR2I& aP, int aClearance );
114 
115  int rescale_trunc( int aNumerator, int aValue, int aDenominator ) const;
116 
117  // converts grid cell coordinates to the polygon coordinates
118  const VECTOR2I grid2poly( const VECTOR2I& p ) const;
119 
120  int grid2polyX( int x ) const;
121 
122  int grid2polyY( int y ) const;
123 
124  const VECTOR2I poly2grid( const VECTOR2I& p ) const;
125 
126  int poly2gridX( int x ) const;
127 
128  int poly2gridY( int y ) const;
129 
130  void build( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize );
131 
132  bool inRange( int v1, int v2, int x ) const;
133 
134  struct SCAN_STATE
135  {
137  {
138  dist_prev = INT_MAX;
139  dist_max = INT_MAX;
140  nearest = -1;
141  nearest_prev = -1;
142  };
143 
144  int dist_prev;
145  int dist_max;
147  int nearest;
148  };
149 
150  void scanCell( SCAN_STATE& state, const EDGE_LIST& cell, const VECTOR2I& aP, int cx,
151  int cy ) const;
152 
153 private:
157  std::vector<int> m_flags;
158  std::vector<EDGE_LIST> m_grid;
159 };
160 
161 #endif
const VECTOR2I poly2grid(const VECTOR2I &p) const
void build(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
void scanCell(SCAN_STATE &state, const EDGE_LIST &cell, const VECTOR2I &aP, int cx, int cy) const
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
SHAPE_LINE_CHAIN m_outline
int ContainsPoint(const VECTOR2I &aP, int aClearance=0)
std::size_t operator()(const SEG &a) const
bool inRange(int v1, int v2, int x) const
int grid2polyY(int y) const
std::vector< int > m_flags
int poly2gridX(int x) const
std::vector< EDGE_LIST > m_grid
const BOX2I & BBox() const
POLY_GRID_PARTITION(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
int containsPoint(const VECTOR2I &aP, bool debug=false) const
bool operator()(const SEG &a, const SEG &b) const
std::vector< int > EDGE_LIST
int grid2polyX(int x) const
Definition: seg.h:40
void hash_combine(std::size_t &seed, const T &v)
const VECTOR2I grid2poly(const VECTOR2I &p) const
Represent a polyline (an zero-thickness chain of connected line segments).
VECTOR2I A
Definition: seg.h:48
int poly2gridY(int y) const
Provide a fast test for point inside polygon.
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const
bool checkClearance(const VECTOR2I &aP, int aClearance)
VECTOR2I B
Definition: seg.h:49