[Geom4j-developer] SF.net SVN: geom4j:[22] trunk/src/net/sourceforge/geom4j
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[22] trunk/src/net/sourceforge/geom4j
|
From: <skh...@us...> - 2009-12-18 18:17:04
|
Revision: 22
http://geom4j.svn.sourceforge.net/geom4j/?rev=22&view=rev
Author: skhenkin
Date: 2009-12-18 18:16:58 +0000 (Fri, 18 Dec 2009)
Log Message:
-----------
Triangle class added.
Triangulation algorithm infrastructure created.
Annoying bug in hashCode() for Segment and PointPair fixed.
Bug in Line.hashCode() to be fixed.
Varargs introduced in Polygon and PointSet constructors.
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/CompoundFigure.java
trunk/src/net/sourceforge/geom4j/DistanceTest.java
trunk/src/net/sourceforge/geom4j/Line.java
trunk/src/net/sourceforge/geom4j/PointPair.java
trunk/src/net/sourceforge/geom4j/PointSet.java
trunk/src/net/sourceforge/geom4j/Polygon.java
trunk/src/net/sourceforge/geom4j/Segment.java
trunk/src/net/sourceforge/geom4j/SegmentSet.java
trunk/src/net/sourceforge/geom4j/demo/Demo.java
Added Paths:
-----------
trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java
trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
trunk/src/net/sourceforge/geom4j/Triangle.java
trunk/src/net/sourceforge/geom4j/TriangleTest.java
trunk/src/net/sourceforge/geom4j/Triangulation.java
trunk/src/net/sourceforge/geom4j/TriangulationTest.java
Modified: trunk/src/net/sourceforge/geom4j/CompoundFigure.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/CompoundFigure.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -44,6 +44,10 @@
}
return this;
}
+
+ public boolean remove(F f) {
+ return figures.remove(f);
+ }
public CompoundFigure<F> add(CompoundFigure<F> f) {
// TODO: think of avoiding duplicate sets of points
@@ -51,6 +55,11 @@
return this;
}
+ public CompoundFigure<F> addAll(Collection<F> figures) {
+ this.figures.addAll(figures);
+ return this;
+ }
+
public int size() {
return figures.size();
}
Modified: trunk/src/net/sourceforge/geom4j/DistanceTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/DistanceTest.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -86,6 +86,7 @@
@Test
public void testPolygonDistance() {
+ // TODO: refactor this and other tests using varargs
Figure p = new Point(10, 20);
Figure square = new Polygon()
.addVertex(new Point(0, 0))
Modified: trunk/src/net/sourceforge/geom4j/Line.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/Line.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -42,6 +42,7 @@
public int hashCode() {
final int prime = 31;
int result = 1;
+ // TODO: !!! this is completely wrong
result = prime * result + p1.hashCode();
result = prime * result + p2.hashCode();
return result;
Modified: trunk/src/net/sourceforge/geom4j/PointPair.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/PointPair.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -39,11 +39,7 @@
@Override
public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + firstPoint.hashCode();
- result = prime * result + secondPoint.hashCode();
- return result;
+ return firstPoint.hashCode() + secondPoint.hashCode();
}
@Override
Modified: trunk/src/net/sourceforge/geom4j/PointSet.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/PointSet.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -15,6 +15,7 @@
package net.sourceforge.geom4j;
+import java.util.Arrays;
import java.util.Collection;
public class PointSet extends CompoundFigure<Point> {
@@ -28,6 +29,10 @@
super(points);
}
+ public PointSet(Point... points) {
+ this(Arrays.asList(points));
+ }
+
/**
* CompoundFigure's equality is overridden for better performance.
*/
@@ -47,8 +52,6 @@
return (PointSet) super.add(f);
}
-
-
/**
* Get a convex hull (convex envelope) for a point set using some algorithm.
* Different algorithms can be used for convex hull construction.
Modified: trunk/src/net/sourceforge/geom4j/Polygon.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/Polygon.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -27,11 +27,19 @@
public class Polygon extends BasicFigure {
// TODO: think of making this class also immutable
- private List<Point> vertices = new ArrayList<Point>();
+ protected List<Point> vertices;
public Polygon() {
+ this.vertices = new ArrayList<Point>();
}
+ public Polygon(Point... vertices) {
+ this.vertices = new ArrayList<Point>(vertices.length);
+ for (Point vertex: vertices) {
+ this.vertices.add(vertex);
+ }
+ }
+
public Polygon addVertex(Point p) {
vertices.add(p);
return this;
@@ -58,6 +66,12 @@
return perimeter;
}
+ /**
+ * Hash code of a polygon is defined as the hash code
+ * of the segment set of which it consists.
+ * This implies equal hash codes for equal polygons.
+ * Hash code based on vertices only is not enough!
+ */
@Override
public int hashCode() {
return getSegmentSet().hashCode();
@@ -238,4 +252,18 @@
intersections.remove(getVertices()); // we don't count vertices
return intersections.isEmpty();
}
+
+ /**
+ * Create polygon triangulation
+ */
+ public Triangulation triangulate() {
+ return triangulate(PolygonTriangulationAlgorithm.NAIVE);
+ }
+
+ /**
+ * Create polygon triangulation using the specified algorithm
+ */
+ public Triangulation triangulate(PolygonTriangulationAlgorithm alg) {
+ return alg.run(this);
+ }
}
Added: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithm.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -0,0 +1,50 @@
+/*
+ * 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;
+
+/**
+ * A polygon triangulation algorithm.
+ *
+ * @author Sergey Khenkin
+ */
+
+public interface PolygonTriangulationAlgorithm {
+
+ /**
+ * Execute the algorithm and find the triangulation,
+ * i.e. a set of triangles
+ */
+ Triangulation run(Polygon polygon);
+
+
+ /**
+ * Naive algorithm
+ */
+ static PolygonTriangulationAlgorithm NAIVE = new PolygonTriangulationAlgorithm() {
+ @Override
+ public Triangulation run(Polygon polygon) {
+ Triangulation triangulation = new Triangulation();
+ int n = polygon.getVertexCount();
+ for (int i = 1; i < n-1; i++) {
+ triangulation.add(new Triangle(polygon.getVertex(0),
+ polygon.getVertex(i),
+ polygon.getVertex(i+1)));
+ }
+ return triangulation;
+ }
+ };
+
+}
Added: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -0,0 +1,32 @@
+/*
+ * 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;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+
+public class PolygonTriangulationAlgorithmTest {
+
+ @Test
+ public void testNaive() {
+ Polygon polygon = new Polygon(new Point(0, 0), new Point(100, 0),
+ new Point(100, 100), new Point(0, 100));
+ Triangulation triangulation = polygon.triangulate();
+ assertTrue(triangulation.fits(polygon));
+ }
+
+}
Modified: trunk/src/net/sourceforge/geom4j/Segment.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/Segment.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -55,8 +55,8 @@
public int hashCode() {
final int prime = 31;
int result = 1;
- result = prime * result + endPoint.hashCode();
- result = prime * result + startPoint.hashCode();
+ result = prime * result + getLeftPoint().hashCode();
+ result = prime * result + getRightPoint().hashCode();
return result;
}
Modified: trunk/src/net/sourceforge/geom4j/SegmentSet.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/SegmentSet.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -15,6 +15,11 @@
package net.sourceforge.geom4j;
+/**
+ * A set of segments
+ *
+ * @author Sergey Khenkin
+ */
public class SegmentSet extends CompoundFigure<Segment> {
@Override
Added: trunk/src/net/sourceforge/geom4j/Triangle.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Triangle.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/Triangle.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -0,0 +1,32 @@
+/*
+ * 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;
+
+/**
+ * Triangle figure.
+ * Implemented as a specialized variation of a polygon.
+ *
+ * @author Sergey Khenkin
+ */
+public class Triangle extends Polygon {
+ public Triangle(Point a, Point b, Point c) {
+ vertices.add(a);
+ vertices.add(b);
+ vertices.add(c);
+ }
+
+
+}
Added: trunk/src/net/sourceforge/geom4j/TriangleTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/TriangleTest.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/TriangleTest.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -0,0 +1,32 @@
+/*
+ * 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;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+
+public class TriangleTest {
+ @Test
+ public void testTriangleConstruction() {
+ Point p1 = new Point(50, 30);
+ Point p2 = new Point(-17, 45);
+ Point p3 = new Point(93, -41);
+ Polygon p = new Polygon(p1, p2, p3);
+ Triangle t = new Triangle(p1, p2, p3);
+ assertEquals(p, t);
+ }
+}
Added: trunk/src/net/sourceforge/geom4j/Triangulation.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Triangulation.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/Triangulation.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -0,0 +1,81 @@
+/*
+ * 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;
+
+/**
+ * A polygon triangulation, actually a set of triangles.
+ *
+ * @author Sergey Khenkin
+ */
+public class Triangulation extends CompoundFigure<Triangle> {
+ /**
+ * Test if this triangulation fits the polygon specified,
+ * i.e. if this is a valid triangulation for this polygon
+ */
+ public boolean fits(Polygon polygon) {
+ /*
+ * We use a sequence of tests to check validity:
+ * 1. Number of triangles is less than number of polygon vertices by 2.
+ * 2. The vertices of triangulation and polygon match.
+ * 3. Every segment in triangulation comes at most twice.
+ * 4. Segments that come once form the polygon.
+ * 5. Other segments don't intersect in points other than polygon vertices.
+ */
+ // 1
+ if (size() != polygon.getVertexCount() - 2) {
+ return false;
+ }
+ // 2
+ if (!getVertices().equals(new PointSet(polygon.getVertices()))) {
+ return false;
+ }
+ SegmentSet singles = new SegmentSet();
+ SegmentSet doubles = new SegmentSet();
+ for (Triangle triangle: figures) {
+ for (Segment segment: triangle.getSegmentSet()) {
+ // 3
+ if (doubles.contains(segment)) {
+ return false; // a segment comes for the third time
+ }
+ if (singles.contains(segment)) {
+ singles.remove(segment);
+ doubles.add(segment);
+ } else {
+ singles.add(segment);
+ }
+ }
+ }
+ // 4
+ if (!singles.equals(polygon.getSegmentSet())) {
+ return false;
+ }
+ // 5
+ if (!getPoints().contains(doubles.getAllIntersectionPoints())) {
+ return false;
+ }
+ return true;
+ }
+
+ public PointSet getVertices() {
+ PointSet vertices = new PointSet();
+ for (Triangle triangle: figures) {
+ vertices.addAll(triangle.getVertices());
+ }
+ return vertices;
+ }
+
+
+}
Added: trunk/src/net/sourceforge/geom4j/TriangulationTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/TriangulationTest.java (rev 0)
+++ trunk/src/net/sourceforge/geom4j/TriangulationTest.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -0,0 +1,52 @@
+/*
+ * 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;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+
+public class TriangulationTest {
+ @Test
+ public void testTriangulationVertices() {
+ Point[] points = new Point[] {
+ new Point(10, 0),
+ new Point(0, 40),
+ new Point(60, 70),
+ new Point(30, 10)
+ };
+ Polygon polygon = new Polygon();
+ for (Point point: points) {
+ polygon.addVertex(point);
+ }
+ assertEquals(new PointSet(points),
+ polygon.triangulate().getVertices());
+ }
+
+ @Test
+ public void testFitting() {
+ Polygon polygon = new Polygon(new Point[] {
+ new Point(10, 0),
+ new Point(0, 40),
+ new Point(60, 70),
+ new Point(30, 10)
+ });
+ Triangulation triangulation = new Triangulation();
+ triangulation.add(new Triangle(new Point(0, 40), new Point(30, 10), new Point(10, 0)))
+ .add(new Triangle(new Point(30, 10), new Point(0, 40), new Point(60, 70)));
+ assertTrue(triangulation.fits(polygon));
+ }
+}
Modified: trunk/src/net/sourceforge/geom4j/demo/Demo.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-18 15:30:14 UTC (rev 21)
+++ trunk/src/net/sourceforge/geom4j/demo/Demo.java 2009-12-18 18:16:58 UTC (rev 22)
@@ -26,6 +26,7 @@
import net.sourceforge.geom4j.Segment;
import net.sourceforge.geom4j.SegmentIntersectionAlgorithm;
import net.sourceforge.geom4j.SegmentSet;
+import net.sourceforge.geom4j.Triangulation;
/**
* Demo class for the library.
@@ -47,6 +48,7 @@
segmentIntersectionDemo();
simplePolygonDemo();
contentDemo();
+ triangulationDemo();
}
/**
@@ -213,4 +215,20 @@
System.out.println("Square " + square + " contains segment " + segment);
}
}
+
+ /**
+ * 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));
+ 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.
|
