1 /* 2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice including the dates of first publication and 13 * either this permission notice or a reference to 14 * http://oss.sgi.com/projects/FreeB/ 15 * shall be included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 * SOFTWARE. 24 * 25 * Except as contained in this notice, the name of Silicon Graphics, Inc. 26 * shall not be used in advertising or otherwise to promote the sale, use or 27 * other dealings in this Software without prior written authorization from 28 * Silicon Graphics, Inc. 29 */ 30 /* 31 */ 32 33 #ifndef _DIRECTEDLINE_H 34 #define _DIRECTEDLINE_H 35 36 //#include "definitions.h" 37 #include "sampledLine.h" 38 39 enum {INCREASING, DECREASING}; 40 41 class directedLine { 42 short direction; /*INCREASING or DECREASING*/ 43 sampledLine* sline; 44 directedLine* next; /*double linked list*/ 45 directedLine* prev; /*double linked list*/ 46 47 /*in case we need a list of polygons each 48 *consisting of a double linked list 49 */ 50 directedLine* nextPolygon; 51 52 /*optimization make cutoff polygon faster*/ 53 /* directedLine* prevPolygon;*/ 54 55 Int rootBit; /*1 if this is a root of the polygon, set by setRootBit*/ 56 /*and reset by resetRootBit()*/ 57 58 directedLine* rootLink; /*fast root-finding*/ 59 60 61 62 public: 63 directedLine(short dir, sampledLine* sl); 64 directedLine(); 65 ~directedLine(); 66 67 void init(short dir, sampledLine* sl); 68 69 Real* head(); /*points[0] if INCREASING, points[n-1] otherwise*/ 70 Real* tail(); /*points[n-1] if INCREASING, points[0] otherwise*/ 71 Real* getVertex(Int i); /*points[i] if INCREASING, points[n-1-i] otherwise*/ get_npoints()72 Int get_npoints() {return sline->get_npoints();} getPrev()73 directedLine* getPrev() {return prev;} getNext()74 directedLine* getNext() {return next;} getNextPolygon()75 directedLine* getNextPolygon() {return nextPolygon;} getSampledLine()76 sampledLine* getSampledLine() {return sline;} 77 getDirection()78 short getDirection(){return direction;} putDirection(short dir)79 void putDirection(short dir) {direction = dir;} putPrev(directedLine * p)80 void putPrev(directedLine *p) {prev = p;} putNext(directedLine * p)81 void putNext(directedLine *p) {next = p;} 82 83 /*insert a new line between prev and this*/ 84 void insert(directedLine* nl); 85 86 /*delete all the polygons following the link: nextPolygon. 87 *notice that sampledLine is not deleted. The caller is 88 *responsible for that 89 */ 90 void deletePolygonList(); 91 void deleteSinglePolygon(); 92 93 void deleteSinglePolygonWithSline(); //also delete sanmpled line 94 void deletePolygonListWithSline(); //also delete sanmpled line 95 96 void deleteSingleLine(directedLine* dline); 97 directedLine* deleteDegenerateLines(); 98 directedLine* deleteDegenerateLinesAllPolygons(); 99 directedLine* cutIntersectionAllPoly(int& cutOccur); 100 101 /*check to see if the list forms a closed polygon 102 *return 1 if yes 103 */ 104 short isPolygon(); 105 106 Int compInY(directedLine* nl); 107 Int compInX(directedLine* nl); 108 109 /*return an array of pointers. 110 *the 111 */ 112 directedLine** sortAllPolygons(); 113 114 Int numEdges(); 115 Int numEdgesAllPolygons(); 116 Int numPolygons(); 117 118 /*check if the head of this edge is connected to 119 *the tail of the prev 120 */ 121 short isConnected(); 122 123 Real polyArea(); 124 125 void printSingle(); 126 void printList(); 127 void printAllPolygons(); 128 void writeAllPolygons(char* filename); 129 130 131 /*insert a polygon: using nextPolygon*/ 132 directedLine* insertPolygon(directedLine* newpolygon); 133 directedLine* cutoffPolygon(directedLine *p); 134 135 Int toArraySinglePolygon(directedLine** array, Int index); 136 directedLine** toArrayAllPolygons(Int& total_num_edges); 137 138 void connectDiagonal(directedLine* v1, directedLine* v2, 139 directedLine** ret_p1, 140 directedLine** ret_p2, 141 sampledLine** generatedLine, directedLine* list); 142 143 /*generate two slines 144 */ 145 void connectDiagonal_2slines(directedLine* v1, directedLine* v2, 146 directedLine** ret_p1, 147 directedLine** ret_p2, 148 directedLine* list); 149 150 Int samePolygon(directedLine* v1, directedLine* v2); setRootBit()151 void setRootBit() {rootBit = 1;} resetRootBit()152 void resetRootBit() {rootBit = 0;} 153 directedLine* findRoot(); 154 rootLinkSet(directedLine * r)155 void rootLinkSet(directedLine* r) {rootLink = r;} 156 directedLine* rootLinkFindRoot(); 157 158 //the chain from begin to end is deleted (the space is deallocated) 159 //and a new edge(which connectes the head of begin and the tail of end) 160 // is inserted. The new polygon is returned. 161 //notice that "this" is arbitrary 162 directedLine* deleteChain(directedLine* begin, directedLine* end); 163 }; 164 165 directedLine* readAllPolygons(char* filename); 166 167 extern Int compV2InY(Real A[2], Real B[2]); 168 extern Int compV2InX(Real A[2], Real B[2]); 169 170 #endif 171 172