vertex_set.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, see <https://www.gnu.org/licenses/>.
 *
 * Based on Uniform Plane Subdivision algorithm from Lamot, Marko, and Borut Žalik.
 * "A fast polygon triangulation algorithm based on uniform plane subdivision."
 * Computers & graphics 27, no. 2 (2003): 239-253.
 *
 * Code derived from:
 * K-3D which is Copyright (c) 2005-2006, Romain Behar, GPL-2, license above
 * earcut which is Copyright (c) 2016, Mapbox, ISC
 *
 * ISC License:
 * Permission to use, copy, modify, and/or distribute this software for any purpose
 * with or without fee is hereby granted, provided that the above copyright notice
 * and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
 * THIS SOFTWARE.
 *
 */
 
#ifndef VERTEX_SET_H
#define VERTEX_SET_H
 
#include <algorithm>
#include <deque>
#include <vector>
 
#include <math/box2.h>
#include <geometry/shape_line_chain.h>
 
class VERTEX_SET;
 
class VERTEX
{
    public:
 
    VERTEX( int aIndex, double aX, double aY, VERTEX_SET* aParent, void* aUserData = nullptr ) :
            i( aIndex ),
            x( aX ),
            y( aY ),
            parent( aParent ),
            m_userData( aUserData )
    {
    }
 
    VERTEX& operator=( const VERTEX& ) = delete;
    VERTEX& operator=( VERTEX&& ) = delete;
 
    bool operator==( const VERTEX& rhs ) const
    {
        return this->x == rhs.x && this->y == rhs.y;
    }
    bool operator!=( const VERTEX& rhs ) const { return !( *this == rhs ); }
 
    void* GetUserData() const { return m_userData; }

    void remove()
    {
        next->prev = prev;
        prev->next = next;
 
        if( prevZ )
            prevZ->nextZ = nextZ;
 
        if( nextZ )
            nextZ->prevZ = prevZ;
 
        next = nullptr;
        prev = nullptr;
        nextZ = nullptr;
        prevZ = nullptr;
    }
 
 

    VERTEX* split( VERTEX* b );
 
    void updateOrder();

    void updateList()
    {
        VERTEX* p = next;
 
        while( p != this )
        {
            if( *p == *p->next )
            {
                p = p->prev;
                p->next->remove();
 
                if( p == p->next )
                    break;
            }
 
            p->updateOrder();
            p = p->next;
        };
 
        updateOrder();
        zSort();
    }

    void zSort()
    {
        std::vector<VERTEX*> queue;
 
        queue.push_back( this );
 
        for( VERTEX* p = next; p && p != this; p = p->next )
            queue.push_back( p );
 
        std::sort( queue.begin(), queue.end(), []( const VERTEX* a, const VERTEX* b )
        {
            if( a->z != b->z )
                return a->z < b->z;
 
            if( a->x != b->x )
                return a->x < b->x;
 
            if( a->y != b->y )
                return a->y < b->y;
 
            return a->i < b->i;
        } );
 
        VERTEX* prev_elem = nullptr;
 
        for( VERTEX* elem : queue )
        {
            // A cached ear blocker is only valid while it shares this z-order list
            elem->m_earBlocker = nullptr;
 
            if( prev_elem )
                prev_elem->nextZ = elem;
 
            elem->prevZ = prev_elem;
            prev_elem = elem;
        }
 
        prev_elem->nextZ = nullptr;
    }
 

    bool inTriangle( const VERTEX& a, const VERTEX& b, const VERTEX& c )
    {
        return     ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
                && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
                && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
    }

    double area( const VERTEX* aEnd = nullptr ) const
    {
        const VERTEX* p = this;
        double a = 0.0;
 
        do
        {
            a += ( p->x + p->next->x ) * ( p->next->y - p->y );
            p = p->next;
        } while( p != this && p != aEnd );
 
        if( p != this )
            a += ( p->x + x ) * ( y - p->y );
 
        return a / 2;
    }

    bool isEar( bool aMatchUserData = false ) const;
 
    const int    i;
    const double x;
    const double y;
    VERTEX_SET*  parent;
 
    // previous and next vertices nodes in a polygon ring
    VERTEX* prev = nullptr;
    VERTEX* next = nullptr;
 
    // z-order curve value
    uint32_t z = 0;
 
    // previous and next nodes in z-order
    VERTEX* prevZ = nullptr;
    VERTEX* nextZ = nullptr;
 
    void* m_userData = nullptr;
 
    // Last vertex found inside this vertex's ear, rechecked before rescanning the z-order list
    mutable VERTEX* m_earBlocker = nullptr;
 
    // Whether the last VERTEX_SET::buildReflexIndex() call recorded this vertex
    bool m_inReflexIndex = false;
};
 
class VERTEX_SET
{
    friend class VERTEX;
 
public:
    VERTEX_SET( int aSimplificationLevel )
    {
        m_simplificationLevel = aSimplificationLevel * ( VECTOR2I::extended_type ) aSimplificationLevel;
    }
    ~VERTEX_SET() {}
 
    void SetBoundingBox( const BOX2I& aBBox );

    VERTEX* insertVertex( int aIndex, const VECTOR2I& pt, VERTEX* last, void* aUserData = nullptr );

    VERTEX* createList( const SHAPE_LINE_CHAIN& points, VERTEX* aTail = nullptr, void* aUserData = nullptr );
 
protected:

    VERTEX* getNextOutlineVertex( const VERTEX* aPt ) const;

    VERTEX* getPrevOutlineVertex( const VERTEX* aPt ) const;

    bool    locallyInside( const VERTEX* a, const VERTEX* b ) const;

    bool middleInside( const VERTEX* a, const VERTEX* b ) const;

    bool    same_point( const VERTEX* aA, const VERTEX* aB ) const;

    uint32_t zOrder( const double aX, const double aY ) const;

    double  area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const;

    void buildReflexIndex( VERTEX* aStart );
 
    struct REFLEX_ENTRY
    {
        uint32_t z;
        double   x;
        double   y;
        VERTEX*  v;
    };
 
    BOX2I                     m_bbox;
    std::deque<VERTEX>        m_vertices;
    VECTOR2I::extended_type   m_simplificationLevel;
    std::vector<REFLEX_ENTRY> m_reflexIndex;
    bool                      m_reflexIndexValid = false;
};
 
 
 
#endif // VERTEX_SET_H