Project 2

This project is individual. You may discuss general approaches with colleagues, but the implementation must be your own. Any similarity of code structure that suggests that one person copied the source code of another or that both wrote it together is not acceptable (even if disguised by changing variable names and reformatting the code). You may use other people's code for the non-essential portions of the assignment, provided that you clearly acknowledge what it is that is not yours and where you got it. The acknowledgement must be made on your web page and in the source code. For example, you may use someone else's code to let the user enter points using the mouse and to edit the polygon.

However, the essential parts (below) must be your own:
 - Subdivision
 - Min distance computation and display
 - Hausdorff distance computation and display
 - Display of both curves around the tolerance zone around one curve
 - Simplification of a polygonal curve


DEADLINE for the WHOLE PROJECT 2: Oct 26 at 11:55 pm by Email to Mel containing URL for your project page

DELIVERABLES on your project web page
Title: CS4451B Project 2: Distances and Simplification
Your name and email (preferably button or form as suggested in project 1)
A link to the source code (which should identify the author and be well commented.)

For each phase described below, please provide
- a title
- a short description of the objectives
- a description of what you have implemented and how
- a subset of your code that implements the key part (well commented)
- figures showing the results (with explanations)
- A DISCUSSION giving your perspective. What are possible applications of this? What are the limitations of this technique? (Maybe give an example of something that either does not work or produces a results that is not what we would consider correct. Of your implementation? Are there delicate issues (numeric precision, very slow for complex models).


Phase 1: Subdivision
Consider a closed-loop polygonal curve C that is free from self intersections and is represented by an array of vertices in 2D.
Implement the 3 split&Tweak subdivision schemes: Jarek's, cubic Bspline and 4-point .
Run them on several (say 3) curves with about a dozen vertices each. For each curve, show 3 images (say 300x300 pixels). Please use white background for all the images. Each image should show the original curve (Black), the result of B-spline subdivision (red), the result of jarek subdivision (dark green) and the result of 4-point subdivision (dark blue). The first image for a curve should show the result after one level of subdivision. The second image after 2 levels. THe third image after 5 levels.
Briefly comment on the advantages /drawback of each scheme, referring to the images to demonstrate your point.

Phase 2: Distances
Specify two control polygons, A (green) and B (blue), with about 12 vertices each.
Make an image (white background) with both original polygons.
Then subdivide them each a few times (maybe 5) and make another image showing both curves subdivided.

Now, let A and B represent the subdivided versions of the two curves.
Compute the minimum distance between the vertices of A and B and the two vertices where it is realized (where "she" is and where "I" am). Note that they may not be unique. That is OK, just pick a pair, one on A and one on B for which the distance is the minimum distance between A and B. Draw a Brown edge between these two points on the previous image.
Now compute the Hausdorff distance H between the two set of vertices.
Find a vertex S that is at distance H from the vertices of the other curve. Assume WLOG that S is a vertex of A. Now, draw a red line between S and each vertex I of B for which |SI|<(1+e)H, where e is something like 0.03. Adjust e so that the number of red lines is small (less than 6).

Your job is to come up with two test cases for this. One where the vertices I are contiguous along B and one where they form two separate runs along B. The latter illustrates a situation where if she moves a little in one direction on A I will take a position to be the closest to her. Then, if she moves a little bit in the other direction along A, I will have to run a long trip along B to reach the point that is closest to her. This is pure torture... if she does it a dozen times.

Phase 3: Offsetting
Suppose that she was on A and that the Hausdorff distance was H. Use the same setting and figures as in phase 2 , but before you draw anything, draw A as a fat yellow curve of thickness 2H. You can do that by painting a disk of radius H around each vertex of A. Then overlay on top of the fat curve the other two curves and the Hausdorff distance lines. Conclude on the relation between growing and Hausdorff distance (we discussed in class).

Phase 4: Simplification
Take a single curve A obtained by subdivision as before. (It can be a curve from phase 3, but you may want to make one custom designed to test simplification. You may need to use more control points here to create some zigzags.)
First draw it as a fat yellow curve with some thickness 2H. Choose H so that it will allow some interesting simplification of details but it will retain the main features of the curve.
Then paint the original curve over it say in green. It should be at the center of the yellow road.
Now simplify the curve using your favorite simplification algorithm. You must generate a new curve (call it B) that is a good simplification of A. It should have as few vertices as possible (or nearly as few). It should stay inside the yellow road. Now this is not a sufficient condition. For example, I could make B be a tiny loop somewhere inside the yellow road. Such a B would not be a good approximation to A. Discuss the proper way of stating the condition we want to impose on B and produce a curve that satisfies it.