diff options
Diffstat (limited to 'include/geometry')
| -rw-r--r-- | include/geometry/rtree.h | 1905 | ||||
| -rw-r--r-- | include/geometry/seg.h | 384 | ||||
| -rw-r--r-- | include/geometry/shape.h | 171 | ||||
| -rw-r--r-- | include/geometry/shape_circle.h | 103 | ||||
| -rw-r--r-- | include/geometry/shape_convex.h | 189 | ||||
| -rw-r--r-- | include/geometry/shape_file_io.h | 69 | ||||
| -rw-r--r-- | include/geometry/shape_index.h | 363 | ||||
| -rw-r--r-- | include/geometry/shape_index_list.h | 291 | ||||
| -rw-r--r-- | include/geometry/shape_line_chain.h | 598 | ||||
| -rw-r--r-- | include/geometry/shape_poly_set.h | 374 | ||||
| -rw-r--r-- | include/geometry/shape_rect.h | 168 | ||||
| -rw-r--r-- | include/geometry/shape_segment.h | 101 |
12 files changed, 4716 insertions, 0 deletions
diff --git a/include/geometry/rtree.h b/include/geometry/rtree.h new file mode 100644 index 0000000..35ccadb --- /dev/null +++ b/include/geometry/rtree.h @@ -0,0 +1,1905 @@ +//TITLE +// +// R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING +// +//DESCRIPTION +// +// A C++ templated version of the RTree algorithm. +// For more information please read the comments in RTree.h +// +//AUTHORS +// +// * 1983 Original algorithm and test code by Antonin Guttman and Michael Stonebraker, UC Berkely +// * 1994 ANCI C ported from original test code by Melinda Green - melinda@superliminal.com +// * 1995 Sphere volume fix for degeneracy problem submitted by Paul Brook +// * 2004 Templated C++ port by Greg Douglas +// * 2013 CERN (www.cern.ch) +// +//LICENSE: +// +// Entirely free for all uses. Enjoy! + +#ifndef RTREE_H +#define RTREE_H + +// NOTE This file compiles under MSVC 6 SP5 and MSVC .Net 2003 it may not work on other compilers without modification. + +// NOTE These next few lines may be win32 specific, you may need to modify them to compile on other platform +#include <stdio.h> +#include <math.h> +#include <assert.h> +#include <stdlib.h> + +#define ASSERT assert // RTree uses ASSERT( condition ) +#ifndef rMin + #define rMin std::min +#endif // rMin +#ifndef rMax + #define rMax std::max +#endif // rMax + +// +// RTree.h +// + +#define RTREE_TEMPLATE template <class DATATYPE, class ELEMTYPE, int NUMDIMS, \ + class ELEMTYPEREAL, int TMAXNODES, int TMINNODES> +#define RTREE_SEARCH_TEMPLATE template <class DATATYPE, class ELEMTYPE, int NUMDIMS, \ + class ELEMTYPEREAL, int TMAXNODES, int TMINNODES, class VISITOR> +#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, \ + TMINNODES> +#define RTREE_SEARCH_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, \ + TMINNODES, VISITOR> + +#define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one. +#define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems + +// Fwd decl +class RTFileStream; // File I/O helper class, look below for implementation and notes. + + +/// \class RTree +/// Implementation of RTree, a multidimensional bounding rectangle tree. +/// Example usage: For a 3-dimensional tree use RTree<Object*, float, 3> myTree; +/// +/// This modified, templated C++ version by Greg Douglas at Auran (http://www.auran.com) +/// +/// DATATYPE Referenced data, should be int, void*, obj* etc. no larger than sizeof<void*> and simple type +/// ELEMTYPE Type of element such as int or float +/// NUMDIMS Number of dimensions such as 2 or 3 +/// ELEMTYPEREAL Type of element that allows fractional and large values such as float or double, for use in volume calcs +/// +/// NOTES: Inserting and removing data requires the knowledge of its constant Minimal Bounding Rectangle. +/// This version uses new/delete for nodes, I recommend using a fixed size allocator for efficiency. +/// Instead of using a callback function for returned results, I recommend and efficient pre-sized, grow-only memory +/// array similar to MFC CArray or STL Vector for returning search query result. +/// +template <class DATATYPE, class ELEMTYPE, int NUMDIMS, + class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2> +class RTree +{ +protected: + + struct Node; // Fwd decl. Used by other internal structs and iterator +public: + + // These constant must be declared after Branch and before Node struct + // Stuck up here for MSVC 6 compiler. NSVC .NET 2003 is much happier. + enum { + MAXNODES = TMAXNODES, ///< Max elements in node + MINNODES = TMINNODES, ///< Min elements in node + }; + + struct Statistics { + int maxDepth; + int avgDepth; + + int maxNodeLoad; + int avgNodeLoad; + int totalItems; + }; + +public: + + RTree(); + virtual ~RTree(); + + /// Insert entry + /// \param a_min Min of bounding rect + /// \param a_max Max of bounding rect + /// \param a_dataId Positive Id of data. Maybe zero, but negative numbers not allowed. + void Insert( const ELEMTYPE a_min[NUMDIMS], + const ELEMTYPE a_max[NUMDIMS], + const DATATYPE& a_dataId ); + + /// Remove entry + /// \param a_min Min of bounding rect + /// \param a_max Max of bounding rect + /// \param a_dataId Positive Id of data. Maybe zero, but negative numbers not allowed. + void Remove( const ELEMTYPE a_min[NUMDIMS], + const ELEMTYPE a_max[NUMDIMS], + const DATATYPE& a_dataId ); + + /// Find all within search rectangle + /// \param a_min Min of search bounding rect + /// \param a_max Max of search bounding rect + /// \param a_resultCallback Callback function to return result. Callback should return 'true' to continue searching + /// \param a_context User context to pass as parameter to a_resultCallback + /// \return Returns the number of entries found + int Search( const ELEMTYPE a_min[NUMDIMS], + const ELEMTYPE a_max[NUMDIMS], + bool a_resultCallback( DATATYPE a_data, void* a_context ), + void* a_context ); + + template <class VISITOR> + int Search( const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], VISITOR& a_visitor ) + { + #ifdef _DEBUG + + for( int index = 0; index<NUMDIMS; ++index ) + { + ASSERT( a_min[index] <= a_max[index] ); + } + + #endif // _DEBUG + + Rect rect; + + for( int axis = 0; axis<NUMDIMS; ++axis ) + { + rect.m_min[axis] = a_min[axis]; + rect.m_max[axis] = a_max[axis]; + } + + + // NOTE: May want to return search result another way, perhaps returning the number of found elements here. + int cnt; + + Search( m_root, &rect, a_visitor, cnt ); + + return cnt; + } + + /// Calculate Statistics + + Statistics CalcStats(); + + /// Remove all entries from tree + void RemoveAll(); + + /// Count the data elements in this container. This is slow as no internal counter is maintained. + int Count(); + + /// Load tree contents from file + bool Load( const char* a_fileName ); + + /// Load tree contents from stream + bool Load( RTFileStream& a_stream ); + + + /// Save tree contents to file + bool Save( const char* a_fileName ); + + /// Save tree contents to stream + bool Save( RTFileStream& a_stream ); + + /// Find the nearest neighbor of a specific point. + /// It uses the MINDIST method, simplifying the one from "R-Trees: Theory and Applications" by Yannis Manolopoulos et al. + /// The bounding rectangle is used to calculate the distance to the DATATYPE. + /// \param a_point point to start the search + /// \return Returns the DATATYPE located closest to a_point, 0 if the tree is empty. + DATATYPE NearestNeighbor( const ELEMTYPE a_point[NUMDIMS] ); + + /// Find the nearest neighbor of a specific point. + /// It uses the MINDIST method, simplifying the one from "R-Trees: Theory and Applications" by Yannis Manolopoulos et al. + /// It receives a callback function to calculate the distance to a DATATYPE object, instead of using the bounding rectangle. + /// \param a_point point to start the search + /// \param a_squareDistanceCallback function that performs the square distance calculation for the selected DATATYPE. + /// \param a_squareDistance Pointer in which the square distance to the nearest neighbour will be returned. + /// \return Returns the DATATYPE located closest to a_point, 0 if the tree is empty. + DATATYPE NearestNeighbor( const ELEMTYPE a_point[NUMDIMS], + ELEMTYPE a_squareDistanceCallback( const ELEMTYPE a_point[NUMDIMS], DATATYPE a_data ), + ELEMTYPE* a_squareDistance ); + + /// Iterator is not remove safe. + class Iterator + { + private: + + enum { MAX_STACK = 32 }; // Max stack size. Allows almost n^32 where n is number of branches in node + + struct StackElement + { + Node* m_node; + int m_branchIndex; + }; + public: + + Iterator() { Init(); } + + ~Iterator() { } + + /// Is iterator invalid + bool IsNull() { return m_tos <= 0; } + + /// Is iterator pointing to valid data + bool IsNotNull() { return m_tos > 0; } + + /// Access the current data element. Caller must be sure iterator is not NULL first. + DATATYPE& operator*() + { + ASSERT( IsNotNull() ); + StackElement& curTos = m_stack[m_tos - 1]; + return curTos.m_node->m_branch[curTos.m_branchIndex].m_data; + } + + /// Access the current data element. Caller must be sure iterator is not NULL first. + const DATATYPE& operator*() const + { + ASSERT( IsNotNull() ); + StackElement& curTos = m_stack[m_tos - 1]; + return curTos.m_node->m_branch[curTos.m_branchIndex].m_data; + } + + /// Find the next data element + bool operator++() { return FindNextData(); } + + /// Get the bounds for this node + void GetBounds( ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS] ) + { + ASSERT( IsNotNull() ); + StackElement& curTos = m_stack[m_tos - 1]; + Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex]; + + for( int index = 0; index < NUMDIMS; ++index ) + { + a_min[index] = curBranch.m_rect.m_min[index]; + a_max[index] = curBranch.m_rect.m_max[index]; + } + } + + private: + + /// Reset iterator + void Init() { m_tos = 0; } + + /// Find the next data element in the tree (For internal use only) + bool FindNextData() + { + for( ; ; ) + { + if( m_tos <= 0 ) + { + return false; + } + + StackElement curTos = Pop(); // Copy stack top cause it may change as we use it + + if( curTos.m_node->IsLeaf() ) + { + // Keep walking through data while we can + if( curTos.m_branchIndex + 1 < curTos.m_node->m_count ) + { + // There is more data, just point to the next one + Push( curTos.m_node, curTos.m_branchIndex + 1 ); + return true; + } + + // No more data, so it will fall back to previous level + } + else + { + if( curTos.m_branchIndex + 1 < curTos.m_node->m_count ) + { + // Push sibling on for future tree walk + // This is the 'fall back' node when we finish with the current level + Push( curTos.m_node, curTos.m_branchIndex + 1 ); + } + + // Since cur node is not a leaf, push first of next level to get deeper into the tree + Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child; + Push( nextLevelnode, 0 ); + + // If we pushed on a new leaf, exit as the data is ready at TOS + if( nextLevelnode->IsLeaf() ) + { + return true; + } + } + } + } + + /// Push node and branch onto iteration stack (For internal use only) + void Push( Node* a_node, int a_branchIndex ) + { + m_stack[m_tos].m_node = a_node; + m_stack[m_tos].m_branchIndex = a_branchIndex; + ++m_tos; + ASSERT( m_tos <= MAX_STACK ); + } + + /// Pop element off iteration stack (For internal use only) + StackElement& Pop() + { + ASSERT( m_tos > 0 ); + --m_tos; + return m_stack[m_tos]; + } + + StackElement m_stack[MAX_STACK]; ///< Stack as we are doing iteration instead of recursion + int m_tos; ///< Top Of Stack index + + friend class RTree; // Allow hiding of non-public functions while allowing manipulation by logical owner + }; + + + /// Get 'first' for iteration + void GetFirst( Iterator& a_it ) + { + a_it.Init(); + Node* first = m_root; + + while( first ) + { + if( first->IsInternalNode() && first->m_count > 1 ) + { + a_it.Push( first, 1 ); // Descend sibling branch later + } + else if( first->IsLeaf() ) + { + if( first->m_count ) + { + a_it.Push( first, 0 ); + } + + break; + } + + first = first->m_branch[0].m_child; + } + } + + /// Get Next for iteration + void GetNext( Iterator& a_it ) { ++a_it; } + + /// Is iterator NULL, or at end? + bool IsNull( Iterator& a_it ) { return a_it.IsNull(); } + + /// Get object at iterator position + DATATYPE& GetAt( Iterator& a_it ) { return *a_it; } +protected: + + /// Minimal bounding rectangle (n-dimensional) + struct Rect + { + ELEMTYPE m_min[NUMDIMS]; ///< Min dimensions of bounding box + ELEMTYPE m_max[NUMDIMS]; ///< Max dimensions of bounding box + }; + + /// May be data or may be another subtree + /// The parents level determines this. + /// If the parents level is 0, then this is data + struct Branch + { + Rect m_rect; ///< Bounds + union + { + Node* m_child; ///< Child node + DATATYPE m_data; ///< Data Id or Ptr + }; + }; + + /// Node for each branch level + struct Node + { + bool IsInternalNode() { return m_level > 0; } // Not a leaf, but a internal node + bool IsLeaf() { return m_level == 0; } // A leaf, contains data + + int m_count; ///< Count + int m_level; ///< Leaf is zero, others positive + Branch m_branch[MAXNODES]; ///< Branch + }; + + /// A link list of nodes for reinsertion after a delete operation + struct ListNode + { + ListNode* m_next; ///< Next in list + Node* m_node; ///< Node + }; + + /// Variables for finding a split partition + struct PartitionVars + { + int m_partition[MAXNODES + 1]; + int m_total; + int m_minFill; + int m_taken[MAXNODES + 1]; + int m_count[2]; + Rect m_cover[2]; + ELEMTYPEREAL m_area[2]; + + Branch m_branchBuf[MAXNODES + 1]; + int m_branchCount; + Rect m_coverSplit; + ELEMTYPEREAL m_coverSplitArea; + }; + + /// Data structure used for Nearest Neighbor search implementation + struct NNNode + { + Branch m_branch; + ELEMTYPE minDist; + bool isLeaf; + }; + + Node* AllocNode(); + void FreeNode( Node* a_node ); + void InitNode( Node* a_node ); + void InitRect( Rect* a_rect ); + bool InsertRectRec( Rect* a_rect, + const DATATYPE& a_id, + Node* a_node, + Node** a_newNode, + int a_level ); + bool InsertRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level ); + Rect NodeCover( Node* a_node ); + bool AddBranch( Branch* a_branch, Node* a_node, Node** a_newNode ); + void DisconnectBranch( Node* a_node, int a_index ); + int PickBranch( Rect* a_rect, Node* a_node ); + Rect CombineRect( Rect* a_rectA, Rect* a_rectB ); + void SplitNode( Node* a_node, Branch* a_branch, Node** a_newNode ); + ELEMTYPEREAL RectSphericalVolume( Rect* a_rect ); + ELEMTYPEREAL RectVolume( Rect* a_rect ); + ELEMTYPEREAL CalcRectVolume( Rect* a_rect ); + void GetBranches( Node* a_node, Branch* a_branch, PartitionVars* a_parVars ); + void ChoosePartition( PartitionVars* a_parVars, int a_minFill ); + void LoadNodes( Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars ); + void InitParVars( PartitionVars* a_parVars, int a_maxRects, int a_minFill ); + void PickSeeds( PartitionVars* a_parVars ); + void Classify( int a_index, int a_group, PartitionVars* a_parVars ); + bool RemoveRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root ); + bool RemoveRectRec( Rect* a_rect, + const DATATYPE& a_id, + Node* a_node, + ListNode** a_listNode ); + ListNode* AllocListNode(); + void FreeListNode( ListNode* a_listNode ); + bool Overlap( Rect* a_rectA, Rect* a_rectB ); + void ReInsert( Node* a_node, ListNode** a_listNode ); + ELEMTYPE MinDist( const ELEMTYPE a_point[NUMDIMS], Rect* a_rect ); + void InsertNNListSorted( std::vector<NNNode*>* nodeList, NNNode* newNode ); + + bool Search( Node * a_node, Rect * a_rect, int& a_foundCount, bool a_resultCallback( + DATATYPE a_data, + void* a_context ), void* a_context ); + + template <class VISITOR> + bool Search( Node* a_node, Rect* a_rect, VISITOR& a_visitor, int& a_foundCount ) + { + ASSERT( a_node ); + ASSERT( a_node->m_level >= 0 ); + ASSERT( a_rect ); + + if( a_node->IsInternalNode() ) // This is an internal node in the tree + { + for( int index = 0; index < a_node->m_count; ++index ) + { + if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) + { + if( !Search( a_node->m_branch[index].m_child, a_rect, a_visitor, a_foundCount ) ) + { + return false; // Don't continue searching + } + } + } + } + else // This is a leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) + { + DATATYPE& id = a_node->m_branch[index].m_data; + + if( !a_visitor( id ) ) + return false; + + a_foundCount++; + } + } + } + + return true; // Continue searching + } + + void RemoveAllRec( Node* a_node ); + void Reset(); + void CountRec( Node* a_node, int& a_count ); + + bool SaveRec( Node* a_node, RTFileStream& a_stream ); + bool LoadRec( Node* a_node, RTFileStream& a_stream ); + + Node* m_root; ///< Root of tree + ELEMTYPEREAL m_unitSphereVolume; ///< Unit sphere constant for required number of dimensions +}; + + +// Because there is not stream support, this is a quick and dirty file I/O helper. +// Users will likely replace its usage with a Stream implementation from their favorite API. +class RTFileStream +{ + FILE* m_file; +public: + + + RTFileStream() + { + m_file = NULL; + } + + ~RTFileStream() + { + Close(); + } + + bool OpenRead( const char* a_fileName ) + { + m_file = fopen( a_fileName, "rb" ); + + if( !m_file ) + { + return false; + } + + return true; + } + + bool OpenWrite( const char* a_fileName ) + { + m_file = fopen( a_fileName, "wb" ); + + if( !m_file ) + { + return false; + } + + return true; + } + + void Close() + { + if( m_file ) + { + fclose( m_file ); + m_file = NULL; + } + } + + template <typename TYPE> + size_t Write( const TYPE& a_value ) + { + ASSERT( m_file ); + return fwrite( (void*) &a_value, sizeof(a_value), 1, m_file ); + } + + template <typename TYPE> + size_t WriteArray( const TYPE* a_array, int a_count ) + { + ASSERT( m_file ); + return fwrite( (void*) a_array, sizeof(TYPE) * a_count, 1, m_file ); + } + + template <typename TYPE> + size_t Read( TYPE& a_value ) + { + ASSERT( m_file ); + return fread( (void*) &a_value, sizeof(a_value), 1, m_file ); + } + + template <typename TYPE> + size_t ReadArray( TYPE* a_array, int a_count ) + { + ASSERT( m_file ); + return fread( (void*) a_array, sizeof(TYPE) * a_count, 1, m_file ); + } +}; + + +RTREE_TEMPLATE RTREE_QUAL::RTree() +{ + ASSERT( MAXNODES > MINNODES ); + ASSERT( MINNODES > 0 ); + + + // We only support machine word size simple data type eg. integer index or object pointer. + // Since we are storing as union with non data branch + ASSERT( sizeof(DATATYPE) == sizeof(void*) || sizeof(DATATYPE) == sizeof(int) ); + + // Precomputed volumes of the unit spheres for the first few dimensions + const float UNIT_SPHERE_VOLUMES[] = + { + 0.000000f, 2.000000f, 3.141593f, // Dimension 0,1,2 + 4.188790f, 4.934802f, 5.263789f, // Dimension 3,4,5 + 5.167713f, 4.724766f, 4.058712f, // Dimension 6,7,8 + 3.298509f, 2.550164f, 1.884104f, // Dimension 9,10,11 + 1.335263f, 0.910629f, 0.599265f, // Dimension 12,13,14 + 0.381443f, 0.235331f, 0.140981f, // Dimension 15,16,17 + 0.082146f, 0.046622f, 0.025807f, // Dimension 18,19,20 + }; + + m_root = AllocNode(); + m_root->m_level = 0; + m_unitSphereVolume = (ELEMTYPEREAL) UNIT_SPHERE_VOLUMES[NUMDIMS]; +} + + +RTREE_TEMPLATE +RTREE_QUAL::~RTree() { + Reset(); // Free, or reset node memory +} + + +RTREE_TEMPLATE +void RTREE_QUAL::Insert( const ELEMTYPE a_min[NUMDIMS], + const ELEMTYPE a_max[NUMDIMS], + const DATATYPE& a_dataId ) +{ +#ifdef _DEBUG + + for( int index = 0; index<NUMDIMS; ++index ) + { + ASSERT( a_min[index] <= a_max[index] ); + } + +#endif // _DEBUG + + Rect rect; + + for( int axis = 0; axis<NUMDIMS; ++axis ) + { + rect.m_min[axis] = a_min[axis]; + rect.m_max[axis] = a_max[axis]; + } + + InsertRect( &rect, a_dataId, &m_root, 0 ); +} + + +RTREE_TEMPLATE +void RTREE_QUAL::Remove( const ELEMTYPE a_min[NUMDIMS], + const ELEMTYPE a_max[NUMDIMS], + const DATATYPE& a_dataId ) +{ +#ifdef _DEBUG + + for( int index = 0; index<NUMDIMS; ++index ) + { + ASSERT( a_min[index] <= a_max[index] ); + } + +#endif // _DEBUG + + Rect rect; + + for( int axis = 0; axis<NUMDIMS; ++axis ) + { + rect.m_min[axis] = a_min[axis]; + rect.m_max[axis] = a_max[axis]; + } + + RemoveRect( &rect, a_dataId, &m_root ); +} + + +RTREE_TEMPLATE +int RTREE_QUAL::Search( const ELEMTYPE a_min[NUMDIMS], + const ELEMTYPE a_max[NUMDIMS], + bool a_resultCallback( DATATYPE a_data, void* a_context ), + void* a_context ) +{ +#ifdef _DEBUG + + for( int index = 0; index<NUMDIMS; ++index ) + { + ASSERT( a_min[index] <= a_max[index] ); + } + +#endif // _DEBUG + + Rect rect; + + for( int axis = 0; axis<NUMDIMS; ++axis ) + { + rect.m_min[axis] = a_min[axis]; + rect.m_max[axis] = a_max[axis]; + } + + // NOTE: May want to return search result another way, perhaps returning the number of found elements here. + + int foundCount = 0; + Search( m_root, &rect, foundCount, a_resultCallback, a_context ); + + return foundCount; +} + + +RTREE_TEMPLATE +DATATYPE RTREE_QUAL::NearestNeighbor( const ELEMTYPE a_point[NUMDIMS] ) +{ + return this->NearestNeighbor( a_point, 0, 0 ); +} + + +RTREE_TEMPLATE +DATATYPE RTREE_QUAL::NearestNeighbor( const ELEMTYPE a_point[NUMDIMS], + ELEMTYPE a_squareDistanceCallback( const ELEMTYPE a_point[NUMDIMS], DATATYPE a_data ), + ELEMTYPE* a_squareDistance ) +{ + typedef typename std::vector<NNNode*>::iterator iterator; + std::vector<NNNode*> nodeList; + Node* node = m_root; + NNNode* closestNode = 0; + while( !closestNode || !closestNode->isLeaf ) + { + //check every node on this level + for( int index = 0; index < node->m_count; ++index ) + { + NNNode* newNode = new NNNode; + newNode->isLeaf = node->IsLeaf(); + newNode->m_branch = node->m_branch[index]; + if( newNode->isLeaf && a_squareDistanceCallback ) + newNode->minDist = a_squareDistanceCallback( a_point, newNode->m_branch.m_data ); + else + newNode->minDist = this->MinDist( a_point, &(node->m_branch[index].m_rect) ); + + //TODO: a custom list could be more efficient than a vector + this->InsertNNListSorted( &nodeList, newNode ); + } + if( nodeList.size() == 0 ) + { + return 0; + } + closestNode = nodeList.back(); + node = closestNode->m_branch.m_child; + nodeList.pop_back(); + free(closestNode); + } + + // free memory used for remaining NNNodes in nodeList + for( iterator iter = nodeList.begin(); iter != nodeList.end(); ++iter ) + { + NNNode* node = *iter; + free(node); + } + + *a_squareDistance = closestNode->minDist; + return closestNode->m_branch.m_data; +} + + +RTREE_TEMPLATE +int RTREE_QUAL::Count() +{ + int count = 0; + + CountRec( m_root, count ); + + return count; +} + + +RTREE_TEMPLATE +void RTREE_QUAL::CountRec( Node* a_node, int& a_count ) +{ + if( a_node->IsInternalNode() ) // not a leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + CountRec( a_node->m_branch[index].m_child, a_count ); + } + } + else // A leaf node + { + a_count += a_node->m_count; + } +} + + +RTREE_TEMPLATE +bool RTREE_QUAL::Load( const char* a_fileName ) +{ + RemoveAll(); // Clear existing tree + + RTFileStream stream; + + if( !stream.OpenRead( a_fileName ) ) + { + return false; + } + + bool result = Load( stream ); + + stream.Close(); + + return result; +}; + + +RTREE_TEMPLATE +bool RTREE_QUAL::Load( RTFileStream& a_stream ) +{ + // Write some kind of header + int _dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); + int _dataSize = sizeof(DATATYPE); + int _dataNumDims = NUMDIMS; + int _dataElemSize = sizeof(ELEMTYPE); + int _dataElemRealSize = sizeof(ELEMTYPEREAL); + int _dataMaxNodes = TMAXNODES; + int _dataMinNodes = TMINNODES; + + int dataFileId = 0; + int dataSize = 0; + int dataNumDims = 0; + int dataElemSize = 0; + int dataElemRealSize = 0; + int dataMaxNodes = 0; + int dataMinNodes = 0; + + a_stream.Read( dataFileId ); + a_stream.Read( dataSize ); + a_stream.Read( dataNumDims ); + a_stream.Read( dataElemSize ); + a_stream.Read( dataElemRealSize ); + a_stream.Read( dataMaxNodes ); + a_stream.Read( dataMinNodes ); + + bool result = false; + + // Test if header was valid and compatible + if( (dataFileId == _dataFileId) + && (dataSize == _dataSize) + && (dataNumDims == _dataNumDims) + && (dataElemSize == _dataElemSize) + && (dataElemRealSize == _dataElemRealSize) + && (dataMaxNodes == _dataMaxNodes) + && (dataMinNodes == _dataMinNodes) + ) + { + // Recursively load tree + result = LoadRec( m_root, a_stream ); + } + + return result; +} + + +RTREE_TEMPLATE +bool RTREE_QUAL::LoadRec( Node* a_node, RTFileStream& a_stream ) +{ + a_stream.Read( a_node->m_level ); + a_stream.Read( a_node->m_count ); + + if( a_node->IsInternalNode() ) // not a leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + Branch* curBranch = &a_node->m_branch[index]; + + a_stream.ReadArray( curBranch->m_rect.m_min, NUMDIMS ); + a_stream.ReadArray( curBranch->m_rect.m_max, NUMDIMS ); + + curBranch->m_child = AllocNode(); + LoadRec( curBranch->m_child, a_stream ); + } + } + else // A leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + Branch* curBranch = &a_node->m_branch[index]; + + a_stream.ReadArray( curBranch->m_rect.m_min, NUMDIMS ); + a_stream.ReadArray( curBranch->m_rect.m_max, NUMDIMS ); + + a_stream.Read( curBranch->m_data ); + } + } + + return true; // Should do more error checking on I/O operations +} + + +RTREE_TEMPLATE +bool RTREE_QUAL::Save( const char* a_fileName ) +{ + RTFileStream stream; + + if( !stream.OpenWrite( a_fileName ) ) + { + return false; + } + + bool result = Save( stream ); + + stream.Close(); + + return result; +} + + +RTREE_TEMPLATE +bool RTREE_QUAL::Save( RTFileStream& a_stream ) +{ + // Write some kind of header + int dataFileId = ('R' << 0) | ('T' << 8) | ('R' << 16) | ('E' << 24); + int dataSize = sizeof(DATATYPE); + int dataNumDims = NUMDIMS; + int dataElemSize = sizeof(ELEMTYPE); + int dataElemRealSize = sizeof(ELEMTYPEREAL); + int dataMaxNodes = TMAXNODES; + int dataMinNodes = TMINNODES; + + a_stream.Write( dataFileId ); + a_stream.Write( dataSize ); + a_stream.Write( dataNumDims ); + a_stream.Write( dataElemSize ); + a_stream.Write( dataElemRealSize ); + a_stream.Write( dataMaxNodes ); + a_stream.Write( dataMinNodes ); + + // Recursively save tree + bool result = SaveRec( m_root, a_stream ); + + return result; +} + + +RTREE_TEMPLATE +bool RTREE_QUAL::SaveRec( Node* a_node, RTFileStream& a_stream ) +{ + a_stream.Write( a_node->m_level ); + a_stream.Write( a_node->m_count ); + + if( a_node->IsInternalNode() ) // not a leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + Branch* curBranch = &a_node->m_branch[index]; + + a_stream.WriteArray( curBranch->m_rect.m_min, NUMDIMS ); + a_stream.WriteArray( curBranch->m_rect.m_max, NUMDIMS ); + + SaveRec( curBranch->m_child, a_stream ); + } + } + else // A leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + Branch* curBranch = &a_node->m_branch[index]; + + a_stream.WriteArray( curBranch->m_rect.m_min, NUMDIMS ); + a_stream.WriteArray( curBranch->m_rect.m_max, NUMDIMS ); + + a_stream.Write( curBranch->m_data ); + } + } + + return true; // Should do more error checking on I/O operations +} + + +RTREE_TEMPLATE +void RTREE_QUAL::RemoveAll() +{ + // Delete all existing nodes + Reset(); + + m_root = AllocNode(); + m_root->m_level = 0; +} + + +RTREE_TEMPLATE +void RTREE_QUAL::Reset() +{ +#ifdef RTREE_DONT_USE_MEMPOOLS + // Delete all existing nodes + RemoveAllRec( m_root ); +#else // RTREE_DONT_USE_MEMPOOLS + // Just reset memory pools. We are not using complex types + // EXAMPLE +#endif // RTREE_DONT_USE_MEMPOOLS +} + + +RTREE_TEMPLATE +void RTREE_QUAL::RemoveAllRec( Node* a_node ) +{ + ASSERT( a_node ); + ASSERT( a_node->m_level >= 0 ); + + if( a_node->IsInternalNode() ) // This is an internal node in the tree + { + for( int index = 0; index < a_node->m_count; ++index ) + { + RemoveAllRec( a_node->m_branch[index].m_child ); + } + } + + FreeNode( a_node ); +} + + +RTREE_TEMPLATE +typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode() +{ + Node* newNode; + +#ifdef RTREE_DONT_USE_MEMPOOLS + newNode = new Node; +#else // RTREE_DONT_USE_MEMPOOLS + // EXAMPLE +#endif // RTREE_DONT_USE_MEMPOOLS + InitNode( newNode ); + return newNode; +} + + +RTREE_TEMPLATE +void RTREE_QUAL::FreeNode( Node* a_node ) +{ + ASSERT( a_node ); + +#ifdef RTREE_DONT_USE_MEMPOOLS + delete a_node; +#else // RTREE_DONT_USE_MEMPOOLS + // EXAMPLE +#endif // RTREE_DONT_USE_MEMPOOLS +} + + +// Allocate space for a node in the list used in DeletRect to +// store Nodes that are too empty. +RTREE_TEMPLATE +typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode() +{ +#ifdef RTREE_DONT_USE_MEMPOOLS + return new ListNode; +#else // RTREE_DONT_USE_MEMPOOLS + // EXAMPLE +#endif // RTREE_DONT_USE_MEMPOOLS +} + + +RTREE_TEMPLATE +void RTREE_QUAL::FreeListNode( ListNode* a_listNode ) +{ +#ifdef RTREE_DONT_USE_MEMPOOLS + delete a_listNode; +#else // RTREE_DONT_USE_MEMPOOLS + // EXAMPLE +#endif // RTREE_DONT_USE_MEMPOOLS +} + + +RTREE_TEMPLATE +void RTREE_QUAL::InitNode( Node* a_node ) +{ + a_node->m_count = 0; + a_node->m_level = -1; +} + + +RTREE_TEMPLATE +void RTREE_QUAL::InitRect( Rect* a_rect ) +{ + for( int index = 0; index < NUMDIMS; ++index ) + { + a_rect->m_min[index] = (ELEMTYPE) 0; + a_rect->m_max[index] = (ELEMTYPE) 0; + } +} + + +// Inserts a new data rectangle into the index structure. +// Recursively descends tree, propagates splits back up. +// Returns 0 if node was not split. Old node updated. +// If node was split, returns 1 and sets the pointer pointed to by +// new_node to point to the new node. Old node updated to become one of two. +// The level argument specifies the number of steps up from the leaf +// level to insert; e.g. a data rectangle goes in at level = 0. +RTREE_TEMPLATE +bool RTREE_QUAL::InsertRectRec( Rect* a_rect, + const DATATYPE& a_id, + Node* a_node, + Node** a_newNode, + int a_level ) +{ + ASSERT( a_rect && a_node && a_newNode ); + ASSERT( a_level >= 0 && a_level <= a_node->m_level ); + + int index; + Branch branch; + Node* otherNode; + + // Still above level for insertion, go down tree recursively + if( a_node->m_level > a_level ) + { + index = PickBranch( a_rect, a_node ); + + if( !InsertRectRec( a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level ) ) + { + // Child was not split + a_node->m_branch[index].m_rect = + CombineRect( a_rect, &(a_node->m_branch[index].m_rect) ); + return false; + } + else // Child was split + { + a_node->m_branch[index].m_rect = NodeCover( a_node->m_branch[index].m_child ); + branch.m_child = otherNode; + branch.m_rect = NodeCover( otherNode ); + return AddBranch( &branch, a_node, a_newNode ); + } + } + else if( a_node->m_level == a_level ) // Have reached level for insertion. Add rect, split if necessary + { + branch.m_rect = *a_rect; + branch.m_child = (Node*) a_id; + // Child field of leaves contains id of data record + return AddBranch( &branch, a_node, a_newNode ); + } + else + { + // Should never occur + ASSERT( 0 ); + return false; + } +} + + +// Insert a data rectangle into an index structure. +// InsertRect provides for splitting the root; +// returns 1 if root was split, 0 if it was not. +// The level argument specifies the number of steps up from the leaf +// level to insert; e.g. a data rectangle goes in at level = 0. +// InsertRect2 does the recursion. +// +RTREE_TEMPLATE +bool RTREE_QUAL::InsertRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level ) +{ + ASSERT( a_rect && a_root ); + ASSERT( a_level >= 0 && a_level <= (*a_root)->m_level ); +#ifdef _DEBUG + + for( int index = 0; index < NUMDIMS; ++index ) + { + ASSERT( a_rect->m_min[index] <= a_rect->m_max[index] ); + } + +#endif // _DEBUG + + Node* newRoot; + Node* newNode; + Branch branch; + + if( InsertRectRec( a_rect, a_id, *a_root, &newNode, a_level ) ) // Root split + { + newRoot = AllocNode(); // Grow tree taller and new root + newRoot->m_level = (*a_root)->m_level + 1; + branch.m_rect = NodeCover( *a_root ); + branch.m_child = *a_root; + AddBranch( &branch, newRoot, NULL ); + branch.m_rect = NodeCover( newNode ); + branch.m_child = newNode; + AddBranch( &branch, newRoot, NULL ); + *a_root = newRoot; + return true; + } + + return false; +} + + +// Find the smallest rectangle that includes all rectangles in branches of a node. +RTREE_TEMPLATE +typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover( Node* a_node ) +{ + ASSERT( a_node ); + + int firstTime = true; + Rect rect; + InitRect( &rect ); + + for( int index = 0; index < a_node->m_count; ++index ) + { + if( firstTime ) + { + rect = a_node->m_branch[index].m_rect; + firstTime = false; + } + else + { + rect = CombineRect( &rect, &(a_node->m_branch[index].m_rect) ); + } + } + + return rect; +} + + +// Add a branch to a node. Split the node if necessary. +// Returns 0 if node not split. Old node updated. +// Returns 1 if node split, sets *new_node to address of new node. +// Old node updated, becomes one of two. +RTREE_TEMPLATE +bool RTREE_QUAL::AddBranch( Branch* a_branch, Node* a_node, Node** a_newNode ) +{ + ASSERT( a_branch ); + ASSERT( a_node ); + + if( a_node->m_count < MAXNODES ) // Split won't be necessary + { + a_node->m_branch[a_node->m_count] = *a_branch; + ++a_node->m_count; + + return false; + } + else + { + ASSERT( a_newNode ); + + SplitNode( a_node, a_branch, a_newNode ); + return true; + } +} + + +// Disconnect a dependent node. +// Caller must return (or stop using iteration index) after this as count has changed +RTREE_TEMPLATE +void RTREE_QUAL::DisconnectBranch( Node* a_node, int a_index ) +{ + ASSERT( a_node && (a_index >= 0) && (a_index < MAXNODES) ); + ASSERT( a_node->m_count > 0 ); + + // Remove element by swapping with the last element to prevent gaps in array + a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1]; + + --a_node->m_count; +} + + +// Pick a branch. Pick the one that will need the smallest increase +// in area to accomodate the new rectangle. This will result in the +// least total area for the covering rectangles in the current node. +// In case of a tie, pick the one which was smaller before, to get +// the best resolution when searching. +RTREE_TEMPLATE +int RTREE_QUAL::PickBranch( Rect* a_rect, Node* a_node ) +{ + ASSERT( a_rect && a_node ); + + bool firstTime = true; + ELEMTYPEREAL increase; + ELEMTYPEREAL bestIncr = (ELEMTYPEREAL) -1; + ELEMTYPEREAL area; + ELEMTYPEREAL bestArea = 0; + int best = 0; + Rect tempRect; + + for( int index = 0; index < a_node->m_count; ++index ) + { + Rect* curRect = &a_node->m_branch[index].m_rect; + area = CalcRectVolume( curRect ); + tempRect = CombineRect( a_rect, curRect ); + increase = CalcRectVolume( &tempRect ) - area; + + if( (increase < bestIncr) || firstTime ) + { + best = index; + bestArea = area; + bestIncr = increase; + firstTime = false; + } + else if( (increase == bestIncr) && (area < bestArea) ) + { + best = index; + bestArea = area; + bestIncr = increase; + } + } + + return best; +} + + +// Combine two rectangles into larger one containing both +RTREE_TEMPLATE +typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect( Rect* a_rectA, Rect* a_rectB ) +{ + ASSERT( a_rectA && a_rectB ); + + Rect newRect; + + for( int index = 0; index < NUMDIMS; ++index ) + { + newRect.m_min[index] = rMin( a_rectA->m_min[index], a_rectB->m_min[index] ); + newRect.m_max[index] = rMax( a_rectA->m_max[index], a_rectB->m_max[index] ); + } + + return newRect; +} + + +// Split a node. +// Divides the nodes branches and the extra one between two nodes. +// Old node is one of the new ones, and one really new one is created. +// Tries more than one method for choosing a partition, uses best result. +RTREE_TEMPLATE +void RTREE_QUAL::SplitNode( Node* a_node, Branch* a_branch, Node** a_newNode ) +{ + ASSERT( a_node ); + ASSERT( a_branch ); + + // Could just use local here, but member or external is faster since it is reused + PartitionVars localVars; + PartitionVars* parVars = &localVars; + int level; + + // Load all the branches into a buffer, initialize old node + level = a_node->m_level; + GetBranches( a_node, a_branch, parVars ); + + // Find partition + ChoosePartition( parVars, MINNODES ); + + // Put branches from buffer into 2 nodes according to chosen partition + *a_newNode = AllocNode(); + (*a_newNode)->m_level = a_node->m_level = level; + LoadNodes( a_node, *a_newNode, parVars ); + + ASSERT( (a_node->m_count + (*a_newNode)->m_count) == parVars->m_total ); +} + + +// Calculate the n-dimensional volume of a rectangle +RTREE_TEMPLATE +ELEMTYPEREAL RTREE_QUAL::RectVolume( Rect* a_rect ) +{ + ASSERT( a_rect ); + + ELEMTYPEREAL volume = (ELEMTYPEREAL) 1; + + for( int index = 0; index<NUMDIMS; ++index ) + { + volume *= a_rect->m_max[index] - a_rect->m_min[index]; + } + + ASSERT( volume >= (ELEMTYPEREAL) 0 ); + + return volume; +} + + +// The exact volume of the bounding sphere for the given Rect +RTREE_TEMPLATE +ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume( Rect* a_rect ) +{ + ASSERT( a_rect ); + + ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL) 0; + ELEMTYPEREAL radius; + + for( int index = 0; index < NUMDIMS; ++index ) + { + ELEMTYPEREAL halfExtent = + ( (ELEMTYPEREAL) a_rect->m_max[index] - (ELEMTYPEREAL) a_rect->m_min[index] ) * 0.5f; + sumOfSquares += halfExtent * halfExtent; + } + + radius = (ELEMTYPEREAL) sqrt( sumOfSquares ); + + // Pow maybe slow, so test for common dims like 2,3 and just use x*x, x*x*x. + if( NUMDIMS == 3 ) + { + return radius * radius * radius * m_unitSphereVolume; + } + else if( NUMDIMS == 2 ) + { + return radius * radius * m_unitSphereVolume; + } + else + { + return (ELEMTYPEREAL) (pow( radius, NUMDIMS ) * m_unitSphereVolume); + } +} + + +// Use one of the methods to calculate retangle volume +RTREE_TEMPLATE +ELEMTYPEREAL RTREE_QUAL::CalcRectVolume( Rect* a_rect ) +{ +#ifdef RTREE_USE_SPHERICAL_VOLUME + return RectSphericalVolume( a_rect ); // Slower but helps certain merge cases +#else // RTREE_USE_SPHERICAL_VOLUME + return RectVolume( a_rect ); // Faster but can cause poor merges +#endif // RTREE_USE_SPHERICAL_VOLUME +} + + +// Load branch buffer with branches from full node plus the extra branch. +RTREE_TEMPLATE +void RTREE_QUAL::GetBranches( Node* a_node, Branch* a_branch, PartitionVars* a_parVars ) +{ + ASSERT( a_node ); + ASSERT( a_branch ); + + ASSERT( a_node->m_count == MAXNODES ); + + // Load the branch buffer + for( int index = 0; index < MAXNODES; ++index ) + { + a_parVars->m_branchBuf[index] = a_node->m_branch[index]; + } + + a_parVars->m_branchBuf[MAXNODES] = *a_branch; + a_parVars->m_branchCount = MAXNODES + 1; + + // Calculate rect containing all in the set + a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect; + + for( int index = 1; index < MAXNODES + 1; ++index ) + { + a_parVars->m_coverSplit = + CombineRect( &a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect ); + } + + a_parVars->m_coverSplitArea = CalcRectVolume( &a_parVars->m_coverSplit ); + + InitNode( a_node ); +} + + +// Method #0 for choosing a partition: +// As the seeds for the two groups, pick the two rects that would waste the +// most area if covered by a single rectangle, i.e. evidently the worst pair +// to have in the same group. +// Of the remaining, one at a time is chosen to be put in one of the two groups. +// The one chosen is the one with the greatest difference in area expansion +// depending on which group - the rect most strongly attracted to one group +// and repelled from the other. +// If one group gets too full (more would force other group to violate min +// fill requirement) then other group gets the rest. +// These last are the ones that can go in either group most easily. +RTREE_TEMPLATE +void RTREE_QUAL::ChoosePartition( PartitionVars* a_parVars, int a_minFill ) +{ + ASSERT( a_parVars ); + + ELEMTYPEREAL biggestDiff; + int group, chosen = 0, betterGroup = 0; + + InitParVars( a_parVars, a_parVars->m_branchCount, a_minFill ); + PickSeeds( a_parVars ); + + while( ( (a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total ) + && ( a_parVars->m_count[0] < (a_parVars->m_total - a_parVars->m_minFill) ) + && ( a_parVars->m_count[1] < (a_parVars->m_total - a_parVars->m_minFill) ) ) + { + biggestDiff = (ELEMTYPEREAL) -1; + + for( int index = 0; index<a_parVars->m_total; ++index ) + { + if( !a_parVars->m_taken[index] ) + { + Rect* curRect = &a_parVars->m_branchBuf[index].m_rect; + Rect rect0 = CombineRect( curRect, &a_parVars->m_cover[0] ); + Rect rect1 = CombineRect( curRect, &a_parVars->m_cover[1] ); + ELEMTYPEREAL growth0 = CalcRectVolume( &rect0 ) - a_parVars->m_area[0]; + ELEMTYPEREAL growth1 = CalcRectVolume( &rect1 ) - a_parVars->m_area[1]; + ELEMTYPEREAL diff = growth1 - growth0; + + if( diff >= 0 ) + { + group = 0; + } + else + { + group = 1; + diff = -diff; + } + + if( diff > biggestDiff ) + { + biggestDiff = diff; + chosen = index; + betterGroup = group; + } + else if( (diff == biggestDiff) + && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]) ) + { + chosen = index; + betterGroup = group; + } + } + } + + Classify( chosen, betterGroup, a_parVars ); + } + + // If one group too full, put remaining rects in the other + if( (a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total ) + { + if( a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill ) + { + group = 1; + } + else + { + group = 0; + } + + for( int index = 0; index<a_parVars->m_total; ++index ) + { + if( !a_parVars->m_taken[index] ) + { + Classify( index, group, a_parVars ); + } + } + } + + ASSERT( (a_parVars->m_count[0] + a_parVars->m_count[1]) == a_parVars->m_total ); + ASSERT( (a_parVars->m_count[0] >= a_parVars->m_minFill) + && (a_parVars->m_count[1] >= a_parVars->m_minFill) ); +} + + +// Copy branches from the buffer into two nodes according to the partition. +RTREE_TEMPLATE +void RTREE_QUAL::LoadNodes( Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars ) +{ + ASSERT( a_nodeA ); + ASSERT( a_nodeB ); + ASSERT( a_parVars ); + + for( int index = 0; index < a_parVars->m_total; ++index ) + { + ASSERT( a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1 ); + + if( a_parVars->m_partition[index] == 0 ) + { + AddBranch( &a_parVars->m_branchBuf[index], a_nodeA, NULL ); + } + else if( a_parVars->m_partition[index] == 1 ) + { + AddBranch( &a_parVars->m_branchBuf[index], a_nodeB, NULL ); + } + } +} + + +// Initialize a PartitionVars structure. +RTREE_TEMPLATE +void RTREE_QUAL::InitParVars( PartitionVars* a_parVars, int a_maxRects, int a_minFill ) +{ + ASSERT( a_parVars ); + + a_parVars->m_count[0] = a_parVars->m_count[1] = 0; + a_parVars->m_area[0] = a_parVars->m_area[1] = (ELEMTYPEREAL) 0; + a_parVars->m_total = a_maxRects; + a_parVars->m_minFill = a_minFill; + + for( int index = 0; index < a_maxRects; ++index ) + { + a_parVars->m_taken[index] = false; + a_parVars->m_partition[index] = -1; + } +} + + +RTREE_TEMPLATE +void RTREE_QUAL::PickSeeds( PartitionVars* a_parVars ) +{ + int seed0 = 0, seed1 = 0; + ELEMTYPEREAL worst, waste; + ELEMTYPEREAL area[MAXNODES + 1]; + + for( int index = 0; index<a_parVars->m_total; ++index ) + { + area[index] = CalcRectVolume( &a_parVars->m_branchBuf[index].m_rect ); + } + + worst = -a_parVars->m_coverSplitArea - 1; + + for( int indexA = 0; indexA < a_parVars->m_total - 1; ++indexA ) + { + for( int indexB = indexA + 1; indexB < a_parVars->m_total; ++indexB ) + { + Rect oneRect = CombineRect( &a_parVars->m_branchBuf[indexA].m_rect, + &a_parVars->m_branchBuf[indexB].m_rect ); + waste = CalcRectVolume( &oneRect ) - area[indexA] - area[indexB]; + + if( waste >= worst ) + { + worst = waste; + seed0 = indexA; + seed1 = indexB; + } + } + } + + Classify( seed0, 0, a_parVars ); + Classify( seed1, 1, a_parVars ); +} + + +// Put a branch in one of the groups. +RTREE_TEMPLATE +void RTREE_QUAL::Classify( int a_index, int a_group, PartitionVars* a_parVars ) +{ + ASSERT( a_parVars ); + ASSERT( !a_parVars->m_taken[a_index] ); + + a_parVars->m_partition[a_index] = a_group; + a_parVars->m_taken[a_index] = true; + + if( a_parVars->m_count[a_group] == 0 ) + { + a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect; + } + else + { + a_parVars->m_cover[a_group] = CombineRect( &a_parVars->m_branchBuf[a_index].m_rect, + &a_parVars->m_cover[a_group] ); + } + + a_parVars->m_area[a_group] = CalcRectVolume( &a_parVars->m_cover[a_group] ); + ++a_parVars->m_count[a_group]; +} + + +// Delete a data rectangle from an index structure. +// Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node. +// Returns 1 if record not found, 0 if success. +// RemoveRect provides for eliminating the root. +RTREE_TEMPLATE +bool RTREE_QUAL::RemoveRect( Rect* a_rect, const DATATYPE& a_id, Node** a_root ) +{ + ASSERT( a_rect && a_root ); + ASSERT( *a_root ); + + Node* tempNode; + ListNode* reInsertList = NULL; + + if( !RemoveRectRec( a_rect, a_id, *a_root, &reInsertList ) ) + { + // Found and deleted a data item + // Reinsert any branches from eliminated nodes + while( reInsertList ) + { + tempNode = reInsertList->m_node; + + for( int index = 0; index < tempNode->m_count; ++index ) + { + InsertRect( &(tempNode->m_branch[index].m_rect), + tempNode->m_branch[index].m_data, + a_root, + tempNode->m_level ); + } + + ListNode* remLNode = reInsertList; + reInsertList = reInsertList->m_next; + + FreeNode( remLNode->m_node ); + FreeListNode( remLNode ); + } + + // Check for redundant root (not leaf, 1 child) and eliminate + if( (*a_root)->m_count == 1 && (*a_root)->IsInternalNode() ) + { + tempNode = (*a_root)->m_branch[0].m_child; + + ASSERT( tempNode ); + FreeNode( *a_root ); + *a_root = tempNode; + } + + return false; + } + else + { + return true; + } +} + + +// Delete a rectangle from non-root part of an index structure. +// Called by RemoveRect. Descends tree recursively, +// merges branches on the way back up. +// Returns 1 if record not found, 0 if success. +RTREE_TEMPLATE +bool RTREE_QUAL::RemoveRectRec( Rect* a_rect, + const DATATYPE& a_id, + Node* a_node, + ListNode** a_listNode ) +{ + ASSERT( a_rect && a_node && a_listNode ); + ASSERT( a_node->m_level >= 0 ); + + if( a_node->IsInternalNode() ) // not a leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + if( Overlap( a_rect, &(a_node->m_branch[index].m_rect) ) ) + { + if( !RemoveRectRec( a_rect, a_id, a_node->m_branch[index].m_child, a_listNode ) ) + { + if( a_node->m_branch[index].m_child->m_count >= MINNODES ) + { + // child removed, just resize parent rect + a_node->m_branch[index].m_rect = + NodeCover( a_node->m_branch[index].m_child ); + } + else + { + // child removed, not enough entries in node, eliminate node + ReInsert( a_node->m_branch[index].m_child, a_listNode ); + DisconnectBranch( a_node, index ); // Must return after this call as count has changed + } + + return false; + } + } + } + + return true; + } + else // A leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + if( a_node->m_branch[index].m_child == (Node*) a_id ) + { + DisconnectBranch( a_node, index ); // Must return after this call as count has changed + return false; + } + } + + return true; + } +} + + +// Decide whether two rectangles overlap. +RTREE_TEMPLATE +bool RTREE_QUAL::Overlap( Rect* a_rectA, Rect* a_rectB ) +{ + ASSERT( a_rectA && a_rectB ); + + for( int index = 0; index < NUMDIMS; ++index ) + { + if( a_rectA->m_min[index] > a_rectB->m_max[index] + || a_rectB->m_min[index] > a_rectA->m_max[index] ) + { + return false; + } + } + + return true; +} + + +// Add a node to the reinsertion list. All its branches will later +// be reinserted into the index structure. +RTREE_TEMPLATE +void RTREE_QUAL::ReInsert( Node* a_node, ListNode** a_listNode ) +{ + ListNode* newListNode; + + newListNode = AllocListNode(); + newListNode->m_node = a_node; + newListNode->m_next = *a_listNode; + *a_listNode = newListNode; +} + + +// Search in an index tree or subtree for all data retangles that overlap the argument rectangle. +RTREE_TEMPLATE +bool RTREE_QUAL::Search( Node* a_node, Rect* a_rect, int& a_foundCount, bool a_resultCallback( + DATATYPE a_data, + void* a_context ), void* a_context ) +{ + ASSERT( a_node ); + ASSERT( a_node->m_level >= 0 ); + ASSERT( a_rect ); + + if( a_node->IsInternalNode() ) // This is an internal node in the tree + { + for( int index = 0; index < a_node->m_count; ++index ) + { + if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) + { + if( !Search( a_node->m_branch[index].m_child, a_rect, a_foundCount, + a_resultCallback, a_context ) ) + { + return false; // Don't continue searching + } + } + } + } + else // This is a leaf node + { + for( int index = 0; index < a_node->m_count; ++index ) + { + if( Overlap( a_rect, &a_node->m_branch[index].m_rect ) ) + { + DATATYPE& id = a_node->m_branch[index].m_data; + + // NOTE: There are different ways to return results. Here's where to modify + if( &a_resultCallback ) + { + ++a_foundCount; + + if( !a_resultCallback( id, a_context ) ) + { + return false; // Don't continue searching + } + } + } + } + } + + return true; // Continue searching +} + + +//calculate the minimum distance between a point and a rectangle as defined by Manolopoulos et al. +//it uses the square distance to avoid the use of ELEMTYPEREAL values, which are slower. +RTREE_TEMPLATE +ELEMTYPE RTREE_QUAL::MinDist( const ELEMTYPE a_point[NUMDIMS], Rect* a_rect ) +{ + ELEMTYPE *q, *s, *t; + q = (ELEMTYPE*) a_point; + s = a_rect->m_min; + t = a_rect->m_max; + int minDist = 0; + for( int index = 0; index < NUMDIMS; index++ ) + { + int r = q[index]; + if( q[index] < s[index] ) + { + r = s[index]; + } + else if( q[index] >t[index] ) + { + r = t[index]; + } + int addend = q[index] - r; + minDist += addend * addend; + } + return minDist; +} + + +//insert a NNNode in a list sorted by its minDist (desc.) +RTREE_TEMPLATE +void RTREE_QUAL::InsertNNListSorted( std::vector<NNNode*>* nodeList, NNNode* newNode ) +{ + typedef typename std::vector<NNNode*>::iterator iterator; + iterator iter = nodeList->begin(); + while( iter != nodeList->end() && (*iter)->minDist > newNode->minDist ) + { + ++iter; + } + nodeList->insert(iter, newNode); +} + + +#undef RTREE_TEMPLATE +#undef RTREE_QUAL +#undef RTREE_SEARCH_TEMPLATE +#undef RTREE_SEARCH_QUAL + +#endif // RTREE_H diff --git a/include/geometry/seg.h b/include/geometry/seg.h new file mode 100644 index 0000000..164457b --- /dev/null +++ b/include/geometry/seg.h @@ -0,0 +1,384 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SEG_H +#define __SEG_H + +#include <cstdio> +#include <climits> + +#include <math/vector2d.h> + +#include <boost/optional/optional.hpp> + +typedef boost::optional<VECTOR2I> OPT_VECTOR2I; + +class SEG +{ +private: + typedef VECTOR2I::extended_type ecoord; + +public: + friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg ); + + /* Start and the of the segment. Public, to make access simpler. These are references + * to an object the segment belongs to (e.g. a line chain) or references to locally stored + * points (m_a, m_b). + */ + VECTOR2I A; + VECTOR2I B; + + /** Default constructor + * Creates an empty (0, 0) segment, locally-referenced + */ + SEG() + { + m_index = -1; + } + + /** + * Constructor + * Creates a segment between (aX1, aY1) and (aX2, aY2), locally referenced + */ + SEG( int aX1, int aY1, int aX2, int aY2 ) : + A ( VECTOR2I( aX1, aY1 ) ), + B ( VECTOR2I( aX2, aY2 ) ) + { + m_index = -1; + } + + /** + * Constructor + * Creates a segment between (aA) and (aB), locally referenced + */ + SEG( const VECTOR2I& aA, const VECTOR2I& aB ) : A( aA ), B( aB ) + { + m_index = -1; + } + + /** + * Constructor + * Creates a segment between (aA) and (aB), referenced to a multi-segment shape + * @param aA reference to the start point in the parent shape + * @param aB reference to the end point in the parent shape + * @param aIndex index of the segment within the parent shape + */ + SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) : A( aA ), B( aB ) + { + m_index = aIndex; + } + + /** + * Copy constructor + */ + SEG( const SEG& aSeg ) : A( aSeg.A ), B( aSeg.B ), m_index( aSeg.m_index ) + { + } + + SEG& operator=( const SEG& aSeg ) + { + A = aSeg.A; + B = aSeg.B; + m_index = aSeg.m_index; + + return *this; + } + + /** + * Function LineProject() + * + * Computes the perpendicular projection point of aP on a line passing through + * ends of the segment. + * @param aP point to project + * @return projected point + */ + VECTOR2I LineProject( const VECTOR2I& aP ) const; + + /** + * Function Side() + * + * Determines on which side of directed line passing via segment ends point aP lies. + * @param aP point to determine the orientation wrs to self + * @return: < 0: left, 0 : on the line, > 0 : right + */ + int Side( const VECTOR2I& aP ) const + { + const ecoord det = ( B - A ).Cross( aP - A ); + + return det < 0 ? -1 : ( det > 0 ? 1 : 0 ); + } + + /** + * Function LineDistance() + * + * Returns the closest Euclidean distance between point aP and the line defined by + * the ends of segment (this). + * @param aDetermineSide: when true, the sign of the returned value indicates + * the side of the line at which we are (negative = left) + * @return the distance + */ + int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const; + + /** + * Function NearestPoint() + * + * Computes a point on the segment (this) that is closest to point aP. + * @return: nearest point + */ + const VECTOR2I NearestPoint( const VECTOR2I &aP ) const; + + /** + * Function Intersect() + * + * Computes intersection point of segment (this) with segment aSeg. + * @param aSeg: segment to intersect with + * @param aIgnoreEndpoints: don't treat corner cases (i.e. end of one segment touching the + * other) as intersections. + * @param aLines: treat segments as infinite lines + * @return intersection point, if exists + */ + OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false, + bool aLines = false ) const; + + /** + * Function IntersectLines() + * + * Computes the intersection point of lines passing through ends of (this) and aSeg + * @param aSeg segment defining the line to intersect with + * @return intersection point, if exists + */ + OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const + { + return Intersect( aSeg, false, true ); + } + + bool Collide( const SEG& aSeg, int aClearance ) const; + + ecoord SquaredDistance( const SEG& aSeg ) const; + + /** + * Function Distance() + * + * Computes minimum Euclidean distance to segment aSeg. + * @param aSeg other segment + * @return minimum distance + */ + int Distance( const SEG& aSeg ) const + { + return sqrt( SquaredDistance( aSeg ) ); + } + + ecoord SquaredDistance( const VECTOR2I& aP ) const + { + return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm(); + } + + /** + * Function Distance() + * + * Computes minimum Euclidean distance to point aP. + * @param aP the point + * @return minimum distance + */ + int Distance( const VECTOR2I& aP ) const + { + return sqrt( SquaredDistance( aP ) ); + } + + void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const + { + qA = A.y - B.y; + qB = B.x - A.x; + qC = -qA * A.x - qB * A.y; + } + + /** + * Function Collinear() + * + * Checks if segment aSeg lies on the same line as (this). + * @param aSeg the segment to chech colinearity with + * @return true, when segments are collinear. + */ + bool Collinear( const SEG& aSeg ) const + { + ecoord qa, qb, qc; + CanonicalCoefs( qa, qb, qc ); + + ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc ); + ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc ); + + return ( d1 <= 1 && d2 <= 1 ); + } + + bool ApproxCollinear( const SEG& aSeg ) const + { + ecoord p, q, r; + CanonicalCoefs( p, q, r ); + + ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q ); + ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q ); + + return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1; + } + + bool ApproxParallel ( const SEG& aSeg ) const + { + ecoord p, q, r; + CanonicalCoefs( p, q, r ); + + ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q ); + ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q ); + + return std::abs( dist1 - dist2 ) <= 1; + } + + + bool Overlaps( const SEG& aSeg ) const + { + if( aSeg.A == aSeg.B ) // single point corner case + { + if( A == aSeg.A || B == aSeg.A ) + return false; + + return Contains( aSeg.A ); + } + + if( !Collinear( aSeg ) ) + return false; + + if( Contains( aSeg.A ) || Contains( aSeg.B ) ) + return true; + if( aSeg.Contains( A ) || aSeg.Contains( B ) ) + return true; + + return false; + } + + /** + * Function Length() + * + * Returns the length (this) + * @return length + */ + int Length() const + { + return ( A - B ).EuclideanNorm(); + } + + ecoord SquaredLength() const + { + return ( A - B ).SquaredEuclideanNorm(); + } + + ecoord TCoef( const VECTOR2I& aP ) const; + + /** + * Function Index() + * + * Return the index of this segment in its parent shape (applicable only to non-local segments) + * @return index value + */ + int Index() const + { + return m_index; + } + + bool Contains( const VECTOR2I& aP ) const; + + bool PointCloserThan( const VECTOR2I& aP, int aDist ) const; + + void Reverse() + { + std::swap( A, B ); + } + +private: + bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const; + + ///> index withing the parent shape (used when m_is_local == false) + int m_index; +}; + +inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const +{ + VECTOR2I d = B - A; + ecoord l_squared = d.Dot( d ); + + if( l_squared == 0 ) + return A; + + ecoord t = d.Dot( aP - A ); + + int xp = rescale( t, (ecoord)d.x, l_squared ); + int yp = rescale( t, (ecoord)d.y, l_squared ); + + return A + VECTOR2I( xp, yp ); +} + +inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const +{ + ecoord p = A.y - B.y; + ecoord q = B.x - A.x; + ecoord r = -p * A.x - q * A.y; + + ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q ); + + return aDetermineSide ? dist : std::abs( dist ); +} + +inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const +{ + VECTOR2I d = B - A; + return d.Dot( aP - A); +} + +inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const +{ + VECTOR2I d = B - A; + ecoord l_squared = d.Dot( d ); + + if( l_squared == 0 ) + return A; + + ecoord t = d.Dot( aP - A ); + + if( t < 0 ) + return A; + else if( t > l_squared ) + return B; + + int xp = rescale( t, (ecoord)d.x, l_squared ); + int yp = rescale( t, (ecoord)d.y, l_squared ); + + return A + VECTOR2I( xp, yp ); +} + +inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg ) +{ + aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]"; + + return aStream; +} + +#endif // __SEG_H diff --git a/include/geometry/shape.h b/include/geometry/shape.h new file mode 100644 index 0000000..300de61 --- /dev/null +++ b/include/geometry/shape.h @@ -0,0 +1,171 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_H +#define __SHAPE_H + +#include <string> +#include <sstream> + +#include <math/vector2d.h> +#include <math/box2.h> + +#include <geometry/seg.h> + +/** + * Enum SHAPE_TYPE + * Lists all supported shapes + */ + +enum SHAPE_TYPE +{ + SH_RECT = 0, ///> axis-aligned rectangle + SH_SEGMENT, ///> line segment + SH_LINE_CHAIN, ///> line chain (polyline) + SH_CIRCLE, ///> circle + SH_CONVEX, ///> convex polygon + SH_POLY_SET, ///> any polygon (with holes, etc.) + SH_COMPOUND ///> compound shape, consisting of multiple simple shapes +}; + +/** + * Class SHAPE + * + * Represents an abstract shape on 2D plane. + */ +class SHAPE +{ +protected: + typedef VECTOR2I::extended_type ecoord; + +public: + /** + * Constructor + * + * Creates an empty shape of type aType + */ + + SHAPE( SHAPE_TYPE aType ) : m_type( aType ) + {} + + // Destructor + virtual ~SHAPE() + {} + + /** + * Function Type() + * + * Returns the type of the shape. + * @retval the type + */ + SHAPE_TYPE Type() const + { + return m_type; + } + + /** + * Function Clone() + * + * Returns a dynamically allocated copy of the shape + * @retval copy of the shape + */ + virtual SHAPE* Clone() const + { + assert( false ); + return NULL; + }; + + /** + * Function Collide() + * + * Checks if the boundary of shape (this) lies closer to the point aP than aClearance, + * indicating a collision. + * @return true, if there is a collision. + */ + virtual bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const + { + return Collide( SEG( aP, aP ), aClearance ); + } + + /** + * Function Collide() + * + * Checks if the boundary of shape (this) lies closer to the shape aShape than aClearance, + * indicating a collision. + * @param aShape shape to check collision against + * @param aClearance minimum clearance + * @param aMTV minimum translation vector + * @return true, if there is a collision. + */ + virtual bool Collide( const SHAPE* aShape, int aClearance, VECTOR2I& aMTV ) const; + virtual bool Collide( const SHAPE* aShape, int aClearance = 0 ) const; + + /** + * Function Collide() + * + * Checks if the boundary of shape (this) lies closer to the segment aSeg than aClearance, + * indicating a collision. + * @return true, if there is a collision. + */ + virtual bool Collide( const SEG& aSeg, int aClearance = 0 ) const = 0; + + /** + * Function BBox() + * + * Computes a bounding box of the shape, with a margin of aClearance + * a collision. + * @param aClearance how much the bounding box is expanded wrs to the minimum enclosing rectangle + * for the shape. + * @return the bounding box. + */ + virtual const BOX2I BBox( int aClearance = 0 ) const = 0; + + /** + * Function Centre() + * + * Computes a center-of-mass of the shape + * @return the center-of-mass point + */ + virtual VECTOR2I Centre() const + { + return BBox( 0 ).Centre(); // if nothing better is available.... + } + + virtual void Move ( const VECTOR2I& aVector ) = 0; + + virtual bool IsSolid() const = 0; + + virtual bool Parse( std::stringstream& aStream ); + + virtual const std::string Format( ) const; + +protected: + ///> type of our shape + SHAPE_TYPE m_type; +}; + +bool CollideShapes( const SHAPE* aA, const SHAPE* aB, int aClearance, + bool aNeedMTV, VECTOR2I& aMTV ); + +#endif // __SHAPE_H diff --git a/include/geometry/shape_circle.h b/include/geometry/shape_circle.h new file mode 100644 index 0000000..a915ef9 --- /dev/null +++ b/include/geometry/shape_circle.h @@ -0,0 +1,103 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_CIRCLE_H +#define __SHAPE_CIRCLE_H + +#include "shape.h" + +class SHAPE_CIRCLE : public SHAPE +{ +public: + SHAPE_CIRCLE() : + SHAPE( SH_CIRCLE ), m_radius( 0 ) + {} + + SHAPE_CIRCLE( const VECTOR2I& aCenter, int aRadius ) : + SHAPE( SH_CIRCLE ), m_radius( aRadius ), m_center( aCenter ) + {} + + SHAPE_CIRCLE( const SHAPE_CIRCLE& aOther ) : + SHAPE( SH_CIRCLE ), + m_radius( aOther.m_radius ), + m_center( aOther.m_center ) + {}; + + ~SHAPE_CIRCLE() + {} + + SHAPE* Clone() const + { + return new SHAPE_CIRCLE( *this ); + } + + const BOX2I BBox( int aClearance = 0 ) const + { + const VECTOR2I rc( m_radius + aClearance, m_radius + aClearance ); + + return BOX2I( m_center - rc, rc * 2 ); + } + + bool Collide( const SEG& aSeg, int aClearance = 0 ) const + { + int rc = aClearance + m_radius; + + return aSeg.Distance( m_center ) < rc; + } + + void SetRadius( int aRadius ) + { + m_radius = aRadius; + } + + void SetCenter( const VECTOR2I& aCenter ) + { + m_center = aCenter; + } + + int GetRadius() const + { + return m_radius; + } + + const VECTOR2I GetCenter() const + { + return m_center; + } + + void Move( const VECTOR2I& aVector ) + { + m_center += aVector; + } + + bool IsSolid() const + { + return true; + } +private: + int m_radius; + VECTOR2I m_center; +}; + +#endif diff --git a/include/geometry/shape_convex.h b/include/geometry/shape_convex.h new file mode 100644 index 0000000..308a1b3 --- /dev/null +++ b/include/geometry/shape_convex.h @@ -0,0 +1,189 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2015 Kicad Developers, see change_log.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 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 __SHAPE_CONVEX_H +#define __SHAPE_CONVEX_H + +#include <vector> + +#include <geometry/shape.h> +#include <geometry/seg.h> +#include <geometry/shape_line_chain.h> + +/** + * Class SHAPE_CONVEX + * + * Represents a convex polygon consisting of a zero-thickness closed chain of + * connected line segments. + * + * Internally the vertices are held in a SHAPE_LINE_CHAIN, please note that + * there is a "virtual" line segment between the last and first vertex. + */ +class SHAPE_CONVEX : public SHAPE +{ +public: + /** + * Constructor + * Creates an empty polygon + */ + SHAPE_CONVEX() : + SHAPE( SH_CONVEX ) + { + m_points.SetClosed( true ); + } + + SHAPE_CONVEX( const SHAPE_CONVEX& aOther ) : + SHAPE( SH_CONVEX ), m_points( aOther.m_points ) + {} + + SHAPE* Clone() const + { + return new SHAPE_CONVEX( *this ); + } + + /** + * Function Clear() + * Removes all points from the polygon. + */ + void Clear() + { + m_points.Clear(); + } + + /// @copydoc SHAPE::BBox() + const BOX2I BBox( int aClearance = 0 ) const + { + return m_points.BBox( aClearance ); + } + + /** + * Function PointCount() + * + * Returns the number of points (vertices) in this polygon + * @return number of points + */ + int PointCount() const + { + return m_points.PointCount(); + } + + /** + * Function Point() + * + * Returns a reference to a given point in the polygon. Negative indices + * count from the end of the point list, e.g. -1 means "last point", -2 + * means "second to last point" and so on. + * @param aIndex index of the point + * @return reference to the point + */ + VECTOR2I& Point( int aIndex ) + { + return m_points.Point( aIndex ); + } + + /** + * Function CPoint() + * + * Returns a const reference to a given point in the polygon. Negative + * indices count from the end of the point list, e.g. -1 means "last + * point", -2 means "second to last point" and so on. + * @param aIndex index of the point + * @return const reference to the point + */ + const VECTOR2I& CPoint( int aIndex ) const + { + return m_points.CPoint( aIndex ); + } + + /** + * Function CDPoint() + * + * Returns a given point as a vector with elements of type double. + * + * @param aIndex index of the point + * @return the point with elements of type double + */ + const VECTOR2D CDPoint( int aIndex ) const + { + const VECTOR2I& v = CPoint( aIndex ); + return VECTOR2D( v.x, v.y ); + } + + /** + * Function Vertices() + * + * Returns the list of vertices defining this convex polygon. + * + * @return the list of vertices defining this convex polygon + */ + const SHAPE_LINE_CHAIN& Vertices() const + { + return m_points; + } + + /** + * Function Append() + * + * Appends a new point at the end of the polygon. + * @param aX is X coordinate of the new point + * @param aY is Y coordinate of the new point + */ + void Append( int aX, int aY ) + { + VECTOR2I v( aX, aY ); + Append( v ); + } + + /** + * Function Append() + * + * Appends a new point at the end of the polygon. + * @param aP the new point + */ + void Append( const VECTOR2I& aP ) + { + m_points.Append( aP ); + } + + /// @copydoc SHAPE::Collide() + bool Collide( const SEG& aSeg, int aClearance = 0 ) const + { + return m_points.Collide( aSeg, aClearance ); + } + + void Move( const VECTOR2I& aVector ) + { + m_points.Move( aVector ); + } + + bool IsSolid() const + { + return true; + } + +private: + // vertices + SHAPE_LINE_CHAIN m_points; +}; + +#endif // __SHAPE_CONVEX_H diff --git a/include/geometry/shape_file_io.h b/include/geometry/shape_file_io.h new file mode 100644 index 0000000..78784d7 --- /dev/null +++ b/include/geometry/shape_file_io.h @@ -0,0 +1,69 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2015 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_FILE_IO_H +#define __SHAPE_FILE_IO_H + +#include <cstdio> + +class SHAPE; + +/** + * Class SHAPE_FILE_IO + * + * Helper class for saving/loading shapes from a file. + */ +class SHAPE_FILE_IO +{ + public: + enum IO_MODE + { + IOM_READ = 0, + IOM_APPEND, + IOM_WRITE + }; + + SHAPE_FILE_IO( const std::string& aFilename, IO_MODE aMode = IOM_READ ); + ~SHAPE_FILE_IO(); + + void BeginGroup( const std::string aName = "<noname>"); + void EndGroup(); + + SHAPE* Read(); + + void Write( const SHAPE* aShape, const std::string aName = "<noname>" ); + + void Write( const SHAPE& aShape, const std::string aName = "<noname>" ) + { + Write( &aShape, aName ); + } + + private: + FILE* m_file; + bool m_groupActive; + IO_MODE m_mode; +}; + +#endif diff --git a/include/geometry/shape_index.h b/include/geometry/shape_index.h new file mode 100644 index 0000000..94703ce --- /dev/null +++ b/include/geometry/shape_index.h @@ -0,0 +1,363 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Jacobo Aragunde Pérez + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_INDEX_H +#define __SHAPE_INDEX_H + +#include <vector> +#include <geometry/shape.h> +#include <geometry/rtree.h> + + +/** + * shapeFunctor template function + * + * It is used by SHAPE_INDEX to get a SHAPE* from another type. + * By default relies on T::GetShape() method, should be specialized if the T object + * doesn't allow that method. + * @param aItem generic T object + * @return a SHAPE* object equivalent to object. + */ +template <class T> +static const SHAPE* shapeFunctor( T aItem ) +{ + return aItem->Shape(); +} + +/** + * boundingBox template method + * + * It is used by SHAPE_INDEX to get the bounding box of a generic T object. + * By default relies on T::BBox() method, should be specialized if the T object + * doesn't allow that method. + * @param aObject generic T object + * @return a BOX2I object containing the bounding box of the T object. + */ +template <class T> +BOX2I boundingBox( T aObject ) +{ + return shapeFunctor( aObject )->BBox(); +} + +/** + * acceptVisitor template method + * + * It is used by SHAPE_INDEX to implement Accept(). + * By default relies on V::operation() redefinition, should be specialized if V class + * doesn't have its () operation defined to accept T objects. + * @param aObject generic T object + * @param aVisitor V visitor object + */ +template <class T, class V> +void acceptVisitor( T aObject, V aVisitor ) +{ + aVisitor( aObject ); +} + +/** + * collide template method + * + * It is used by SHAPE_INDEX to implement Query(). + * By default relies on T::Collide(U) method, should be specialized if the T object + * doesn't allow that method. + * @param aObject generic T object + * @param aAnotherObject generic U object + * @param aMinDistance minimum collision distance + * @return if object and anotherObject collide + */ +template <class T, class U> +bool collide( T aObject, U aAnotherObject, int aMinDistance ) +{ + return shapeFunctor( aObject )->Collide( aAnotherObject, aMinDistance ); +} + +template <class T, class V> +bool queryCallback( T aShape, void* aContext ) +{ + V* visitor = (V*) aContext; + + acceptVisitor<T, V>( aShape, *visitor ); + + return true; +} + +template <class T = SHAPE*> +class SHAPE_INDEX +{ + public: + class Iterator + { + private: + typedef typename RTree<T, int, 2, float>::Iterator RTreeIterator; + RTreeIterator iterator; + + /** + * Function Init() + * + * Setup the internal tree iterator. + * @param aTree pointer to a RTREE object + */ + void Init( RTree<T, int, 2, float>* aTree ) + { + aTree->GetFirst( iterator ); + } + + public: + /** + * Iterator constructor + * + * Creates an iterator for the index object + * @param aIndex SHAPE_INDEX object to iterate + */ + Iterator( SHAPE_INDEX* aIndex ) + { + Init( aIndex->m_tree ); + } + + /** + * Operator * (prefix) + * + * Returns the next data element. + */ + T operator*() + { + return *iterator; + } + + /** + * Operator ++ (prefix) + * + * Shifts the iterator to the next element. + */ + bool operator++() + { + return ++iterator; + } + + /** + * Operator ++ (postfix) + * + * Shifts the iterator to the next element. + */ + bool operator++( int ) + { + return ++iterator; + } + + /** + * Function IsNull() + * + * Checks if the iterator has reached the end. + * @return true if it is in an invalid position (data finished) + */ + bool IsNull() + { + return iterator.IsNull(); + } + + /** + * Function IsNotNull() + * + * Checks if the iterator has not reached the end. + * @return true if it is in an valid position (data not finished) + */ + bool IsNotNull() + { + return iterator.IsNotNull(); + } + + /** + * Function Next() + * + * Returns the current element of the iterator and moves to the next + * position. + * @return SHAPE object pointed by the iterator before moving to the next position. + */ + T Next() + { + T object = *iterator; + ++iterator; + + return object; + } + }; + + SHAPE_INDEX(); + + ~SHAPE_INDEX(); + + /** + * Function Add() + * + * Adds a SHAPE to the index. + * @param aShape is the new SHAPE. + */ + void Add( T aShape ); + + /** + * Function Remove() + * + * Removes a SHAPE to the index. + * @param aShape is the new SHAPE. + */ + void Remove( T aShape ); + + /** + * Function RemoveAll() + * + * Removes all the contents of the index. + */ + void RemoveAll(); + + /** + * Function Accept() + * + * Accepts a visitor for every SHAPE object contained in this INDEX. + * @param aVisitor Visitor object to be run + */ + template <class V> + void Accept( V aVisitor ) + { + Iterator iter = this->Begin(); + + while( !iter.IsNull() ) + { + T shape = *iter; + acceptVisitor( shape, aVisitor ); + iter++; + } + } + + /** + * Function Reindex() + * + * Rebuilds the index. This should be used if the geometry of the objects + * contained by the index has changed. + */ + void Reindex(); + + /** + * Function Query() + * + * Runs a callback on every SHAPE object contained in the bounding box of (shape). + * @param aShape shape to search against + * @param aMinDistance distance threshold + * @param aVisitor object to be invoked on every object contained in the search area. + */ + template <class V> + int Query( const SHAPE *aShape, int aMinDistance, V& aVisitor, bool aExact ) + { + BOX2I box = aShape->BBox(); + box.Inflate( aMinDistance ); + + int min[2] = { box.GetX(), box.GetY() }; + int max[2] = { box.GetRight(), box.GetBottom() }; + + return this->m_tree->Search( min, max, aVisitor ); + } + + /** + * Function Begin() + * + * Creates an iterator for the current index object + * @return iterator + */ + Iterator Begin(); + + private: + RTree<T, int, 2, float>* m_tree; +}; + +/* + * Class members implementation + */ + +template <class T> +SHAPE_INDEX<T>::SHAPE_INDEX() +{ + this->m_tree = new RTree<T, int, 2, float>(); +} + +template <class T> +SHAPE_INDEX<T>::~SHAPE_INDEX() +{ + delete this->m_tree; +} + +template <class T> +void SHAPE_INDEX<T>::Add( T aShape ) +{ + BOX2I box = boundingBox( aShape ); + int min[2] = { box.GetX(), box.GetY() }; + int max[2] = { box.GetRight(), box.GetBottom() }; + + this->m_tree->Insert( min, max, aShape ); +} + +template <class T> +void SHAPE_INDEX<T>::Remove( T aShape ) +{ + BOX2I box = boundingBox( aShape ); + int min[2] = { box.GetX(), box.GetY() }; + int max[2] = { box.GetRight(), box.GetBottom() }; + + this->m_tree->Remove( min, max, aShape ); +} + +template <class T> +void SHAPE_INDEX<T>::RemoveAll() +{ + this->m_tree->RemoveAll(); +} + +template <class T> +void SHAPE_INDEX<T>::Reindex() +{ + RTree<T, int, 2, float>* newTree; + newTree = new RTree<T, int, 2, float>(); + + Iterator iter = this->Begin(); + + while( !iter.IsNull() ) + { + T shape = *iter; + BOX2I box = boundingBox( shape ); + int min[2] = { box.GetX(), box.GetY() }; + int max[2] = { box.GetRight(), box.GetBottom() }; + newTree->Insert( min, max, shape ); + iter++; + } + + delete this->m_tree; + this->m_tree = newTree; +} + +template <class T> +typename SHAPE_INDEX<T>::Iterator SHAPE_INDEX<T>::Begin() +{ + return Iterator( this ); +} + +#endif diff --git a/include/geometry/shape_index_list.h b/include/geometry/shape_index_list.h new file mode 100644 index 0000000..194ae5f --- /dev/null +++ b/include/geometry/shape_index_list.h @@ -0,0 +1,291 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_INDEX_LIST_H +#define __SHAPE_INDEX_LIST_H + +#include <boost/unordered_map.hpp> + +template <class T> +const SHAPE* defaultShapeFunctor( const T aItem ) +{ + return aItem->Shape(); +} + +template <class T, const SHAPE* (ShapeFunctor) (const T) = defaultShapeFunctor<T> > +class SHAPE_INDEX_LIST +{ + struct SHAPE_ENTRY + { + SHAPE_ENTRY( T aParent ) + { + shape = ShapeFunctor( aParent ); + bbox = shape->BBox( 0 ); + parent = aParent; + } + + ~SHAPE_ENTRY() + { + } + + T parent; + const SHAPE* shape; + BOX2I bbox; + }; + + typedef std::vector<SHAPE_ENTRY> SHAPE_VEC; + typedef typename std::vector<SHAPE_ENTRY>::iterator SHAPE_VEC_ITER; + +public: + // "Normal" iterator interface, for STL algorithms. + class iterator + { + public: + iterator() + {} + + iterator( SHAPE_VEC_ITER aCurrent ) : + m_current( aCurrent ) + {} + + iterator( const iterator& aB ) : + m_current( aB.m_current ) + {} + + T operator*() const + { + return (*m_current).parent; + } + + void operator++() + { + ++m_current; + } + + iterator& operator++( int aDummy ) + { + ++m_current; + return *this; + } + + bool operator==( const iterator& aRhs ) const + { + return m_current == aRhs.m_current; + } + + bool operator!=( const iterator& aRhs ) const + { + return m_current != aRhs.m_current; + } + + const iterator& operator=( const iterator& aRhs ) + { + m_current = aRhs.m_current; + return *this; + } + + private: + SHAPE_VEC_ITER m_current; + }; + + // "Query" iterator, for iterating over a set of spatially matching shapes. + class query_iterator + { + public: + query_iterator() + { + } + + query_iterator( SHAPE_VEC_ITER aCurrent, SHAPE_VEC_ITER aEnd, SHAPE* aShape, + int aMinDistance, bool aExact ) : + m_end( aEnd ), + m_current( aCurrent ), + m_shape( aShape ), + m_minDistance( aMinDistance ), + m_exact( aExact ) + { + if( aShape ) + { + m_refBBox = aShape->BBox(); + next(); + } + } + + query_iterator( const query_iterator& aB ) : + m_end( aB.m_end ), + m_current( aB.m_current ), + m_shape( aB.m_shape ), + m_minDistance( aB.m_minDistance ), + m_exact( aB.m_exact ), + m_refBBox( aB.m_refBBox ) + { + } + + T operator*() const + { + return (*m_current).parent; + } + + query_iterator& operator++() + { + ++m_current; + next(); + return *this; + } + + query_iterator& operator++( int aDummy ) + { + ++m_current; + next(); + return *this; + } + + bool operator==( const query_iterator& aRhs ) const + { + return m_current == aRhs.m_current; + } + + bool operator!=( const query_iterator& aRhs ) const + { + return m_current != aRhs.m_current; + } + + const query_iterator& operator=( const query_iterator& aRhs ) + { + m_end = aRhs.m_end; + m_current = aRhs.m_current; + m_shape = aRhs.m_shape; + m_minDistance = aRhs.m_minDistance; + m_exact = aRhs.m_exact; + m_refBBox = aRhs.m_refBBox; + return *this; + } + + private: + void next() + { + while( m_current != m_end ) + { + if( m_refBBox.Distance( m_current->bbox ) <= m_minDistance ) + { + if( !m_exact || m_current->shape->Collide( m_shape, m_minDistance ) ) + return; + } + + ++m_current; + } + } + + SHAPE_VEC_ITER m_end; + SHAPE_VEC_ITER m_current; + BOX2I m_refBBox; + bool m_exact; + SHAPE* m_shape; + int m_minDistance; + }; + + void Add( T aItem ) + { + SHAPE_ENTRY s( aItem ); + + m_shapes.push_back( s ); + } + + void Remove( const T aItem ) + { + SHAPE_VEC_ITER i; + + for( i = m_shapes.begin(); i != m_shapes.end(); ++i ) + { + if( i->parent == aItem ) + break; + } + + if( i == m_shapes.end() ) + return; + + m_shapes.erase( i ); + } + + int Size() const + { + return m_shapes.size(); + } + + template <class Visitor> + int Query( const SHAPE* aShape, int aMinDistance, Visitor& aV, bool aExact = true ) // const + { + SHAPE_VEC_ITER i; + int n = 0; + VECTOR2I::extended_type minDistSq = (VECTOR2I::extended_type) aMinDistance * aMinDistance; + + BOX2I refBBox = aShape->BBox(); + + for( i = m_shapes.begin(); i != m_shapes.end(); ++i ) + { + if( refBBox.SquaredDistance( i->bbox ) <= minDistSq ) + { + if( !aExact || i->shape->Collide( aShape, aMinDistance ) ) + { + n++; + + if( !aV( i->parent ) ) + return n; + } + } + } + + return n; + } + + void Clear() + { + m_shapes.clear(); + } + + query_iterator qbegin( SHAPE* aShape, int aMinDistance, bool aExact ) + { + return query_iterator( m_shapes.begin(), m_shapes.end(), aShape, aMinDistance, aExact ); + } + + const query_iterator qend() + { + return query_iterator( m_shapes.end(), m_shapes.end(), NULL, 0, false ); + } + + iterator begin() + { + return iterator( m_shapes.begin() ); + } + + iterator end() + { + return iterator( m_shapes.end() ); + } + +private: + SHAPE_VEC m_shapes; +}; + +#endif diff --git a/include/geometry/shape_line_chain.h b/include/geometry/shape_line_chain.h new file mode 100644 index 0000000..ae2bf5e --- /dev/null +++ b/include/geometry/shape_line_chain.h @@ -0,0 +1,598 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_LINE_CHAIN +#define __SHAPE_LINE_CHAIN + +#include <vector> +#include <sstream> + +#include <boost/optional.hpp> + +#include <math/vector2d.h> +#include <geometry/shape.h> +#include <geometry/seg.h> + +/** + * Class SHAPE_LINE_CHAIN + * + * Represents a polyline (an zero-thickness chain of connected line segments). + * I purposedly didn't name it "polyline" to avoid confusion with the existing CPolyLine + * class in pcbnew. + * + * SHAPE_LINE_CHAIN class shall not be used for polygons! + */ +class SHAPE_LINE_CHAIN : public SHAPE +{ +private: + typedef std::vector<VECTOR2I>::iterator point_iter; + typedef std::vector<VECTOR2I>::const_iterator point_citer; + +public: + /** + * Struct INTERSECTION + * + * Represents an intersection between two line segments + */ + struct INTERSECTION + { + /// segment belonging from the (this) argument of Intersect() + SEG our; + /// segment belonging from the aOther argument of Intersect() + SEG their; + /// point of intersection between our and their. + VECTOR2I p; + }; + + typedef std::vector<INTERSECTION> INTERSECTIONS; + + /** + * Constructor + * Initializes an empty line chain. + */ + SHAPE_LINE_CHAIN() : + SHAPE( SH_LINE_CHAIN ), m_closed( false ) + {} + + /** + * Copy Constructor + */ + SHAPE_LINE_CHAIN( const SHAPE_LINE_CHAIN& aShape ) : + SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed ) + {} + + /** + * Constructor + * Initializes a 2-point line chain (a single segment) + */ + SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) : + SHAPE( SH_LINE_CHAIN ), m_closed( false ) + { + m_points.resize( 2 ); + m_points[0] = aA; + m_points[1] = aB; + } + + SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) : + SHAPE( SH_LINE_CHAIN ), m_closed( false ) + { + m_points.resize( 3 ); + m_points[0] = aA; + m_points[1] = aB; + m_points[2] = aC; + } + + SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) : + SHAPE( SH_LINE_CHAIN ), m_closed( false ) + { + m_points.resize( 4 ); + m_points[0] = aA; + m_points[1] = aB; + m_points[2] = aC; + m_points[3] = aD; + } + + + SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) : + SHAPE( SH_LINE_CHAIN ), + m_closed( false ) + { + m_points.resize( aCount ); + + for( int i = 0; i < aCount; i++ ) + m_points[i] = *aV++; + } + + ~SHAPE_LINE_CHAIN() + {} + + SHAPE* Clone() const; + + /** + * Function Clear() + * Removes all points from the line chain. + */ + void Clear() + { + m_points.clear(); + m_closed = false; + } + + /** + * Function SetClosed() + * + * Marks the line chain as closed (i.e. with a segment connecting the last point with + * the first point). + * @param aClosed: whether the line chain is to be closed or not. + */ + void SetClosed( bool aClosed ) + { + m_closed = aClosed; + } + + /** + * Function IsClosed() + * + * @return aClosed: true, when our line is closed. + */ + bool IsClosed() const + { + return m_closed; + } + + /** + * Function SegmentCount() + * + * Returns number of segments in this line chain. + * @return number of segments + */ + int SegmentCount() const + { + int c = m_points.size() - 1; + if( m_closed ) + c++; + + return std::max( 0, c ); + } + + /** + * Function PointCount() + * + * Returns the number of points (vertices) in this line chain + * @return number of points + */ + int PointCount() const + { + return m_points.size(); + } + + /** + * Function Segment() + * + * Returns a segment referencing to the segment (index) in the line chain. + * Modifying ends of the returned segment will modify corresponding points in the line chain. + * @param aIndex: index of the segment in the line chain. Negative values are counted from + * the end (i.e. -1 means the last segment in the line chain) + * @return SEG referenced to given segment in the line chain + */ + SEG Segment( int aIndex ) + { + if( aIndex < 0 ) + aIndex += SegmentCount(); + + if( aIndex == (int)( m_points.size() - 1 ) && m_closed ) + return SEG( m_points[aIndex], m_points[0], aIndex ); + else + return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex ); + } + + /** + * Function CSegment() + * + * Returns a read-only segment referencing to the segment (index) in the line chain. + * @param aIndex: index of the segment in the line chain. Negative values are counted from + * the end (i.e. -1 means the last segment in the line chain) + * @return SEG referenced to given segment in the line chain + */ + const SEG CSegment( int aIndex ) const + { + if( aIndex < 0 ) + aIndex += SegmentCount(); + + if( aIndex == (int)( m_points.size() - 1 ) && m_closed ) + return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ), + const_cast<VECTOR2I&>( m_points[0] ), aIndex ); + else + return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ), + const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex ); + } + + /** + * Function Point() + * + * Returns a reference to a given point in the line chain. + * @param aIndex index of the point + * @return reference to the point + */ + VECTOR2I& Point( int aIndex ) + { + if( aIndex < 0 ) + aIndex += PointCount(); + + return m_points[aIndex]; + } + + /** + * Function CPoint() + * + * Returns a const reference to a given point in the line chain. + * @param aIndex index of the point + * @return const reference to the point + */ + const VECTOR2I& CPoint( int aIndex ) const + { + if( aIndex < 0 ) + aIndex += PointCount(); + else if( aIndex >= PointCount() ) + aIndex -= PointCount(); + + return m_points[aIndex]; + } + + /// @copydoc SHAPE::BBox() + const BOX2I BBox( int aClearance = 0 ) const + { + BOX2I bbox; + bbox.Compute( m_points ); + + if( aClearance != 0 ) + bbox.Inflate( aClearance ); + + return bbox; + } + + /** + * Function Collide() + * + * Checks if point aP lies closer to us than aClearance. + * @param aP the point to check for collisions with + * @param aClearance minimum distance that does not qualify as a collision. + * @return true, when a collision has been found + */ + bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const; + + /** + * Function Collide() + * + * Checks if segment aSeg lies closer to us than aClearance. + * @param aSeg the segment to check for collisions with + * @param aClearance minimum distance that does not qualify as a collision. + * @return true, when a collision has been found + */ + bool Collide( const SEG& aSeg, int aClearance = 0 ) const; + + /** + * Function Distance() + * + * Computes the minimum distance between the line chain and a point aP. + * @param aP the point + * @return minimum distance. + */ + int Distance( const VECTOR2I& aP ) const; + + /** + * Function Reverse() + * + * Reverses point order in the line chain. + * @return line chain with reversed point order (original A-B-C-D: returned D-C-B-A) + */ + const SHAPE_LINE_CHAIN Reverse() const; + + /** + * Function Length() + * + * Returns length of the line chain in Euclidean metric. + * @return length of the line chain + */ + int Length() const; + + /** + * Function Append() + * + * Appends a new point at the end of the line chain. + * @param aX is X coordinate of the new point + * @param aY is Y coordinate of the new point + */ + void Append( int aX, int aY, bool aAllowDuplication = false ) + { + VECTOR2I v( aX, aY ); + Append( v, aAllowDuplication ); + } + + /** + * Function Append() + * + * Appends a new point at the end of the line chain. + * @param aP the new point + */ + void Append( const VECTOR2I& aP, bool aAllowDuplication = false ) + { + if( m_points.size() == 0 ) + m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) ); + + if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP ) + { + m_points.push_back( aP ); + m_bbox.Merge( aP ); + } + } + + /** + * Function Append() + * + * Appends another line chain at the end. + * @param aOtherLine the line chain to be appended. + */ + void Append( const SHAPE_LINE_CHAIN& aOtherLine ) + { + if( aOtherLine.PointCount() == 0 ) + return; + + else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) ) + { + const VECTOR2I p = aOtherLine.CPoint( 0 ); + m_points.push_back( p ); + m_bbox.Merge( p ); + } + + for( int i = 1; i < aOtherLine.PointCount(); i++ ) + { + const VECTOR2I p = aOtherLine.CPoint( i ); + m_points.push_back( p ); + m_bbox.Merge( p ); + } + } + + void Insert( int aVertex, const VECTOR2I& aP ) + { + m_points.insert( m_points.begin() + aVertex, aP ); + } + + /** + * Function Replace() + * + * Replaces points with indices in range [start_index, end_index] with a single + * point aP. + * @param aStartIndex start of the point range to be replaced (inclusive) + * @param aEndIndex end of the point range to be replaced (inclusive) + * @param aP replacement point + */ + void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP ); + + /** + * Function Replace() + * + * Replaces points with indices in range [start_index, end_index] with the points from + * line chain aLine. + * @param aStartIndex start of the point range to be replaced (inclusive) + * @param aEndIndex end of the point range to be replaced (inclusive) + * @param aLine replacement line chain. + */ + void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine ); + + /** + * Function Remove() + * + * Removes the range of points [start_index, end_index] from the line chain. + * @param aStartIndex start of the point range to be replaced (inclusive) + * @param aEndIndex end of the point range to be replaced (inclusive) + */ + void Remove( int aStartIndex, int aEndIndex ); + + /** + * Function Split() + * + * Inserts the point aP belonging to one of the our segments, splitting the adjacent + * segment in two. + * @param aP the point to be inserted + * @return index of the newly inserted point (or a negative value if aP does not lie on + * our line) + */ + int Split( const VECTOR2I& aP ); + + /** + * Function Find() + * + * Searches for point aP. + * @param aP the point to be looked for + * @return index of the correspoinding point in the line chain or negative when not found. + */ + int Find( const VECTOR2I& aP ) const; + + /** + * Function FindSegment() + * + * Searches for segment containing point aP. + * @param aP the point to be looked for + * @return index of the correspoinding segment in the line chain or negative when not found. + */ + int FindSegment( const VECTOR2I& aP ) const; + + /** + * Function Slice() + * + * Returns a subset of this line chain containing the [start_index, end_index] range of points. + * @param aStartIndex start of the point range to be returned (inclusive) + * @param aEndIndex end of the point range to be returned (inclusive) + * @return cut line chain. + */ + const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const; + + struct compareOriginDistance + { + compareOriginDistance( const VECTOR2I& aOrigin ): + m_origin( aOrigin ) + {} + + bool operator()( const INTERSECTION& aA, const INTERSECTION& aB ) + { + return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm(); + } + + VECTOR2I m_origin; + }; + + bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const; + + /** + * Function Intersect() + * + * Finds all intersection points between our line chain and the segment aSeg. + * @param aSeg the segment chain to find intersections with + * @param aIp reference to a vector to store found intersections. Intersection points + * are sorted with increasing distances from point aSeg.a. + * @return number of intersections found + */ + int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const; + + /** + * Function Intersect() + * + * Finds all intersection points between our line chain and the line chain aChain. + * @param aChain the line chain to find intersections with + * @param aIp reference to a vector to store found intersections. Intersection points + * are sorted with increasing path lengths from the starting point of aChain. + * @return number of intersections found + */ + int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const; + + /** + * Function PathLength() + * + * Computes the walk path length from the beginning of the line chain and + * the point aP belonging to our line. + * @return: path length in Euclidean metric or negative if aP does not belong to + * the line chain. + */ + int PathLength( const VECTOR2I& aP ) const; + + /** + * Function PointInside() + * + * Checks if point aP lies inside a convex polygon defined by the line chain. For closed + * shapes only. + * @param aP point to check + * @return true if the point is inside the shape (edge is not treated as being inside). + */ + bool PointInside( const VECTOR2I& aP ) const; + + /** + * Function PointOnEdge() + * + * Checks if point aP lies on an edge or vertex of the line chain. + * @param aP point to check + * @return true if the point lies on the edge. + */ + bool PointOnEdge( const VECTOR2I& aP ) const; + + /** + * Function SelfIntersecting() + * + * Checks if the line chain is self-intersecting. + * @return (optional) first found self-intersection point. + */ + const boost::optional<INTERSECTION> SelfIntersecting() const; + + /** + * Function Simplify() + * + * Simplifies the line chain by removing colinear adjacent segments and duplicate vertices. + * @return reference to self. + */ + SHAPE_LINE_CHAIN& Simplify(); + + /** + * Function NearestPoint() + * + * Finds a point on the line chain that is closest to point aP. + * @return the nearest point. + */ + const VECTOR2I NearestPoint( const VECTOR2I& aP ) const; + + /** + * Function NearestPoint() + * + * Finds a point on the line chain that is closest to the line defined + * by the points of segment aSeg, also returns the distance. + * @param aSeg Segment defining the line. + * @param dist reference receiving the distance to the nearest point. + * @return the nearest point. + */ + const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const; + + /// @copydoc SHAPE::Format() + const std::string Format() const; + + /// @copydoc SHAPE::Parse() + bool Parse( std::stringstream& aStream ); + + bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const + { + if( PointCount() != aRhs.PointCount() ) + return true; + + for( int i = 0; i < PointCount(); i++ ) + { + if( CPoint( i ) != aRhs.CPoint( i ) ) + return true; + } + + return false; + } + + bool CompareGeometry( const SHAPE_LINE_CHAIN & aOther ) const; + + void Move( const VECTOR2I& aVector ) + { + for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i ) + (*i) += aVector; + } + + bool IsSolid() const + { + return false; + } + +private: + /// array of vertices + std::vector<VECTOR2I> m_points; + + /// is the line chain closed? + bool m_closed; + + /// cached bounding box + BOX2I m_bbox; +}; + +#endif // __SHAPE_LINE_CHAIN diff --git a/include/geometry/shape_poly_set.h b/include/geometry/shape_poly_set.h new file mode 100644 index 0000000..24c4a91 --- /dev/null +++ b/include/geometry/shape_poly_set.h @@ -0,0 +1,374 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2015 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_POLY_SET_H +#define __SHAPE_POLY_SET_H + +#include <vector> +#include <cstdio> +#include <geometry/shape.h> +#include <geometry/shape_line_chain.h> + +#include "clipper.hpp" + + +/** + * Class SHAPE_POLY_SET + * + * Represents a set of closed polygons. Polygons may be nonconvex, self-intersecting + * and have holes. Provides boolean operations (using Clipper library as the backend). + * + * TODO: add convex partitioning & spatial index + */ +class SHAPE_POLY_SET : public SHAPE +{ + public: + ///> represents a single polygon outline with holes. The first entry is the outline, + ///> the remaining (if any), are the holes + typedef std::vector<SHAPE_LINE_CHAIN> POLYGON; + + /** + * Class ITERATOR_TEMPLATE + * + * Base class for iterating over all vertices in a given SHAPE_POLY_SET + */ + template <class T> + class ITERATOR_TEMPLATE + { + public: + + bool IsEndContour() const + { + return m_currentVertex + 1 == m_poly->CPolygon( m_currentOutline )[0].PointCount(); + } + + bool IsLastContour() const + { + return m_currentOutline == m_lastOutline; + } + + operator bool() const + { + return m_currentOutline <= m_lastOutline; + } + + void Advance() + { + m_currentVertex ++; + + if( m_currentVertex >= m_poly->CPolygon( m_currentOutline )[0].PointCount() ) + { + m_currentVertex = 0; + m_currentOutline++; + } + } + + void operator++( int dummy ) + { + Advance(); + } + + void operator++() + { + Advance(); + } + + T& Get() + { + return m_poly->Polygon( m_currentOutline )[0].Point( m_currentVertex ); + } + + T& operator*() + { + return Get(); + } + + T* operator->() + { + return &Get(); + } + + + private: + friend class SHAPE_POLY_SET; + + SHAPE_POLY_SET* m_poly; + int m_currentOutline; + int m_lastOutline; + int m_currentVertex; + }; + + typedef ITERATOR_TEMPLATE<VECTOR2I> ITERATOR; + typedef ITERATOR_TEMPLATE<const VECTOR2I> CONST_ITERATOR; + + SHAPE_POLY_SET(); + ~SHAPE_POLY_SET(); + + ///> Creates a new empty polygon in the set and returns its index + int NewOutline(); + + ///> Creates a new hole in a given outline + int NewHole( int aOutline = -1 ); + + ///> Adds a new outline to the set and returns its index + int AddOutline( const SHAPE_LINE_CHAIN& aOutline ); + + ///> Adds a new hole to the given outline (default: last) and returns its index + int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 ); + + ///> Appends a vertex at the end of the given outline/hole (default: the last outline) + int Append( int x, int y, int aOutline = -1, int aHole = -1 ); + + ///> Merges polygons from two sets. + void Append( const SHAPE_POLY_SET& aSet ); + + ///> Appends a vertex at the end of the given outline/hole (default: the last outline) + void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 ); + + ///> Returns the index-th vertex in a given hole outline within a given outline + VECTOR2I& Vertex( int index, int aOutline = -1, int aHole = -1 ); + + ///> Returns the index-th vertex in a given hole outline within a given outline + const VECTOR2I& CVertex( int index, int aOutline = -1, int aHole = -1 ) const; + + ///> Returns true if any of the outlines is self-intersecting + bool IsSelfIntersecting(); + + ///> Returns the number of outlines in the set + int OutlineCount() const { return m_polys.size(); } + + ///> Returns the number of vertices in a given outline/hole + int VertexCount( int aOutline = -1, int aHole = -1 ) const; + + ///> Returns the number of holes in a given outline + int HoleCount( int aOutline ) const + { + if( (aOutline > (int)m_polys.size()) || (m_polys[aOutline].size() < 2) ) + return 0; + return m_polys[aOutline].size() - 1; + } + + ///> Returns the reference to aIndex-th outline in the set + SHAPE_LINE_CHAIN& Outline( int aIndex ) + { + return m_polys[aIndex][0]; + } + + ///> Returns the reference to aHole-th hole in the aIndex-th outline + SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole ) + { + return m_polys[aOutline][aHole + 1]; + } + + ///> Returns the aIndex-th subpolygon in the set + POLYGON& Polygon( int aIndex ) + { + return m_polys[aIndex]; + } + + const SHAPE_LINE_CHAIN& COutline( int aIndex ) const + { + return m_polys[aIndex][0]; + } + + const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const + { + return m_polys[aOutline][aHole + 1]; + } + + const POLYGON& CPolygon( int aIndex ) const + { + return m_polys[aIndex]; + } + + ///> Returns an iterator object, for iterating between aFirst and aLast outline. + ITERATOR Iterate( int aFirst, int aLast ) + { + ITERATOR iter; + + iter.m_poly = this; + iter.m_currentOutline = aFirst; + iter.m_lastOutline = aLast < 0 ? OutlineCount() - 1 : aLast; + iter.m_currentVertex = 0; + + return iter; + } + + ///> Returns an iterator object, for iterating aOutline-th outline + ITERATOR Iterate( int aOutline ) + { + return Iterate( aOutline, aOutline ); + } + + ///> Returns an iterator object, for all outlines in the set (no holes) + ITERATOR Iterate() + { + return Iterate( 0, OutlineCount() - 1 ); + } + + CONST_ITERATOR CIterate( int aFirst, int aLast ) const + { + CONST_ITERATOR iter; + + iter.m_poly = const_cast<SHAPE_POLY_SET*>( this ); + iter.m_currentOutline = aFirst; + iter.m_lastOutline = aLast < 0 ? OutlineCount() - 1 : aLast; + iter.m_currentVertex = 0; + + return iter; + } + + CONST_ITERATOR CIterate( int aOutline ) const + { + return CIterate( aOutline, aOutline ); + } + + CONST_ITERATOR CIterate() const + { + return CIterate( 0, OutlineCount() - 1 ); + } + + + ///> Performs boolean polyset union + ///> For aFastMode meaning, see function booleanOp + void BooleanAdd( const SHAPE_POLY_SET& b, bool aFastMode = false ); + + ///> Performs boolean polyset difference + ///> For aFastMode meaning, see function booleanOp + void BooleanSubtract( const SHAPE_POLY_SET& b, bool aFastMode = false ); + + ///> Performs boolean polyset intersection + ///> For aFastMode meaning, see function booleanOp + void BooleanIntersection( const SHAPE_POLY_SET& b, bool aFastMode = false ); + + ///> Performs boolean polyset union between a and b, store the result in it self + ///> For aFastMode meaning, see function booleanOp + void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b, bool aFastMode = false ); + + ///> Performs boolean polyset difference between a and b, store the result in it self + ///> For aFastMode meaning, see function booleanOp + void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b, bool aFastMode = false ); + + ///> Performs boolean polyset intersection between a and b, store the result in it self + ///> For aFastMode meaning, see function booleanOp + void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b, bool aFastMode = false ); + + ///> Performs outline inflation/deflation, using round corners. + void Inflate( int aFactor, int aCircleSegmentsCount ); + + ///> Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the outer ring + ///> to the inner holes + ///> For aFastMode meaning, see function booleanOp + void Fracture( bool aFastMode = false ); + + ///> Converts a set of slitted polygons to a set of polygons with holes + void Unfracture(); + + ///> Returns true if the polygon set has any holes. + bool HasHoles() const; + + ///> Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) + ///> For aFastMode meaning, see function booleanOp + void Simplify( bool aFastMode = false); + + /// @copydoc SHAPE::Format() + const std::string Format() const; + + /// @copydoc SHAPE::Parse() + bool Parse( std::stringstream& aStream ); + + /// @copydoc SHAPE::Move() + void Move( const VECTOR2I& aVector ); + + /// @copydoc SHAPE::IsSolid() + bool IsSolid() const + { + return true; + } + + const BOX2I BBox( int aClearance = 0 ) const; + + // fixme: add collision support + bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const { return false; } + bool Collide( const SEG& aSeg, int aClearance = 0 ) const { return false; } + + + ///> Returns true is a given subpolygon contains the point aP. If aSubpolyIndex < 0 (default value), + ///> checks all polygons in the set + bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1 ) const; + + ///> Returns true if the set is empty (no polygons at all) + bool IsEmpty() const + { + return m_polys.size() == 0; + } + + ///> Removes all outlines & holes (clears) the polygon set. + void RemoveAllContours(); + + ///> Returns total number of vertices stored in the set. + int TotalVertices() const; + + ///> Deletes aIdx-th polygon from the set + void DeletePolygon( int aIdx ); + + private: + + SHAPE_LINE_CHAIN& getContourForCorner( int aCornerId, int& aIndexWithinContour ); + VECTOR2I& vertex( int aCornerId ); + const VECTOR2I& cvertex( int aCornerId ) const; + + + void fractureSingle( POLYGON& paths ); + void importTree( ClipperLib::PolyTree* tree ); + + /** Function booleanOp + * this is the engine to execute all polygon boolean transforms + * (AND, OR, ... and polygon simplification (merging overlaping polygons) + * @param aType is the transform type ( see ClipperLib::ClipType ) + * @param aOtherShape is the SHAPE_LINE_CHAIN to combine with me. + * @param aFastMode is an option to choos if the result is a weak polygon + * or a stricty simple polygon. + * if aFastMode is true the result can be a weak polygon + * if aFastMode is false (default) the result is (theorically) a strictly + * simple polygon, but calculations can be really significantly time consuming + */ + void booleanOp( ClipperLib::ClipType aType, + const SHAPE_POLY_SET& aOtherShape, bool aFastMode = false ); + + void booleanOp( ClipperLib::ClipType aType, + const SHAPE_POLY_SET& aShape, + const SHAPE_POLY_SET& aOtherShape, bool aFastMode = false ); + + bool pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const; + + const ClipperLib::Path convertToClipper( const SHAPE_LINE_CHAIN& aPath, bool aRequiredOrientation ); + const SHAPE_LINE_CHAIN convertFromClipper( const ClipperLib::Path& aPath ); + + typedef std::vector<POLYGON> Polyset; + + Polyset m_polys; +}; + +#endif diff --git a/include/geometry/shape_rect.h b/include/geometry/shape_rect.h new file mode 100644 index 0000000..47e6b13 --- /dev/null +++ b/include/geometry/shape_rect.h @@ -0,0 +1,168 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_RECT_H +#define __SHAPE_RECT_H + +#include <geometry/shape.h> +#include <geometry/shape_line_chain.h> +#include <geometry/shape_circle.h> +#include <geometry/seg.h> + +class SHAPE_RECT : public SHAPE +{ +public: + /** + * Constructor + * Creates an empty (0-sized) rectangle + */ + SHAPE_RECT() : + SHAPE( SH_RECT ), m_w( 0 ), m_h( 0 ) + {} + + /** + * Constructor + * Creates a rectangle defined by top-left corner (aX0, aY0), width aW and height aH. + */ + SHAPE_RECT( int aX0, int aY0, int aW, int aH ) : + SHAPE( SH_RECT ), m_p0( aX0, aY0 ), m_w( aW ), m_h( aH ) + {} + + /** + * Constructor + * Creates a rectangle defined by top-left corner aP0, width aW and height aH. + */ + SHAPE_RECT( const VECTOR2I& aP0, int aW, int aH ) : + SHAPE( SH_RECT ), m_p0( aP0 ), m_w( aW ), m_h( aH ) + {} + + SHAPE_RECT( const SHAPE_RECT& aOther ) : + SHAPE( SH_RECT ), + m_p0( aOther.m_p0 ), + m_w( aOther.m_w ), + m_h( aOther.m_h ) + {}; + + SHAPE* Clone() const + { + return new SHAPE_RECT( *this ); + } + + /// @copydoc SHAPE::BBox() + const BOX2I BBox( int aClearance = 0 ) const + { + BOX2I bbox( VECTOR2I( m_p0.x - aClearance, m_p0.y - aClearance ), + VECTOR2I( m_w + 2 * aClearance, m_h + 2 * aClearance ) ); + //printf("bb : %s\n",bbox.Format().c_str()); + return bbox; + } + + /** + * Function Diagonal() + * + * Returns length of the diagonal of the rectangle + * @return diagonal length + */ + int Diagonal() const + { + return VECTOR2I( m_w, m_h ).EuclideanNorm(); + } + + /// @copydoc SHAPE::Collide() + bool Collide( const SEG& aSeg, int aClearance = 0 ) const; + + /** + * Function GetPosition() + * + * @return top-left corner of the rectangle + */ + const VECTOR2I& GetPosition() const + { + return m_p0; + } + + /** + * Function GetSize() + * + * @return size of the rectangle + */ + const VECTOR2I GetSize() const + { + return VECTOR2I( m_w, m_h ); + } + + /** + * Function GetWidth() + * + * @return width of the rectangle + */ + const int GetWidth() const + { + return m_w; + } + + /** + * Function GetHeight() + * + * @return height of the rectangle + */ + const int GetHeight() const + { + return m_h; + } + + void Move( const VECTOR2I& aVector ) + { + m_p0 += aVector; + } + + bool IsSolid() const + { + return true; + } + + const SHAPE_LINE_CHAIN Outline() const + { + SHAPE_LINE_CHAIN rv; + rv.Append( m_p0 ); + rv.Append( m_p0.x, m_p0.y + m_w ); + rv.Append( m_p0.x + m_h, m_p0.y + m_w ); + rv.Append( m_p0.x + m_h, m_p0.y ); + rv.Append( m_p0 ); + rv.SetClosed( true ); + return rv; + } + +private: + ///> Top-left corner + VECTOR2I m_p0; + + ///> Width + int m_w; + + ///> Height + int m_h; +}; + +#endif // __SHAPE_RECT_H diff --git a/include/geometry/shape_segment.h b/include/geometry/shape_segment.h new file mode 100644 index 0000000..71ed5b1 --- /dev/null +++ b/include/geometry/shape_segment.h @@ -0,0 +1,101 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 __SHAPE_SEGMENT_H +#define __SHAPE_SEGMENT_H + +#include <geometry/shape.h> +#include <geometry/seg.h> + +class SHAPE_SEGMENT : public SHAPE { + +public: + SHAPE_SEGMENT(): + SHAPE( SH_SEGMENT ), m_width( 0 ) {}; + + SHAPE_SEGMENT( const VECTOR2I& aA, const VECTOR2I& aB, int aWidth = 0 ): + SHAPE( SH_SEGMENT ), m_seg( aA, aB ), m_width( aWidth ) {}; + + SHAPE_SEGMENT( const SEG& aSeg, int aWidth = 0 ): + SHAPE( SH_SEGMENT ), m_seg( aSeg ), m_width( aWidth ) {}; + + ~SHAPE_SEGMENT() {}; + + SHAPE* Clone() const + { + return new SHAPE_SEGMENT( m_seg, m_width ); + } + + const BOX2I BBox( int aClearance = 0 ) const + { + return BOX2I( m_seg.A, m_seg.B - m_seg.A ).Inflate( aClearance + ( m_width + 1 ) / 2 ); + } + + bool Collide( const SEG& aSeg, int aClearance = 0 ) const + { + return m_seg.Distance( aSeg ) < ( m_width + 1 ) / 2 + aClearance; + } + + bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const + { + return m_seg.Distance( aP ) < ( m_width + 1 ) / 2 + aClearance; + } + + void SetSeg( const SEG& aSeg ) + { + m_seg = aSeg; + } + + const SEG& GetSeg() const + { + return m_seg; + } + + void SetWidth( int aWidth ) + { + m_width = aWidth; + } + + int GetWidth() const + { + return m_width; + } + + bool IsSolid() const + { + return true; + } + + void Move( const VECTOR2I& aVector ) + { + m_seg.A += aVector; + m_seg.B += aVector; + } + +private: + SEG m_seg; + int m_width; +}; + +#endif |