[Geom4j-developer] SF.net SVN: geom4j:[33] trunk/src/net/sourceforge/geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[33] trunk/src/net/sourceforge/geom4j
|
From: <skh...@us...> - 2010-01-17 08:59:09
|
Revision: 33
http://geom4j.svn.sourceforge.net/geom4j/?rev=33&view=rev
Author: skhenkin
Date: 2010-01-17 08:59:01 +0000 (Sun, 17 Jan 2010)
Log Message:
-----------
Bug in Point.isInside() fixed. An initial version of ear clipping polygon triangulation algorithm implemented.
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/Point.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/PolygonTriangulationAlgorithmTest.java
Modified: trunk/src/net/sourceforge/geom4j/Point.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Point.java 2010-01-16 23:19:49 UTC (rev 32)
+++ trunk/src/net/sourceforge/geom4j/Point.java 2010-01-17 08:59:01 UTC (rev 33)
@@ -183,6 +183,10 @@
* and http://erich.realtimerendering.com/ptinpoly/
*/
public boolean isInside(Polygon p) {
+ if (p.contains(this)) {
+ // the point lies on border of the polygon
+ return true;
+ }
// Construct a "ray" to test crossings with. This is actually a long enough segment
double maxX = getX() + 1;
for (Point pt: p.getVertices()) {
Modified: trunk/src/net/sourceforge/geom4j/PointTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-16 23:19:49 UTC (rev 32)
+++ trunk/src/net/sourceforge/geom4j/PointTest.java 2010-01-17 08:59:01 UTC (rev 33)
@@ -88,4 +88,15 @@
assertTrue(new Point(3, 1).isInside(p));
assertFalse(new Point(1, 0).isInside(p));
}
+
+
+ @Test
+ public void testPointInPolygonSpecialCase1() {
+ Polygon poly = new Polygon(
+ new Point(2, 0),
+ new Point(8, 3),
+ new Point(7, 5));
+ Point pt = new Point(4, 2);
+ assertTrue(pt.isInside(poly));
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/Polygon.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-16 23:19:49 UTC (rev 32)
+++ trunk/src/net/sourceforge/geom4j/Polygon.java 2010-01-17 08:59:01 UTC (rev 33)
@@ -19,6 +19,7 @@
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
+import java.util.LinkedList;
import java.util.List;
import net.sourceforge.geom4j.util.Utils;
@@ -225,23 +226,31 @@
return Math.abs(s);
}
- public Point getVertex(int i) {
+ public final Point getVertex(int i) {
return vertices.get(i);
}
- public Point getNextVertex(int i) {
- return getVertex(i == vertices.size()-1 ? 0 : i+1);
+ public final int getNextVertexIndex(int i) {
+ return i == vertices.size()-1 ? 0 : i+1;
}
- public Point getPreviousVertex(int i) {
- return getVertex(i == 0 ? vertices.size()-1 : i-1);
+ public final Point getNextVertex(int i) {
+ return getVertex(getNextVertexIndex(i));
}
- public Point getFirstVertex() {
+ public final int getPreviousVertexIndex(int i) {
+ return i == 0 ? vertices.size()-1 : i-1;
+ }
+
+ public final Point getPreviousVertex(int i) {
+ return getVertex(getPreviousVertexIndex(i));
+ }
+
+ public final Point getFirstVertex() {
return getVertex(0);
}
- public Point getLastVertex() {
+ public final Point getLastVertex() {
return getVertex(getVertexCount()-1);
}
@@ -303,11 +312,27 @@
/** Check if the vertex number i is convex */
public boolean isConvexVertex(int i) {
- return Utils.isNonRightTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i));
+ return !Utils.isNonLeftTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i));
}
/** Check if the vertex number i is concave */
public boolean isConcaveVertex(int i) {
- return !isConvexVertex(i);
+ return !Utils.isNonRightTurn(getPreviousVertex(i), getVertex(i), getNextVertex(i));
}
+
+ /**
+ * Create a polygon which is the same as given but without a vertex
+ * with the specified index.
+ */
+ public Polygon withoutVertex(int vertexIndex) {
+ int n = this.vertices.size();
+ Point[] vertices = new Point[n-1];
+ for (int i = 0; i < vertexIndex; i++) {
+ vertices[i] = this.vertices.get(i);
+ }
+ for (int i = vertexIndex + 1; i < n; i++) {
+ vertices[i-1] = this.vertices.get(i);
+ }
+ return new Polygon(vertices);
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/PolygonTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-16 23:19:49 UTC (rev 32)
+++ trunk/src/net/sourceforge/geom4j/PolygonTest.java 2010-01-17 08:59:01 UTC (rev 33)
@@ -195,7 +195,8 @@
assertTrue(p.isConvexVertex(0));
assertTrue(p.isConvexVertex(1));
assertTrue(p.isConvexVertex(2));
- assertTrue(p.isConvexVertex(3));
+ assertFalse(p.isConvexVertex(3));
+ assertFalse(p.isConcaveVertex(3));
assertTrue(p.isConvexVertex(4));
assertTrue(p.isConcaveVertex(5));
assertTrue(p.isConvexVertex(6));
@@ -225,5 +226,21 @@
assertEquals(new Point(8, 8), p.getPreviousVertex(7));
assertEquals(new Point(1, 4), p.getNextVertex(7));
}
+
+ @Test
+ public void testWithoutVertex() {
+ Polygon p1 = new Polygon(
+ new Point(0, 0),
+ new Point(100, 0),
+ new Point(100, 100),
+ new Point(50, 100),
+ new Point(0, 50));
+ Polygon p2 = new Polygon(
+ new Point(0, 0),
+ new Point(100, 0),
+ new Point(50, 100),
+ new Point(0, 50));
+ assertEquals(p2, p1.withoutVertex(2));
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-16 23:19:49 UTC (rev 32)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2010-01-17 08:59:01 UTC (rev 33)
@@ -64,8 +64,47 @@
@Override
public Triangulation run(Polygon polygon) {
Triangulation triangulation = new Triangulation();
+ while (polygon.getVertexCount() >= 3) {
+ int earIndex = findEarVertexIndex(polygon);
+ triangulation.add(new Triangle(
+ polygon.getPreviousVertex(earIndex),
+ polygon.getVertex(earIndex),
+ polygon.getNextVertex(earIndex)));
+ polygon = polygon.withoutVertex(earIndex);
+ }
return triangulation;
}
+
+ /**
+ * Find the index of an ear vertex in polygon
+ */
+ private int findEarVertexIndex(Polygon polygon) {
+ int n = polygon.getVertexCount();
+ for (int i = 0; i < n; i++) {
+ if (polygon.isConvexVertex(i)) {
+ // check if a concave vertex is inside the triangle
+ boolean concaveVertexInside = false;
+ for (int j = 0; j < n ; j++) {
+ if (j == i || j == polygon.getPreviousVertexIndex(i)
+ || j == polygon.getNextVertexIndex(i)) {
+ continue; // skip vertices that form current triangle
+ }
+ if (!polygon.isConvexVertex(j)){
+ if (polygon.getVertex(j).isInside(new Triangle(polygon.getPreviousVertex(i),
+ polygon.getVertex(i),
+ polygon.getNextVertex(i)))) {
+ concaveVertexInside = true;
+ break;
+ }
+ }
+ }
+ if (!concaveVertexInside) {
+ return i;
+ }
+ }
+ }
+ throw new IllegalArgumentException("No ear can be found in polygon " + polygon);
+ }
};
}
Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-16 23:19:49 UTC (rev 32)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-17 08:59:01 UTC (rev 33)
@@ -36,7 +36,7 @@
}
@Test
- public void testX() {
+ public void testConvexFailure() {
Polygon polygon = new Polygon(
new Point(1, 1),
new Point(3, 2),
@@ -50,4 +50,29 @@
assertFalse(triangulation.fits(polygon));
}
+ @Test
+ public void testEarClipping() {
+ Polygon polygon = new Polygon(
+ new Point(1, 1),
+ new Point(3, 2),
+ new Point(2, 0),
+ new Point(8, 3),
+ new Point(7, 5),
+ new Point(4, 2),
+ new Point(3, 3),
+ new Point(3, 4));
+ Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.EAR_CLIPPING);
+ assertTrue(triangulation.fits(polygon));
+ }
+
+ @Test
+ public void testEarClippingPrimitive() {
+ Polygon polygon = new Polygon(
+ new Point(1, 1),
+ new Point(2, 0),
+ new Point(3, 2));
+ Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.EAR_CLIPPING);
+ assertTrue(triangulation.fits(polygon));
+ }
+
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
