Chris Pollett>Old Classes>PIC 20, Winter 2000>Hw3>Hw3 Solutions
// 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: Draws convex polygon through top coordinate.
// of point which doesn't look as nice as say drawing it
// through the center.
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)
{
drawState=DRWPOLY;
repaint();
}
}
); // this ActionListener without a name is an example
// of an anonymous inner class.
c.add(hullify);
clearScreen = new JButton("ClearScreen");
clearScreen.addActionListener( new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
drawState=CLEAR;
repaint();
}
}
);
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)
{ g.setColor(Color.black);
g.fillOval(xLoc,yLoc, 5,5);
hull.addPoint(xLoc, yLoc);
}
break;
case DRWPOLY:
g.setColor(Color.black);
g.drawPolygon(hull.makePolygon());
drawState = DRWPOINT;
break;
case CLEAR:
super.paint(g);
drawState =DRWPOINT;
hull.clear();
break;
default:
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)
{
c.xLoc = e.getX();
c.yLoc = e.getY();
repaint();
}
}
}
// Program Name: HullPoints.java
//
// Purpose: This class is used to store points in a Vector
// using its public method addPoint(Point p).
// The method makePolygon() is able to return the
// convex hull of these points using Jarvis'
// Gift Wrapping Algorithm. The public method
// clear() can be used to delete the Points
// stored in the Vector.
//
//
// Known Bugs: none
import java.util.*;
import java.awt.*;
public class HullPoints implements CreatePolygon
{
Vector MyPoints; // this is where we will store our
// Points.
//Name: HullPoints()
//Purpose: Constructor initializes vectore of Points MyPoint
// to be empty.
//
public HullPoints()
{
MyPoints = new Vector();
}
//Name: makePolygon()
//Purpose: Computes the polygon that is convex hull of the Points stored
// in MyVector. If fewer than 3 points it just
// returns those points in a Polygon
// Otherwise, computes the point, min, of minimal
// horizontal value. Then the point, max, of maximal
// horizontal value. Then using a vertical line and
// starting at min until one gets to max calculate
// the next point of minimal clockwise angle. Add these
// points in turn to the polygon.
// Then using a vertical line and starting at max
// until one gets to min calculate
// the next point of minimal clockwise angle greater than 180.
// Add these points in turn to the polygon.
// The Polygon obtained from the above procedure is then
// returned.
public Polygon makePolygon()
{
Point min, max, minTheta, maxTheta;
Polygon hull;
hull = new Polygon();
//less than 3 points case
if(MyPoints.size() < 3)
{
for(int i=0; i< MyPoints.size(); i++)
{
min = (Point) MyPoints.elementAt(i);
hull.addPoint(min.x,min.y);
}
return hull;
}
//find the point with minimal horizontal value
min = minHor();
// find the point with maximal horizontal value
max = maxHor();
minTheta =min;
// starting with min successively find points of
// of minimal angle from current point till get to max
do
{
hull.addPoint(minTheta.x, minTheta.y);
minTheta = minAng(minTheta);
} while( minTheta != max);
maxTheta =max;
// starting with max successively find points of
// of minimal angle >180 from current point till get to min
do
{
hull.addPoint(maxTheta.x, maxTheta.y);
maxTheta = minAng(maxTheta);
} while( maxTheta != min);
return hull;
}
//Name: addPoint
//Purpose: This method creates a Point out of its two
// input parameters x and y
// then add this Point to the Vector
// of Points MyPoint.
//
public void addPoint(int x, int y)
{
MyPoints.addElement(new Point(x,y));
}
//Name: clear
//Purpose: deletes all the points from internally
// stored Vector of points MyPoints
//
public void clear()
{
MyPoints =new Vector();
}
//Name: minHor
//Purpose: calculates the point in MyVector
// of minimal horizontal value
private Point minHor()
{
Point curMin = (Point) MyPoints.elementAt(0);
Point tmp;
for(int i=1; i < MyPoints.size(); i++)
{
tmp = (Point) MyPoints.elementAt(i);
if(curMin.x > tmp.x ||
(curMin.x == tmp.x && curMin.y > tmp.y))
{curMin =tmp;}
// in case of ties look at min y value
}
return curMin;
}
//Name: maxHor
//Purpose: calculates the point in MyVector
// of maximal horizontal value
private Point maxHor()
{
Point curMax = (Point) MyPoints.elementAt(0);
Point tmp;
for(int i=1; i < MyPoints.size(); i++)
{
tmp = (Point)MyPoints.elementAt(i);
if(curMax.x < tmp.x ||
(curMax.x == tmp.x && curMax.y < tmp.y))
{curMax =tmp;}
// in case of ties look at max y value
}
return curMax;
}
//Name: minAng
//Purpose: returns Point p in MyVector of point of minimal clockwise
// angle from the vertical line through p
private Point minAng(Point p)
{
Point curMin = (Point) MyPoints.elementAt(0);
Point tmp;
int cross;
if( p == curMin) curMin = (Point) MyPoints.elementAt(1);
for(int i=0; i < MyPoints.size(); i++)
{
tmp = (Point) MyPoints.elementAt(i);
if(tmp == p) continue;
cross = crossProd(p, curMin, tmp);
if(cross > 0 ) {curMin =tmp;}
}
return curMin;
}
//Name: maxAng
//Purpose: returns Point p in MyVector of point of minimal
// clockwise angle greater than 180 from the vertical
// through p
//
private Point maxAng(Point p)
{
Point curMax = (Point) MyPoints.elementAt(0);
Point tmp;
int cross;
if( p == curMax) curMax = (Point) MyPoints.elementAt(1);
for(int i=0; i < MyPoints.size(); i++)
{
tmp = (Point) MyPoints.elementAt(i);
if(tmp == p) continue;
cross = crossProd(p, curMax, tmp);
if(cross < 0 ) {curMax =tmp;}
}
return curMax;
}
//Name: crossProd
//Purpose: Used by minAng and maxAng to compute
// the cross product (b-a)X(c-a) in R^2 of
// the points a, b,c.
private int crossProd(Point a, Point b, Point c)
{
return (b.x - a.x)*(c.y - a.y) - (c.x -a.x)*(b.y - a.y);
}
}
// Program Name: CreatePolygon.java
//
// Purpose: An interface that requires classes that implement it
// to be able to return a polygon for drawing
//
// Known Bugs: none.
import java.awt.*; //imported to get class Polygon
public interface CreatePolygon
{
public abstract Polygon makePolygon();
}