programming-examples/java/Data_Structures/RandomPolygon.java

import javax.swing.*;
import java.awt.*;
import java.util.Random;

public class RandomPolygon extends JFrame {

	public static int[][] getRandomPolygon(int n, int maxWidth, int maxHeight) {
		Random rnd = new Random(1);
		int[] x = new int[n];
		int[] y = new int[n];
		int[] p = new int[n];
		while (true) {
			for (int i = 0; i < n; i++) {
				x[i] = rnd.nextInt(maxWidth);
				y[i] = rnd.nextInt(maxHeight);
				p[i] = i;
			}
			for (boolean improved = true; improved; ) {
				improved = false;
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						int[] p1 = p.clone();
						reverse(p1, i, j);
						if (len(x, y, p) > len(x, y, p1)) {
							p = p1;
							improved = true;
						}
					}
				}
			}
			int[] tx = x.clone();
			int[] ty = y.clone();
			for (int i = 0; i < n; i++) {
				x[i] = tx[p[i]];
				y[i] = ty[p[i]];
			}
			boolean ok = true;
			for (int i = 0; i < n; i++) {
				long x1 = x[(i - 1 + n) % n] - x[i];
				long y1 = y[(i - 1 + n) % n] - y[i];
				long x2 = x[(i + 1) % n] - x[i];
				long y2 = y[(i + 1) % n] - y[i];
				ok &= x1 * y2 - x2 * y1 != 0 || x1 * x2 + y1 * y2 <= 0;
			}
			for (int i2 = 0, i1 = n - 1; i2 < n; i1 = i2++)
				for (int j2 = 0, j1 = n - 1; j2 < n; j1 = j2++)
					ok &= i1 == j1 || i1 == j2 || i2 == j1
							|| !isCrossOrTouchIntersect(x[i1], y[i1], x[i2], y[i2], x[j1], y[j1], x[j2], y[j2]);
			if (ok)
				return new int[][]{x, y};
		}
	}

	// http://en.wikipedia.org/wiki/2-opt
	static void reverse(int[] p, int i, int j) {
		int n = p.length;
		// reverse order from i to j
		while (i != j) {
			int t = p[j];
			p[j] = p[i];
			p[i] = t;
			i = (i + 1) % n;
			if (i == j) break;
			j = (j - 1 + n) % n;
		}
	}

	static double len(int[] x, int[] y, int[] p) {
		double res = 0;
		for (int i = 0, j = p.length - 1; i < p.length; j = i++) {
			double dx = x[p[i]] - x[p[j]];
			double dy = y[p[i]] - y[p[j]];
			res += Math.sqrt(dx * dx + dy * dy);
		}
		return res;
	}

	static boolean isCrossOrTouchIntersect(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
		if (Math.max(x1, x2) < Math.min(x3, x4) || Math.max(x3, x4) < Math.min(x1, x2)
				|| Math.max(y1, y2) < Math.min(y3, y4) || Math.max(y3, y4) < Math.min(y1, y2))
			return false;
		long z1 = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
		long z2 = (x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1);
		long z3 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
		long z4 = (x4 - x3) * (y2 - y3) - (y4 - y3) * (x2 - x3);
		return (z1 <= 0 || z2 <= 0) && (z1 >= 0 || z2 >= 0) && (z3 <= 0 || z4 <= 0) && (z3 >= 0 || z4 >= 0);
	}

	// visualization code
	public RandomPolygon() {
		setContentPane(new JPanel() {
			protected void paintComponent(Graphics g) {
				super.paintComponent(g);
				((Graphics2D) g).setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
				((Graphics2D) g).setStroke(new BasicStroke(3));
				int[][] xy = getRandomPolygon(new Random().nextInt(100) + 3, getWidth() - 20, getHeight() - 50);
				g.setColor(Color.BLUE);
				int n = xy[0].length;
				for (int i = 0, j = n - 1; i < n; j = i++)
					g.drawLine(xy[0][i], xy[1][i], xy[0][j], xy[1][j]);
				g.setColor(Color.RED);
				for (int i = 0; i < n; i++)
					g.drawOval(xy[0][i] - 1, xy[1][i] - 1, 3, 3);
			}
		});
		setSize(new Dimension(600, 600));
		setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
		setVisible(true);
		new Thread() {
			public void run() {
				while (true) {
					try {
						Thread.sleep(200);
					} catch (InterruptedException e) {
					}
					repaint();
				}
			}
		}.start();
	}

	public static void main(String[] args) {
		new RandomPolygon();
	}
}