1 /*! \file kbool/include/kbool/graph.h 2 \author Klaas Holwerda 3 4 Copyright: 2001-2004 (C) Klaas Holwerda 5 6 Licence: see kboollicense.txt 7 8 RCS-ID: $Id: graph.h,v 1.1 2005/05/24 19:13:37 titato Exp $ 9 */ 10 11 /* @@(#) $Source: /cvsroot/wxart2d/wxArt2D/modules/kbool/include/graph.h,v $ $Revision: 1.1 $ $Date: 2005/05/24 19:13:37 $ */ 12 13 /* 14 Program GRAPH.H 15 Purpose Used to Intercect and other process functions 16 Last Update 03-04-1996 17 */ 18 19 #ifndef GRAPH_H 20 #define GRAPH_H 21 22 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) 23 #pragma interface 24 #endif 25 26 #include "kbool/include/booleng.h" 27 #include "kbool/include/_lnk_itr.h" 28 #include "kbool/include/link.h" 29 #include "kbool/include/line.h" 30 #include "kbool/include/scanbeam.h" 31 32 class Node; 33 34 class GraphList; 35 36 //! one graph containing links that cab be connected. 37 class A2DKBOOLDLLEXP Graph 38 { 39 protected: 40 Bool_Engine* _GC; 41 public: 42 43 Graph(Bool_Engine* GC); 44 Graph(KBoolLink*,Bool_Engine* GC); 45 46 Graph( Graph* other ); 47 48 ~Graph(); 49 GetBin()50 bool GetBin() { return _bin; }; SetBin(bool b)51 void SetBin(bool b) { _bin = b; }; 52 53 void Prepare( int intersectionruns ); 54 void RoundInt(B_INT grid); 55 void Rotate(bool plus90); 56 57 //! adds a link to the linklist 58 void AddLink(Node *begin,Node *end, int user_data); 59 60 //! adds a link to the linklist 61 void AddLink(KBoolLink *a_link); 62 63 bool AreZeroLines(B_INT Marge); 64 65 //! Delete parallel lines 66 void DeleteDoubles(); 67 68 //! delete zerolines 69 bool DeleteZeroLines(B_INT Marge); 70 bool RemoveNullLinks(); 71 72 //! Process found intersections 73 void ProcessCrossings(); 74 //! set flags for operations based on group 75 void Set_Operation_Flags(); 76 77 //! Left Right values 78 void Remove_IN_Links(); 79 80 //! reset bin and mark flags in links. 81 void ResetBinMark(); 82 83 // Remove unused links 84 void ReverseAllLinks(); 85 86 //! Simplify the graph 87 bool Simplify( B_INT Marge ); 88 89 90 //! Takes over all links of the argument 91 bool Smoothen( B_INT Marge); 92 93 void TakeOver(Graph*); 94 95 //! function for maximum performance 96 97 //! Get the First link from the graph 98 KBoolLink* GetFirstLink(); 99 Node* GetTopNode(); 100 void SetBeenHere(bool); 101 void Reset_flags(); 102 103 //! Set the group of a graph 104 void SetGroup(GroupType); 105 106 //! Set the number of the graph 107 void SetNumber(int); 108 void Reset_Mark_and_Bin(); 109 bool GetBeenHere(); 110 int GetGraphNum(); 111 int GetNumberOfLinks(); 112 113 void Boolean(BOOL_OP operation,GraphList* Result); 114 void Correction(GraphList* Result,double factor); 115 void MakeRing(GraphList* Result,double factor); 116 void CreateRing(GraphList *ring,double factor); 117 void CreateRing_fast(GraphList *ring,double factor); 118 void CreateArc(Node* center, KBoolLine* incoming, Node* end,double radius,double aber, int user_data); 119 void CreateArc(Node* center, Node* begin, Node* end,double radius,bool clock,double aber, int user_data); 120 void MakeOneDirection(); 121 void Make_Rounded_Shape(KBoolLink* a_link, double factor); 122 bool MakeClockWise(); 123 bool writegraph(bool linked); 124 bool writeintersections(); 125 void WriteKEY( Bool_Engine* GC, FILE* file = NULL ); 126 void WriteGraphKEY( Bool_Engine* GC ); 127 128 protected: 129 130 //! Extracts partical polygons from the graph 131 /* 132 Links are sorted in XY at beginpoint. Bin and mark flag are reset. 133 Next start to collect subparts from the graph, setting the links bin for all found parts. 134 The parts are searched starting at a topleft corner NON set bin flag link. 135 Found parts are numbered, to be easily split into to real sperate graphs by Split() 136 137 \param operation operation to collect for. 138 \param detecthole if you want holes detected, influences also way of extraction. 139 \param foundholes when holes are found this flag is set true, but only if detecthole is set true. 140 */ 141 void Extract_Simples(BOOL_OP operation, bool detecthole, bool& foundholes ); 142 143 //! split graph into small graph, using the numbers in links. 144 void Split(GraphList* partlist); 145 146 //! Collect a graph by starting at argument link 147 /* 148 Called from Extract_Simples, and assumes sorted links with bin flag unset for non extarted piece 149 150 Collect graphs pieces from a total graph, by following links set to a given boolean operation. 151 \param current_node start node to collect 152 \param operation operation to collect for. 153 \param detecthole if you want holes detected, influences also way of extraction. 154 \param graphnumber number to be given to links in the extracted graph piece 155 \param foundholes when holes are found this flag is set true. 156 */ 157 void CollectGraph(Node *current_node, BOOL_OP operation, bool detecthole,int graphnumber, bool& foundholes ); 158 159 void CollectGraphLast(Node *current_node, BOOL_OP operation, bool detecthole,int graphnumber, bool& foundholes ); 160 161 //! find a link not bin in the top left corner ( links should be sorted already ) 162 /*! 163 Last found position is used to find it quickly. 164 Used in ExtractSimples() 165 */ 166 Node* GetMostTopLeft(TDLI<KBoolLink>* _LI); 167 168 //! calculates crossing for all links in a graph, and add those as part of the graph. 169 /* 170 It is not just crossings calculation, snapping close nodes is part of it. 171 This is not done at maximum stability in economic time. 172 There are faster ways, but hardly ever they solve the problems, and they do not snap. 173 Here it is on purpose split into separate steps, to get a better result in snapping, and 174 to reach a better stability. 175 176 \param Marge nodes and lines closer to eachother then this, are merged. 177 */ 178 bool CalculateCrossings(B_INT Marge); 179 180 //! equal nodes in position are merged into one. 181 int Merge_NodeToNode(B_INT Marge); 182 183 //! basic scan algorithm with a sweeping beam are line. 184 /*! 185 \param scantype a different face in the algorithm. 186 \param holes to detect hole when needed. 187 */ 188 int ScanGraph2( SCANTYPE scantype, bool& holes ); 189 190 //! links not used for a certain operation can be deleted, simplifying extraction 191 void DeleteNonCond(BOOL_OP operation); 192 193 //! links not used for a certain operation can be set bin, simplifying extraction 194 void HandleNonCond(BOOL_OP operation); 195 196 //! debug 197 bool checksort(); 198 199 //! used in correction/offset algorithm 200 bool Small(B_INT howsmall); 201 202 203 bool _bin; 204 205 DL_List<void*>* _linklist; 206 207 }; 208 209 #endif 210 211 212