[Geom4j-developer] SF.net SVN: geom4j:[32] trunk/src/net/sourceforge/geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[32] trunk/src/net/sourceforge/geom4j
|
From: <skh...@us...> - 2010-01-16 23:19:57
|
Revision: 32
http://geom4j.svn.sourceforge.net/geom4j/?rev=32&view=rev
Author: skhenkin
Date: 2010-01-16 23:19:49 +0000 (Sat, 16 Jan 2010)
Log Message:
-----------
Polygon class refactored to store vertices in counter-clockwise traversal order
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java
trunk/src/net/sourceforge/geom4j/Polygon.java
trunk/src/net/sourceforge/geom4j/PolygonTest.java
Added Paths:
-----------
trunk/src/net/sourceforge/geom4j/util/Utils.java
trunk/src/net/sourceforge/geom4j/util/UtilsTest.java
Modified: trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 11:32:17 UTC (rev 31)
+++ trunk/src/net/sourceforge/geom4j/ConvexHullAlgorithm.java 2010-01-16 23:19:49 UTC (rev 32)
@@ -21,6 +21,8 @@
import java.util.LinkedList;
import java.util.List;
+import net.sourceforge.geom4j.util.Utils;
+
/**
* An algorithm to construct convex hull (convex envelope) for a point set.
* The convex hull is represented as a polygon.
@@ -138,7 +140,7 @@
int m = 2; // a pointer to the top stack element
for (int i = 2; i < points.size(); i++) {
// test each point of the set
- while (nonLeftTurn(stack[m-1], stack[m], points.get(i))) {
+ while (Utils.isNonLeftTurn(stack[m-1], stack[m], points.get(i))) {
/* rollback if the turn is non-left,
i.e. it breaks the rule for a convex polygon */
m--;
@@ -151,14 +153,6 @@
hull.add(stack[i]);
}
return new Polygon(hull);
- }
-
- /** Test if p1-p2-p3 form a non-left turn, i.e. straight line or right turn */
- private boolean nonLeftTurn(Point p1, Point p2, Point p3) {
- Vector v1 = new Vector(p1, p2);
- Vector v2 = new Vector(p2, p3);
- return v1.crossProduct(v2) <= 0;
- }
-
+ }
};
}
Modified: trunk/src/net/sourceforge/geom4j/Polygon.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 11:32:17 UTC (rev 31)
+++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 23:19:49 UTC (rev 32)
@@ -17,9 +17,12 @@
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Collections;
import java.util.Iterator;
import java.util.List;
+import net.sourceforge.geom4j.util.Utils;
+
/**
* A polygon is a closed shape in a plane.
* This is immutable class.
@@ -40,6 +43,7 @@
for (Point vertex: vertices) {
this.vertices.add(vertex);
}
+ orderCounterClockwise();
}
public Polygon(Collection<Point> vertices) {
@@ -196,21 +200,13 @@
/** Check if the polygon is convex or not */
public boolean isConvex() {
- if (vertices.size() < 3) return true; // it's not really a polygon
- // convex polygon <=> all cross products of its sides are of the same sign
- Iterator<Point> i = vertices.iterator();
- Point p1 = vertices.get(getVertexCount()-1);
- Point p2 = i.next();
- Vector v1 = new Vector(vertices.get(getVertexCount()-2), p1);
- Vector v2 = new Vector(p1, p2);
- double sign0 = Math.signum(v1.crossProduct(v2));
- while (i.hasNext()) {
- p1 = p2;
- p2 = i.next();
- v1 = v2;
- v2 = new Vector(p1, p2);
- double sign = Math.signum(v1.crossProduct(v2));
- if (sign0*sign < 0) {
+ /* check if there's no right turns in counter-clockwise traversal
+ * of the polygon vertices
+ */
+ int n = vertices.size();
+ for (int i = 0; i < n; i++) {
+ if (!Utils.isNonRightTurn(getPreviousVertex(i),
+ getVertex(i), getNextVertex(i))) {
return false;
}
}
@@ -233,6 +229,14 @@
return vertices.get(i);
}
+ public Point getNextVertex(int i) {
+ return getVertex(i == vertices.size()-1 ? 0 : i+1);
+ }
+
+ public Point getPreviousVertex(int i) {
+ return getVertex(i == 0 ? vertices.size()-1 : i-1);
+ }
+
public Point getFirstVertex() {
return getVertex(0);
}
@@ -267,18 +271,39 @@
public Triangulation triangulate(PolygonTriangulationAlgorithm alg) {
return alg.run(this);
}
-
+
+ /** Order vertices so that the traversal order is counter clockwise */
+ private void orderCounterClockwise() {
+ if (isClockwise()) {
+ Collections.reverse(vertices);
+ }
+ }
+
/**
* 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
+ boolean isClockwise() {
+ int n = vertices.size();
+ // find rightmost vertex
+ int maxIdx = 0;
+ double maxX = Double.MIN_VALUE;
+ for (int i = 0; i < n; i++) {
+ if (vertices.get(i).getX() > maxX) {
+ maxIdx = i;
+ maxX = vertices.get(i).getX();
+ }
+ }
+ // check if the the turn at this point is wrong
+ return isConcaveVertex(maxIdx)
+ || getPreviousVertex(maxIdx).getX() == getVertex(maxIdx).getX()
+ && getVertex(maxIdx).getX() == getNextVertex(maxIdx).getX()
+ && getPreviousVertex(maxIdx).getY() < getNextVertex(maxIdx).getY();
}
/** Check if the vertex number i is convex */
public boolean isConvexVertex(int i) {
- return true; // TODO: implement
+ return Utils.isNonRightTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i));
}
/** Check if the vertex number i is concave */
Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 11:32:17 UTC (rev 31)
+++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 23:19:49 UTC (rev 32)
@@ -33,13 +33,13 @@
public void setUp() throws Exception {
p = new Polygon(
new Point(1, 4),
- new Point(4, 8),
+ new Point(3, 4),
+ new Point(3, 6),
+ new Point(7, 3),
+ new Point(11, 6),
+ new Point(8, 10),
new Point(8, 8),
- new Point(8, 10),
- new Point(11, 6),
- new Point(7, 3),
- new Point(3, 6),
- new Point(3, 4));
+ new Point(4, 8));
}
@Test
@@ -158,4 +158,72 @@
new Point(20, 20))
.isSimple());
}
+
+ @Test
+ public void testIsClockwise() {
+ assertFalse(new Polygon(
+ new Point(4, 4),
+ new Point(5, 3),
+ new Point(6, 4),
+ new Point(5, 5)).isClockwise());
+ assertFalse(new Polygon(
+ new Point(4, 4),
+ new Point(5, 5),
+ new Point(6, 4),
+ new Point(5, 3)).isClockwise());
+ assertFalse(new Polygon(
+ new Point(4, 4),
+ new Point(5, 3),
+ new Point(6, 3),
+ new Point(6, 4),
+ new Point(6, 5),
+ new Point(5, 5)).isClockwise());
+ }
+
+ @Test
+ public void testConvexAndConcaveVertex1() {
+ Polygon p = new Polygon(
+ new Point(4, 4), //0
+ new Point(5, 3), //1
+ new Point(6, 3), //2
+ new Point(6, 4), //3
+ new Point(6, 5), //4
+ new Point(5, 6), //5
+ new Point(6, 7), //6
+ new Point(5, 7), //7
+ new Point(4, 6)); //8
+ assertTrue(p.isConvexVertex(0));
+ assertTrue(p.isConvexVertex(1));
+ assertTrue(p.isConvexVertex(2));
+ assertTrue(p.isConvexVertex(3));
+ assertTrue(p.isConvexVertex(4));
+ assertTrue(p.isConcaveVertex(5));
+ assertTrue(p.isConvexVertex(6));
+ assertTrue(p.isConvexVertex(7));
+ assertTrue(p.isConvexVertex(8));
+
+ }
+
+ @Test
+ public void testConvexAndConcaveVertex2() {
+ assertTrue(p.isConvexVertex(0));
+ assertTrue(p.isConvexVertex(1));
+ assertTrue(p.isConcaveVertex(2));
+ assertTrue(p.isConvexVertex(3));
+ assertTrue(p.isConvexVertex(4));
+ assertTrue(p.isConvexVertex(5));
+ assertTrue(p.isConcaveVertex(6));
+ assertTrue(p.isConvexVertex(7));
+ }
+
+ @Test
+ public void testPreviousAndNextVertex() {
+ assertEquals(new Point(4, 8), p.getPreviousVertex(0));
+ assertEquals(new Point(3, 4), p.getNextVertex(0));
+ assertEquals(new Point(7, 3), p.getPreviousVertex(4));
+ assertEquals(new Point(8, 10), p.getNextVertex(4));
+ assertEquals(new Point(8, 8), p.getPreviousVertex(7));
+ assertEquals(new Point(1, 4), p.getNextVertex(7));
+ }
}
+
Added: trunk/src/net/sourceforge/geom4j/util/Utils.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/Utils.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/util/Utils.java 2010-01-16 23:19:49 UTC (rev 32)
@@ -0,0 +1,47 @@
+/*
+ * Copyright (c) 2009 Sergey Khenkin. All rights reserved.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package net.sourceforge.geom4j.util;
+
+import net.sourceforge.geom4j.Point;
+import net.sourceforge.geom4j.Vector;
+
+/**
+ * Miscellaneous utility functions.
+ *
+ * @author Sergey Khenkin
+ * @since 1.0.0
+ */
+public class Utils {
+ /**
+ * Test if p1-p2-p3 form a non-left turn, i.e. straight line or right turn
+ */
+ public static boolean isNonLeftTurn(Point p1, Point p2, Point p3) {
+ return pointProduct(p1, p2, p3) <= 0;
+ }
+
+ /**
+ * Test if p1-p2-p3 form a non-right turn, i.e. straight line or left turn
+ */
+ public static boolean isNonRightTurn(Point p1, Point p2, Point p3) {
+ return pointProduct(p1, p2, p3) >= 0;
+ }
+
+ private static double pointProduct(Point p1, Point p2, Point p3) {
+ Vector v1 = new Vector(p1, p2);
+ Vector v2 = new Vector(p2, p3);
+ return v1.crossProduct(v2);
+ }
+}
Added: trunk/src/net/sourceforge/geom4j/util/UtilsTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/UtilsTest.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/util/UtilsTest.java 2010-01-16 23:19:49 UTC (rev 32)
@@ -0,0 +1,44 @@
+/*
+ * Copyright (c) 2009 Sergey Khenkin. All rights reserved.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package net.sourceforge.geom4j.util;
+
+import net.sourceforge.geom4j.Point;
+
+import org.junit.Test;
+import static net.sourceforge.geom4j.util.Utils.*;
+import static org.junit.Assert.*;
+
+/**
+ * Tests for miscellaneous utility functions
+ *
+ * @author Sergey Khenkin
+ * @since 1.0.0
+ */
+public class UtilsTest {
+ @Test
+ public void testNonLeftTurn() {
+ assertTrue(isNonLeftTurn(new Point(5, 5), new Point(9, 8), new Point(11, 3)));
+ assertTrue(isNonLeftTurn(new Point(5, 5), new Point(9, 9), new Point(11, 11)));
+ assertFalse(isNonLeftTurn(new Point(5, 5), new Point(9, 9), new Point(8, 11)));
+ }
+
+ @Test
+ public void testNonRightTurn() {
+ assertFalse(isNonRightTurn(new Point(5, 5), new Point(9, 8), new Point(11, 3)));
+ assertTrue(isNonRightTurn(new Point(5, 5), new Point(9, 9), new Point(11, 11)));
+ assertTrue(isNonRightTurn(new Point(5, 5), new Point(9, 9), new Point(8, 11)));
+ }
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
