# Densifying JTS LINESTRING (add points)?

I have a LineString I would like to "soften" in a way that if two coordinates (vertices) in the LineString are very far apart, I want to automatically add some coordinates in between.

The line string should stay the same but with more coordinates describing it. Do you know of a way? I have a LineString like the one on the left - and I want to add some coordinates in the between the existing coordinates (like on the right) - hopefully by JTS and hopefully automatically.

The algorithm for line densification isn't all that difficult (Pythagorean theorem for length and prorate dX and dY at the same ratio). The only tricky part is deciding between even distribution of spacing, or a fixed interval along the middle. You should evaluate the output of the existing method available within JTS before coding your own.

The problem becomes more complex when the coordinates are in decimal degrees (especially over long distances), in which case the spheroidal length is needed (inverse geodetic problem), and the intervening vertices must be solved along the great circle route using the forward geodetic problem (there are simpler spherical solutions, but they are less accurate). These algorithms have posted solutions within GSE.

I wrote this method which does the trick using JTS:

``````public LineString refineLineString(LineString ls, double maximalDistance){
// list to store coordinates for resulting line string
ArrayList<Coordinate> resultLineStringCoordinates = new ArrayList();
// list of LineSegments from input LineString
ArrayList<LineSegment> segmentList = new ArrayList();
for(int i = 1; i < ls.getCoordinates().length; i++){
// create LineSegments from input LineString and add them to list
}
boolean isFirstSegment = true;
// refine each LineSegment if necessary
for(LineSegment currentSegment : segmentList){
// add startpoint from first segment only
if(isFirstSegment){
isFirstSegment = false;
}
// refinement necessary
if(currentSegment.getLength() > maximalDistance){
// calculate distance between coordinates as fraction (0-1)
double distanceFraction = 1 / (currentSegment.getLength()/maximalDistance);
for(double currentFraction = distanceFraction; currentFraction < 1; currentFraction += distanceFraction){
// add coordinates from calculated fraction
}
}
// add segment endpoint coordinate to result list
}
return new GeometryFactory().createLineString(resultLineStringCoordinates.toArray(new Coordinate[resultLineStringCoordinates.size()]));
}
``````

Note that the last part of a segment can be smaller than the rest (rest is equal to maximalDistance). If you prefer equal distances along one segment over setting the distances to maximalDistance you just have to adjust the calculation of distanceFraction.

Simple example:

``````LineString lineA = new GeometryFactory().createLineString(new Coordinate[]{new Coordinate(0, 0), new Coordinate(0, 10), new Coordinate(5, 10)});
System.out.println("LineString before refinement: " + lineA.toText());
LineString refined = Test.refineLineString(lineA, 1.5);
System.out.println("LineString ater refinement: " + refined.toText());
``````

Output:

``````LineString before refinement: LINESTRING (0 0, 0 10, 5 10)
LineString ater refinement: LINESTRING (0 0, 0 1.5, 0 3, 0 4.5, 0 6, 0 7.5, 0 9, 0 10, 1.5 10, 3 10, 4.5 10, 5 10)
``````

OpenJUMP has a "densifier" function in Tools-Analysis-Geometry functions. The source code (GPL licensed) of the tool is in http://sourceforge.net/p/jump-pilot/code/HEAD/tree/core/trunk/src/com/vividsolutions/jump/algorithm/Densifier.java. I believe it will help you.

Here's my solution for the same problem: https://github.com/mcserby/tools

I am splitting the lineString into lineSegments, calculate total lenght of the line string and the "step" size, and then extract the coordinates at the "step" intervals on the line string.

See the class below:

``````package com.fci.graphic;

import java.util.ArrayList;
import java.util.List;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.LineSegment;
import com.vividsolutions.jts.geom.LineString;

public class EchidistantPointsCalculator {

public static List<Coordinate> findEchidistantPoints(LineString lineString, int resolution) {
List<LineSegment> lineSegments = buildLineSegments(lineString);
double lineStringLength = lineSegments.parallelStream().mapToDouble(l -> l.getLength()).sum();
double stepSize = lineStringLength / resolution;
List<Coordinate> coords = new ArrayList<>();
double startingDistance = 0;
for(LineSegment ls : lineSegments){
SegmetData segmentData = processSegment(ls, stepSize, startingDistance);
startingDistance = segmentData.getNextStartingDistance();
}
return coords;

}

private static SegmetData processSegment(LineSegment segment, double stepSize,
double currentDistance) {
List<Coordinate> coords = new ArrayList<>();
LineSegment remainingSegment = new LineSegment(segment);
double remainingLength = remainingSegment.getLength();
while(remainingLength >= currentDistance){
Coordinate c = remainingSegment.pointAlong(currentDistance/remainingLength);
currentDistance = stepSize;
remainingSegment = new LineSegment(c, remainingSegment.p1);
remainingLength = remainingSegment.getLength();
}
return new SegmetData(coords, remainingLength);
}

private static List<LineSegment> buildLineSegments(LineString lineString) {
Coordinate[] coords = lineString.getCoordinates();
List<LineSegment> segments = new ArrayList<>();
for(int i = 0; i < coords.length - 1; i++){