Lab 2: Dot to Dot Generator

Learning Outcomes


This week you will implement an algorithm to reduce the number of dots in the picture so that more reasonable dot to dot challenges can be created.


Your program must:

Note: If the user loads a picture with 2,000 dots, and enters 100 for the desired number of dots, and subsequently enters 1,000 for the desired number of dots, your program must show a picture with 1,000 dots, not 100.


Changes to Dot Class

You must add the following two methods to the Dot class:

Changes to Picture Class

You must remove all constructors from the Picture class and implement the following constructors:

These constructors provide flexibility in our Picture class because we can now specify the specific implementation of the List used (e.g., ArrayList, LinkedList, or even our own List implementation) by passing the appropriate list to the constructor. In fact, the Picture class is no longer dependent on any concrete list implementation.

You must also implement the following methods in the Picture class:

Your implementation of the removeDots() method must be consistent with this flowchart:

graph LR A((Begin)) --> B{Picture has more than numberDesired dots?}; B -->|Yes| C[Calc critical value of all dots in picture]; C --> D[Remove dot with lowest critical value]; D --> A; B -->|No| E[End];
Figure 2: Dot Removal Algorithm Flowchart

Calculating the Critical Value of a Dot

The critical value of a dot depends on the relative proximity of it and its immediate neighbors. Consider three dots, labeled 1, 2, and 3, on a straight line. If dot 2 is removed, the connect the dots version of the line from 1 to 3 will look exactly the same. Therefore, we can conclude that the dot is not critical. If dot 2 is significantly far from the line connecting dot 1 and 3, then error would be introduced if dot 2 is eliminated, as shown in Figure 3.

Critical Value Illustration
Figure 3: Critical Value Illustration

The critical value of dot 2 is calculated as the sum of the distances from dot 2 to dot 1 and from dot 2 to dot 3 minus the distance from dot 1 to dot 3, i.e., \( cv_2 = d_{12} + d_{23} - d_{13} \)

where \( cv_y \) is the critical value for dot \( y \) and \( d_{xz} \) are the distances illustrated below.

Critical Value Calculation
Figure 4: Critical Value Calculation

Note that in the case of a straight line between dots 1 and 3, \( cv_2 = 0 \)

Your program should assume that the first and the last dots are connected so they should be treated as neighbors when calculating their critical values.

Exception Handling

There are a number of situations that could cause your program to throw an exception. For example, if the file is not found, cannot be opened, or contains incorrectly formatted data, it is likely that an exception will be thrown. In these cases, the program should display an useful message in an Alert.

Just For Fun

Ambitious students may wish to:


This laboratory assignment, developed by Dr. Chris Taylor, is motivated by the eighth programming project in chapter 2 of our textbook which is based on the paper: L. J. Latecki and R. Lakamper, "Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution," Computer Vision and Image Understanding (CVIU) 73(1999), pp. 441-454.

See your professor's instructions for details on submission guidelines and due dates.