XC Assignment 1 --- Due on the last day of class


XC Challenge

Try to draw a simple polygon of shorter length than I have done, through a random collection of points in the plane.

The program to the right is a modification of homework assignment 2. 

Here are some ground rules:
  • Your program must run in under 5 seconds even on 100 points, which is the maximum value of the slider
  • Add all accessory functions that you require to the "HochbergPanel," so that I can add just your panel to my code.
  • I will rename the "HochbergPanel" when you send it to me, to have your own name, and then add it as a tab to my tabbed pane.
  • You'll get 25 points if your length beats mine on a majority of the larger point sets, and partial credit for doing pretty good otherwise.
Program

The following Java program ought to compile (at least under a 4.2 compiler) without any trouble, and run:
     javac SimpleXC.java
     java SimpleXC
// Sample program
// Draws a bunch of points
// Then draws a random polygon through them.
//
// Your job is to make that polygon simple, by
// permuting the elements of the array C[],
// and to get as much XC as possible by making
// your simple polygon as short as possible.
//
// Original by:  Robert Hochberg
// April 4, 2007
//
//   
// modified by:
//

import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.awt.image.*;
import javax.swing.*;

public class SimpleXC {
    static int POINTWID = 2; // size of points

    // the x and y arrays hold the coordinates
    // the B array is the order of the points in the polygon
    // You want to fill the C array with the simple polygon
    static double x[] = new double[200];

    static double y[] = new double[200];

    static int B[] = new int[200]; // the permutation matrix

    static int C[] = new int[200]; // the one that becomes simple

    static SimpleFrame myFrame;

    static int numPoints = 3;

    public static void main(String args[]) {
    makePolygons();

    // Create the frame to draw on
    myFrame = new SimpleFrame();
    myFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    myFrame.setSize(600, 600);
    myFrame.setVisible(true);
    }

    public static void makePolygons() {
    // Build an array of random points in the unit square
    for (int i = 0; i < numPoints; i++) {
        x[i] = Math.random();
        y[i] = Math.random();// Sample program
        B[i] = i; // default permutation
    }
    }

    public static double dis(int i, int j) {
    return Math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
             * (y[i] - y[j]));
    }
   

    public static class SimpleFrame extends JFrame {
    public static JSlider numPointsSlider;

    public SimpleFrame() {
        super("Create you own Simple Polygon");
        Container content = getContentPane();
        content.setLayout(new java.awt.BorderLayout());
        JTabbedPane tabbedPane = new JTabbedPane();
        tabbedPane.setPreferredSize(new java.awt.Dimension(300, 400));
        tabbedPane.addTab("Scrambled", new ScrambledPanel());
        tabbedPane.addTab("Simple", new HochbergPanel());
        content.add(tabbedPane, java.awt.BorderLayout.CENTER);

        // Slider for the number of points
        numPointsSlider = new JSlider(
                      javax.swing.SwingConstants.HORIZONTAL, 3, 100, 11);
        numPointsSlider
        .addChangeListener(new javax.swing.event.ChangeListener() {
            public void stateChanged(
                         javax.swing.event.ChangeEvent evt) {
                numPointsSliderStateChanged(evt);
            }
            });
        content.add(numPointsSlider, java.awt.BorderLayout.SOUTH);
    }

    private void numPointsSliderStateChanged(
                         javax.swing.event.ChangeEvent evt) {
        numPoints = numPointsSlider.getValue();
        makePolygons();
        repaint();
    }
    }

    public static class ScrambledPanel extends JPanel {
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;

        // First set the scaling to fit the window
        Dimension size = getSize();
        int Xwid = (int) (0.95 * size.width);
        int Ywid = (int) (0.95 * size.height);

        // First draw the segments
        g2.setColor(Color.red);
        for (int i = 0; i < numPoints; i++)
        g2.drawLine((int) (Xwid * x[B[i]]), (int) (Ywid * y[B[i]]),
                (int) (Xwid * x[B[(i + 1) % numPoints]]),
                (int) (Ywid * y[B[(i + 1) % numPoints]]));

        // Now draw the points
        for (int i = 0; i < numPoints; i++) {
        g2.fillRect((int) (Xwid * x[i]) - POINTWID, (int) (Ywid * y[i])
                - POINTWID, 2 * POINTWID + 1, 2 * POINTWID + 1);
        }
    }
    }

    public static class HochbergPanel extends JPanel {
    float totalLength = 0;

    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;

        // First set the scaling to fit the window
        Dimension size = getSize();
        int Xwid = (int) (0.95 * size.width);
        int Ywid = (int) (0.95 * size.height);

        // Create the simple polygon
        createSimplePolygon();

        // First draw the segments
        g2.setColor(Color.red);
        for (int i = 0; i < numPoints; i++) {
        g2.drawLine((int) (Xwid * x[C[i]]), (int) (Ywid * y[C[i]]),
                (int) (Xwid * x[C[(i + 1) % numPoints]]),
                (int) (Ywid * y[C[(i + 1) % numPoints]]));
        totalLength += dis(C[i], C[(i + 1) % numPoints]);
        }

        // Now draw the points
        for (int i = 0; i < numPoints; i++) {
        g2.fillRect((int) (Xwid * x[i]) - POINTWID, (int) (Ywid * y[i])
                - POINTWID, 2 * POINTWID + 1, 2 * POINTWID + 1);
        }

        // Finally, display the total length
        g2.drawString("Length: " + totalLength + "          ", 0, 20);
    }

    /*
     * This is the only function you need to mess with
     */
    public static void createSimplePolygon() {
        // Initialize the C[] array with the identity permutation
        for (int i = 0; i < numPoints; i++)
        C[i] = i;
    }
   

    }
}