poly_containment_index.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 *
 * 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 3
 * 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-3.0.html
 * or you may search the http://www.gnu.org website for the version 3 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */
 
#ifndef POLY_CONTAINMENT_INDEX_H
#define POLY_CONTAINMENT_INDEX_H
 
#include <climits>
#include <cstdint>
#include <vector>
 
#include <geometry/rtree/packed_rtree.h>
#include <geometry/seg.h>
#include <geometry/shape_poly_set.h>
#include <math/util.h>
#include <math/vector2d.h>

class POLY_CONTAINMENT_INDEX
{
public:
    POLY_CONTAINMENT_INDEX() = default;

    void Build( const SHAPE_POLY_SET& aPolySet )
    {
        m_outlineCount = aPolySet.OutlineCount();
 
        KIRTREE::PACKED_RTREE<intptr_t, int, 2>::Builder builder;
 
        for( int outlineIdx = 0; outlineIdx < m_outlineCount; outlineIdx++ )
        {
            const SHAPE_LINE_CHAIN& outline = aPolySet.COutline( outlineIdx );
            int                     ptCount = outline.PointCount();
 
            if( ptCount < 3 )
                continue;
 
            for( int j = 0; j < ptCount; j++ )
            {
                const VECTOR2I& p1 = outline.CPoint( j );
                const VECTOR2I& p2 = outline.CPoint( ( j + 1 ) % ptCount );
 
                intptr_t idx = static_cast<intptr_t>( m_segments.size() );
                m_segments.push_back( { p1, p2, outlineIdx } );
 
                int min[2] = { std::min( p1.x, p2.x ), std::min( p1.y, p2.y ) };
                int max[2] = { std::max( p1.x, p2.x ), std::max( p1.y, p2.y ) };
                builder.Add( min, max, idx );
            }
        }
 
        m_tree = builder.Build();
    }

    bool Contains( const VECTOR2I& aPt, int aAccuracy = 0 ) const
    {
        if( m_segments.empty() )
            return false;
 
        // Most polygon sets have very few outlines, so use a stack buffer to avoid
        // per-query heap allocation.
        int  crossingsStack[8] = {};
        int* crossings = crossingsStack;
        std::vector<int> crossingsHeap;
 
        if( m_outlineCount > 8 )
        {
            crossingsHeap.resize( m_outlineCount, 0 );
            crossings = crossingsHeap.data();
        }
 
        // Only segments whose X extent reaches past aPt.x can produce a rightward ray crossing.
        int searchMin[2] = { aPt.x, aPt.y };
        int searchMax[2] = { INT_MAX, aPt.y };
 
        auto rayCrossVisitor = [&]( intptr_t idx ) -> bool
        {
            const EDGE& seg = m_segments[idx];
            const VECTOR2I& p1 = seg.p1;
            const VECTOR2I& p2 = seg.p2;
 
            if( ( p1.y >= aPt.y ) == ( p2.y >= aPt.y ) )
                return true;
 
            const VECTOR2I diff = p2 - p1;
            const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
 
            if( aPt.x - p1.x < d )
                crossings[seg.outlineIdx]++;
 
            return true;
        };
 
        m_tree.Search( searchMin, searchMax, rayCrossVisitor );
 
        for( int i = 0; i < m_outlineCount; i++ )
        {
            if( crossings[i] & 1 )
                return true;
        }
 
        if( aAccuracy > 1 )
        {
            int edgeMin[2] = { aPt.x - aAccuracy, aPt.y - aAccuracy };
            int edgeMax[2] = { aPt.x + aAccuracy, aPt.y + aAccuracy };
            SEG::ecoord accuracySq = SEG::Square( aAccuracy );
            bool onEdge = false;
 
            auto edgeDistVisitor = [&]( intptr_t idx ) -> bool
            {
                const EDGE& seg = m_segments[idx];
                SEG s( seg.p1, seg.p2 );
 
                if( s.SquaredDistance( aPt ) <= accuracySq )
                {
                    onEdge = true;
                    return false;
                }
 
                return true;
            };
 
            m_tree.Search( edgeMin, edgeMax, edgeDistVisitor );
 
            return onEdge;
        }
 
        return false;
    }
 
private:
    struct EDGE
    {
        VECTOR2I p1;
        VECTOR2I p2;
        int      outlineIdx;
    };
 
    std::vector<EDGE>                      m_segments;
    KIRTREE::PACKED_RTREE<intptr_t, int, 2> m_tree;
    int                                    m_outlineCount = 0;
};
 
#endif // POLY_CONTAINMENT_INDEX_H