poly_grid_partition.h

Go to the documentation of this file.

/*
 * This program source code file is part of KICAD, a free EDA CAD application.
 *
 * Copyright (C) 2016-2017 CERN
 * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
 * @author Tomasz Wlostowski <[email protected]>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */

#ifndef __POLY_GRID_PARTITION_H
#define __POLY_GRID_PARTITION_H


#include <algorithm>
#include <functional>
#include <set>
#include <unordered_map>
#include <vector>

#include <geometry/seg.h>
#include <geometry/shape_line_chain.h>
#include <geometry/shape_rect.h>
#include <math/vector2d.h>

class POLY_GRID_PARTITION
{
public:
 POLY_GRID_PARTITION( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize );

 int ContainsPoint( const VECTOR2I& aP, int aClearance = 0 );

 const BOX2I& BBox() const
 {
 return m_bbox;
 }

private:
 enum HASH_FLAG
 {
 LEAD_EDGE = 1,
 TRAIL_EDGE = 2,
 };

 using EDGE_LIST = std::vector<int>;

 template <class T>
 inline void hash_combine( std::size_t& seed, const T& v )
 {
 std::hash<T> hasher;
 seed ^= hasher( v ) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
 }

 struct segsEqual
 {
 bool operator()( const SEG& a, const SEG& b ) const
 {
 return (a.A == b.A && a.B == b.B) || (a.A == b.B && a.B == b.A);
 }
 };

 struct segHash
 {
 std::size_t operator()( const SEG& a ) const
 {
 return a.A.x + a.B.x + a.A.y + a.B.y;
 }
 };

 int containsPoint( const VECTOR2I& aP, bool debug = false ) const;

 bool checkClearance( const VECTOR2I& aP, int aClearance );

 int rescale_trunc( int aNumerator, int aValue, int aDenominator ) const;

 // converts grid cell coordinates to the polygon coordinates
 const VECTOR2I grid2poly( const VECTOR2I& p ) const;

 int grid2polyX( int x ) const;

 int grid2polyY( int y ) const;

 const VECTOR2I poly2grid( const VECTOR2I& p ) const;

 int poly2gridX( int x ) const;

 int poly2gridY( int y ) const;

 void build( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize );

 bool inRange( int v1, int v2, int x ) const;

 struct SCAN_STATE
 {
 SCAN_STATE()
 {
 dist_prev = INT_MAX;
 dist_max = INT_MAX;
 nearest = -1;
 nearest_prev = -1;
 };

 int dist_prev;
 int dist_max;
 int nearest_prev;
 int nearest;
 };

 void scanCell( SCAN_STATE& state, const EDGE_LIST& cell, const VECTOR2I& aP, int cx,
 int cy ) const;

private:
 int m_gridSize;
 SHAPE_LINE_CHAIN m_outline;
 BOX2I m_bbox;
 std::vector<int> m_flags;
 std::vector<EDGE_LIST> m_grid;
};

#endif