/**
* @(#)GridSpiralsApplet.java
* Done in java 1.1 for any browser.
* @author JLMJ
* @date 2004/2/13
*/
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class GridSpiralsApplet extends Applet
{
static V[] vectors = new V[] {
new V(1, 0), // 1
new V(1, 1), // 2
new V(2, 0), // 4
new V(2, 1), // 5
new V(2, 2), // 8
new V(3, 0), // 9
new V(3, 1), // 10
new V(3, 2), // 13
new V(4, 0), // 16
new V(4, 1), // 17
new V(3, 3) // 18
};
static int MAX_DISTINCT = 6;
class Distinct extends Panel implements ItemListener
{
Checkbox[] radioBs;
Checkbox[] abc;
Choice[] choices;
int n;
Distinct() {
super();
setLayout(new GridBagLayout());
GridBagConstraints g = new GridBagConstraints();
g.gridx = g.gridy = 0;
abc = new Checkbox[3];
CheckboxGroup abcG = new CheckboxGroup();
(abc[0] = new Checkbox("A", abcG, true)).addItemListener(this);
(abc[1] = new Checkbox("B", abcG, false)).addItemListener(this);
(abc[2] = new Checkbox("C", abcG, false)).addItemListener(this);
Panel abcP = new Panel(new FlowLayout(FlowLayout.RIGHT,0,0));
abcP.add(abc[0]);
abcP.add(abc[1]); abc[1].setEnabled(false);
abcP.add(abc[2]); abc[2].setEnabled(false);
CheckboxGroup group = new CheckboxGroup();
radioBs = new Checkbox[MAX_DISTINCT];
choices = new Choice[MAX_DISTINCT];
g.gridwidth = 2;
add(new Label("Diagonals"), g); g.gridy++;
add(new Label("Squared"), g); g.gridy++;
g.gridwidth = 1;
for (int i=0; i < radioBs.length; i++) {
radioBs[i] = new Checkbox(
String.valueOf(i+1), group, i==0);
radioBs[i].addItemListener(this);
choices[i] = new Choice();
for (int j=0; j < vectors.length; j++)
choices[i].add(String.valueOf(vectors[j].diagonal));
choices[i].addItemListener(this);
g.gridx = 0; add(radioBs[i], g);
g.gridx = 1; add(choices[i], g);
if (i==0) {
g.gridy++; g.gridx = 1; add(abcP, g);
}
g.gridy++;
}
n = 1;
}
public void select(int[] selections, int abcIndex) {
n = selections.length;
radioBs[n-1].setState(true);
for (int j=0; j < choices.length; j++) {
if (j < n)
choices[j].select(String.valueOf(selections[j]));
choices[j].setVisible(j < n);
}
abc[abcIndex].setState(true);
updateSpiral();
}
public void itemStateChanged(ItemEvent e) {
for (int i=0; i < radioBs.length; i++) {
if (e.getSource() == radioBs[i]) {
n = i+1;
for (int j=0; j < choices.length; j++)
choices[j].setVisible(j < n);
updateSpiral();
return;
}
}
if (e.getSource() == choices[0]) {
int s = choices[0].getSelectedIndex();
int[] starts = vectors[s].abc();
abc[0].setEnabled(false);
abc[1].setEnabled(false);
abc[2].setEnabled(false);
for (int i=0; i < starts.length; i++)
abc[i].setEnabled(true);
abc[0].setState(true);
}
updateSpiral();
}
public V[] getDistinctVectors() {
V[] v = new V[n];
for (int i=0; i < v.length; i++)
v[i] = vectors[choices[i].getSelectedIndex()];
return v;
}
public int getABCstate() {
if (abc[0].getState()) return 0;
else if (abc[1].getState()) return 1;
return 2;
}
}
class Segments extends Panel implements AdjustmentListener
{
final int MAX_SEGMENTS = 1000;
Scrollbar scroll;
int nSegments;
Label segmentsL;
Label haltL;
int haltPointIndex = -1;
int grid = 7;
Scrollbar gridScroll;
Label gridLabel;
Segments() {
super(new BorderLayout());
scroll = new Scrollbar(Scrollbar.VERTICAL,1,1,1,MAX_SEGMENTS);
scroll.addAdjustmentListener(this);
nSegments = 1;
segmentsL = new Label(" ", Label.RIGHT);
add(BorderLayout.NORTH, new Label("# of Segments", Label.RIGHT));
add(BorderLayout.EAST, scroll);
add(BorderLayout.WEST, haltL = new Label("Halted"));
add(BorderLayout.CENTER, segmentsL);
gridScroll = new Scrollbar(Scrollbar.HORIZONTAL,grid,1,5,30);
gridScroll.addAdjustmentListener(this);
Panel gridP = new Panel(new FlowLayout(FlowLayout.LEFT,0,0));
gridP.add(new Label("Grid"));
gridP.add(gridScroll);
gridP.add(gridLabel = new Label(String.valueOf(grid)));
add(BorderLayout.SOUTH, gridP);
}
public void setValue(int v) {
nSegments = v;
scroll.setValue(v);
segmentsL.setText(String.valueOf(v));
}
public void adjustmentValueChanged(AdjustmentEvent e) {
if (e.getAdjustable() == scroll) {
nSegments = scroll.getValue();
segmentsL.setText(String.valueOf(nSegments));
updateSpiral();
} else if (e.getAdjustable() == gridScroll) {
grid = gridScroll.getValue();
gridLabel.setText(String.valueOf(grid));
updateSpiral();
}
}
synchronized Point[] getPoints(V[] vs, int abcIndex) {
haltPointIndex = -1;
Vector vector = new Vector();
vector.addElement(new Point(0, 0));
int v = 0; // current selected vector index
double angle = vs[v].getAngle(abcIndex);
for (int i=1; i < nSegments + 1; i++) {
int n = vs[v].getNumber();
int pos = n-1; // last vector
double a=0, b=0;
for (int j=0; j < n; j++) {
// found two consecutive angles a,b such that
// a < angle && b >= angle, several times as needed
a = vs[v].getAngle(j);
b = vs[v].getAngle(j+1);
if (a < angle && b >= angle) {
pos = j;
break;
}
}
Point p1 = (Point)vector.elementAt(i-1);
boolean next = false;
for (int j=0; j < n; j++) {
int realPos = (n + pos - j) % n;
int p2x = p1.x + vs[v].dx[realPos];
int p2y = p1.y + vs[v].dy[realPos];
Point p2 = new Point(p2x, p2y);
boolean intersected = false;
if (i > 2) {
for (int k=0; k < i-2; k++) {
Point q1 = (Point)vector.elementAt(k);
Point q2 = (Point)vector.elementAt(k+1);
if (intersects(q1, q2, p1, p2)) {
intersected = true;
break;
}
}
}
if (!intersected) {
pos = realPos;
vector.addElement(p2);
next = true;
break;
}
}
if (!next) {
haltPointIndex = i - 1;
break;
}
// reflect 180
angle = vs[v].getAngle(pos + n/2);
v++; v %= vs.length;
}
Point[] points = new Point[vector.size()];
for (int i=0; i < points.length; i++)
points[i] = (Point)vector.elementAt(i);
setValue(points.length-1);
haltL.setVisible(haltPointIndex != -1);
return points;
}
int getHaltPointIndex() {
return haltPointIndex;
}
/**
* Returns true if line segment formed by points a1
* and a2 touches at least on point of line segment formed by
* point b1 and b2. Returns false otherwise.
*/
boolean intersects(Point a1, Point a2, Point b1, Point b2) {
if (a1.x == a2.x && b1.x == b2.x && a1.x == b1.x) {
// Both lines are vertical and co-lineals
// verify both b's y1,y2 are not inside a's y1, y2 range.
if (b2.y > b1.y) {
if (b1.y > a1.y && b1.y > a2.y) return false;
if (b2.y < a1.y && b2.y < a2.y) return false;
} else if (b2.y < b1.y) {
if (b2.y > a1.y && b2.y > a2.y) return false;
if (b1.y < a1.y && b1.y < a2.y) return false;
}
return true;
}
// Used to compute (one or two times):
// dx = x2 - x1
// dy = y2 - y1
// xy = x2y1 - x1y2
int dx, dy, xy;
// Used to compute (one or two times):
//
// (y2-y1)X x2y1 - x1y2 dyX + xy
// Y = -------- + ------------- = --------
// (x2-x1) x2 - x1 dx
//
// diffY =
// find if b1.y and b2.y are at the same side of line "a"
// taking into account b1.x and b2.x
int dy1_times_dx, dy2_times_dx;
// Point a
dx = a2.x - a1.x;
dy = a2.y - a1.y;
xy = a2.x*a1.y - a1.x*a2.y; // x2y1 - x1y2
// Calculte y differences with b points and line a.
dy1_times_dx = (dy*b1.x) + xy - (b1.y*dx);
dy2_times_dx = (dy*b2.x) + xy - (b2.y*dx);
if (dy1_times_dx == 0 && dy2_times_dx == 0) {
// Both lines are parallel and co-lineals
// check both b's x1,x2 are not inside a's x1, x2 range
if (b2.x > b1.x) {
if (b1.x > a1.x && b1.x > a2.x) return false;
if (b2.x < a1.x && b2.x < a2.x) return false;
} else if (b2.x < b1.x) {
if (b2.x > a1.x && b2.x > a2.x) return false;
if (b1.x < a1.x && b1.x < a2.x) return false;
}
return true;
}
if ((dy1_times_dx * dy2_times_dx) > 0) {
// Points in the same side of line a
return false;
}
// Invert lines to check again
dx = b2.x - b1.x;
dy = b2.y - b1.y;
xy = b2.x*b1.y - b1.x*b2.y;
dy1_times_dx = (dy*a1.x) + xy - (a1.y*dx);
dy2_times_dx = (dy*a2.x) + xy - (a2.y*dx);
if ((dy1_times_dx * dy2_times_dx) > 0) {
// Points in the same side of line b
return false;
} else {
// Points in the distinct side of line b (and a).
return true;
}
}
}
class Spiral extends Canvas
{
final int MAX = 400;
private Point[] points;
private int haltPointIndex;
Spiral() {
setBounds(0, 0, MAX, MAX);
}
Image offscreen;
Dimension offscreensize;
Graphics hidden;
public void draw(Point[] points, int haltPointIndex) {
this.points = points;
this.haltPointIndex = haltPointIndex;
repaint();
}
public void update(Graphics g) {
Dimension d = size();
if ((offscreen == null) || (d.width != offscreensize.width) ||
(d.height != offscreensize.height)) {
offscreen = createImage(d.width, d.height);
offscreensize = d;
hidden = offscreen.getGraphics();
}
hidden.setColor(getBackground());
hidden.fillRect(0, 0, d.width, d.height);
hidden.setColor(Color.black);
paint(hidden);
g.drawImage(offscreen, 0, 0, null);
}
public void paint(Graphics g) {
int grid = segments.grid;
int center = (MAX/grid/2) * grid;
g.setColor(Color.white);
g.fillRect(0, 0, MAX, MAX);
g.setColor(Color.cyan);
for (int x=0; x < MAX; x += grid)
g.drawLine(x, 0, x, MAX);
for (int y=0; y < MAX; y += grid)
g.drawLine(0, y, MAX, y);
for (int i=1; i < points.length; i++) {
g.setColor(Color.blue);
Point p1 = points[i-1];
Point p2 = points[i];
if (p1 == null || p2 == null)
continue;
int x1 = center + p1.x*grid;
int y1 = center - p1.y*grid;
int x2 = center + p2.x*grid;
int y2 = center - p2.y*grid;
g.drawLine(x1, y1, x2, y2);
g.fillOval(x1-2, y1-2, 4, 4);
if (haltPointIndex == i)
g.setColor(Color.red);
g.fillOval(x2-2, y2-2, 4, 4);
}
}
}
private Distinct distinct;
private Spiral spiral;
private Segments segments;
public void init()
{
setLayout(new BorderLayout());
setBackground(Color.lightGray);
distinct = new Distinct();
spiral = new Spiral();
segments = new Segments();
Panel west = new Panel(new BorderLayout());
west.add(BorderLayout.NORTH, distinct);
west.add(BorderLayout.CENTER, segments);
add(BorderLayout.WEST, west);
add(BorderLayout.CENTER, spiral);
}
StringBuffer finite, infinite;
Stack stack;
private void nonRecursive() {
finite = new StringBuffer();
infinite = new StringBuffer();
stack = new Stack();
System.out.print("Firsts: ");
recursive(0);
System.out.println("\nINFINITE:\n" + infinite.toString());
System.out.println("\nFINITE:\n" + finite.toString());
}
private void recursive(int pass) {
for (int i=0; i < vectors.length; i++) {
if (pass == 0)
System.out.print(vectors[i].diagonal + " ");
stack.push(vectors[i]);
if (pass == 0) {
V[] vs = new V[stack.size()];
for (int m=0; m < vs.length; m++)
vs[m] = (V)stack.elementAt(m);
int[] abc = vs[0].abc();
for (int z = 0; z < abc.length; z++) {
segments.setValue(segments.MAX_SEGMENTS);
Point[] points = segments.getPoints(vs, z);
int n = points.length - 1;
String row = "";
for (int m=0; m < vs.length; m++) {
row += vs[m].diagonal;
if (m==0) {
row += ((z==0)?"A":(z==1)?"B":"C") + "-";
} else if (m < vs.length-1) {
row += "-";
}
}
if (n == segments.MAX_SEGMENTS)
infinite.append(row + "\n");
else if (n > 0)
finite.append(row + " -> " + n + "\n");
}
} else {
recursive(pass-1);
}
stack.pop();
}
}
public void start() {
//nonRecursive();
distinct.select(new int[] { 13, 16 }, 1);
segments.setValue(300);
updateSpiral();
}
private void updateSpiral() {
V[] vs = distinct.getDistinctVectors();
Point[] points = segments.getPoints(vs, distinct.getABCstate());
spiral.draw(points, segments.getHaltPointIndex());
}
}
class V {
private double[] angles;
int[] dx, dy;
int diagonal;
V (int x, int y) {
if (x < 0) x = -x; // fix x to be positive
if (y < 0) y = -y; // fix y to be positive
if (y > x) { int m = y; y = x; x = m; } // x must be greater than y
diagonal = x*x + y*y;
if (y == 0) {
// Four vectors at 0, 90, 180 and 180 degrees.
angles = new double[4];
dx = new int[4];
dy = new int[4];
dx[0] = x; dy[0] = 0; // quadrant I
dx[1] = 0; dy[1] = x; // quadrant II
dx[2] = -x; dy[2] = 0; // quadrant III
dx[3] = 0; dy[3] = -x; // quadrant IV
angles[0] = 0;
angles[1] = 90;
angles[2] = 180;
angles[3] = 270;
} else if (x == y) {
// Four vectors at 45, 135, 225 and 315 degrees
angles = new double[4];
dx = new int[4];
dy = new int[4];
dx[0] = x; dy[0] = y; // quadrant I
dx[1] = -y; dy[1] = x; // quadrant II
dx[2] = -x; dy[2] = -y; // quadrant III
dx[3] = y; dy[3] = -x; // quadrant IV
angles[0] = 45;
angles[1] = 135;
angles[2] = 225;
angles[3] = 315;
} else {
angles = new double[8];
dx = new int[8];
dy = new int[8];
// quadrant I
dx[0] = x; dy[0] = y;
dx[1] = y; dy[1] = x;
// quadrant II
dx[2] = -y; dy[2] = x;
dx[3] = -x; dy[3] = y;
// quadrant III
dx[4] = -x; dy[4] = -y;
dx[5] = -y; dy[5] = -x;
// quadrant IV
dx[6] = y; dy[6] = -x;
dx[7] = x; dy[7] = -y;
angles[0] = (x==0) ? 90 : 180*Math.atan((float)y/(float)x)/Math.PI;
angles[1] = (y==0) ? 90 : 180*Math.atan((float)x/(float)y)/Math.PI;
angles[2] = 90 + angles[0];
angles[3] = 90 + angles[1];
angles[4] = 180 + angles[0];
angles[5] = 180 + angles[1];
angles[6] = 270 + angles[0];
angles[7] = 270 + angles[1];
}
}
public int getNumber() { return angles.length; }
public double getAngle(int pos) { return angles[pos%angles.length]; }
public int[] abc() {
if (angles.length == 4) { return new int[] { 0 }; }
else if (angles.length == 8) { return new int[] { 0,1 }; }
else { return new int[] { 0,1,2 }; }
}
}