00001 /* main.c 00002 COPYRIGHT 00003 Both this software and its documentation are 00004 00005 Copyright 1993 by IRISA /Universite de Rennes I - France, 00006 Copyright 1995,1996 by BYU 00007 all rights reserved. 00008 00009 Permission is granted to copy, use, and distribute 00010 for any commercial or noncommercial purpose under the terms 00011 of the GNU General Public license, version 2, June 1991 00012 (see file : LICENSING). 00013 00014 This file along with polyhedron.c and vector.c do the following functions: 00015 - Extraction of a minimal set of constraints from some set of constraints 00016 - Intersection of two convexes 00017 - Application of a linear function to some convex 00018 - Verification that a convex is included in some other convex 00019 00020 They are compiled together into an executable file called "test". 00021 The file test.in contains sample input data for the program. 00022 The file test.out contains the output produced by the program. 00023 00024 This directory also contains a makefile to build and run the test. 00025 00026 This file is a tutorial on how to use the library. The comments 00027 explain whats going on. You can use this file as a pattern for your 00028 own program. Good Luck ! 00029 00030 --Doran 00031 */ 00032 00033 #include <stdio.h> 00034 00035 #include <polylib/polylib.h> 00036 00037 00038 int main() { 00039 00040 Matrix *a, *b, *t; 00041 Polyhedron *A, *B, *C, *D; 00042 00043 printf("Polyhedral Library Test\n\n"); 00044 00045 /* read in a matrix containing your equations */ 00046 /* for example, run this program and type in these five lines: 00047 4 4 00048 1 0 1 -1 00049 1 -1 0 6 00050 1 0 -1 7 00051 1 1 0 -2 00052 This is a matrix for the following inequalities 00053 1 = inequality, 0x + 1y -1 >=0 --> y >= 1 00054 1 = inequality, -1x + 0y +6 >=0 --> x <= 6 00055 1 = inequality, 0x + -1y +7 >=0 --> y <= 7 00056 1 = inequality, 1x + 0y -2 >=0 --> x >= 2 00057 If the first number is a 0 instead of a 1, then that constraint 00058 is an 'equality' instead of an 'inequality'. 00059 */ 00060 a = Matrix_Read(); 00061 00062 /* read in a second matrix containing a second set of constraints: 00063 for example : 00064 4 4 00065 1 1 0 -1 00066 1 -1 0 3 00067 1 0 -1 5 00068 1 0 1 -2 00069 */ 00070 b = Matrix_Read(); 00071 00072 /* Convert the constraints to a Polyhedron. 00073 This operation 1. Computes the dual ray/vertice form of the 00074 system, and 2. Eliminates redundant constraints and reduces 00075 them to a minimal form. 00076 */ 00077 A = Constraints2Polyhedron(a, 200); 00078 B = Constraints2Polyhedron(b, 200); 00079 00080 /* the 200 is the size of the working space (in terms of number 00081 of rays) that is allocated temporarily 00082 -- you can enlarge or reduce it as needed */ 00083 00084 /* There is likewise a rays to polyhedron procedure */ 00085 00086 /* Since you are done with the matrices a and b, be a good citizen 00087 and clean up your garbage */ 00088 Matrix_Free(a); 00089 Matrix_Free(b); 00090 00091 /* If you want the the reduced set of equations back, you can 00092 either learn to read the polyhedron structure (not hard, 00093 look in "types.h"... 00094 or you can get the matrix back in the same format it started 00095 in... */ 00096 a = Polyhedron2Constraints(A); 00097 b = Polyhedron2Constraints(B); 00098 00099 /* Take a look at them if you want */ 00100 printf("\na ="); 00101 Matrix_Print(stdout,P_VALUE_FMT,a); 00102 printf("\nb ="); 00103 Matrix_Print(stdout,P_VALUE_FMT,b); 00104 00105 Matrix_Free(a); 00106 Matrix_Free(b); 00107 00108 /* To intersect the two systems, use the polyhedron formats... */ 00109 C = DomainIntersection(A, B, 200); 00110 00111 /* Again, the 200 is the size of the working space */ 00112 00113 /* This time, lets look a the polyhedron itself... */ 00114 printf("\nC = A and B ="); 00115 Polyhedron_Print(stdout,P_VALUE_FMT,C); 00116 00117 /* 00118 * The operations DomainUnion, DomainDifference, and DomainConvex 00119 * are also available 00120 */ 00121 00122 /* 00123 * Read in a third matrix containing a transformation matrix, 00124 * this one swaps the indices (x,y --> y,x): 00125 * 3 3 00126 * 0 1 0 00127 * 1 0 0 00128 * 0 0 1 00129 */ 00130 00131 00132 t = Matrix_Read(); 00133 00134 /* Take the preimage (transform the equations) of the domain C to 00135 get D. Are you catching on to this 200 thing yet ??? */ 00136 00137 D = Polyhedron_Preimage(C, t, 200); 00138 00139 /* cleanup please */ 00140 Matrix_Free(t); 00141 00142 printf("\nD = transformed C ="); 00143 Polyhedron_Print(stdout,P_VALUE_FMT,D); 00144 Domain_Free(D); 00145 00146 /* in a similar way, Polyhedron_Image(dom, mat, 200), takes the image 00147 of dom under matrix mat (transforms the vertices/rays) */ 00148 00149 /* The function PolyhedronIncludes(Pol1, Pol2) returns 1 if Pol1 00150 includes (covers) Pol2, and a 0 otherwise */ 00151 00152 if (PolyhedronIncludes(A,C)) 00153 printf("\nWe expected A to cover C since C = A intersect B\n"); 00154 if (!PolyhedronIncludes(C,B)) 00155 printf("and C does not cover B...\n"); 00156 00157 /* Final note: some functions are defined for Domains, others 00158 * for Polyhedrons. A domain is simply a list of polyhedrons. 00159 * Every polyhedron structure has a "next" pointer used to 00160 * make a list of polyhedrons... For instance, the union of 00161 * two disjoint polyhedra is a domain consisting of two polyhedra. 00162 * If you want the convex domain... you have to call 00163 * DomainConvex(Pol1, 200) explicity. 00164 * Note that includes does not work on domains, only on simple 00165 * polyhedrons... 00166 * Thats the end of the demo... write me if you have questions. 00167 * And remember to clean up... 00168 */ 00169 00170 Domain_Free(A); 00171 Domain_Free(B); 00172 Domain_Free(C); 00173 00174 return 0; 00175 } 00176 00177
1.5.6