corkum@csri.toronto.edu (Brent Thomas Corkum) (10/03/90)
In article <1990Oct3.121330.11851@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes: > >Due to popular demand I am posting my generalised point in a volume (polytope) >tester. It's written in C, and handles concave,convex polygons making >up a concave or convex volume. The polygons may have any number of >vertices. I don't really like posting it but I don't have, and don't care >to have, anonymous ftp capability, so if anyone wants to donate some space >to make this available, mail me. > > >The following two postings contain information and source code for my >point inside a volume tester. The first file contains the readme file >that explains how to compile and run the test program. The test program >illustrates the use of the point inside a volume tester, and gives an example. > >Feel free to distribute this code, I place it in the public domain with >the only criteria for using it being proper acknowledgement. You may >use it in commercial software free of charge with only the above >restriction. So have fun. > >Brent Corkum >corkum@boulder.civ.toronto.edu (128.100.14.11) or >corkum@csri.toronto.edu This program will determine if point (x,y,z) is inside a closed polytope defined by the list "polygons" which contains "numpolys" concave or convex polygons. The main subroutine of the program reads in a closed polytope from a .geo file and then prompts the user for a point to check. The Insidepolytope subroutine is then called which will return TRUE if the point is inside the polytope. J. Andrew Wyllie and Brent Corkum Data Visualization Laboratory Dept Of Civil Engineering University of Toronto Canada September 1990 Any questions or comments can be sent to : corkum@boulder.civ.toronto.edu (128.100.14.11) or corkum@csri.toronto.edu This code may be distributed free of charge and is public domain. We disclaim any responsibility for the use or misuse of this code. The file inside.c contains a program that calculates whether a point is within a closed volume. The volume is defined by convex or concave polygons with any number of vertices. The main function which does this calculation is Insidepolytope which takes as arguments the floating point coordinate of the point you wish to check. There is also a point in a polygon tester called Inside_2D_Polygon that takes as arguments a 2d point (x,y) and a array containing the polygons vertices and figures out whether the point is inside or not. THe file also contains a couple other goodies , one especially that I like that calculates the 4X4 transformation matrix from one arbitrary 3d vector to another. Feel free to edit the source, change the data structures etc. etc. The file will compile to an executable that reads a data file containing polygons representing the closed volume. To compile type: cc inside.c -lm -o inside I use a SGI 4D/25 and I know it'll compile on a PC using Turbo C++. Anything else is not my headache. To run the program type inside it will ask for the name of the data file, enter the name, it will then prompt you to enter the x,y,and z coordinate of the point you wish to test. This is only a test program so don't expect any bells and whistles. Expect functionality! The format of the data file is simple, this is an example of a cube: 8 6 0 -> 8=#points;6=#polygons;0=dummy arg! -1.0 -1.0 1.0 -> list of 3d points (8 of them) -1.0 1.0 1.0 1.0 1.0 1.0 1.0 -1.0 1.0 -1.0 -1.0 -1.0 -1.0 1.0 -1.0 1.0 1.0 -1.0 1.0 -1.0 -1.0 4 1 2 3 4 -> list of polygons, ids to points 4 5 6 2 1 4 3 2 6 7 4 3 7 8 4 4 1 4 8 5 4 8 7 6 5 this is an actual example file of a soccer ball centered at the origin and of radius ~= 1.0: /************************** cut here **********************************/ 60 32 400 0.348012 0 0.93749 0.107542 0.330979 0.93749 -0.281548 0.204556 0.93749 -0.281548 -0.204556 0.93749 0.107542 -0.330979 0.93749 0.694318 0 0.719669 0.799191 -0.327801 0.502204 0.965027 -0.20654 0.154057 0.965027 0.20654 0.154057 0.799191 0.327801 0.502204 0.214556 0.660335 0.719669 0.558721 0.65878 0.502204 0.494641 0.853971 0.154057 0.101778 0.981619 0.154057 -0.0647933 0.861372 0.502204 -0.561715 0.40811 0.719669 -0.453883 0.734949 0.502204 -0.659322 0.734323 0.154057 -0.902124 0.400134 0.154057 -0.839236 0.204556 0.502204 -0.561715 -0.40811 0.719669 -0.839236 -0.204556 0.502204 -0.902124 -0.400134 0.154057 -0.659322 -0.734323 0.154057 -0.453883 -0.734949 0.502204 0.214556 -0.660335 0.719669 -0.0647933 -0.861372 0.502204 0.101778 -0.981619 0.154057 0.494641 -0.853971 0.154057 0.558721 -0.65878 0.502204 0.902124 0.400134 -0.154057 0.839236 0.204556 -0.502204 0.561715 0.40811 -0.719669 0.453883 0.734949 -0.502204 0.659322 0.734323 -0.154057 -0.101778 0.981619 -0.154057 0.0647933 0.861372 -0.502204 -0.214556 0.660335 -0.719669 -0.558721 0.65878 -0.502204 -0.494641 0.853971 -0.154057 -0.965027 0.20654 -0.154057 -0.799191 0.327801 -0.502204 -0.694318 0 -0.719669 -0.799191 -0.327801 -0.502204 -0.965027 -0.20654 -0.154057 -0.494641 -0.853971 -0.154057 -0.558721 -0.65878 -0.502204 -0.214556 -0.660335 -0.719669 0.0647933 -0.861372 -0.502204 -0.101778 -0.981619 -0.154057 0.659322 -0.734323 -0.154057 0.453883 -0.734949 -0.502204 0.561715 -0.40811 -0.719669 0.839236 -0.204556 -0.502204 0.902124 -0.400134 -0.154057 0.281548 -0.204556 -0.93749 -0.107542 -0.330979 -0.93749 -0.348012 0 -0.93749 -0.107542 0.330979 -0.93749 0.281548 0.204556 -0.93749 5 5 4 3 2 1 5 10 9 8 7 6 5 15 14 13 12 11 5 20 19 18 17 16 5 25 24 23 22 21 5 30 29 28 27 26 5 35 34 33 32 31 5 40 39 38 37 36 5 45 44 43 42 41 5 50 49 48 47 46 5 55 54 53 52 51 5 60 59 58 57 56 6 2 11 12 10 6 1 6 3 16 17 15 11 2 6 4 21 22 20 16 3 6 5 26 27 25 21 4 6 1 6 7 30 26 5 6 12 13 35 31 9 10 6 17 18 40 36 14 15 6 22 23 45 41 19 20 6 27 28 50 46 24 25 6 7 8 55 51 29 30 6 9 31 32 54 55 8 6 14 36 37 34 35 13 6 19 41 42 39 40 18 6 24 46 47 44 45 23 6 29 51 52 49 50 28 6 32 33 60 56 53 54 6 37 38 59 60 33 34 6 42 43 58 59 38 39 6 47 48 57 58 43 44 6 52 53 56 57 48 49 /************************** end cut here **********************************/