1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284

/**
 *  Copyright (c) 2005-2010 Hank Dolben
 *  Licensed under the Open Software License version 2.1
 *  http://opensource.org/licenses/osl-2.1.php
 */
package org.dolben.poly;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import org.dolben.iiid.R3;
import org.dolben.iiid.Rn;

/**
 *  A polyhedron that has edges that are all the same length.
 *
 *  create() only sets the vertices. Constructor sets the faces.
 */
public abstract class Equilateral extends Polyhedron {
    
    private double edgeLength;
    
    public Equilateral( ) {
        create();
        setEdgeLength();
        findFaces();
    }
    
    /**
     *  Sets the length of an edge. All edges must be the same length.
     *
     *  Finds the minimum distance between vertices.
     */
    protected void setEdgeLength( ) {
        edgeLength = Rn.magnitude(Rn.subtract(vertex[0],vertex[1]));
        for ( int i = 0; i < vertex.length-1; ++i ) {
            for ( int j = i+1; j < vertex.length; ++j ) {
                double distance =
                    Rn.magnitude(Rn.subtract(vertex[i],vertex[j]));
                if ( distance < edgeLength ) {
                    edgeLength = distance;
                }
            }
        }
    }
    
    /**
     *  Finds and sets all of the faces for Polyhedron.
     */
    private void findFaces( ) {
        /*
         *  For each vertex find all of the edges and sort them
         *  by angle around the radius.
         *
         *  Then, for each vertex walk around the faces starting with
         *  each untraversed edge leading from the vertex.
         *  At the next vertex, take the edge that comes after the
         *  one just followed, i.e., exit the node to the left of
         *  where it was entered.
         *
         *  Set the faces array from the list of faces.
         */
        setFaces(walkGraph(createGraph()));
    }
    
    /**
     *  Creates a graph (nodes and edges) of the polyhedron
     *  and returns a list of the nodes.
     */
    private List createGraph( ) {
        List nodes = new LinkedList();
        for ( int i = 0; i < vertex.length; ++i ) {
            nodes.add(new Node(i));
        }
        return nodes;
    }
    
    /**
     *  Walks around each face of the graph and returns a list of the faces.
     */
    private List walkGraph( List nodes ) {
        /*
         *  There are a couple of key points to this algorithm.
         *
         *  First, the list of edges at a node have been ordered by angle
         *  around the vertex, so that if you're looking along the radius
         *  of a vertex towards the center of the polyhedron, the edges are
         *  listed in clockwise order. Then, following the edges around a
         *  face in the counter-clockwise direction (viewed from outside
         *  the polyhedron), upon arriving at a node the next edge will be
         *  to the left of (following, on the list) the edge on which you
         *  arrived.
         *
         *  Second, each edge is listed at two nodes and is on two faces,
         *  and so is traversed twice, once in each direction; each time
         *  for the face on the left.
         */
        List faces = new LinkedList();
        for ( int index = 0; index < vertex.length; ++index ) {
            while ( true ) {
                Node node = (Node)nodes.get(index);
                int next = node.getNodeOnUntraversedEdge();
                if ( next == index ) {
                    break;
                }
                List face = new LinkedList();
                faces.add(face);
                face.add(new Integer(index));
                int last = index;
                while ( next != index ) {
                    face.add(new Integer(next));
                    node = (Node)nodes.get(next);
                    int current = next;
                    next = node.getNextNode(last);
                    last = current;
                }
            }
        }
        return faces;
    }
    
    /**
     *  Sets the array of faces as required by Polyhedron.
     */
    private void setFaces( List faces ) {
        face = new int[faces.size()][];
        for ( int i = 0; i < faces.size(); ++i ) {
            List f = (List)faces.get(i);
            int[] index = new int[f.size()];
            face[i] = index;
            for ( int j = 0; j < f.size(); ++j ) {
                index[j] = ((Integer)f.get(j)).intValue();
            }
        }
    }
    
    /**
     *  Node in the graph of a polyhedron has edges to adjacent nodes.
     *
     *  Edges are ordered where right-hand rule produces the direction
     *  from the node's point to the center.
     */
    private class Node {
        
        private List edges;         // edges at this node
        private int index;          // identity of this node
        private double[] reference; // edges sorted by angle relative to this
        
        /**
         *  Creates a node with the given identity, finding its edges.
         */
        public Node( int i ) {
            edges = null;
            index = i;
            reference = null;
            findEdges();
        }
        
        /**
         *  Finds all of the edges of this node
         *  assuming that they are all the same length.
         */
        private void findEdges( ) {
            final double TOLERANCE = 1e-2;
            double[] v = vertex[index];
            double[] u = unit(v);
            for ( int other = 0; other < vertex.length; ++other ) {
                if ( other != index ) {
                    double[] disp = Rn.subtract(vertex[other],v);
                    double distance = Rn.magnitude(disp);
                    if ( Math.abs(1-(distance/edgeLength)) < TOLERANCE ) {
                        double r = Rn.dot(disp,u)/distance;
                        double[] direction = Rn.subtract(disp,Rn.multiply(r,u));
                        addEdge(other,unit(direction));
                    }
                }
            }
            Collections.sort(edges);
        }
        
        /**
         *  Adds an edge that goes to the given other node in some direction
         *  (perpendicular to the radius vector to this node's vertex).
         */
        public void addEdge( int other, double[] direction ) {
            double angle = 0;
            if ( edges == null ) {
                reference = direction;
                edges = new LinkedList();
            } else {
                angle = Math.acos(Rn.dot(direction,reference));
                if ( Rn.dot(direction,R3.cross(reference,vertex[index])) < 0 ) {
                    angle = -angle;
                }
            }
            edges.add(new Edge(other,angle));
        }
        
        /**
         *  Returns the unit vector in the direction of the one given.
         */
        private double[] unit( double[] v ) {
            return Rn.multiply(1/Rn.magnitude(v),v);
        }
        
        /**
         *  Returns the index of the next node in a face
         *  given the index of the last node.
         */
        public int getNextNode( int last ) {
            Iterator it = edges.iterator();
            while ( it.hasNext() ) {
                Edge edge = (Edge)it.next();
                if ( edge.getOther() == last ) {
                    break;
                }
            }
            Edge edge = (Edge)( it.hasNext() ? it.next() : edges.get(0) );
            return edge.traverse();
        }
        
        /**
         *  Returns the index of the node that is on
         *  a previously untraversed edge from this node.
         */
        public int getNodeOnUntraversedEdge( ) {
            Iterator it = edges.iterator();
            while ( it.hasNext() ) {
                Edge edge = (Edge)it.next();
                if ( !edge.getTraversed() ) {
                    return edge.traverse();
                }
            }
            return index;
        }
    
    }
    
    // An edge in a graph
    private class Edge implements Comparable {
        
        private int other;          // index of node at the other end of edge
        private boolean traversed;  // edge has been traversed
        private double angle;       // angle of edge around radial
        
        // makes a new edge
        public Edge( int othr, double angl ) {
            other = othr;
            angle = angl;
            traversed = false;
        }
        
        // traverses the edge returning the index of the node there
        public int traverse( ) {
            traversed = true;
            return other;
        }
        
        // returns node
        public int getOther( ) {
            return other;
        }
        
        // returns traversed
        public boolean getTraversed( ) {
            return traversed;
        }
        
        // Order Edges by increasing angle.
        public int compareTo( Object obj ) {
            Edge o = (Edge)obj;
            if ( angle < o.angle ) {
                return -1;
            } else if ( angle > o.angle ) {
                return 1;
            } else {
                return 0;
            }
        }
    
    }

}