Hi Martin, Peter
I made a few changes to polygonizer, so that it should be able to fit my
old requirements (keeping edge-face relations) and Peter's one
(agregating edge information onto faces).
There are very small changes in EdgeRing and PolygonizeGraph in order to
preserve face labels on edges, and the following changes in Polygonizer :
- add edgeList + getter/setter (list all edges with relations to faces)
- add faceEdgeMap (containing face->edges relations)
- polygonize() has been reworked so that it assigns an id to each
polygon (in userData) and adds left/right face ids to edge's userData.
- I also added 3 (optional) helper method to take advantage of these
relations : getLeftFace(LineString), getRightFace(LineString) and
getEdges(Polygon).
Martin, let me know what you think, and if I made something wrong or
consider
applying this patch to JTS.
Here attached are
- the patch modifying EdgeRing, PolygonizeGraph and Polygonizer
- a test class I used to check results
PS : while running junit ant task, I get a failure caused by test data
referenced as an aboslute path in text.jts.TestFiles class
I wish you an happy new year,
Michaël
Hi Martin, Peter,
I retrieved my code and realized that the problem I have tried to
solve is a bit
different from Peter's one.
Let me explain and let see if some low-level modifications could serve
both purposes.
I wanted to build a planar graph from a set of linestrings and get 2
or 3 layers (faces,
edges and eventually nodes) where all geometries would be attributed
an id, and
where the following relations would be held on edges
- initial node
- final node
- left face
- right face
To get it, I had to do the following changes
- pre-process my linework so that it is correctly splitted at
intersections
- rewrite EdgeRing where I added a long label attribute (class is
package protected)
- rewrite PolygonizeDirectedEdge where I added a startNode label
- rewrite PolygonizeGraph which have several private methods I had to
change so that
they accept my new EdgeRing and PolygonizeDirectedEdge
- Polygonizer : I added 2 attributes labeledEdgeList and nodeList. I
rewrote polygonize
(maybe I could have add a method) so that
* it does not remove dangles and cutedges
* while building polygons (and nodes) I use userData to set labels
from edgeRingLabel
(or PolygonizeDirectedGraph.startNode label for nodes)
*...
(I can send my changes if needed)
I'm wondering if such modifications could also serve Peter's problem.
My first thought when I did that changes is that I could probably have
extended
some class/methods and done less copy/paste if some methods had been
public or
protected.
It would need more thought to check if such a modification could also
serve Peter's
purpose. I think once edge to face relation computed, it would be
quite easy to get
face to edgelist. Not sure if I could have preserved user UserData as
I also used it in
my code to transfer element's id.
Sorry i I'm a bit confused, it would probaby need more work to get a
nice solution
able to serve multiple purposes.
Michaël
That would be great if you can provide some suggestions, Michael.
My best idea for meeting Peter's requirement for preserving edge
information is to add an option to the polygonizer to keep lists of
the edge userdata as I outlined in my email. This could be
incorporated in the Polygonizer as it stands. And perhaps you have
some further ideas for making the Polygonizer more flexible.
On Tue, Nov 25, 2014 at 11:10 PM, Michael Michaud
<[email protected] <mailto:[email protected]>> wrote:
Hi,
> Well, the original linestrings and the border/polygon hole line strings
wouldn't necessarily be equal,
correct? One option would be to first dissolve the line strings
into segments, so that all resulting line strings were one
segment long. Construct the hashmap from that set. Then after
polygonization, you could walk the segments of the polygon
linestrings and use the hashmap to determine the values of
contributing line strings. If line string values are not unique,
this method would require some tweaking.
A few years ago, I had a similar problem where I wanted to keep
relations between polygon and enclosing edges after polygonization. I
had to hack Polygonizer. I hoped it would not be too much work, but
because Polygonizer made many low-level methods private, I had to
duplicate several classes.
I think it would make things easier if Polygonizer itsef coud
preserve
information where it is possible, or if it could expose more
methods in
its api. I'll try to give more details about what I had to
change, if I
can retrieve it.
Michaël Michaud
>
>
>
>> On Nov 25, 2014, at 4:48 PM, Michael Bedward
<[email protected] <mailto:[email protected]>> wrote:
>>
>> Hi Peter,
>>
>> Perhaps a HashMap of LineString -> Double will do the trick ?
>>
>> Michael
>>
>>> On 26 November 2014 at 05:29, Peter Kovac
<[email protected]
<mailto:[email protected]>> wrote:
>>> Hi JTS,
>>>
>>> I'm computing a polygonization of a large set of LineStrings
(tens to
>>> hundred thousands), each with one Double value as user data.
What is the
>>> most efficient way to determine for each resulting polygon
the set of
>>> Double values of LineStrings which are the borders of the
polygon?
>>>
>>> Can I find by extending the Poylgonizer somehow (I think it's
unlikely)?
>>> Currently, I keep the input LineStrings in a SpatialIndex and
query each
>>> polygon coordinate for LineStrings containing it, but it's a
very slow
>>> process (tens of seconds).
>>>
>>> For example:
>>> Let's give LineStrings in this MULTILINESTRING ((10 0, 0 0, 0
20, 10
>>> 20), (10 0, 20 0, 20 20, 10 20), (10 0, 10 20)) values 1, 2,
and 3
>>> respectively.
>>> Then the set of values of POLYGON ((10 20, 10 0, 0 0, 0 20,
10 20)) is
>>> {1, 3} and of POLYGON ((10 20, 20 20, 20 0, 10 0, 10 20)) is
{2, 3}.
>>>
>>> Thank you,
>>>
>>> --
>>> Peter Kovac
>>> MicroStep-MIS
>>> Programmer
>>> [email protected]
<mailto:[email protected]>
>>> http://www.microstep-mis.com
>>>
>>>
>>>
------------------------------------------------------------------------------
>>> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
>>> from Actuate! Instantly Supercharge Your Business Reports and
Dashboards
>>> with Interactivity, Sharing, Native Excel Exports, App
Integration & more
>>> Get technology previously reserved for billion-dollar
corporations, FREE
>>>
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> Jts-topo-suite-user mailing list
>>> [email protected]
<mailto:[email protected]>
>>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
------------------------------------------------------------------------------
>> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
>> from Actuate! Instantly Supercharge Your Business Reports and
Dashboards
>> with Interactivity, Sharing, Native Excel Exports, App
Integration & more
>> Get technology previously reserved for billion-dollar
corporations, FREE
>>
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> [email protected]
<mailto:[email protected]>
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and
Dashboards
> with Interactivity, Sharing, Native Excel Exports, App
Integration & more
> Get technology previously reserved for billion-dollar
corporations, FREE
>
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
> _______________________________________________
> Jts-topo-suite-user mailing list
> [email protected]
<mailto:[email protected]>
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and
Dashboards
with Interactivity, Sharing, Native Excel Exports, App
Integration & more
Get technology previously reserved for billion-dollar
corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
<mailto:[email protected]>
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
package vividsolutions.jts.operation.polygonize;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;
import com.vividsolutions.jts.operation.polygonize.Polygonizer;
import com.vividsolutions.jts.util.Assert;
import junit.framework.TestCase;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
/**
* Created by Michaël on 21/12/14.
*/
public class PolygonizeNewTest extends TestCase {
private WKTReader reader = new WKTReader();
public PolygonizeNewTest(String name) {
super(name);
}
public static void main(String[] args) {
junit.textui.TestRunner.run(PolygonizeNewTest.class);
}
public void test1() {
// 110
// | 103
// |-----------|-----------|
// | |109 |
// | | --|--111
// | |------|------| |
// | | |108 | | 112 |-----|
// | | 5 | 2 | |-------| 6 |113
// | | |107 | | |-----|
// | |------|------| |
// | 101 | 100 |
// | 4 |106 1 |
// |-----------|-----------|
// 104 | 102
// 105
Collection coll = toGeometries(new String[]{
"LINESTRING(0 -5, 5 -5, 5 5, 0 5)",
"LINESTRING(0 -5, -5 -5, -5 5, 0 5)",
"LINESTRING(0 -9, 9 -9, 9 0)",
"LINESTRING(9 0, 9 9, 0 9)",
"LINESTRING(0 -9, -9 -9, -9 9, 0 9)",
"LINESTRING(0 -10, 0 -9)",
"LINESTRING(0 -9, 0 -5)",
"LINESTRING(0 -5, 0 0)",
"LINESTRING(0 0, 0 5)",
"LINESTRING(0 5, 0 9)",
"LINESTRING(0 9, 0 10)",
"LINESTRING(7 7, 14 7)",
"LINESTRING(9 0, 15 0)",
"LINESTRING(15 0, 15 -2, 18 -2, 18 2, 15 2, 15 0)"
});
int nb = 100;
for (Iterator it = coll.iterator() ; it.hasNext() ; ) {
Geometry g = (Geometry)it.next();
g.setUserData(nb++);
}
Polygonizer polygonizer = new Polygonizer();
polygonizer.add(coll);
printWithUserData(polygonizer.getPolygons());
System.out.println();
printWithUserData(polygonizer.getEdges());
System.out.println();
printWithUserData(polygonizer.getDangles());
System.out.println();
printWithUserData(polygonizer.getCutEdges());
System.out.println();
for (Iterator it = polygonizer.getPolygons().iterator() ; it.hasNext()
; ) {
Polygon p = (Polygon)it.next();
System.out.println(p.toText() + " : " + polygonizer.getEdges(p));
}
System.out.println();
for (Iterator it = polygonizer.getEdges().iterator() ; it.hasNext() ; )
{
LineString line = (LineString)it.next();
System.out.println(line.toText() + " : L=" +
polygonizer.getLeftFace(line) + " R=" + polygonizer.getRightFace(line));
}
}
private void printWithUserData(Collection coll) {
for (Iterator it = coll.iterator() ; it.hasNext() ; ) {
Geometry g = (Geometry)it.next();
if (g.getUserData() == null) System.out.println(g);
else if (g.getUserData() instanceof Object[]) {
System.out.println(g + " : " + Arrays.toString((Object[])
g.getUserData()));
}
else System.out.println(g + " : " + g.getUserData());
}
}
private void doTest(String[] inputWKT, String[] expectedOutputWKT) {
Polygonizer polygonizer = new Polygonizer();
polygonizer.add(toGeometries(inputWKT));
compare(toGeometries(expectedOutputWKT), polygonizer.getPolygons());
}
private void doTestEdges(String[] inputWKT, String[] expectedOutputWKT) {
Polygonizer polygonizer = new Polygonizer();
polygonizer.add(toGeometries(inputWKT));
compare(toGeometries(expectedOutputWKT), polygonizer.getEdges());
}
private void compare(Collection expectedGeometries,
Collection actualGeometries) {
assertEquals("Geometry count - expected " + expectedGeometries.size()
+ " but actual was " + actualGeometries.size()
+ " in " + actualGeometries,
expectedGeometries.size(), actualGeometries.size());
for (Iterator i = expectedGeometries.iterator(); i.hasNext();) {
Geometry expectedGeometry = (Geometry) i.next();
assertTrue("Expected to find: " + expectedGeometry + " in Actual
result:" + actualGeometries,
contains(actualGeometries, expectedGeometry));
}
}
private boolean contains(Collection geometries, Geometry g) {
for (Iterator i = geometries.iterator(); i.hasNext();) {
Geometry element = (Geometry) i.next();
if (element.equalsNorm(g)) {
return true;
}
}
return false;
}
private Collection toGeometries(String[] inputWKT) {
ArrayList geometries = new ArrayList();
for (int i = 0; i < inputWKT.length; i++) {
try {
geometries.add(reader.read(inputWKT[i]));
} catch (ParseException e) {
Assert.shouldNeverReachHere();
}
}
return geometries;
}
}
Index: trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/EdgeRing.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
--- trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/EdgeRing.java (revision 947)
+++ trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/EdgeRing.java (revision )
@@ -144,12 +144,29 @@
private Coordinate[] ringPts = null;
private List holes;
+ private long label;
public EdgeRing(GeometryFactory factory)
{
this.factory = factory;
}
+ public EdgeRing(GeometryFactory factory, long label)
+ {
+ this.factory = factory;
+ this.label = label;
+ }
+
+ public long getLabel()
+ {
+ return label;
+ }
+
+ public void setLabel(long label)
+ {
+ this.label = label;
+ }
+
/**
* Adds a {@link DirectedEdge} which is known to form part of this ring.
* @param de the {@link DirectedEdge} to add.
@@ -157,6 +174,14 @@
public void add(DirectedEdge de)
{
deList.add(de);
+ }
+
+ /**
+ * Get directed edges associated to this edge.
+ * @return
+ */
+ public List getEdges() {
+ return deList;
}
/**
Index: trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/PolygonizeGraph.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
--- trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/PolygonizeGraph.java (revision 947)
+++ trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/PolygonizeGraph.java (revision )
@@ -43,7 +43,7 @@
/**
* Represents a planar graph of edges that can be used to compute a
* polygonization, and implements the algorithms to compute the
- * {@link EdgeRings} formed by the graph.
+ * {@link EdgeRing}s formed by the graph.
* <p>
* The marked flag on {@link DirectedEdge}s is used to indicate that a directed edge
* has be logically deleted from the graph.
@@ -218,6 +218,8 @@
if (de.isInRing()) continue;
EdgeRing er = findEdgeRing(de);
+ // copy label onto ring edge
+ er.setLabel(de.getLabel());
edgeRingList.add(er);
}
return edgeRingList;
@@ -384,7 +386,7 @@
private EdgeRing findEdgeRing(PolygonizeDirectedEdge startDE)
{
PolygonizeDirectedEdge de = startDE;
- EdgeRing er = new EdgeRing(factory);
+ EdgeRing er = new EdgeRing(factory, de.getLabel()); // build a "labeled" edge ring
do {
er.add(de);
de.setRing(er);
Index: trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/Polygonizer.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
--- trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/Polygonizer.java (revision 947)
+++ trunk/jts/java/src/com/vividsolutions/jts/operation/polygonize/Polygonizer.java (revision )
@@ -33,10 +33,7 @@
*/
package com.vividsolutions.jts.operation.polygonize;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Iterator;
-import java.util.List;
+import java.util.*;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryComponentFilter;
@@ -91,7 +88,9 @@
protected List holeList = null;
protected List shellList = null;
protected List polyList = null;
+ protected List edgeList = null;
+ private Map faceEdgeMap = null;
private boolean isCheckingRingsValid = true;
/**
@@ -168,6 +167,17 @@
}
/**
+ * Gets all edges from the planar graph computed from input polygons and linestrings,
+ * including ring edges, dangles and cut edges.
+ * @return a collection of the input {@link
+ */
+ public Collection getEdges()
+ {
+ polygonize();
+ return edgeList;
+ }
+
+ /**
* Gets the list of dangling lines found during polygonization.
* @return a collection of the input {@link LineString}s which are dangles
*/
@@ -187,6 +197,28 @@
return cutEdges;
}
+ public Long getLeftFace(LineString edge) {
+ if (faceEdgeMap == null) computeRelations();
+ if (edge.getUserData() == null) return null;
+ if (!(edge.getUserData() instanceof Object[])) return null;
+ if (((Object[])edge.getUserData()).length < 3) return null;
+ return (Long)(((Object[])edge.getUserData())[1]);
+ }
+
+ public Long getRightFace(LineString edge) {
+ if (faceEdgeMap == null) computeRelations();
+ if (edge.getUserData() == null) return null;
+ if (!(edge.getUserData() instanceof Object[])) return null;
+ if (((Object[])edge.getUserData()).length < 3) return null;
+ return (Long)(((Object[])edge.getUserData())[2]);
+ }
+
+ public Collection getEdges(Polygon polygon) {
+ if (faceEdgeMap == null) computeRelations();
+ if (polygon.getUserData() == null) return null;
+ return (List)faceEdgeMap.get((Long)polygon.getUserData());
+ }
+
/**
* Gets the list of lines forming invalid rings found during polygonization.
* @return a collection of the input {@link LineString}s which form invalid rings
@@ -213,8 +245,6 @@
cutEdges = graph.deleteCutEdges();
List edgeRingList = graph.getEdgeRings();
- //Debug.printTime("Build Edge Rings");
-
List validEdgeRingList = new ArrayList();
invalidRingLines = new ArrayList();
if (isCheckingRingsValid) {
@@ -223,20 +253,60 @@
else {
validEdgeRingList = edgeRingList;
}
- //Debug.printTime("Validate Rings");
-
+
findShellsAndHoles(validEdgeRingList);
assignHolesToShells(holeList, shellList);
-
- //Debug.printTime("Assign Holes");
-
- polyList = new ArrayList();
+ Set polygonLabels = new HashSet();
for (Iterator i = shellList.iterator(); i.hasNext(); ) {
EdgeRing er = (EdgeRing) i.next();
- polyList.add(er.getPolygon());
+ Polygon polygon = er.getPolygon();
+ // copy shell label into polygon's UserData
+ Long polygonLabel = new Long(er.getLabel());
+ polygon.setUserData(polygonLabel);
+ polygonLabels.add(polygonLabel);
+ polyList.add(polygon);
}
+
+ // transform graph edges to linestrings and add left/right side polygon
+ // identifier in each linestring's userdata
+ if (edgeList == null) edgeList = new ArrayList();
+ for (Iterator it = graph.getEdges().iterator() ; it.hasNext() ;) {
+ PolygonizeEdge edge = (PolygonizeEdge)it.next();
+ LineString line = edge.getLine();
+ Long rightLabel = new Long(((PolygonizeDirectedEdge) edge.getDirEdge(0)).getLabel());
+ if (!polygonLabels.contains(rightLabel)) {
+ rightLabel = new Long(-1);
- }
+ }
+ Long leftLabel = new Long(((PolygonizeDirectedEdge) edge.getDirEdge(1)).getLabel());
+ if (!polygonLabels.contains(leftLabel)) {
+ leftLabel = new Long(-1);
+ }
+ line.setUserData(new Object[]{
+ edge.getLine().getUserData(), leftLabel, rightLabel
+ });
+ edgeList.add(line);
+ }
+ }
+ private void computeRelations() {
+ polygonize();
+ if (faceEdgeMap == null) {
+ faceEdgeMap = new HashMap(getPolygons().size());
+ for (Iterator it = getPolygons().iterator() ; it.hasNext() ; ) {
+ Geometry face = (Geometry)it.next();
+ faceEdgeMap.put(face.getUserData(), new ArrayList());
+ }
+ for (Iterator it = getEdges().iterator() ; it.hasNext() ; ) {
+ Geometry edge = (Geometry)it.next();
+ Object[] userData = (Object[])edge.getUserData();
+ List side0 = (List)faceEdgeMap.get(userData[1]);
+ if (side0 != null) side0.add(userData[0]);
+ List side1 = (List)faceEdgeMap.get(userData[2]);
+ if (side1 != null) side1.add(userData[0]);
+ }
+ }
+ }
+
private void findValidRings(List edgeRingList, List validEdgeRingList, List invalidRingList)
{
for (Iterator i = edgeRingList.iterator(); i.hasNext(); ) {
@@ -273,8 +343,14 @@
private static void assignHoleToShell(EdgeRing holeER, List shellList)
{
EdgeRing shell = EdgeRing.findEdgeRingContaining(holeER, shellList);
- if (shell != null)
+ if (shell != null) {
shell.addHole(holeER.getRing());
+ // copy the shell label to the hole edges
+ for (Iterator it = holeER.getEdges().iterator() ; it.hasNext() ; ) {
+ PolygonizeDirectedEdge edge = (PolygonizeDirectedEdge)it.next();
+ edge.setLabel(shell.getLabel());
+ }
+ }
}
------------------------------------------------------------------------------
Dive into the World of Parallel Programming! The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
