Revision: 5462
http://sourceforge.net/p/jump-pilot/code/5462
Author: michaudm
Date: 2017-06-10 20:39:31 +0000 (Sat, 10 Jun 2017)
Log Message:
-----------
improvement of HydrographicNetworkAnalysis and Skeleton PlugIns
Modified Paths:
--------------
plug-ins/GraphToolboxPlugin/trunk/build.xml
plug-ins/GraphToolboxPlugin/trunk/doc/GraphToolboxExtension4OJ.odt
plug-ins/GraphToolboxPlugin/trunk/doc/GraphToolboxExtension4OJ_fr.odt
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/GraphExtension.java
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/HydrographicNetworkAnalysisPlugIn.java
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/SkeletonPlugIn.java
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph.properties
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph_fr.properties
Modified: plug-ins/GraphToolboxPlugin/trunk/build.xml
===================================================================
--- plug-ins/GraphToolboxPlugin/trunk/build.xml 2017-06-10 15:12:55 UTC (rev
5461)
+++ plug-ins/GraphToolboxPlugin/trunk/build.xml 2017-06-10 20:39:31 UTC (rev
5462)
@@ -17,7 +17,7 @@
<property name="dist" value="dist" />
<property name="javadoc" value="javadoc" />
- <property name="version" value="0.5.0" />
+ <property name="version" value="0.5.5" />
<!-- ===================================================================
-->
<!-- Defines the classpath used for compilation and test.
-->
Modified: plug-ins/GraphToolboxPlugin/trunk/doc/GraphToolboxExtension4OJ.odt
===================================================================
(Binary files differ)
Modified: plug-ins/GraphToolboxPlugin/trunk/doc/GraphToolboxExtension4OJ_fr.odt
===================================================================
(Binary files differ)
Modified:
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/GraphExtension.java
===================================================================
---
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/GraphExtension.java
2017-06-10 15:12:55 UTC (rev 5461)
+++
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/GraphExtension.java
2017-06-10 20:39:31 UTC (rev 5462)
@@ -35,8 +35,10 @@
* <li>CycleFinderPlugIn : computes a graph from a linear network and find
base cycles</li>
* </ul>
* @author Michaël Michaud
- * @version 0.4.1 (2017-02-03)
+ * @version 0.5.5 (2017-06-10)
*/
+//version 0.5.5 (2017-06-10) improvement of HydrographicNetworkAnalysis and
Skeleton PlugIns
+//version 0.5.0 (2017-04-10) add HydrographicNetworkAnalysisPlugIn
//version 0.4.1 (2017-02-03) fix a small I18N problem
//version 0.4.0 (2017-01-12) add DirectedGraph option in GraphNodesPlugIn
//version 0.3.1 (2016-11-24) fix a severe regression on StrahlerNumberPlugIn
@@ -54,7 +56,7 @@
}
public String getVersion() {
- return "0.4.1 (2017-02-03)";
+ return "0.5.5 (2017-06-10)";
}
public void configure(PlugInContext context) throws Exception {
Modified:
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/HydrographicNetworkAnalysisPlugIn.java
===================================================================
---
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/HydrographicNetworkAnalysisPlugIn.java
2017-06-10 15:12:55 UTC (rev 5461)
+++
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/HydrographicNetworkAnalysisPlugIn.java
2017-06-10 20:39:31 UTC (rev 5462)
@@ -4,6 +4,7 @@
import com.vividsolutions.jump.feature.*;
import com.vividsolutions.jump.task.TaskMonitor;
import com.vividsolutions.jump.workbench.model.Layer;
+import com.vividsolutions.jump.workbench.model.StandardCategoryNames;
import com.vividsolutions.jump.workbench.plugin.MultiEnableCheck;
import com.vividsolutions.jump.workbench.plugin.PlugInContext;
import com.vividsolutions.jump.workbench.plugin.ThreadedBasePlugIn;
@@ -16,22 +17,23 @@
import fr.michaelm.jump.feature.jgrapht.INode;
import org.jgrapht.DirectedGraph;
import org.jgrapht.Graph;
-import org.jgrapht.GraphPath;
+import org.jgrapht.alg.CycleDetector;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.alg.cycle.HawickJamesSimpleCycles;
import org.jgrapht.graph.DirectedSubgraph;
import org.jgrapht.graph.EdgeReversedGraph;
import org.jgrapht.traverse.BreadthFirstIterator;
-import org.openjump.core.ui.style.decoration.ArrowLineStringMiddlepointStyle;
import javax.swing.*;
import java.awt.*;
+import java.awt.event.ActionEvent;
+import java.awt.event.ActionListener;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.List;
/**
- * Created by UMichael on 06/04/2017.
+ * PlugIn to detect or repair anomalies in a hydrographic network
*/
public class HydrographicNetworkAnalysisPlugIn extends ThreadedBasePlugIn {
@@ -61,6 +63,7 @@
private static String Z_ANOMALY;
private static String CYCLE_ANOMALY;
private static String NODE_ANOMALY;
+ private static String REVERSED_EDGES;
private Layer layer;
private boolean detect = true;
@@ -101,6 +104,7 @@
Z_ANOMALY =
I18NPlug.getI18N("HydrographicNetworkAnalysisPlugIn.z-anomaly");
CYCLE_ANOMALY =
I18NPlug.getI18N("HydrographicNetworkAnalysisPlugIn.cycle-anomaly");
NODE_ANOMALY =
I18NPlug.getI18N("HydrographicNetworkAnalysisPlugIn.node-anomaly");
+ REVERSED_EDGES =
I18NPlug.getI18N("HydrographicNetworkAnalysisPlugIn.reversed-edge");
context.getFeatureInstaller().addMainMenuPlugin(
this, new String[]{MenuNames.PLUGINS, GRAPH},
@@ -116,19 +120,28 @@
context.getWorkbenchFrame(), HYDROGRAPHIC_NETWORK_ANALYSIS,
true);
dialog.setSideBarDescription(I18NPlug.getI18N("HydrographicNetworkAnalysisPlugIn.Description"));
- final JComboBox jcb_layer = dialog.addLayerComboBox(
- LAYER, context.getCandidateLayer(0), null,
context.getLayerManager());
+ dialog.addLayerComboBox(LAYER,
+ context.getCandidateLayer(0), null, context.getLayerManager());
- final JRadioButton jrb_detect = dialog.addRadioButton(DETECT,
"action", detect, DETECT);
- final JRadioButton jrb_repair = dialog.addRadioButton(REPAIR,
"action", repair, REPAIR);
+ dialog.addRadioButton(DETECT, "action", detect, DETECT);
+ dialog.addRadioButton(REPAIR, "action", repair, REPAIR);
- final JCheckBox jcb_cycles = dialog.addCheckBox(FIND_CYCLES,
findCycles, FIND_CYCLES_TT);
- final JCheckBox jcb_source = dialog.addCheckBox(FIND_SOURCES,
findSources, FIND_SOURCES_TT);
- final JCheckBox jcb_well = dialog.addCheckBox(FIND_SINKS, findSinks,
FIND_SINKS_TT);
final JCheckBox jcb_use_z = dialog.addCheckBox(USE_Z, useZ, USE_Z_TT);
final JTextField jtf_tol_z = dialog.addDoubleField(TOL_Z, tolZ, 12,
TOL_Z_TT);
+ jtf_tol_z.setEnabled(jcb_use_z.isSelected());
+ jcb_use_z.addActionListener(new ActionListener() {
+ @Override
+ public void actionPerformed(ActionEvent e) {
+ jtf_tol_z.setEnabled(jcb_use_z.isSelected());
+ }
+ });
+ dialog.addCheckBox(FIND_SOURCES, findSources, FIND_SOURCES_TT);
+ dialog.addCheckBox(FIND_SINKS, findSinks, FIND_SINKS_TT);
+ dialog.addCheckBox(FIND_CYCLES, findCycles, FIND_CYCLES_TT);
+
+
GUIUtil.centreOnWindow(dialog);
dialog.setVisible(true);
if (dialog.wasOKPressed()) {
@@ -150,41 +163,57 @@
monitor.allowCancellationRequests();
monitor.report(GRAPH_COMPUTATION + "...");
FeatureCollection fc = layer.getFeatureCollectionWrapper();
- if (detect && useZ) {
- Layer lyr = context.getLayerManager().addLayer("Result",
layer.getName() + "-" + Z_ANOMALY, getInversedEdges(fc));
- setInversionStyle(lyr);
- }
DirectedGraph<INode,FeatureAsEdge> graph =
(DirectedGraph<INode,FeatureAsEdge>)
GraphFactory.createDirectedPseudograph(fc.getFeatures(), false);
- if (detect && findCycles) {
- Layer lyr = context.getLayerManager().addLayer("Result",
layer.getName() + "-" + CYCLE_ANOMALY, getCycles(graph));
- setCycleStyle(lyr);
+
+ if (detect) {
+ if (useZ) {
+ Layer lyr =
context.getLayerManager().addLayer(StandardCategoryNames.RESULT,
+ layer.getName() + "-" + Z_ANOMALY,
getInversedEdges(fc));
+ setInversionStyle(lyr);
+ }
+ if (findCycles) {
+ Layer lyr =
context.getLayerManager().addLayer(StandardCategoryNames.RESULT,
+ layer.getName() + "-" + CYCLE_ANOMALY,
getCycles(graph));
+ setCycleStyle(lyr);
+ }
+ if (findSources || findSinks) {
+ Layer lyr =
context.getLayerManager().addLayer(StandardCategoryNames.RESULT,
+ layer.getName() + "-" + NODE_ANOMALY,
getSourcesAndSinks(graph));
+ setNodeStyle(lyr);
+ }
}
- if (detect && (findSources || findSinks)) {
- Layer lyr = context.getLayerManager().addLayer("Result",
layer.getName() + "-" + NODE_ANOMALY, getSourcesAndWells(graph));
- lyr.getBasicStyle().setFillColor(Color.RED);
- lyr.addStyle(new MyRingVertexStyle());
- lyr.getStyle(MyRingVertexStyle.class).setEnabled(true);
- }
- Set<Integer> set = new HashSet<Integer>();
- if (repair && findCycles) {
- repairCycles(graph, set);
- }
- if (repair && findSources) {
- repairSources(graph, set);
- }
- if (repair && findSinks) {
- repairSinks(graph, set);
- }
+
if (repair) {
+ Set<Integer> set = new HashSet<Integer>();
+ if (useZ) {
+ repairDownwardEdges(graph, set);
+ }
+ if (findSources) {
+ repairSources(graph, set);
+ }
+ if (findSinks) {
+ repairSinks(graph, set);
+ }
+ if (findCycles) {
+ repairCycles(graph, set);
+ }
+ FeatureCollection reversedFeatures =
+ new
FeatureDataset(layer.getFeatureCollectionWrapper().getFeatureSchema());
+
EditTransaction transaction = new EditTransaction(new
LinkedHashSet<Feature>(),
- "HydrographicNetworkAnalysis", layer, true, true,
context.getLayerViewPanel().getContext());
+ HYDROGRAPHIC_NETWORK_ANALYSIS, layer, true, true,
context.getLayerViewPanel().getContext());
for (Feature feature : fc.getFeatures()) {
if (set.contains(feature.getID())) {
+ reversedFeatures.add(feature.clone(true, true));
transaction.modifyFeatureGeometry(feature,
feature.getGeometry().reverse());
}
}
+ Layer lyr =
context.getLayerManager().addLayer(StandardCategoryNames.RESULT,
+ layer.getName() + "-" + REVERSED_EDGES, reversedFeatures);
+ setReversedStyle(lyr);
+
transaction.commit();
}
}
@@ -234,7 +263,7 @@
return dataset;
}
- private FeatureCollection
getSourcesAndWells(DirectedGraph<INode,FeatureAsEdge> graph) {
+ private FeatureCollection
getSourcesAndSinks(DirectedGraph<INode,FeatureAsEdge> graph) {
FeatureSchema anomalySchema = getAnomalySchema();
FeatureCollection dataset = new FeatureDataset(anomalySchema);
@@ -244,7 +273,7 @@
feature.setGeometry(node.getGeometry());
feature.setAttribute("type", SOURCE);
dataset.add(feature);
- } else if (findSinks && isWell(graph, node)) {
+ } else if (findSinks && isSink(graph, node)) {
Feature feature = new BasicFeature(anomalySchema);
feature.setGeometry(node.getGeometry());
feature.setAttribute("type", SINK);
@@ -254,16 +283,29 @@
return dataset;
}
- boolean isSource(DirectedGraph<INode,FeatureAsEdge> graph, INode node) {
+ private boolean isSource(DirectedGraph<INode,FeatureAsEdge> graph, INode
node) {
return graph.inDegreeOf(node) == 0 && graph.outDegreeOf(node) > 1;
}
- boolean isWell(DirectedGraph<INode,FeatureAsEdge> graph, INode node) {
+ private boolean isSink(DirectedGraph<INode,FeatureAsEdge> graph, INode
node) {
return graph.outDegreeOf(node) == 0 && graph.inDegreeOf(node) > 1;
}
+ private void repairDownwardEdges(DirectedGraph<INode,FeatureAsEdge> graph,
Set<Integer> set) {
+ for (FeatureAsEdge edge : new
ArrayList<FeatureAsEdge>(graph.edgeSet())) {
+ Geometry geometry = edge.getFeature().getGeometry();
+ if (!geometry.isEmpty() && geometry instanceof LineString) {
+ double z1 = geometry.getCoordinates()[0].z;
+ double z2 =
geometry.getCoordinates()[geometry.getNumPoints()-1].z;
+ if (!Double.isNaN(z1) && !Double.isNaN(z2) && (z1-z2) < -tolZ)
{
+ reverseEdge(graph, edge);
+ set.add(edge.getFeature().getID());
+ }
+ }
+ }
+ }
- private List<Integer> repairCycles(DirectedGraph<INode,FeatureAsEdge>
graph, Set<Integer> set) {
+ private void repairCycles(DirectedGraph<INode,FeatureAsEdge> graph,
Set<Integer> set) {
List<List<INode>> cycles = new
HawickJamesSimpleCycles<INode,FeatureAsEdge>(graph).findSimpleCycles();
for (List<INode> cycle : cycles) {
Set<FeatureAsEdge> edgeSet = new
DirectedSubgraph<INode,FeatureAsEdge>(
@@ -282,13 +324,13 @@
set.add(edgeToReverse.getFeature().getID());
}
}
- return new ArrayList<Integer>();
}
private void repairSources(DirectedGraph<INode,FeatureAsEdge> graph,
Set<Integer> set) {
for (INode node : graph.vertexSet()) {
if (findSources && isSource(graph, node)) {
- BreadthFirstIterator<INode,FeatureAsEdge> it = new
BreadthFirstIterator(graph, node);
+ BreadthFirstIterator<INode,FeatureAsEdge> it =
+ new BreadthFirstIterator<INode,FeatureAsEdge>(graph,
node);
INode stopNode = null;
while (it.hasNext()) {
INode n = it.next();
@@ -307,11 +349,29 @@
}
}
if (stopNode != null) {
- List<FeatureAsEdge> edges =
DijkstraShortestPath.findPathBetween(graph, node, stopNode);
- for (FeatureAsEdge edge : edges) {
- reverseEdge(graph, edge);
- set.add(edge.getFeature().getID());
- }
+ reversePath(graph, node, stopNode, set);
+ // List<FeatureAsEdge> edges =
DijkstraShortestPath.findPathBetween(graph, node, stopNode);
+ // Set<Integer> temp = new HashSet<Integer>();
+ // for (FeatureAsEdge edge : edges) {
+ // reverseEdge(graph, edge);
+ // temp.add(edge.getFeature().getID());
+ // }
+ // boolean hasCycle = false;
+ // CycleDetector cycleDetector = new CycleDetector(graph);
+ // for (FeatureAsEdge edge : edges) {
+ // if
(cycleDetector.detectCyclesContainingVertex(graph.getEdgeTarget(edge))) {
+ // hasCycle = true;
+ // break;
+ // }
+ // }
+ // if (hasCycle) {
+ // for (FeatureAsEdge edge : edges) {
+ // reverseEdge(graph, edge);
+ // }
+ // temp.clear();
+ // } else {
+ // set.addAll(temp);
+ // }
}
}
}
@@ -319,10 +379,11 @@
}
private void repairSinks(DirectedGraph<INode,FeatureAsEdge> graph,
Set<Integer> set) {
- graph = new EdgeReversedGraph(graph);
+ graph = new EdgeReversedGraph<INode,FeatureAsEdge>(graph);
for (INode node : graph.vertexSet()) {
if (findSources && isSource(graph, node)) {
- BreadthFirstIterator<INode,FeatureAsEdge> it = new
BreadthFirstIterator(graph, node);
+ BreadthFirstIterator<INode,FeatureAsEdge> it =
+ new BreadthFirstIterator<INode,FeatureAsEdge>(graph,
node);
INode stopNode = null;
while (it.hasNext()) {
INode n = it.next();
@@ -341,11 +402,29 @@
}
}
if (stopNode != null) {
- List<FeatureAsEdge> edges =
DijkstraShortestPath.findPathBetween(graph, node, stopNode);
- for (FeatureAsEdge edge : edges) {
- reverseEdge(graph, edge);
- set.add(edge.getFeature().getID());
- }
+ reversePath(graph, node, stopNode, set);
+ // List<FeatureAsEdge> edges =
DijkstraShortestPath.findPathBetween(graph, node, stopNode);
+ // Set<Integer> temp = new HashSet<Integer>();
+ // for (FeatureAsEdge edge : edges) {
+ // reverseEdge(graph, edge);
+ // temp.add(edge.getFeature().getID());
+ // }
+ // boolean hasCycle = false;
+ // CycleDetector cycleDetector = new CycleDetector(graph);
+ // for (FeatureAsEdge edge : edges) {
+ // if
(cycleDetector.detectCyclesContainingVertex(graph.getEdgeSource(edge))) {
+ // hasCycle = true;
+ // break;
+ // }
+ // }
+ // if (hasCycle) {
+ // for (FeatureAsEdge edge : edges) {
+ // reverseEdge(graph, edge);
+ // }
+ // temp.clear();
+ // } else {
+ // set.addAll(temp);
+ // }
}
}
}
@@ -352,6 +431,37 @@
//return new ArrayList<Integer>();
}
+ private void reversePath(DirectedGraph<INode,FeatureAsEdge> graph, INode
node1, INode node2, Set<Integer> set) {
+ List<FeatureAsEdge> edges =
DijkstraShortestPath.findPathBetween(graph, node1, node2);
+ Set<Integer> temp = new HashSet<Integer>();
+ for (FeatureAsEdge edge : edges) {
+ reverseEdge(graph, edge);
+ temp.add(edge.getFeature().getID());
+ }
+ // Before validation, check that we did not introduce cycles
+ boolean hasCycle = false;
+ CycleDetector<INode,FeatureAsEdge> cycleDetector = new
CycleDetector<INode,FeatureAsEdge>(graph);
+ if (cycleDetector.detectCyclesContainingVertex(node1)) hasCycle = true;
+ else if (cycleDetector.detectCyclesContainingVertex(node2)) hasCycle =
true;
+ else {
+ for (FeatureAsEdge edge : edges) {
+ if
(cycleDetector.detectCyclesContainingVertex(graph.getEdgeSource(edge))) {
+ hasCycle = true;
+ break;
+ }
+ }
+ }
+ // If a cycle has been found, we reverse the graph back to the
previous situation
+ if (hasCycle) {
+ for (FeatureAsEdge edge : edges) {
+ reverseEdge(graph, edge);
+ }
+ temp.clear();
+ } else {
+ set.addAll(temp);
+ }
+ }
+
private void reverseEdge(Graph<INode,FeatureAsEdge> graph, FeatureAsEdge
edge) {
INode start = graph.getEdgeSource(edge);
INode end = graph.getEdgeTarget(edge);
@@ -371,8 +481,8 @@
graph.removeEdge(edge);
graph.addEdge(end, start, edge);
double result;
- if (isSource(graph, start) || isWell(graph, start)) result = 0;
- else if (isSource(graph, end) || isWell(graph, end)) result = 0;
+ if (isSource(graph, start) || isSink(graph, start)) result = 0;
+ else if (isSource(graph, end) || isSink(graph, end)) result = 0;
else if (useZ) {
double z0 =
((LineString)edge.getGeometry()).getStartPoint().getCoordinate().z;
double z1 =
((LineString)edge.getGeometry()).getEndPoint().getCoordinate().z;
@@ -401,7 +511,7 @@
return schema;
}
- public void setInversionStyle(Layer layer) {
+ private void setInversionStyle(Layer layer) {
BasicStyle style = layer.getBasicStyle();
style.setLineColor(Color.ORANGE);
style.setLineWidth(3);
@@ -410,14 +520,26 @@
layer.addStyle(new ArrowLineStringSegmentStyle.Solid());
}
- public void setCycleStyle(Layer layer) {
- BasicStyle style = layer.getBasicStyle();
- style.setLineColor(Color.RED);
- style.setLineWidth(3);
- style.setAlpha(200);
- style.setFillColor(Color.LIGHT_GRAY);
+ private void setCycleStyle(Layer layer) {
+ layer.getBasicStyle().setFillColor(Color.LIGHT_GRAY);
+ layer.getBasicStyle().setLineColor(Color.RED);
+ layer.getBasicStyle().setLineWidth(3);
+ layer.getBasicStyle().setAlpha(200);
}
+ private void setNodeStyle(Layer layer) {
+ layer.getBasicStyle().setFillColor(Color.RED);
+ layer.addStyle(new MyRingVertexStyle());
+ layer.getStyle(MyRingVertexStyle.class).setEnabled(true);
+ }
+
+ private void setReversedStyle(Layer layer) {
+ layer.getBasicStyle().setFillColor(Color.LIGHT_GRAY);
+ layer.getBasicStyle().setLineColor(Color.BLUE);
+ layer.getBasicStyle().setLineWidth(3);
+ layer.getBasicStyle().setAlpha(200);
+ }
+
private static class MyRingVertexStyle extends RingVertexStyle {
MyRingVertexStyle() {super();}
Modified:
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/SkeletonPlugIn.java
===================================================================
---
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/SkeletonPlugIn.java
2017-06-10 15:12:55 UTC (rev 5461)
+++
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/SkeletonPlugIn.java
2017-06-10 20:39:31 UTC (rev 5462)
@@ -1,6 +1,8 @@
package fr.michaelm.jump.plugin.graph;
import com.vividsolutions.jts.algorithm.MCPointInRing;
+import com.vividsolutions.jts.algorithm.distance.DistanceToPoint;
+import com.vividsolutions.jts.algorithm.distance.PointPairDistance;
import com.vividsolutions.jts.densify.Densifier;
import com.vividsolutions.jts.geom.*;
import com.vividsolutions.jts.geom.util.LineStringExtracter;
@@ -8,6 +10,7 @@
import com.vividsolutions.jts.simplify.TopologyPreservingSimplifier;
import com.vividsolutions.jts.triangulate.VoronoiDiagramBuilder;
import com.vividsolutions.jump.feature.*;
+import com.vividsolutions.jump.geom.Angle;
import com.vividsolutions.jump.task.TaskMonitor;
import com.vividsolutions.jump.workbench.WorkbenchContext;
import com.vividsolutions.jump.workbench.model.LayerManager;
@@ -38,31 +41,39 @@
*/
public class SkeletonPlugIn extends AbstractThreadedUiPlugIn {
- private static String GRAPH = I18NPlug.getI18N("Graph");
- private static String CENTRAL_SKELETON =
I18NPlug.getI18N("SkeletonPlugIn");
- private static String SKELETONIZE =
I18NPlug.getI18N("SkeletonPlugIn.skeletonize");
- private static String SOURCE_LAYER =
I18NPlug.getI18N("SkeletonPlugIn.source-layer");
- private static String AUTO_PARAMETERS =
I18NPlug.getI18N("SkeletonPlugIn.auto-parameters");
- private static String AUTO_PARAMETERS_TT =
I18NPlug.getI18N("SkeletonPlugIn.auto-parameters-tooltip");
- private static String MIN_WIDTH =
I18NPlug.getI18N("SkeletonPlugIn.min-width");
- private static String MIN_WIDTH_TT =
I18NPlug.getI18N("SkeletonPlugIn.min-width-tooltip");
- private static String ITERATIONS =
I18NPlug.getI18N("SkeletonPlugIn.iterations");
- private static String ITERATIONS_TT =
I18NPlug.getI18N("SkeletonPlugIn.iterations-tooltip");
- private static String MIN_FORK_LENGTH =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length");
- private static String MIN_FORK_LENGTH_TT =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length-tooltip");
- private static String BEAUTIFY_ENDS =
I18NPlug.getI18N("SkeletonPlugIn.beautify-ends");
- private static String BEAUTIFY_ENDS_TT =
I18NPlug.getI18N("SkeletonPlugIn.beautify-ends-tooltip");
- private static String DISPLAY_VORONOI_EDGES =
I18NPlug.getI18N("SkeletonPlugIn.display-voronoi-edges");
- private static String DESCRIPTION =
I18NPlug.getI18N("SkeletonPlugIn.description");
+ private static String GRAPH = I18NPlug.getI18N("Graph");
+ private static String CENTRAL_SKELETON =
I18NPlug.getI18N("SkeletonPlugIn");
+ private static String SKELETONIZE =
I18NPlug.getI18N("SkeletonPlugIn.skeletonize");
+ private static String SOURCE_LAYER =
I18NPlug.getI18N("SkeletonPlugIn.source-layer");
+ private static String AUTO_WIDTH_PARAMETER =
I18NPlug.getI18N("SkeletonPlugIn.auto-width-parameter");
+ private static String AUTO_WIDTH_PARAMETER_TT =
I18NPlug.getI18N("SkeletonPlugIn.auto-width-parameter-tooltip");
+ private static String MIN_WIDTH =
I18NPlug.getI18N("SkeletonPlugIn.min-width");
+ private static String MIN_WIDTH_TT =
I18NPlug.getI18N("SkeletonPlugIn.min-width-tooltip");
+ private static String MIN_FORK_LENGTH_FROM_MEAN_WIDTH =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length-from-mean-width");
+ private static String MIN_FORK_LENGTH_FROM_MEAN_WIDTH_TT =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length-from-mean-width-tooltip");
+ private static String MIN_FORK_LENGTH_IN_MAP_UNITS =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length-in-map-units");
+ private static String MIN_FORK_LENGTH_IN_MAP_UNITS_TT =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length-in-map-units-tooltip");
+ private static String MIN_FORK_LENGTH =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length");
+ private static String MIN_FORK_LENGTH_TT =
I18NPlug.getI18N("SkeletonPlugIn.min-fork-length-tooltip");
+ private static String SNAP_TO_BOUNDARY =
I18NPlug.getI18N("SkeletonPlugIn.snap-to_boundary");
+ private static String SNAP_TO_BOUNDARY_TT =
I18NPlug.getI18N("SkeletonPlugIn.snap-to_boundary-tooltip");
+ private static String DISPLAY_VORONOI_EDGES =
I18NPlug.getI18N("SkeletonPlugIn.display-voronoi-edges");
+ private static String DESCRIPTION =
I18NPlug.getI18N("SkeletonPlugIn.description");
- private String layerName;
- private boolean autoParameters = true;
- private double minWidth = 1.0;
- private int iterations = 10;
- private double minForkLength = 10.0;
- private boolean snapEnds = true;
+ private String layerName;
+ private boolean autoWidth = true;
+ private double minWidth = 1.0; // minimum width of the polygon
+ private double meanWidth = 2.0; // mean width of the polygon
+ private int maxIterations = 8192; // maximum iteration to eliminate
forks
+ private double forkLengthMul = 2.5; // minimum length of a fork
+ private double minForkLength = 10.0; // minimum length of a fork
+ private boolean fromMeanWidth = true; // minimum fork length from mean
width
+ private boolean fromMapUnits = false; // minimum fork length in map units
+ private boolean snapEnds = false; // wheter the skeletton must snap
the polygon boundary
private boolean displayVoronoiEdges = false;
+ private static Collection debugGeometries = new ArrayList<Geometry>();
+
public void initialize(PlugInContext context) throws Exception {
workbenchContext = context.getWorkbenchContext();
@@ -100,20 +111,24 @@
layerName = context.getCandidateLayer(0).getName();
dialog.addLayerComboBox(SOURCE_LAYER,
context.getLayerManager().getLayer(layerName),
null, context.getLayerManager());
- final JCheckBox autoJcb = dialog.addCheckBox(AUTO_PARAMETERS,
autoParameters,AUTO_PARAMETERS_TT);
+
+ final JCheckBox autoWidthJcb =
dialog.addCheckBox(AUTO_WIDTH_PARAMETER, autoWidth,AUTO_WIDTH_PARAMETER_TT);
final JTextField minWidthTF = dialog.addDoubleField(MIN_WIDTH,
minWidth, 12, MIN_WIDTH_TT);
- final JTextField minForkLengthTF =
dialog.addDoubleField(MIN_FORK_LENGTH, minForkLength, 12, MIN_FORK_LENGTH_TT);
- final JTextField iterationsTF = dialog.addIntegerField(ITERATIONS,
iterations, 12, ITERATIONS_TT);
- dialog.addCheckBox(BEAUTIFY_ENDS, snapEnds, BEAUTIFY_ENDS_TT);
+
+ final JTextField minForkLengthTF =
dialog.addDoubleField(MIN_FORK_LENGTH, forkLengthMul, 12, MIN_FORK_LENGTH_TT);
+ final JRadioButton mflFromMinWidthJRB =
dialog.addRadioButton(MIN_FORK_LENGTH_FROM_MEAN_WIDTH,
+ "fork-length-units", fromMeanWidth,
MIN_FORK_LENGTH_FROM_MEAN_WIDTH_TT);
+ final JRadioButton mflFromMapUnitsJRB =
dialog.addRadioButton(MIN_FORK_LENGTH_IN_MAP_UNITS,
+ "fork-length-units", fromMapUnits,
MIN_FORK_LENGTH_IN_MAP_UNITS_TT);
+
+ dialog.addCheckBox(SNAP_TO_BOUNDARY, snapEnds, SNAP_TO_BOUNDARY_TT);
dialog.addCheckBox(DISPLAY_VORONOI_EDGES, displayVoronoiEdges);
- minWidthTF.setEnabled(!autoJcb.isSelected());
- minForkLengthTF.setEnabled(!autoJcb.isSelected());
- autoJcb.addActionListener(new ActionListener() {
+ minWidthTF.setEnabled(!autoWidthJcb.isSelected());
+ autoWidthJcb.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
- minWidthTF.setEnabled(!autoJcb.isSelected());
- minForkLengthTF.setEnabled(!autoJcb.isSelected());
+ minWidthTF.setEnabled(!autoWidthJcb.isSelected());
}
});
}
@@ -120,11 +135,12 @@
private void getDialogValues(MultiInputDialog dialog) {
layerName = dialog.getLayer(SOURCE_LAYER).getName();
- autoParameters = dialog.getBoolean(AUTO_PARAMETERS);
+ autoWidth = dialog.getBoolean(AUTO_WIDTH_PARAMETER);
minWidth = dialog.getDouble(MIN_WIDTH);
- iterations = dialog.getInteger(ITERATIONS);
- minForkLength = dialog.getDouble(MIN_FORK_LENGTH);
- snapEnds = dialog.getBoolean(BEAUTIFY_ENDS);
+ forkLengthMul = dialog.getDouble(MIN_FORK_LENGTH);
+ fromMeanWidth = dialog.getBoolean(MIN_FORK_LENGTH_FROM_MEAN_WIDTH);
+ fromMapUnits = dialog.getBoolean(MIN_FORK_LENGTH_IN_MAP_UNITS);
+ snapEnds = dialog.getBoolean(SNAP_TO_BOUNDARY);
displayVoronoiEdges = dialog.getBoolean(DISPLAY_VORONOI_EDGES);
}
@@ -132,7 +148,13 @@
monitor.report(SKELETONIZE);
LayerManager layerManager = context.getLayerManager();
FeatureCollection inputFC =
layerManager.getLayer(layerName).getFeatureCollectionWrapper();
- FeatureCollection outputFC = new
FeatureDataset(inputFC.getFeatureSchema());
+ FeatureSchema schema = inputFC.getFeatureSchema().clone();
+ schema.addAttribute("mean_width", AttributeType.DOUBLE);
+ schema.addAttribute("min_width", AttributeType.DOUBLE);
+ schema.addAttribute("min_fork_length", AttributeType.DOUBLE);
+ schema.addAttribute("iteration_number", AttributeType.INTEGER);
+ //schema.addAttribute("snap_ends", AttributeType.BOOLEAN);
+ FeatureCollection outputFC = new FeatureDataset(schema);
int count = 0;
// edges = list to collect original edges from the voronoi diagram
List<Geometry> edges = new ArrayList<Geometry>();
@@ -142,10 +164,24 @@
Geometry geom = feature.getGeometry();
if (!geom.isValid()) geom = geom.buffer(0);
for (int i = 0 ; i < geom.getNumGeometries() ; i++) {
- Feature newFeature = feature.clone(false, false);
+ //Feature newFeature = feature.clone(false, false);
+ Feature newFeature = new BasicFeature(schema);
+ Object[] objects = new Object[schema.getAttributeCount()];
+ System.arraycopy(feature.getAttributes(), 0, objects, 0,
feature.getSchema().getAttributeCount());
+ newFeature.setAttributes(objects);
Geometry g = geom.getGeometryN(i);
- computeAutoParams(g);
- newFeature.setGeometry(skeletonize(g, edges));
+ try {
+ computeParams(g);
+ } catch (Exception e) {
+ context.getWorkbenchFrame().warnUser(e.getMessage());
+ }
+ newFeature.setAttribute("mean_width", meanWidth);
+ newFeature.setAttribute("min_width", minWidth);
+ newFeature.setAttribute("min_fork_length", minForkLength);
+ g = skeletonize(g, edges);
+ newFeature.setGeometry(g);
+ newFeature.setAttribute("iteration_number",
g.getUserData());
+ g.setUserData(null);
outputFC.add(newFeature);
}
} else {
@@ -158,31 +194,41 @@
if (edges.size() > 0) {
layerManager.addLayer(StandardCategoryNames.RESULT, layerName + "
- voronoi-edges",
FeatureDatasetFactory.createFromGeometry(edges));
+ //if (debugGeometries.size() > 0) {
+ // layerManager.addLayer(StandardCategoryNames.RESULT,
layerName + " - debug",
+ //
FeatureDatasetFactory.createFromGeometry(debugGeometries));
+ //}
}
}
// Get minWidth and meanWidth from the geometry
- private void computeAutoParams(Geometry geometry) throws Exception {
- if (autoParameters) {
- double meanWidth = getMeanWidth(geometry);
- if (meanWidth==0) meanWidth =
geometry.getLength()/geometry.getNumPoints()/5;
- minForkLength = 2*meanWidth;
+ private void computeParams(Geometry geometry) throws Exception {
+ meanWidth = getMeanWidth(geometry);
+ double SQRT2 = Math.sqrt(2.0);
+ if (meanWidth==0) meanWidth =
geometry.getLength()/geometry.getNumPoints()/5;
+ if (autoWidth) {
// Iterative function to find the minimal width of the polygon
// A buffer < -minWidth/2 will split the polygon into two polygons
// (except in polygons with holes where)
int numGeometries = geometry.getNumGeometries();
- double buffParam = meanWidth/2;
- Geometry buffer = geometry.buffer(-buffParam);
- while (buffer.getNumGeometries() > numGeometries) {
- buffParam = buffParam/2;
- buffer = geometry.buffer(-buffParam);
- if (buffParam < meanWidth/128) {
- System.out.println("Problem with geometry " + geometry);
- break;
- }
+ double semiMinWidth = meanWidth*0.5/64;
+ double originalLength = geometry.getLength();
+ Geometry buffer = geometry.buffer(-semiMinWidth);
+ // Use buffParam as the minimalWidth if
+ // - buffParam split the geometry into several parts
+ // - buffParam reduces boundary length by more than 10%
+ while (buffer.getNumGeometries() == numGeometries &&
buffer.getLength()/originalLength > 0.9) {
+ semiMinWidth = semiMinWidth*SQRT2;
+ buffer = geometry.buffer(-semiMinWidth);
+ //if (buffParam < meanWidth/64) break;
}
- minWidth = 2*buffParam;
+ minWidth = semiMinWidth;
}
+ if (fromMeanWidth) {
+ minForkLength = forkLengthMul*meanWidth;
+ } else if (fromMapUnits) {
+ minForkLength = forkLengthMul;
+ }
}
// Computes the mean width of a polygon
@@ -217,10 +263,10 @@
private Geometry getVoronoiDiagram(Geometry geometry) throws Exception {
if (geometry.isEmpty()) return geometry;
VoronoiDiagramBuilder voronoiBuilder = new VoronoiDiagramBuilder();
+ voronoiBuilder.setTolerance(Math.sqrt(geometry.getArea())/1000000);
voronoiBuilder.setSites(geometry.getFactory().createMultiPoint(geometry.getCoordinates()));
- voronoiBuilder.setTolerance(0);
Envelope env = geometry.getEnvelopeInternal();
- env.expandBy(env.getWidth()/4, env.getHeight()/4);
+ env.expandBy(env.getWidth()/3, env.getHeight()/3);
voronoiBuilder.setClipEnvelope(env);
try {
return voronoiBuilder.getDiagram(geometry.getFactory());
@@ -239,13 +285,10 @@
if (g instanceof GeometryCollection) {
getEdges(g, edges);
}
- else if (g.getDimension() == 0) {
- continue;
- }
else if (g.getDimension() == 1) {
addSegments((LineString)g, edges);
}
- else {
+ else if (g.getDimension() == 2){
Polygon p = (Polygon)g;
addSegments(p.getExteriorRing(), edges);
for (int j = 0 ; j < p.getNumInteriorRing() ; j++) {
@@ -252,6 +295,7 @@
addSegments(p.getInteriorRingN(j), edges);
}
}
+ // do nothing for geometries of dimension 0 (points)
}
}
@@ -325,59 +369,134 @@
//System.out.println("build graph : " +
(System.currentTimeMillis()-t0)/1000);
// 5 - Simplify the graph iteratively
- for (int i = 0 ; i < iterations ; i++) {
- graph = simplify(graph, geometry.getBoundary(), i+1);
+ // In each loop, the method eliminates the shortest branch of each fork
+ int i = 1;
+ Geometry boundary = geometry.getBoundary();
+ for (i = 0; i < maxIterations ; i++) {
+ int edgeNumber = graph.edgeSet().size();
+ graph = simplify(graph, boundary, true);
+ // if simplify() does not remove edges any more, break the loop
+ if (graph.edgeSet().size() == edgeNumber) break;
}
+ graph = simplify(graph, boundary, false);
+ i++;
- // 6 - Simplify the graph even more using forkingFactor
- // build a new array to avoid ConcurrentModificationException
+ // 6 - Beautify ends
List<FeatureAsEdge> finalEdges = new
ArrayList<FeatureAsEdge>(graph.edgeSet());
for (FeatureAsEdge f : finalEdges) {
- int[] dd = getEdgeDegree(graph, f);
- if ((dd[0]==1 || dd[1]==1)) {
- if (f.getGeometry().getLength() < minForkLength) {
- if (dd[0] == 1) graph.removeVertex(graph.getEdgeSource(f));
- if (dd[1] == 1) graph.removeVertex(graph.getEdgeTarget(f));
- graph.removeEdge(f);
- } else if (snapEnds) {
- if (dd[0] == 1 && dd[1] == 1) {
- if (f.getGeometry().getLength() > minWidth*6) {
- CoordinateList cl = new
CoordinateList(f.getGeometry().getCoordinates());
- if (cl.getCoordinate(cl.size() -
2).distance(cl.getCoordinate(cl.size() - 1)) < minWidth * 2) {
- cl.remove(cl.getCoordinate(cl.size() - 1));
- }
- if
(cl.getCoordinate(0).distance(cl.getCoordinate(1)) < minWidth * 2) {
- cl.remove(cl.getCoordinate(0));
- }
- if (cl.size() < f.getGeometry().getNumPoints()) {
-
f.setGeometry(f.getGeometry().getFactory().createLineString(cl.toCoordinateArray()));
- }
- }
- } else if (dd[0] == 1 && f.getGeometry().getNumPoints() >
2) {
- CoordinateList cl = new
CoordinateList(f.getGeometry().getCoordinates());
- if (cl.getCoordinate(0).distance(cl.getCoordinate(1))
< minWidth*2) {
- cl.remove(cl.getCoordinate(0));
-
f.setGeometry(f.getGeometry().getFactory().createLineString(cl.toCoordinateArray()));
- }
- } else if (dd[1] == 1 && f.getGeometry().getNumPoints() >
2) {
- CoordinateList cl = new
CoordinateList(f.getGeometry().getCoordinates());
- if
(cl.getCoordinate(cl.size()-2).distance(cl.getCoordinate(cl.size()-1)) <
minWidth*2) {
- cl.remove(cl.getCoordinate(cl.size()-1));
-
f.setGeometry(f.getGeometry().getFactory().createLineString(cl.toCoordinateArray()));
- }
- }
- }
+
f.setGeometry(TopologyPreservingSimplifier.simplify(f.getGeometry(),
minWidth/5));
+ EdgeNodes nodes = new EdgeNodes(graph, f);
+ if (nodes.srcDegree == 1) {
+ f.setGeometry(snapStart(f.getGeometry(),
geometry.getBoundary(), snapEnds));
}
+ if (nodes.tgtDegree == 1) {
+ f.setGeometry(snapEnd(f.getGeometry(), geometry.getBoundary(),
snapEnds));
+ }
}
+
//System.out.println(String.format("simplify graph : %d",
(System.currentTimeMillis() - t0) / 1000));
- // 7 - Finalise (connect graph ens with geometry boundary)
-
- // 8 - Retourner une geometrie
+ // 7 - Retourner une geometrie
Geometry geom = graph2geometry(graph);
- return TopologyPreservingSimplifier.simplify(geom, minWidth/5);
+ geom = TopologyPreservingSimplifier.simplify(geom, minWidth/5);
+ geom.setUserData(i); // set the number of iteration used
+ return geom;
}
+ private Geometry snapStart(Geometry edge, Geometry boundary, boolean snap)
throws Exception {
+ CoordinateList cl = new CoordinateList(edge.getCoordinates());
+ Coordinate c0 = cl.getCoordinate(0);
+ Coordinate c1 = cl.getCoordinate(1);
+ double segmentLength = c0.distance(c1);
+
+ PointPairDistance ppd = new PointPairDistance();
+ DistanceToPoint.computeDistance(boundary, c1, ppd);
+ double localWidth = ppd.getDistance();
+
+ // Last segment c0-c1 is short compared to local mean width (distance
between c1 and the boundary)
+ if (segmentLength < localWidth*2 && edge.getNumPoints() > 2) {
+ Coordinate c2 = cl.getCoordinate(2);
+ //Returns the unoriented smallest angle between two vectors.
+ double angle = Angle.toDegrees(Angle.angleBetween(c2, c1, c0));
+ // angle between two last segments on a square buffer is typically
135°
+ if (snap && angle < 145) {
+ cl.set(0, extendTo(c2, c1, boundary, ppd.getDistance()/3));
+ } else if (angle < 145) {
+ cl.remove(0);
+ }
+ } else if (snap){
+ cl.add(0, extendTo(c1, c0, boundary, ppd.getDistance()/3));
+ }
+ return edge.getFactory().createLineString(cl.toCoordinateArray());
+ }
+
+ private Geometry snapEnd(Geometry edge, Geometry boundary, boolean snap)
throws Exception {
+ CoordinateList cl = new CoordinateList(edge.getCoordinates());
+ Coordinate c_0 = cl.getCoordinate(cl.size()-1);
+ Coordinate c_1 = cl.getCoordinate(cl.size()-2);
+ double segmentLength = c_0.distance(c_1);
+
+ PointPairDistance ppd = new PointPairDistance();
+ DistanceToPoint.computeDistance(boundary, c_1, ppd);
+ double localWidth = ppd.getDistance();
+ // Last segment c_0-c_1 is short compared to local mean width
(distance between c1 and the boundary)
+ if (segmentLength < localWidth*2 && edge.getNumPoints() > 2) {
+ Coordinate c_2 = cl.getCoordinate(cl.size()-3);
+ double angle = Angle.toDegrees(Angle.angleBetween(c_2, c_1, c_0));
+ // angle between two last segments on a square buffer is typically
135°
+ if (snap && angle < 145) {
+ cl.set(cl.size()-1, extendTo(c_2, c_1, boundary,
ppd.getDistance()/3));
+ } else if (angle < 145){
+ cl.remove(cl.size()-1);
+ }
+ } else if (snap) {
+ cl.add(extendTo(c_1, c_0, boundary, ppd.getDistance()/3));
+ }
+ return edge.getFactory().createLineString(cl.toCoordinateArray());
+ }
+
+ // Extends c0-c1 segment until it crosses boundary.
+ // Returns the first intersection or a coordinate of the boundary close to
this intersection
+ // if distance to the intersection is < tol
+ private Coordinate extendTo(Coordinate c0, Coordinate c1, Geometry
boundary, double tol) throws Exception {
+ Envelope env = boundary.getEnvelopeInternal();
+ double length = Math.max(env.getWidth(), env.getHeight());
+ double segmentLength = c0.distance(c1);
+ Coordinate c2 = new Coordinate(
+ c1.x + (c1.x-c0.x)*length/segmentLength,
+ c1.y + (c1.y-c0.y)*length/segmentLength);
+ Geometry intersection = boundary.getFactory().createLineString(new
Coordinate[]{c1, c2}).intersection(boundary);
+ if (intersection.isEmpty()) {
+ throw new Exception("Extension of segment " + c0 + " - " + c1 + "
does not intersect the geometry boundary");
+ }
+ Coordinate c3 = intersection.getCoordinate();
+ if (intersection.getNumPoints() > 1) {
+ double min = c1.distance(c3);
+ for (Coordinate c : intersection.getCoordinates()) {
+ double d = c1.distance(c);
+ if (d < min) {
+ min = d;
+ c3 = c;
+ }
+ }
+ }
+ return snap(c3, boundary.getCoordinates(), tol);
+ }
+
+ // Snap c to one of cc if one of cc is close enough
+ private Coordinate snap(Coordinate c, Coordinate[] cc, double tol) {
+ double max2 = tol*tol;
+ Coordinate result = c;
+ for (Coordinate v : cc) {
+ double d2 = (c.x-v.x)*(c.x-v.x) + (c.y-v.y)*(c.y-v.y);
+ if (d2 < max2) {
+ max2 = d2;
+ result = v;
+ }
+ }
+ return result;
+ }
+
private Geometry graph2geometry(UndirectedGraph<INode,FeatureAsEdge>
graph) {
Collection<Geometry> lines = new ArrayList<Geometry>();
for (FeatureAsEdge f : graph.edgeSet()) {
@@ -391,17 +510,11 @@
return gf.buildGeometry(lines);
}
- private int[] getEdgeDegree(UndirectedGraph<INode,FeatureAsEdge> graph,
FeatureAsEdge edge) {
- INode source = graph.getEdgeSource(edge);
- INode target = graph.getEdgeTarget(edge);
- return new int[]{graph.degreeOf(source), graph.degreeOf(target)};
- }
private WeightedGraph<INode,FeatureAsEdge> getGraph(Collection<LineString>
edges) {
// Build the graph (with jgrapht library)
FeatureSchema schema = new FeatureSchema();
schema.addAttribute("geometry", AttributeType.GEOMETRY);
- schema.addAttribute("keepit", AttributeType.BOOLEAN);
List<Feature> features = new ArrayList<Feature>();
for (LineString line : edges) {
Feature feature = new BasicFeature(schema);
@@ -411,77 +524,45 @@
return GraphFactory.createGraph(features, false);
}
- // Simplify the edges graph.
- // Remove edges having a node of degree 1 :
- // - if the distance from edge to the geometry boundary is greater than the
- // tolerance (tolerance is relaxed after each iteration)
- // - if it touches another longer edge of degree 1 also close to the
geometry
- // This method is used by skeletonize method in an iterative way.
+
+
+ // Main method for simplification of the skeleton
private UndirectedGraph<INode,FeatureAsEdge> simplify(
- UndirectedGraph<INode,FeatureAsEdge> graph,
- Geometry boundary,
- int iteration) {
+ UndirectedGraph<INode,FeatureAsEdge> graph, Geometry boundary,
boolean iterative) {
if (graph.edgeSet().size()==1) return graph;
- // Mark all edges having a node of degree 1 close to polygon boundary
- for (FeatureAsEdge edge : graph.edgeSet()) {
- INode ini = graph.getEdgeSource(edge);
- INode fin = graph.getEdgeTarget(edge);
- double degreeIni = graph.degreeOf(ini);
- double degreeFin = graph.degreeOf(fin);
- if (degreeIni == 1 && boundary.distance(ini.getGeometry()) <
(Math.min(minWidth*iteration, minForkLength))) {
- edge.setAttribute("keepit", true);
- } else if (degreeFin == 1 && boundary.distance(fin.getGeometry())
< (Math.min(minWidth*iteration, minForkLength))) {
- edge.setAttribute("keepit", true);
- } else if (degreeIni > 1 && degreeFin > 1) {
- edge.setAttribute("keepit", true);
- } else {
- edge.setAttribute("keepit", false);
- }
- }
- // Mark edges of degree 1 touching another longer edge of degree 1
- for (FeatureAsEdge edge : graph.edgeSet()) {
- if ((Boolean)edge.getAttribute("keepit")) {
- INode ini = graph.getEdgeSource(edge);
- INode fin = graph.getEdgeTarget(edge);
- if (graph.degreeOf(ini) > 1 && graph.degreeOf(fin) == 1) {
- for (FeatureAsEdge e : graph.edgesOf(ini)) {
- if (e != edge && (Boolean)e.getAttribute("keepit")) {
- if (graph.degreeOf(graph.getEdgeSource(e))>1 &&
- graph.degreeOf(graph.getEdgeTarget(e))>1)
continue;
- if (edge.getGeometry().getLength() <
e.getGeometry().getLength() &&
- edge.getGeometry().getLength() <
minForkLength) {
- edge.setAttribute("keepit", false);
- continue;
- }
- }
+ Set<FeatureAsEdge> featuresToremove = new HashSet<FeatureAsEdge>();
+ // Traverse all nodes but skip nodes with at least two incident edges
linked
+ // to another edges
+ for (INode node : graph.vertexSet()) {
+ if (graph.degreeOf(node) > 2) { // skip nodes of degree 1
+ FeatureAsEdge candidateForRemoval = null;
+ // We'll analyze terminal segments and try to eliminate the
one with the worst coefficient
+ double worst = 0;
+ // We need to count nonTerminal adjacent segments to skip nodes
+ // located in the middle of the graph
+ int nonTerminalSegmentNumber = 0;
+ // Iterates through incident edges
+ for (FeatureAsEdge e : graph.edgesOf(node)) {
+ EdgeNodes nodes = new EdgeNodes(graph, e);
+ if (nodes.nbOfDegreeN()==2) nonTerminalSegmentNumber++;
+ if (nonTerminalSegmentNumber>1 && iterative) break;
+ if (nodes.nbOfDegree1() != 1) continue;
+ if (e.getGeometry().getLength() > minForkLength) continue;
+ PointPairDistance ppd = new PointPairDistance();
+ DistanceToPoint.computeDistance(boundary,
nodes.getDegree1().getCoordinate(), ppd);
+ double coeff = ppd.getDistance() /
e.getGeometry().getLength();
+ if (coeff > worst) {
+ worst = coeff;
+ candidateForRemoval = e;
}
}
- else if (graph.degreeOf(fin) > 1 && graph.degreeOf(ini) == 1) {
- for (FeatureAsEdge e : graph.edgesOf(fin)) {
- if (e != edge && (Boolean)e.getAttribute("keepit")) {
- if (graph.degreeOf(graph.getEdgeSource(e))>1 &&
- graph.degreeOf(graph.getEdgeTarget(e))>1)
continue;
- if (edge.getGeometry().getLength() <
e.getGeometry().getLength() &&
- edge.getGeometry().getLength() <
minForkLength) {
- edge.setAttribute("keepit", false);
- continue;
- }
- }
- }
+ if (candidateForRemoval != null && (!iterative ||
nonTerminalSegmentNumber < 2)) {
+ featuresToremove.add(candidateForRemoval);
+ //debugGeometries.add(candidateForRemoval.getGeometry());
}
}
}
- // Supprimer les arcs et refusionner le résultat
- //Set<INode> nodesToRemove = new HashSet<INode>();
- Set<FeatureAsEdge> featuresToremove = new HashSet<FeatureAsEdge>();
- for (FeatureAsEdge edge : graph.edgeSet()) {
- if (!(Boolean)edge.getAttribute("keepit") &&
- featuresToremove.size() < graph.edgeSet().size()-1) {
- featuresToremove.add(edge);
- }
- }
graph.removeAllEdges(featuresToremove);
- //graph.removeAllVertices(nodesToRemove);
// merge lines after simplification
Geometry geom = graph2geometry(graph);
@@ -489,34 +570,32 @@
LineMerger merger = new LineMerger();
merger.add(edges);
edges = (List)merger.getMergedLineStrings();
- graph = (UndirectedGraph<INode,FeatureAsEdge>)getGraph(edges);
- return graph;
+ return (UndirectedGraph<INode,FeatureAsEdge>)getGraph(edges);
}
- /*
- private int minDegree(UndirectedGraph<INode,FeatureAsEdge> graph,
FeatureAsEdge edge) {
- return Math.min(
- graph.degreeOf(graph.getEdgeSource(edge)),
- graph.degreeOf(graph.getEdgeTarget(edge)));
+ // A class wrapping both nodes of a edge with their degree
+ public static class EdgeNodes {
+ INode src;
+ INode tgt;
+ int srcDegree;
+ int tgtDegree;
+ EdgeNodes(UndirectedGraph<INode,FeatureAsEdge> graph, FeatureAsEdge
edge) {
+ src = graph.getEdgeSource(edge);
+ tgt = graph.getEdgeTarget(edge);
+ srcDegree = graph.degreeOf(src);
+ tgtDegree = graph.degreeOf(tgt);
+ }
+ int nbOfDegree1() {
+ return (srcDegree==1?1:0) + (tgtDegree==1?1:0);
+ }
+ INode getDegree1() {
+ if (srcDegree == 1) return src;
+ else if (tgtDegree == 1) return tgt;
+ else return null;
+ }
+ int nbOfDegreeN() {
+ return (srcDegree>1?1:0) + (tgtDegree>1?1:0);
+ }
}
- private int minDegree(UndirectedGraph<INode,FeatureAsEdge> graph,
Set<FeatureAsEdge> edgeSet) {
- if (edgeSet.isEmpty()) return 0;
- int min = Integer.MAX_VALUE;
- for (FeatureAsEdge edge : edgeSet) min = Math.min(min,
minDegree(graph, edge));
- return min;
- }
-
- private Set<FeatureAsEdge>
connectedEdges(UndirectedGraph<INode,FeatureAsEdge> graph, FeatureAsEdge edge) {
- if (minDegree(graph,edge)==1) {
- Set<FeatureAsEdge> set = new HashSet<FeatureAsEdge>();
- set.addAll(graph.edgesOf(graph.getEdgeSource(edge)));
- set.addAll(graph.edgesOf(graph.getEdgeTarget(edge)));
- set.remove(edge);
- return set;
- } else {throw new IllegalArgumentException("The method is only defined
for edges of degree 1");}
- }
- */
-
-
}
Modified:
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph.properties
===================================================================
---
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph.properties
2017-06-10 15:12:55 UTC (rev 5461)
+++
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph.properties
2017-06-10 20:39:31 UTC (rev 5462)
@@ -126,16 +126,20 @@
SkeletonPlugIn = Skeleton
SkeletonPlugIn.skeletonize = Skeletonize
SkeletonPlugIn.source-layer = Source layer
-SkeletonPlugIn.auto-parameters = Parameters by feature
-SkeletonPlugIn.auto-parameters-tooltip = Compute automatic parameters for each
feature
+SkeletonPlugIn.auto-width-parameter = Automatic width computation
+SkeletonPlugIn.auto-width-parameter-tooltip = Computes automatically a minimum
width for each feature
SkeletonPlugIn.min-width = Minimum width
SkeletonPlugIn.min-width-tooltip = Boundary is densified according to this
parameter
-SkeletonPlugIn.iterations = Number of iterations
-SkeletonPlugIn.iterations-tooltip = Increase the number of iteration to remove
small forks without truncating main fork
-SkeletonPlugIn.min-fork-length = Minimum length of secondary forks
-SkeletonPlugIn.min-fork-length-tooltip = Decrease this parameter to keep more
forks
-SkeletonPlugIn.beautify-ends = Truncate small ending segments
-SkeletonPlugIn.beautify-ends-tooltip = Ending segments shorter than 2*min
width often look like artefacts
+
+SkeletonPlugIn.min-fork-length = Minimum length of forks
+SkeletonPlugIn.min-fork-length-tooltip = Minimum length of forks
+SkeletonPlugIn.min-fork-length-from-mean-width = ...relative to mean width
+SkeletonPlugIn.min-fork-length-from-mean-width-tooltip = Minimum length of
forks is a multiplicative factor relative to mean feature width
+SkeletonPlugIn.min-fork-length-in-map-units = ...in map units
+SkeletonPlugIn.min-fork-length-in-map-units-tooltip = Minimum length of forks
is in map units
+
+SkeletonPlugIn.snap-to_boundary = Snap edge ends to polygon boundary
+SkeletonPlugIn.snap-to_boundary-tooltip = Snap edge ends to polygon boundary
SkeletonPlugIn.display-voronoi-edges = Display a layer with initial voronoi
edges
SkeletonPlugIn.description = Polygon Skeletonizer\n\
- Parameters by feature will automatically compute suitable parameters for
each feature\n\
@@ -162,6 +166,7 @@
HydrographicNetworkAnalysisPlugIn.z-anomaly = z-anomaly
HydrographicNetworkAnalysisPlugIn.cycle-anomaly = cycle-anomaly
HydrographicNetworkAnalysisPlugIn.node-anomaly = node-anomaly
+HydrographicNetworkAnalysisPlugIn.reversed-edge = reversed-edge
HydrographicNetworkAnalysisPlugIn.Source = Source
HydrographicNetworkAnalysisPlugIn.Sink = Sink
HydrographicNetworkAnalysisPlugIn.Cycle = Cycle
Modified:
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph_fr.properties
===================================================================
---
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph_fr.properties
2017-06-10 15:12:55 UTC (rev 5461)
+++
plug-ins/GraphToolboxPlugin/trunk/src/fr/michaelm/jump/plugin/graph/graph_fr.properties
2017-06-10 20:39:31 UTC (rev 5462)
@@ -127,16 +127,20 @@
SkeletonPlugIn = Squelettisation
SkeletonPlugIn.skeletonize = Squelettiser
SkeletonPlugIn.source-layer = Couche source
-SkeletonPlugIn.auto-parameters = Param\xE8tres automatiques par objet
-SkeletonPlugIn.auto-parameters-tooltip = Calcul des param\xE8tres automatiques
pour chaque objet
-SkeletonPlugIn.min-width = Largeur minimum
+SkeletonPlugIn.auto-width-parameter = Largeur minimale automatique
+SkeletonPlugIn.auto-width-parameter-tooltip = Calcul automatiquement une
largeur minimale adapt\xE9e \xE0 chaque objet
+SkeletonPlugIn.min-width = Largeur minimale
SkeletonPlugIn.min-width-tooltip = La fronti\xE8re est densifi\xE9e en
fonction de se param\xE8tre
-SkeletonPlugIn.iterations = Nombre d'iterations
-SkeletonPlugIn.iterations-tooltip = Augmenter le nombre d'it\xE9rations pour
enlever les petits embranchements sans toucher aux plus longs
-SkeletonPlugIn.min-fork-length = Longueur minimum des embranchements
secondaires
-SkeletonPlugIn.min-fork-length-tooltip = Baisser ce param\xE8tre pour
conserver plus d'embranchements
-SkeletonPlugIn.beautify-ends = Supprimer les artefacts aux extr\xE9mit\xE9s
-SkeletonPlugIn.beautify-ends-tooltip = Tronque les petits artefacts situ\xE9s
aux terminaisons du squelette
+
+SkeletonPlugIn.min-fork-length = Longueur minimale des embranchements
+SkeletonPlugIn.min-fork-length-tooltip = Longueur minimale des embranchements
+SkeletonPlugIn.min-fork-length-from-mean-width = ...relativement \xE0 la
largeur moyenne
+SkeletonPlugIn.min-fork-length-from-mean-width-tooltip = La longueur minimale
des embranchements est relative au param\xE8tre de largeur moyenne
+SkeletonPlugIn.min-fork-length-in-map-units = ...en unit\xE9s de la carte
+SkeletonPlugIn.min-fork-length-in-map-units-tooltip = La longueur minimale des
embranchements est relative \xE0 l'unit\xE9 de la carte
+
+SkeletonPlugIn.snap-to_boundary = Prolonger les extr\xE9mit\xE9s jusqu'au bord
+SkeletonPlugIn.snap-to_boundary-tooltip = Prolonge les extr\xE9mit\xE9s
jusqu'au bord de la surface
SkeletonPlugIn.display-voronoi-edges = Cr\xE9er une couche avec les ar\xEAtes
de Voronoi initiale
SkeletonPlugIn.description = Skelettisation\n\
- Les param\xE8res automatiques sont d\xE9termin\xE9s en fonction des
caract\xE9ristiques de chaque objet\n\
@@ -163,6 +167,7 @@
HydrographicNetworkAnalysisPlugIn.z-anomaly = anomalie-z
HydrographicNetworkAnalysisPlugIn.cycle-anomaly = anomalie-cycle
HydrographicNetworkAnalysisPlugIn.node-anomaly = anomalie-n\u0153ud
+HydrographicNetworkAnalysisPlugIn.reversed-edge = arcs-invers\xE9s
HydrographicNetworkAnalysisPlugIn.Source = Source
HydrographicNetworkAnalysisPlugIn.Sink = Puits
HydrographicNetworkAnalysisPlugIn.Cycle = Cycle
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
