mirror of
https://gitlab.com/kicad/code/kicad.git
synced 2024-11-28 00:31:20 +00:00
8dda9b37fa
Edge cases can happen where point + clearance is larger than the bbox. This can cause the zOrder min and max to get switched as max get a high bit and is negative. Clamping to limit the input values and using uint32 for the output solves the corner case
350 lines
10 KiB
C++
350 lines
10 KiB
C++
/*
|
|
* This program source code file is part of KiCad, a free EDA CAD application.
|
|
*
|
|
* Copyright (C) 20218 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/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
|
|
*
|
|
* 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 <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; }
|
|
|
|
/**
|
|
* Remove the node from the linked list and z-ordered linked list.
|
|
*/
|
|
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;
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
* Split the referenced polygon between the reference point and
|
|
* vertex b, assuming they are in the same polygon. Notes that while we
|
|
* create a new vertex pointer for the linked list, we maintain the same
|
|
* vertex index value from the original polygon. In this way, we have
|
|
* two polygons that both share the same vertices.
|
|
*
|
|
* @return the newly created vertex in the polygon that does not include the
|
|
* reference vertex.
|
|
*/
|
|
VERTEX* split( VERTEX* b );
|
|
|
|
void updateOrder();
|
|
|
|
/**
|
|
* After inserting or changing nodes, this function should be called to
|
|
* remove duplicate vertices and ensure z-ordering is correct.
|
|
*/
|
|
void updateList()
|
|
{
|
|
VERTEX* p = next;
|
|
|
|
while( p != this )
|
|
{
|
|
/**
|
|
* Remove duplicates
|
|
*/
|
|
if( *p == *p->next )
|
|
{
|
|
p = p->prev;
|
|
p->next->remove();
|
|
|
|
if( p == p->next )
|
|
break;
|
|
}
|
|
|
|
p->updateOrder();
|
|
p = p->next;
|
|
};
|
|
|
|
updateOrder();
|
|
zSort();
|
|
}
|
|
|
|
/**
|
|
* Sort all vertices in this vertex's list by their Morton code.
|
|
*/
|
|
void zSort()
|
|
{
|
|
std::deque<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 )
|
|
{
|
|
if( prev_elem )
|
|
prev_elem->nextZ = elem;
|
|
|
|
elem->prevZ = prev_elem;
|
|
prev_elem = elem;
|
|
}
|
|
|
|
prev_elem->nextZ = nullptr;
|
|
}
|
|
|
|
|
|
/**
|
|
* Check to see if triangle surrounds our current vertex
|
|
*/
|
|
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;
|
|
}
|
|
|
|
/**
|
|
* Returns the signed area of the polygon connected to the current vertex,
|
|
* optionally ending at a specified vertex.
|
|
*/
|
|
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;
|
|
}
|
|
|
|
/**
|
|
* Check whether the given vertex is in the middle of an ear.
|
|
*
|
|
* This works by walking forward and backward in zOrder to the limits of the minimal
|
|
* bounding box formed around the triangle, checking whether any points are located
|
|
* inside the given triangle.
|
|
*
|
|
* @param aMatchUserData if true, the user data of the vertices must match. This can be
|
|
* useful when the vertices come from different polygons.
|
|
*
|
|
*
|
|
* @return true if aEar is the apex point of a ear in the polygon.
|
|
*/
|
|
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;
|
|
};
|
|
|
|
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 );
|
|
|
|
/**
|
|
* Insert a vertex into the vertex set
|
|
* @param aIndex the index of the vertex
|
|
* @param pt the point to insert
|
|
* @param last the last vertex in the list
|
|
* @param aUserData user data to associate with the vertex
|
|
* @return the newly inserted vertex
|
|
*/
|
|
VERTEX* insertVertex( int aIndex, const VECTOR2I& pt, VERTEX* last, void* aUserData = nullptr );
|
|
|
|
/**
|
|
* Create a list of vertices from a line chain
|
|
* @param points the line chain to create the list from
|
|
* @param aTail the optional vertex to which to append the list
|
|
* @param aUserData user data to associate with the vertices
|
|
* @return the first vertex in the list
|
|
*/
|
|
VERTEX* createList( const SHAPE_LINE_CHAIN& points, VERTEX* aTail = nullptr, void* aUserData = nullptr );
|
|
|
|
protected:
|
|
|
|
/**
|
|
* Get the next vertex in the outline, avoiding steiner points
|
|
* and points that overlap with splits
|
|
* @param aPt the current vertex
|
|
* @return the next vertex in the outline
|
|
*/
|
|
VERTEX* getNextOutlineVertex( const VERTEX* aPt ) const;
|
|
|
|
/**
|
|
* Get the previous vertex in the outline, avoiding steiner points
|
|
* and points that overlap with splits
|
|
* @param aPt the current vertex
|
|
* @return the previous vertex in the outline
|
|
*/
|
|
VERTEX* getPrevOutlineVertex( const VERTEX* aPt ) const;
|
|
|
|
/**
|
|
* Check whether the segment from vertex a -> vertex b is inside the polygon
|
|
* around the immediate area of vertex a.
|
|
*
|
|
* We don't define the exact area over which the segment is inside but it is guaranteed to
|
|
* be inside the polygon immediately adjacent to vertex a.
|
|
*
|
|
* @return true if the segment from a->b is inside a's polygon next to vertex a.
|
|
*/
|
|
bool locallyInside( const VERTEX* a, const VERTEX* b ) const;
|
|
|
|
/**
|
|
* Check if the middle of the segment from a to b is inside the polygon
|
|
* @param a the first vertex
|
|
* @param b the second vertex
|
|
* @return true if the point is in the middle of the triangle
|
|
*/
|
|
bool middleInside( const VERTEX* a, const VERTEX* b ) const;
|
|
|
|
/**
|
|
* Check if two vertices are at the same point
|
|
* @param aA the first vertex
|
|
* @param aB the second vertex
|
|
* @return true if the vertices are at the same point
|
|
*/
|
|
bool same_point( const VERTEX* aA, const VERTEX* aB ) const;
|
|
|
|
/**
|
|
* Note that while the inputs are doubles, these are scaled
|
|
* by the size of the bounding box to fit into a 32-bit Morton code
|
|
* @return the Morton code for the point (aX, aY)
|
|
*/
|
|
uint32_t zOrder( const double aX, const double aY ) const;
|
|
|
|
/**
|
|
* @return the area of the triangle defined by the three vertices
|
|
*/
|
|
double area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const;
|
|
|
|
BOX2I m_bbox;
|
|
std::deque<VERTEX> m_vertices;
|
|
VECTOR2I::extended_type m_simplificationLevel;
|
|
};
|
|
|
|
|
|
|
|
#endif // VERTEX_SET_H
|