[Geom4j-developer] SF.net SVN: geom4j:[31] trunk/src/net/sourceforge/geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[31] trunk/src/net/sourceforge/geom4j
|
From: <skh...@us...> - 2010-01-16 11:32:25
|
Revision: 31
http://geom4j.svn.sourceforge.net/geom4j/?rev=31&view=rev
Author: skhenkin
Date: 2010-01-16 11:32:17 +0000 (Sat, 16 Jan 2010)
Log Message:
-----------
Refactoring of the code to remove Polygon.addVertex() method completely.
So from now on Polygon is an immutable class.
This is also a preparation step for making polygons always counter-clockwise traversed.
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java
trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java
trunk/src/net/sourceforge/geom4j/PointTest.java
trunk/src/net/sourceforge/geom4j/Polygon.java
trunk/src/net/sourceforge/geom4j/PolygonTest.java
trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java
trunk/src/net/sourceforge/geom4j/TriangulationTest.java
trunk/src/net/sourceforge/geom4j/demo/Demo.java
Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -18,6 +18,7 @@
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
+import java.util.LinkedList;
import java.util.List;
/**
@@ -61,13 +62,14 @@
static ConvexHullAlgorithm JARVIS_MARCH = new ConvexHullAlgorithm() {
@Override
public Polygon run(PointSet ps) {
- Polygon hull = new Polygon();
+ List<Point> hull = new LinkedList<Point>();
Point pointOnHull = ps.getLeftmost();
+ Point firstVertex = pointOnHull;
do {
- hull.addVertex(pointOnHull);
+ hull.add(pointOnHull);
pointOnHull = getNextPoint(ps, pointOnHull);
- } while (!pointOnHull.equals(hull.getFirstVertex()));
- return hull;
+ } while (!pointOnHull.equals(firstVertex));
+ return new Polygon(hull);
}
/* Find the point with the biggest polar angle
@@ -143,12 +145,12 @@
}
stack[++m] = points.get(i);
}
-
- Polygon hull = new Polygon();
+
+ List<Point> hull = new LinkedList<Point>();
for (int i = 0; i <= m; i++) {
- hull.addVertex(stack[i]);
+ hull.add(stack[i]);
}
- return hull;
+ return new Polygon(hull);
}
/** Test if p1-p2-p3 form a non-left turn, i.e. straight line or right turn */
Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithmTest.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -52,15 +52,15 @@
ps.add(new Point(11, 4));
ps.add(new Point(9, 2));
- ch = new Polygon();
- ch.addVertex(new Point(5, 1));
- ch.addVertex(new Point(9, 2));
- ch.addVertex(new Point(11, 4));
- ch.addVertex(new Point(10, 5));
- ch.addVertex(new Point(5, 7));
- ch.addVertex(new Point(3, 6));
- ch.addVertex(new Point(2, 4));
- ch.addVertex(new Point(2, 2));
+ ch = new Polygon(
+ new Point(5, 1),
+ new Point(9, 2),
+ new Point(11, 4),
+ new Point(10, 5),
+ new Point(5, 7),
+ new Point(3, 6),
+ new Point(2, 4),
+ new Point(2, 2));
}
Modified: trunk/src/net/sourceforge/geom4j/PointTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -53,18 +53,18 @@
@Test
public void testPointInPolygon() {
- Polygon p = new Polygon()
- .addVertex(new Point(2, 0))
- .addVertex(new Point(1, 2))
- .addVertex(new Point(2, 5))
- .addVertex(new Point(3, 3))
- .addVertex(new Point(4, 5))
- .addVertex(new Point(5, 3))
- .addVertex(new Point(6, 5))
- .addVertex(new Point(7, 2))
- .addVertex(new Point(6, 1))
- .addVertex(new Point(5, 1))
- .addVertex(new Point(4, 0));
+ Polygon p = new Polygon(
+ new Point(2, 0),
+ new Point(1, 2),
+ new Point(2, 5),
+ new Point(3, 3),
+ new Point(4, 5),
+ new Point(5, 3),
+ new Point(6, 5),
+ new Point(7, 2),
+ new Point(6, 1),
+ new Point(5, 1),
+ new Point(4, 0));
assertTrue(new Point(6, 4).isInside(p));
assertFalse(new Point(5, 4).isInside(p));
Modified: trunk/src/net/sourceforge/geom4j/Polygon.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -16,17 +16,18 @@
package net.sourceforge.geom4j;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.Iterator;
import java.util.List;
/**
* A polygon is a closed shape in a plane.
+ * This is immutable class.
*
* @author Sergey Khenkin
* @since 1.0.0
*/
public class Polygon extends BasicFigure {
- // TODO: think of making this class also immutable
protected List<Point> vertices;
@@ -41,11 +42,10 @@
}
}
- public Polygon addVertex(Point p) {
- vertices.add(p);
- return this;
+ public Polygon(Collection<Point> vertices) {
+ this(vertices.toArray(new Point[0]));
}
-
+
/** Get number of polygon's vertices (corners) */
public int getVertexCount() {
return vertices.size();
@@ -267,4 +267,22 @@
public Triangulation triangulate(PolygonTriangulationAlgorithm alg) {
return alg.run(this);
}
+
+ /**
+ * Check if the traversal order of the vertices in the polygon is clockwise.
+ * @return true for clockwise order and false for counter-clockwise
+ */
+ public boolean isClockwise() {
+ return true; // TODO: implement
+ }
+
+ /** Check if the vertex number i is convex */
+ public boolean isConvexVertex(int i) {
+ return true; // TODO: implement
+ }
+
+ /** Check if the vertex number i is concave */
+ public boolean isConcaveVertex(int i) {
+ return !isConvexVertex(i);
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -27,18 +27,19 @@
* @since 1.0.0
*/
public class PolygonTest {
- Polygon p = new Polygon();
+ Polygon p;
@Before
public void setUp() throws Exception {
- p.addVertex(new Point(1, 4))
- .addVertex(new Point(4, 8))
- .addVertex(new Point(8, 8))
- .addVertex(new Point(8, 10))
- .addVertex(new Point(11, 6))
- .addVertex(new Point(7, 3))
- .addVertex(new Point(3, 6))
- .addVertex(new Point(3, 4));
+ p = new Polygon(
+ new Point(1, 4),
+ new Point(4, 8),
+ new Point(8, 8),
+ new Point(8, 10),
+ new Point(11, 6),
+ new Point(7, 3),
+ new Point(3, 6),
+ new Point(3, 4));
}
@Test
Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -32,7 +32,8 @@
/**
- * Straightforward algorithm for convex polygon triangulation
+ * Straightforward algorithm for convex polygon triangulation.
+ * Complexity is O(n) where n is the number of vertices of the polygon.
*/
static PolygonTriangulationAlgorithm CONVEX = new PolygonTriangulationAlgorithm() {
@Override
@@ -48,4 +49,23 @@
}
};
+ /**
+ * Ear clipping triangulation algorithm for simple polygons without holes.
+ * Has computational complexity of O(n*n) where n is the number
+ * of vertices of the polygon.
+ * The idea of the method is to use the assertion that any simple polygon
+ * without holes has at least two so called 'ears'. An ear is a triangle
+ * with two sides on the edge of the polygon and the other one completely
+ * inside it. The algorithm then consists of finding such an ear, removing
+ * it from the polygon (which results in a new polygon that still meets
+ * the conditions) and repeating until there is only one triangle left.
+ */
+ static PolygonTriangulationAlgorithm EAR_CLIPPING = new PolygonTriangulationAlgorithm() {
+ @Override
+ public Triangulation run(Polygon polygon) {
+ Triangulation triangulation = new Triangulation();
+ return triangulation;
+ }
+ };
+
}
Modified: trunk/src/net/sourceforge/geom4j/TriangulationTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -34,10 +34,7 @@
new Point(60, 70),
new Point(30, 10)
};
- Polygon polygon = new Polygon();
- for (Point point: points) {
- polygon.addVertex(point);
- }
+ Polygon polygon = new Polygon(points);
assertEquals(new PointSet(points),
polygon.triangulate().getVertices());
}
Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2010-01-16 08:24:36 UTC (rev 30)
+++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2010-01-16 11:32:17 UTC (rev 31)
@@ -57,16 +57,16 @@
*/
private static void intersectionDemo() {
// Create some polygon
- Figure polygon = new Polygon()
- .addVertex(new Point( 0, 0))
- .addVertex(new Point(10, 10))
- .addVertex(new Point(20, 0))
- .addVertex(new Point(30, 10))
- .addVertex(new Point(40, 0))
- .addVertex(new Point(50, 10))
- .addVertex(new Point(60, 0))
- .addVertex(new Point(70, 10))
- .addVertex(new Point(80, 0));
+ Figure polygon = new Polygon(
+ new Point( 0, 0),
+ new Point(10, 10),
+ new Point(20, 0),
+ new Point(30, 10),
+ new Point(40, 0),
+ new Point(50, 10),
+ new Point(60, 0),
+ new Point(70, 10),
+ new Point(80, 0));
// Create some line
Figure line = new Line(new Point(0, 5), new Point(80, 5));
// Iterate through the points of intersection
@@ -81,17 +81,17 @@
*/
private static void distanceDemo() {
// Create some polygon
- Figure square = new Polygon()
- .addVertex(new Point( 0, 0))
- .addVertex(new Point( 0, 20))
- .addVertex(new Point(20, 20))
- .addVertex(new Point(20, 0));
+ Figure square = new Polygon(
+ new Point( 0, 0),
+ new Point( 0, 20),
+ new Point(20, 20),
+ new Point(20, 0));
// Create another one
- Figure diamond = new Polygon()
- .addVertex(new Point(30, 10))
- .addVertex(new Point(35, 15))
- .addVertex(new Point(30, 20))
- .addVertex(new Point(25, 15));
+ Figure diamond = new Polygon(
+ new Point(30, 10),
+ new Point(35, 15),
+ new Point(30, 20),
+ new Point(25, 15));
// Get the distance between them
System.out.println("Distance: " + square.distanceTo(diamond));
}
@@ -100,12 +100,12 @@
* Demonstrate convex polygon check
*/
private static void convexPolygonDemo() {
- Polygon convex = new Polygon()
- .addVertex(new Point(0, 0))
- .addVertex(new Point(100, 0))
- .addVertex(new Point(100, 100))
- .addVertex(new Point(50, 100))
- .addVertex(new Point(0, 50));
+ Polygon convex = new Polygon(
+ new Point(0, 0),
+ new Point(100, 0),
+ new Point(100, 100),
+ new Point(50, 100),
+ new Point(0, 50));
System.out.println(String.format("Polygon %s is %sconvex", convex, convex.isConvex() ? "" : "not "));
}
@@ -113,11 +113,11 @@
* Demonstrate polygon area calculation
*/
private static void polygonAreaDemo() {
- Polygon romb = new Polygon()
- .addVertex(new Point(10, 10))
- .addVertex(new Point(50, 40))
- .addVertex(new Point(20, 80))
- .addVertex(new Point(-20, 50));
+ Polygon romb = new Polygon(
+ new Point(10, 10),
+ new Point(50, 40),
+ new Point(20, 80),
+ new Point(-20, 50));
System.out.println("Area: " + romb.getArea());
}
@@ -154,10 +154,10 @@
* Demonstrate point-in-polygon test
*/
private static void pointInsidePolygonDemo() {
- Polygon triangle = new Polygon()
- .addVertex(new Point(1, 1))
- .addVertex(new Point(6, 3))
- .addVertex(new Point(5, 4));
+ Polygon triangle = new Polygon(
+ new Point(1, 1),
+ new Point(6, 3),
+ new Point(5, 4));
if (new Point(5, 3).isInside(triangle)) {
System.out.println("Point (5, 3) is on the inside of the triangle.");
@@ -184,20 +184,20 @@
* Demonstrate polygon simplicity test
*/
private static void simplePolygonDemo() {
- Polygon p1 = new Polygon()
- .addVertex(new Point(0, 0))
- .addVertex(new Point(100, 0))
- .addVertex(new Point(100, 100))
- .addVertex(new Point(50, 100))
- .addVertex(new Point(0, 50));
+ Polygon p1 = new Polygon(
+ new Point(0, 0),
+ new Point(100, 0),
+ new Point(100, 100),
+ new Point(50, 100),
+ new Point(0, 50));
System.out.println(String.format("Polygon %s is %ssimple",
p1, p1.isSimple() ? "" : "not "));
- Polygon p2 = new Polygon()
- .addVertex(new Point(0, 0))
- .addVertex(new Point(100, 100))
- .addVertex(new Point(100, 0))
- .addVertex(new Point(50, 100))
- .addVertex(new Point(0, 50));
+ Polygon p2 = new Polygon(
+ new Point(0, 0),
+ new Point(100, 100),
+ new Point(100, 0),
+ new Point(50, 100),
+ new Point(0, 50));
System.out.println(String.format("Polygon %s is %ssimple",
p2, p2.isSimple() ? "" : "not "));
}
@@ -206,11 +206,11 @@
* Demonstrate how to determine if one figure contains another
*/
private static void contentDemo() {
- Figure square = new Polygon()
- .addVertex(new Point(0, 0))
- .addVertex(new Point(100, 0))
- .addVertex(new Point(100, 100))
- .addVertex(new Point(0, 100));
+ Figure square = new Polygon(
+ new Point(0, 0),
+ new Point(100, 0),
+ new Point(100, 100),
+ new Point(0, 100));
Figure segment = new Segment(new Point(100, 20), new Point(100, 40));
if (square.contains(segment)) {
System.out.println("Square " + square + " contains segment " + segment);
@@ -221,12 +221,12 @@
* Demonstrate polygon triangulation
*/
private static void triangulationDemo() {
- Polygon polygon = new Polygon()
- .addVertex(new Point(0, 0))
- .addVertex(new Point(100, 0))
- .addVertex(new Point(100, 100))
- .addVertex(new Point(50, 100))
- .addVertex(new Point(0, 50));
+ Polygon polygon = new Polygon(
+ new Point(0, 0),
+ new Point(100, 0),
+ new Point(100, 100),
+ new Point(50, 100),
+ new Point(0, 50));
Triangulation triangulation = polygon.triangulate();
System.out.println(String.format("Triangulation of the polygon %s is %s",
polygon, triangulation));
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
