Data Structures Assignment 6 - IITD Computer Sc. & Engg.

COL 106 Assignment 6

Clarifications

Merger of all faces, polygon or triangle, is to be supported, but no test case will include two adjacent facets with multiple shared edges.
Remove any duplicate polygons after mergers.
Two triangle share and edge if two of their vertices are co-located. If all three vertices are co-located, the triangles are duplicate, and one may be removed.
You may simplify the computation of dihedral angles between polygons by simply taking the smallest angle between their planes. (Absolute value of the dot product of their normals will do.)
Please implement your own Hash table. Do not use any other implementation (like JAVA's).
You should count all consituent triangles of polygons, i.e., the number of triangles before the merger.

Assignment

In this assignment, you will deal with 3D geometric models. The first step is to read and store in a data structure one model at a time. A model is listed triangle by triangle, one triangle per line in the following format:

X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3

The given values are strings representing decimal values of the X, Y, and Z coordinates of each vertex of the triangle.

The internal data structure will store the model as a graph. In fact, you will read all the files in a given input directory. Thus there may be a number of 3D models, aka graphs.

The goal is to find, for each 3D model, other models with a similar shape. Two models have a similar shape if minor modifications to one of the models yields the other one. The modifications can be one of these:

merger of adjacent triangles lying on the same plane (Two triangles are adjacent if they share an edge.)
a rotation, translation or scale

As an approximation, after merger of planar facets, two models match if they have the same

number of triangles, edges and vertices
number of shared and open edges (a shared edge is shared by two ~~triangles~~facets, an open edge belongs to only one ~~triangle~~facet.)
set of all dihedral angles (Dihedral angle is the angle between adjacent polygon's planes)
correctness (a model is correct if no edge is shared by more than two ~~triangles~~facets)

You may use a hash function to check for matches. The output will contain one line per input model. The first word on the line is the name of the model file. It is followed by blank-separated names all its matching models' file names. The output is in the sorted order of model file names. You must implement you own sorting.

Implementation

Implement public class Assignment6, with a static main that takes on the command line, only the (path)name of a directory that contains all the input model files. It reads each file in the directory (one model per file), merging co-planar adjacent triangles and storing the details of the resulting shape for later matching. It then iterates over each model, find its matches. Speed is important.

At the end, it print the sorted model matches on standard output.

Examples

Input Directory

Output:

tri1 tri2
tri2 tri1

Input Directory

Output:

model1 model2 model3
model2 model1 model3
model3 model1 model2

Submission instructions

Submission will be at moodle.

Please ensure that you follow the following set of instructions meticulously while submitting the assignment on Moodle. Also, please note that in case of deviation from this procedure will render your submission faulty, and your assignment might not be evaluated at all by the script. Please follow these steps:

On eclipse, by default, all your source files (.java files) are saved into a directory called "src" inside your project. You have to compress this directory (to zip format) and rename the zip file in this format:
```
your-entry-number_assignment6.zip
```
Example: If your entry number is 2012CSZ8019, the zip file should be named 2012CSZ8019_assignment6.zip. It should expand to a directory called src, which contains all your .java files. Please make sure that you follow exactly this naming format.
Next, convert the zip file to base64 format. On any linux system, you can do this easily by issuing the following command on the terminal :
```
   base64 entrynumber_assignment6.zip > entrynumber_assignment6.zip.b64
```
This will create a file with the same name with a b64 extension appended at the end.
Upload this b64 file on moodle and submit it (in the "Submission" section). After Submission, there is an option of "Evaluate" in the "Edit" section. Click on "Evaluate". On the right side of the window, you will get information about the submission status. On clicking the "Evaluate" link, you should see a script running and producing an output of your codes' performance against the standard set of test cases that we supply internally for the assessment. A dialog box will show you the messages on how your codes performed against the benchmarks that we provided.

Important notes

Please note that the immediate feedback is based on simple checks and to inform you whether your java code produces some right output for a basic test case. It is not the real grading. Hence, the grade that you see at submission is only to indicate if submission succeeded. During the actual evaluation, we will run many other tests and provide the final grade based on those. That grade will be uploaded on moodle after grading.
Please do not submit any executable or class files along with the source code. The "src" directory should only contain your code (.java) files, Makefile and README file.
As you approach the deadline for assignment submission, multiple students will submit their files together. As a result, the server will be slow to respond to clicks on "Evaluate" link. In fact, we may even turn off the immediate feedback (Evaluate) option up to an hour before the submission in case of excessive load. You should submit well in advance to check for basic gradability. You may always modify and re-submit your assignment until the deadline. In any case, when the response to "Evaluate" request is slow, please be patient and re-try after 30 seconds. Incessant clicking will only make it worse. Please also note that no emails regarding slow response to "Evaluate" will be entertained on the day of submission.
Following is the full specification of the JDK that will run on the server for evaluation purpose. So please make sure that your own system also satisfies these requirements and that your java codes run in this setup. It will be extremely difficult for us to entertain requests that say the code ran on some other version of JDK, but does not comply with the server's version of JDK:
```
java version "1.7.0_79"
OpenJDK Runtime Environment (IcedTea 2.5.5) (7u79-2.5.5-0ubuntu0.12.04.1)
OpenJDK 64-Bit Server VM (build 24.79-b02, mixed mode)
```
Note that you must click on "Evaluate" after you submit the b64 file. Submitting the file without clicking on "Evaluate" may mean that your code does not meet the desired specifications. In that case, your submission will not be evaluated for the assignment.
The system will only be able to evaluate submissions in base64 format. Direct uploading of zip/java/txt/other formats would not let the system evaluate your submission.