Mutating Polygons

by Michael Gilleland, Merriam Park Software

In their book The Mathematical Experience (Houghton Mifflin, 1981), Philip J. Davis and Reuben Hirsch describe the following example of order emerging from chaos: "A polygon whose vertices are random is transformed by replacing it by the polygon formed by the midpoints of its sides. Upon iteration of this transformation, an ellipse-like convex figure almost always emerges" (pp. 175-176).

Here is a Java applet which illustrates this interesting transformation. Keep clicking on the Transform button to see the polygon eventually change itself into "an ellipse-like convex figure".

The source code consists of two classes, MutatingPolygon and MutatingPolygonApplet:

MutatingPolygon

import java.awt.Point;
import java.awt.Polygon;

//------------------------------------------------------
// This polygon mutates in accordance with the
// rules defined in Philip J. Davis and Reuben Hirsch,
// The Mathematical Experience (Houghton Mifflin, 1981),
// pp. 175 ff.
//------------------------------------------------------

public class MutatingPolygon {

  private Polygon polygon = null;
  private int maxVertices = 0;
  private int maxX = 0;
  private int maxY = 0;
  private boolean debug = false;

  //-------------
  // Constructors
  //-------------

  public MutatingPolygon (int maxVertices, int maxX, int maxY) {
    this (maxVertices, maxX, maxY, false);
  }

  public MutatingPolygon (int maxVertices, int maxX, int maxY, boolean debug) {
    this.maxVertices = maxVertices;
    this.debug = debug;
    this.maxX = maxX;
    this.maxY = maxY;
    reset ();
  }

  //------------
  // Get polygon
  //------------

  public Polygon get () {
    return polygon;
  }

  //------
  // Reset
  //------

  public void reset () {
    polygon = new Polygon ();
    Point p = null;
    for (int i = 0; i < maxVertices; i++) {
      p = getRandomPoint ();
      polygon.addPoint (p.x, p.y);
    }
    if (debug) {
      trace ("reset");
      trace (toString ());
    }
  }

  //----------
  // Transform
  //----------

  public void transform () {

    if (polygon == null) {
      reset ();
      return;
    }

    if (polygon.npoints <= 2) {
      reset ();
      return;
    }

    Polygon old = clonePolygon (polygon);
    polygon = new Polygon ();
    Point p = null;
    for (int i = 0; i < old.npoints - 1; i++) {
      p = getNextPoint (old.xpoints [i], old.ypoints [i],
                        old.xpoints [i + 1], old.ypoints [i + 1]);
      polygon.addPoint (p.x, p.y);
    }

    if (debug) {
      trace ("transform");
      trace (toString ());
    }

  }

  //-------------------------------------------------------------
  // Get next point, which is midway between the specified points
  //-------------------------------------------------------------

  private Point getNextPoint (int x1, int y1, int x2, int y2) {
    int halfx = java.lang.Math.abs (x1 - x2) / 2;
    int halfy = java.lang.Math.abs (y1 - y2) / 2;
    int midx = java.lang.Math.min (x1, x2) + halfx;
    int midy = java.lang.Math.min (y1, y2) + halfy;
    return new Point (midx, midy);
  }

  //-----------------
  // Get random point
  //-----------------

  private Point getRandomPoint () {
    Point p = new Point (getRandomInt (maxX), getRandomInt (maxY));
    return p;
  }

  //-------------------
  // Get random integer
  //-------------------

  private int getRandomInt (int max) {
    return (int) (java.lang.Math.random () * max);
  }

  //--------------
  // Clone polygon
  //--------------

  private static Polygon clonePolygon (Polygon poly) {
    return new Polygon (poly.xpoints, poly.ypoints, poly.npoints);
  }

  //------------------
  // Override toString
  //------------------

  public String toString () {
    StringBuffer sb = new StringBuffer ();
    sb.append ("npoints: " + polygon.npoints + "\n");
    for (int i = 0; i < polygon.npoints; i++) {
      sb.append ("point " + i + " [" + polygon.xpoints [i] +
                                ", " + polygon.ypoints [i] + "]\n");
    }
    return sb.toString ();
  }

  //------
  // Trace
  //------

  private void trace (String s) {
    System.out.println (s);
  }

}

MutatingPolygonApplet

import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;

//---------------------------------------------
// This applet displays a polygon which mutates
// under the user's control.
//---------------------------------------------

public class MutatingPolygonApplet extends Applet {

  private MutatingPolygon mutating = null;
  private Button resetButton = null;
  private Button transformButton = null;
  private DrawingRegion drawingRegion = null;

  //------------------------
  // Override Applet methods
  //------------------------

  public void init () {

    resetButton = new Button ("Start Over");
    add (resetButton);

    transformButton = new Button ("Transform");
    add (transformButton);

    mutating = new MutatingPolygon (20, 360, 360);

    drawingRegion = new DrawingRegion (360, 360);
    add (drawingRegion);

  }

  public void paint (Graphics g) {
    drawingRegion.repaint ();
  }

  public boolean action (Event e, Object arg) {

    if (e.target == resetButton) {
      mutating.reset ();
      repaint ();
      return true;
    }

    else if (e.target == transformButton) {
      mutating.transform ();
      repaint ();
      return true;
    }

    else {
      return false;
    }

  }

  //-------------------------------
  // Drawing region for the polygon
  //-------------------------------

  class DrawingRegion extends Canvas {

    public DrawingRegion (int width, int height) {
      setSize (width, height);
    }

    public void paint (Graphics g) {
      Polygon polygon = mutating.get ();
      if (polygon != null) {
        g.drawPolygon (polygon);
      }
    }

  }

  //-------------------
  // Run as application
  //-------------------

  public static void main (String[] args) {

    // Create frame to house the applet

    Frame frame = new Frame ("Mutating Polygon");

    // Create an instance of the applet

    MutatingPolygonApplet app = new MutatingPolygonApplet ();

    // Add it to the center of the frame

    frame.add (app, BorderLayout.CENTER);
    frame.setSize (425, 425);

    // Listen for window closing event

    frame.addWindowListener (new WindowAdapter () {
      public void windowClosing (WindowEvent e) {
        System.exit (0);
      }
    });

    // Call the applet methods

    app.init ();
    app.start ();

    // Set the frame visible

    frame.setVisible (true);

  }

}