Chris Pollett>Old Classes>PIC 20, Winter 2000>Hw3
For this assignment you will submit four files: Convex.java, Convex.php, CreatePolygon.java, and HullPoints.java. The purpose of this assignment is to learn about the Jarvis' Gift-wrapping algorithm for finding the convex hull of a set of points in the plane. You will also get some experience with object oriented programming. Namely, how to use classes you create within other classes, how to extend classes, as well as, how to use interfaces, inner classes, and anonymous inner classes. You will also learn a little about handling mouse events and get experience at working with other people's code. Let's have a look at what the finished program should look like:
The idea of the above applet is that when you click inside the applet it draws a point at where the arrow position was. If you click the Clear button it clears the screen. If you click the Hullify button, it draws the smallest convex polygon that contains all the points you have drawn. A polygon is convex if whenever two points are inside the polygon so is the line between them. The smallest convex polygon is called the convex hull. Convex hulls are useful in computational geometry, linear optimization, and computer graphics.
Now let's describe what you need to do for this assignment. The file Convex.java contains the public class Convex which extends JApplet. This class will be responsible for doing all the drawing. The class HullPoints.java implements the interface CreatePolygon.This class will be used to store the mouse click positions and also to compute the convex hull. Finally, the interface CreatePolygon has only one public abstract method makePolygon(). This method returns an object of type Polygon (Polygon is in java.awt.*) So any class that implements CreatePolygon must have a makePolygon() method. In the HullPoints class case this method will be used to return the polygon for the convex hull. The file CreatePolygon.java should be at most 5-6 lines. Below is a partially completed version of Convex.java. You will have to add to areas marked: //fill in here.
// Program Name: Convex.java
//
// Purpose: This is code for an applet with two buttons and a drawing area
// used to demonstrate convex hulls.
//
// The user can click in the drawing area to draw a point to the
// screen.
//
// The Hullify button causes the polygon which is the convex hull
// of the currently displayed points to be drawn.
//
// The ClearScreen button clears the screen.
//
// Known Bugs: To be added.... NOT.
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
public class Convex extends JApplet
{
JButton hullify;
JButton clearScreen;
// Our applet is always in one of three drawing states
// we are either about to draw a point, about to draw a polygon,
// or about to clear the screen. We give these states the following
// names:
final int DRWPOINT = 0, DRWPOLY=1, CLEAR = 2;
int drawState = CLEAR; //start in clear screen state
int xLoc =-10, yLoc = -10; // xLoc and yLoc should contain
// the location of when the last mouse press
// was.
boolean inApplet = false; //this flag is used to determine
//if mouse is in applet or not. If not
//we won't try to draw the point
//and we won't try to add it to our current
//Vector of points.
HullPoints hull; //hull used to store locations of points that have
//been drawn. Its makePolygon() method will give us
//the convex hull.
//Name: init()
//
//Purpose: set up the applets JButtons and their
// ActionListeners. Also sets up the MouseEvent handler
// for the applet and initializes the HullPoints object
// used to keep of what points have been drawn and used
// used to compute the convex hull.
public void init() {
Container c=getContentPane();
MouseHandler mHandler = new MouseHandler(this);
//MouseHandler is our inner class defined
// below to handle MouseEvents
c.setLayout(new FlowLayout());
c.setBackground(Color.white);
hullify = new JButton("Hullify");
hullify.addActionListener( new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
//fill in here with what
// to do when Hullify button pressed
}
}
); // this ActionListener without a name is an example
// of an anonymous inner class.
c.add(hullify);
clearScreen = new JButton("ClearScreen");
clearScreen.addActionListener(
//fill in here with another anonymous inner class
//definition. This time with what to do
// When the ClearScreen button pressed
);
c.add(clearScreen);
c.addMouseListener(mHandler);
hull =new HullPoints();
}
//Name: update
//
//Purpose: This is a method built-in to class JApplet that we have
// overridden. It is normally called by repaint() after
// repaint() gets the applet's Graphics object g. It normally
// clears the screen and then calls paint(g). This would
// erase the points we've drawn so we've overriden it so that
// it only clears the screen if we're in the CLEAR state.
public void update( Graphics g)
{
if(drawState==CLEAR)
{super.update(g);
}
else{ paint (g );}
}
//Name: paint
//Purpose: Depending on the value of drawState either draws
// a point, a polygon, or redraw the buttons.
// (can be done using super.paint(g);)
// If drawState is not DRWPOINT then it is
// set to be DRWPOINT
public void paint( Graphics g)
{
switch(drawState)
{
case DRWPOINT:
if (inApplet)
{ //fill in here
//should draw a point at current
//xLoc,yLoc and call addPoint method
//of hull
}
break;
case DRWPOLY:
//fill in here
//should draw Polygon returned by
// by hull.makePolygon() and return
// drawState to DRWPOINT value
break;
case CLEAR:
//fill in here
// should redraw buttons
// then clear all the points stored in hull
// then set the drawState back to DRWPOINT
break;
default:
}
}
// Name: MouseHandler
//
// Purpose: Inner class used to handle events for Convex applets
//
class MouseHandler extends MouseAdapter
{
Convex c; //will contain the instance of class Convex
//for which mouse events are going to be handled
//constructor sets up which instance
public MouseHandler(Convex convex){ c= convex;}
//Name:mouseEntered
//
//Purpose: signal to our instance of Convex
// that the mouse is now pointing in the applet
// area.
public void mouseEntered( MouseEvent e)
{
c.inApplet = true;
}
//Name:mouseExited
//
//Purpose: signal to our instance of Convex
// that the mouse has now left the applet
// area.
public void mouseExited( MouseEvent e)
{
c.inApplet = false;
}
//Name:mousePressed
//
//Purpose:
// (1) set current Convex instances values of
// xLoc and yLoc to current location
// (2) call repaint()
public void mousePressed( MouseEvent e)
{
//fill in here.
// e.getX() and e.getY()
// get current mouse position
}
}
}
The class HullPoints should contain a private Vector variable and at least have the public methods:
HullPoints() -- the constructor just initializes the Vector variable. void addPoint(int x, int y) -- first stores the x and y into a Point object then stores Point object into the private Vector variable. The Point class is in java.awt.* To create a Point can do: Point a; a=new Point(x,y); To get the x and y coordinates of a Point can then do a.x and a.y . Polygon makePolygon() -- returns the Polygon given by gift wrapping algorithm. The Polygon class in java.awt.* has the constructor Polygon(). It has an addPoint(int x, int y) method to add points to it. To cause a Polygon p to be drawn on Graphics object g you can use g.drawPolygon(p); void clear() -- gets rid of points in the private Vector variable.
The gift-wrapping algorithm works as follows: If we have three or fewer points they will all be in the convex hull so we just return all of them. Otherwise, we do the following:
(1) search through our Vector of Points for the Point of least horizontal value (in case of a tie pick Point with least y value) (2) search through our Vector of Points for the Point of greatest horizontal value (in case of a tie pick Point with greastest y value) These two points will be in the convex hull. We now just need to find the remaining points. (3) Starting with our Point from (1) being our current point we do the following until we reach the Point we got from (2). (i) Add the current point to the Polygon. (ii) Search through the Vector of points for the point different from the current point which requires the least counterclockwise rotation of a vertical line through the current point to strike it. Set this new point to be the current point under consideration and goto (i). (4) Starting with our Point from (2) being our current point we do the following until we reach the Point we got from (1). (i) Add the current point to the Polygon. (ii) Search through the Vector of points for the point different from the current point which requires the least counterclockwise rotation of a vertical line through the current point to strike it. Set this new point to be the current point under consideration and goto (i).
Given a current point cur, and two points p1 and p2, the cross product (p1-cur) X (p2-cur) = (p1.x-cur.x)(p2.y-cur.y)-(p1.y-cur.y)(p2.x-cur.x) will be positive if p2 requires less of counterclockwise rotation than p1. (Before we get to the maximum point) and will be negative if p2 requires less of a counterclockwise rotations than p1.(For points after the maximum point).