[Geom4j-developer] SF.net SVN: geom4j:[25] trunk
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[25] trunk
|
From: <skh...@us...> - 2010-01-09 21:20:29
|
Revision: 25
http://geom4j.svn.sourceforge.net/geom4j/?rev=25&view=rev
Author: skhenkin
Date: 2010-01-09 21:20:22 +0000 (Sat, 09 Jan 2010)
Log Message:
-----------
Bentley-Ottmman algorithm enhanced to work with points of intersection of more than 2 segments. Minor changes.
Modified Paths:
--------------
trunk/build.xml
trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java
trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java
trunk/src/net/sourceforge/geom4j/Triangulation.java
trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java
trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java
trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java
trunk/src/net/sourceforge/geom4j/util/SmartQueue.java
Modified: trunk/build.xml
===================================================================
--- trunk/build.xml 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/build.xml 2010-01-09 21:20:22 UTC (rev 25)
@@ -19,6 +19,7 @@
<property name="app.bin.tgz" value="${build.dir}/${ant.project.name}-${app.version}-bin.tar.gz"/>
<property name="app.src.zip" value="${build.dir}/${ant.project.name}-${app.version}-src.zip"/>
<property name="app.src.tgz" value="${build.dir}/${ant.project.name}-${app.version}-src.tar.gz"/>
+ <property name="javadoc.dir" value="${build.dir}/javadoc"/>
<path id="junit.classpath">
<fileset dir="${junit.dir}" includes="**/*.jar"/>
@@ -108,7 +109,7 @@
</target>
<target name="all" depends="package-application, package-binaries,
- package-sources, package-tests, unit-test, run-demo" />
+ package-sources, package-tests, unit-test, run-demo, javadoc" />
<target name="compile-debug">
<mkdir dir="${debug.classes.dir}"/>
@@ -159,4 +160,20 @@
</target>
<target name="coverage" depends="coverage-report" />
+
+ <target name="javadoc">
+ <javadoc
+ destdir="${javadoc.dir}"
+ author="true"
+ version="true"
+ use="true"
+ windowtitle="Geom4J ${app.version}"
+ classpathref="junit.classpath">
+
+ <fileset dir="${src.dir}" defaultexcludes="yes" />
+
+ <doctitle><![CDATA[<h1>Geom4J - A Pure Java Computational Geometry Library</h1>]]></doctitle>
+ <bottom><![CDATA[<i>Copyright © 2009 Sergey Khenkin. All Rights Reserved.</i>]]></bottom>
+ </javadoc>
+ </target>
</project>
Modified: trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/PolygonTriangulationAlgorithmTest.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -28,11 +28,26 @@
public class PolygonTriangulationAlgorithmTest {
@Test
- public void testNaive() {
+ public void testConvex() {
Polygon polygon = new Polygon(new Point(0, 0), new Point(100, 0),
new Point(100, 100), new Point(0, 100));
- Triangulation triangulation = polygon.triangulate();
+ Triangulation triangulation = polygon.triangulate(PolygonTriangulationAlgorithm.CONVEX);
assertTrue(triangulation.fits(polygon));
}
+ @Test
+ public void testX() {
+ 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.CONVEX);
+ assertTrue(triangulation.fits(polygon));
+ }
+
}
Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithm.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -15,7 +15,11 @@
package net.sourceforge.geom4j;
+import java.util.Collection;
+import java.util.Collections;
import java.util.Comparator;
+import java.util.HashSet;
+import java.util.Set;
import net.sourceforge.geom4j.util.BinaryTreeBasedSmartQueue;
import net.sourceforge.geom4j.util.SmartQueue;
@@ -77,10 +81,9 @@
public PointSet run(SegmentSet segments) {
// initialization
SmartQueue<Event> eventQueue = initializeEventQueue(segments);
- //SmartQueue<SweepLineSegment> sweepLine
- // = new ListBasedSmartQueue<Segment>(sweepLineComparator);
- SmartQueue<Segment> sweepLine =
- new BinaryTreeBasedSmartQueue<Segment>(sweepLineComparator);
+ SmartQueue<Segment> sweepLine
+ //= new ListBasedSmartQueue<Segment>(sweepLineComparator);
+ = new BinaryTreeBasedSmartQueue<Segment>(sweepLineComparator);
PointSet intersections = new PointSet();
// process all events in the queue
while (!eventQueue.isEmpty()) {
@@ -147,7 +150,16 @@
if (seg1 != null && seg2 != null) {
for (Point p : seg1.intersects(seg2).getPoints()) {
if (p.getX() >= curPoint.getX()) {
- eventQueue.insert(new IntersectionEvent(p, seg1, seg2, sweepLineComparator));
+ IntersectionEvent templateEvent = new IntersectionEvent(p, seg1, seg2, sweepLineComparator);
+ Event existingEvent = eventQueue.find(templateEvent);
+ if (existingEvent != null && existingEvent instanceof IntersectionEvent) {
+ // found a point where more than 2 segments intersect
+ ((IntersectionEvent) existingEvent).addSegment(seg1);
+ ((IntersectionEvent) existingEvent).addSegment(seg2);
+ } else {
+ // it's just a point of intersection of 2 segments
+ eventQueue.insert(templateEvent);
+ }
}
}
}
@@ -267,16 +279,23 @@
*/
class IntersectionEvent extends Event {
private Point p;
- private Segment sAbove;
- private Segment sBelow;
+ private Set<Segment> segments;
public IntersectionEvent(Point p, Segment sAbove, Segment sBelow,
SweepLineComparator sweepLineComparator) {
super(sweepLineComparator);
this.p = p;
- this.sAbove = sAbove;
- this.sBelow = sBelow;
+ this.segments = new HashSet<Segment>();
+ this.segments.add(sBelow);
+ this.segments.add(sAbove);
}
+
+ public IntersectionEvent(Point p, Collection<Segment> segments,
+ SweepLineComparator sweepLineComparator) {
+ super(sweepLineComparator);
+ this.p = p;
+ this.segments = new HashSet<Segment>(segments);
+ }
/**
* On reaching intersection point of two segments on the sweep line add
@@ -289,12 +308,24 @@
SmartQueue<Segment> sweepLine, PointSet intersectionSet) {
intersectionSet.add(p);
sweepLineComparator.setBefore(true);
- sweepLine.swap(sAbove, sBelow);
+ Segment sAbove = getLastSegment();
+ Segment sBelow = getFirstSegment();
+ sweepLine.revert(sBelow, sAbove);
sweepLineComparator.setBefore(false);
addIntersectionEvent(eventQueue, sAbove, sweepLine.previous(sAbove), p);
addIntersectionEvent(eventQueue, sweepLine.next(sBelow), sBelow, p);
}
+ private Segment getLastSegment() {
+ //return segments.get(segments.size()-1);
+ return Collections.max(segments, sweepLineComparator);
+ }
+
+ private Segment getFirstSegment() {
+ //return segments.get(0);
+ return Collections.min(segments, sweepLineComparator);
+ }
+
@Override
public Point getPoint() {
return p;
@@ -306,19 +337,36 @@
}
public String toString() {
- return "<" + getType() + ", " + getPoint() + ", " + sAbove + ", "
- + sBelow + ">";
+ return "<" + getType() + ", " + getPoint() + ", [" + segments + "]>";
}
@Override
public boolean equals(Object obj) {
if (obj instanceof IntersectionEvent) {
IntersectionEvent ie = (IntersectionEvent) obj;
- return p.equals(ie.p) && sAbove.equals(ie.sAbove)
- && sBelow.equals(ie.sBelow);
+ return p.equals(ie.p) /* sAbove.equals(ie.sAbove)
+ && sBelow.equals(ie.sBelow) */;
}
return false;
}
+
+ private void addSegment(Segment s) {
+/* Iterator<Segment> i = segments.iterator();
+ int j = 0;
+ while (i.hasNext()) {
+ Segment intersectingSegment = i.next();
+ if (sweepLineComparator.compare(intersectingSegment, s) < 0) {
+ //if (sweepLineComparator.compare(intersectingSegment, s) < 0) {
+ break;
+ }
+ if (intersectingSegment.equals(s)) {
+ return;
+ }
+ j++;
+ }
+ segments.add(j, s);*/
+ segments.add(s);
+ }
}
/** Comparator for events in the event queue */
Modified: trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/SegmentIntersectionAlgorithmTest.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -170,4 +170,42 @@
//System.out.println(naiveSet.size());
assertEquals(naiveSet, boSet);
}
+
+ @Test
+ public void testBentleyOttmanSpecialCase3SegmentsIntersection() {
+ double[][] coords = new double[][] {
+ //{5, 2, 1, 1},
+ {3, 3, 1, 1},
+ {2, 0, 1, 1},
+ {1, 1, 8, 3},
+ //{1, 1, 7, 5}
+ };
+ SegmentSet ss = new SegmentSet();
+ for (int i = 0; i < coords.length; i++) {
+ ss.add(new Segment(new Point(coords[i][0], coords[i][1]),
+ new Point(coords[i][2], coords[i][3])));
+ }
+ PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE);
+ PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN);
+ assertEquals(naiveSet, boSet);
+ }
+
+ @Test
+ public void testBentleyOttmanSpecialCase4SegmentsIntersection() {
+ double[][] coords = new double[][] {
+ {5, 2, 1, 1},
+ {3, 3, 1, 1},
+ {2, 0, 1, 1},
+ {1, 1, 8, 3},
+ //{1, 1, 7, 5}
+ };
+ SegmentSet ss = new SegmentSet();
+ for (int i = 0; i < coords.length; i++) {
+ ss.add(new Segment(new Point(coords[i][0], coords[i][1]),
+ new Point(coords[i][2], coords[i][3])));
+ }
+ PointSet naiveSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.NAIVE);
+ PointSet boSet = ss.getAllIntersectionPoints(SegmentIntersectionAlgorithm.BENTLEY_OTTMANN);
+ assertEquals(naiveSet, boSet);
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/Triangulation.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/Triangulation.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/Triangulation.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -16,7 +16,7 @@
package net.sourceforge.geom4j;
/**
- * A polygon triangulation, actually a set of triangles.
+ * Polygon triangulation, actually a set of triangles.
*
* @author Sergey Khenkin
* @since 1.0.0
@@ -64,9 +64,10 @@
return false;
}
// 5
- if (!getPoints().contains(doubles.getAllIntersectionPoints())) {
+ if (!new PointSet(polygon.getVertices()).contains(doubles.getAllIntersectionPoints())) {
return false;
}
+ // everything is fine
return true;
}
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -84,7 +84,11 @@
public void setParent(Node parent) {
this.parent = parent;
}
-
+
+ @Override
+ public String toString() {
+ return value.toString();
+ }
}
/** Root of the tree */
@@ -249,7 +253,7 @@
}
@SuppressWarnings("unchecked")
- private int compare(E e1, E e2) {
+ protected int compare(E e1, E e2) {
if (comparator == null)
return ((Comparable<? super E>) e1).compareTo(e2);
else
Modified: trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/util/BinaryTreeBasedSmartQueue.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -16,6 +16,8 @@
package net.sourceforge.geom4j.util;
import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
/**
* "Smarter" implementation of SmartQueue based on a self-balancing
@@ -56,6 +58,31 @@
n2.value = e1;
}
}
+
+ @Override
+ public void revert(E e1, E e2) {
+ List<Node> nodes = new LinkedList<Node>();
+ Node n = findNode(e1);
+ nodes.add(n);
+ do {
+ n = nextNode(n);
+ nodes.add(n);
+ } while (!n.value.equals(e2));
+ int s = nodes.size();
+ for (int i = 0; i < s/2; i++) {
+ Node n1 = nodes.get(i);
+ Node n2 = nodes.get(s-i-1);
+ E t = n1.value;
+ n1.value = n2.value;
+ n2.value = t;
+ }
+ }
+
+ @Override
+ public E find(E e) {
+ Node n = findNode(e);
+ return n == null ? null : n.value;
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueue.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -125,6 +125,36 @@
return comparator.compare(e1, e2);
}
}
+
+ @Override
+ public void revert(E e1, E e2) {
+ // TODO change: to real implementation
+ int i1 = list.indexOf(e1);
+ int i2 = list.indexOf(e2);
+ if (i1 != -1 && i2 != -1 && i1 != i2) {
+ for (int i = 0; i < (i2-i1-1)/2+1; i++) {
+ swap(list.get(i1+i), list.get(i2-i));
+ }
+ }
+ }
+
+ @Override
+ public E find(E e) {
+ int i = 0;
+ while (i < list.size()) {
+ if (compare(list.get(i), e) > 0) {
+ break;
+ } else if (compare(list.get(i), e) == 0) {
+ if (list.get(i).equals(e)) {
+ return list.get(i);
+ } else {
+ break;
+ }
+ }
+ i++;
+ }
+ return null;
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/util/ListBasedSmartQueueTest.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -16,6 +16,7 @@
package net.sourceforge.geom4j.util;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;
@@ -54,4 +55,20 @@
assertTrue(q.isEmpty());
}
+ @Test
+ public void testRevert() {
+ SmartQueue<String> q = createQueue();
+ q.revert("New York", "Toronto");
+ assertFalse(q.isEmpty());
+ assertEquals("Brussels", q.poll());
+ assertEquals("London", q.poll());
+ assertEquals("Toronto", q.poll());
+ assertEquals("Tel Aviv", q.poll());
+ assertEquals("Sydney", q.poll());
+ assertEquals("San Francisco", q.poll());
+ assertEquals("Paris", q.poll());
+ assertEquals("New York", q.poll());
+ assertEquals("Zurich", q.poll());
+ assertTrue(q.isEmpty());
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/util/SmartQueue.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2009-12-25 22:05:23 UTC (rev 24)
+++ trunk/src/net/sourceforge/geom4j/util/SmartQueue.java 2010-01-09 21:20:22 UTC (rev 25)
@@ -20,11 +20,13 @@
* <ul>
* <li>only unique elements are stored;</li>
* <li>elements are kept sorted according to some order;</li>
- * <li>elements can be inserted and removed efficiently;</li>
+ * <li>elements can be searched, inserted and removed efficiently;</li>
* <li>first element (smallest) can be extracted from the queue;</li>
* <li>for any element immediately previous and immediately next
* elements can be obtained;</li>
- * <li>any pair of elements can be swapped.</li>
+ * <li>any pair of elements can be swapped;</li>
+ * <li>an order of a set of elements between the given pair of elements
+ * can be inverted.</li>
* </ul>
* All these actions should be performed efficiently.
*
@@ -46,5 +48,9 @@
boolean isEmpty();
/** Swap 2 elements */
void swap(E e1, E e2);
+ /** Invert the order of elements between e1 and e2 */
+ void revert(E e1, E e2);
+ /** Find an element and return it */
+ E find(E e);
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
