Horizon
Loading...
Searching...
No Matches
poly_grid_partition.h
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>
37#include <geometry/shape_line_chain.h>
38#include <geometry/shape_rect.h>
39#include <math/vector2d.h>
40
68{
69public:
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
79private:
80 enum HASH_FLAG
81 {
82 LEAD_EDGE = 1,
83 TRAIL_EDGE = 2,
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 {
136 SCAN_STATE()
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;
146 int nearest_prev;
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
153private:
154 int m_gridSize;
155 SHAPE_LINE_CHAIN m_outline;
156 BOX2I m_bbox;
157 std::vector<int> m_flags;
158 std::vector<EDGE_LIST> m_grid;
159};
160
161#endif
Provide a fast test for point inside polygon.
Definition poly_grid_partition.h:68
Definition seg.h:41
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition shape_line_chain.h:81