1. Algorithm background
At present, many projects require the ability to plan routes. There are many open source map SDKs or paid SDKs that can achieve this. The user selects the starting point, end point and route points to plan the route the user wants, but the ability to identify intersections is average. It is not available. Here I just introduce the algorithm I used in project development to support intersection recognition and the corresponding sequence.
2. Basic environment
JDK version: 1.8
Map SDK: Dugis (Baidu offline map is a paid SDK. It only uses route planning capabilities and can be replaced with other map SDKs)
Geometric calculation tool: JTS (Dugis itself has the capability of geometric calculation, but this algorithm requires a lot of calculations, and calling the SDK takes a long time, so JTS is selected to calculate in memory)
3. Plan routes and identify intersections
The planned route identification of intersections is based on the point coordinates of all intersections in the known area. There is a high probability that the planned route will not pass the coordinate points of the intersection when it passes the intersection. After all, the intersection coordinate is a point, and the real intersection is an area. This algorithm defines a The threshold K (the area buffered by the intersection coordinate point with the radius K) is used to identify the intersection, and then the distance S (1) The intersection is actually quite large, and the area buffered by the intersection cannot cover the entire intersection; (2) There is a auxiliary road intersection next to the intersection, and it is two intersections with the main intersection, within the threshold K; (3) The threshold K is set larger, and its buffer area covers multiple intersections (non-auxiliary road intersections); To solve the above problem, it is necessary to set a basic threshold K and a threshold K’ unique to the special intersection. K’ has a higher priority and is calculated differently when identifying intersections on the line;
Specific algorithm steps:
1. Plan a complete set of route points through the Dugis route;
2. Calculate the shortest distance between all intersections and the route;
The JTS tool used here is used for calculation. Since the input parameter is the coordinate output parameter and not the distance, it needs to be converted and multiplied by a coefficient C;
/**
* Angle to meter coefficient
*/
private static final double C = 111120.0;
private static GeometryFactory geometryFactory = JTSFactoryFinder.getGeometryFactory( null );
private static WKTReader reader = new WKTReader(geometryFactory);
/**
* @Description Calculate the minimum distance between coordinate points and lines
* @param pointKwt Point longitude and latitude (WKT format)
* @param lineKwt Line longitude and latitude (WKT format)
* @return java.lang.Double
*/
public static Double pointToLineDistance(String pointKwt, String lineKwt) {
try {
Point point = (Point) reader.read(pointKwt);
LineString line = (LineString) reader.read(lineKwt);
return DistanceOp.distance(point, line) * C;
} catch (ParseException e) {
log.error("pointToLineDistance ParseException:", e);
}
return Double.MAX_VALUE;
}
3. Filter the intersections that meet the requirements through the thresholds K and K’;
3. Calculate the order of intersection routes
Idea one:
If the plan is a straight line, then the sequence of intersections can be calculated by calculating the distance from each intersection to the starting intersection and sorted in increasing order of distance, that is, the sequence of route intersections. The disadvantage is that the route cannot have turns, otherwise the calculation may not be accurate;
Idea two:
Optimize the first idea, because when planning routes, route points are generally selected to constrain the route and make it meet the needs of the user, and most of them are distributed at inflection points. Divide the entire route into route points, use the method of idea 1 to sort each section of the route, and finally integrate and remove duplicates to obtain the complete sequence of route intersections;
Idea three:
The road division in each area is not a horizontal and vertical road. Some roads are curved or irregular road distribution. Calculating the straight-line distance from point to point cannot obtain the correct intersection sequence, so it is necessary to calculate the curve length of the route. The sub-line segmentation in JTS is introduced here, that is, the length of the curve between all intersections other than the starting point and the closest point on the route to the starting intersection is calculated, and sorted to obtain the order of the corresponding intersections.
/**
* Get the closest point from a certain point to the points included in the line
* @param point
* @param lineString
* @return
*/
public static Geolocation getNearestPointToLine(Geolocation point, LineString lineString) {
try {
Coordinate coordinate = new Coordinate(point.getLongitude(), point.getLatitude());
PointPairDistance ppd = new PointPairDistance();
DistanceToPoint.computeDistance(lineString, coordinate, ppd);
Coordinate[] coordinates = ppd.getCoordinates();
if (Objects.nonNull(coordinate) & amp; & amp; coordinates.length > 0) {
Coordinate nearestPoint = coordinates[0];
return new Geolocation(nearestPoint.getX(), nearestPoint.getY());
}
} catch (Exception e) {
log.error(e.getMessage(), e);
}
return null;
}
The following solution is used to obtain sub-lines. Specifically, it needs to be nested based on the business in your own project. There will be corresponding lengths in the sub-lines.
GeometryFactory GeometryFactory = new GeometryFactory();
WKTReader reader = new WKTReader(GeometryFactory);
Geometry geom = reader.read("LINESTRING(0 0, 10 0, 10 10, 20 10)");
LocationIndexedLine lil = new LocationIndexedLine(geom);
LinearLocation start = lil.indexOf(new Coordinate(8, 5));
LinearLocation end = lil.indexOf(new Coordinate(17, 10));
Geometry result = lil.extractLine(start, end);
System.out.println(result.toText());
System.out.println("Sub-line length: " + result.getLength);
// result
LINESTRING (10 5, 10 10, 17 10)
Idea four:
The intersection recognition sequence in the third idea is relatively accurate, but if an intersection is passed twice or multiple times, the order of passing intersections will be inaccurate. There will only be one closest point between the calculated intersection coordinates and the planned route, and it is impossible to identify the situation where the intersection has passed multiple times. In order to solve this problem, a geometric concept is introduced here. When a line passes through a circle, it will produce two intersections with the circle. Intersection point, after passing it twice, there will be four intersection points (if you pass it twice and do not go out, there will be three intersection points), so we know that when the number of intersections N > 2, it means that the intersection has been passed multiple times. Divide the intersection points into sub-lines and sort the sub-line lengths to get the order of intersections. However, there will be duplicate intersections, which need to be removed. The principle of deduplication is that two adjacent intersections cannot be consistent, that is, the intersections are separated by One or more intersections can be repeated, thus obtaining a complete intersection sequence; however, in actual development, buffering the coordinate points of the intersection with the threshold K or K’ as the radius does not result in a perfect circle but a perfect circle. Similar to an ellipse. When calculating the intersection between the route and the buffer zone, the number of intersections obtained does not meet our expectations; if the number of intersections between the route and the buffer zone is N >= 2, intersection points will also appear in the buffer zone. At this time, two solutions can be considered plan.
Solution 1: Divide all intersections between the line and the buffer into sub-lines and sort them to remove duplicates.
Option 2: Obtain the outer boundary of the buffer, which is in line with our assumption. After two intersections appear at one time, the intersections with intersection times N > 2 will be segmented and sorted by intersection sub-lines to remove duplicates, while intersections with N == 2 will not be considered;
The above is my sharing this time. I welcome everyone who has a new algorithm to calculate the order of identifying intersections to leave a message in the comment area. Finally, I attach part of my development code. There will be some other attribute data in the object, which does not affect the algorithm idea. ;
/**
* @Description The latest calculated route passes through the intersection (supports multiple intersections)
* @param pointList A list of intersections that meet the threshold K or K' - unordered
* @param lineStr WKT format string of planned route
* @param passPoint list of pass points (the beginning and end are the starting and ending intersections, and the period is the pass points size >= 2)
* @param coverThreshold threshold K (K' is not configured here, you can get K at the intersection if needed)
*/
public static List<LinePointVO> calculationCrossSeq(List<DirectionDTO> pointList, String lineStr,
List<LinePointVO> passPoint, Double coverThreshold) {
LinePointVO startCross = passPoint.get(0);
LinePointVO endCross = passPoint.get(passPoint.size() - 1);
LocationIndexedLine line;
Geometry geom;
try {
geom = reader.read(lineStr);
line = new LocationIndexedLine(geom);
} catch (ParseException e) {
log.error("calculationCrossSeq ParseException:", e);
throw new RuntimeException("calculationCrossSeq ParseException:" + e);
}
Geolocation startPoint = startCross.getGeolocation();
LinearLocation start = line.indexOf(new Coordinate(startPoint.getLongitude(), startPoint.getLatitude()));
List<DirectionDTO> subLineLengts = Lists.newArrayList();
for (DirectionDTO dto : pointList) {
Geometry buffer = createPointBuffer(dto.getPoint(), coverThreshold);
Geometry intersections = geom.intersection(buffer);
for(Coordinate coord : intersections.getCoordinates()){
DirectionDTO intersect = new DirectionDTO();
BeanUtils.copyProperties(dto, intersect);
LinearLocation end = line.indexOf(new Coordinate(coord.x, coord.y));
Geometry extractLine = line.extractLine(start, end);
Double dis = extractLine.getLength();
intersect.setDistance(dis);
subLineLengts.add(intersect);
}
}
subLineLengts = subLineLengts.stream().sorted(Comparator.comparing(DirectionDTO::getDistance))
.collect(Collectors.toList());
pointList = removeAdjacentToSameCross(subLineLengts);
List<LinePointVO> list = pointList.stream().sorted(Comparator.comparing(DirectionDTO::getDistance)).map(o -> {
LinePointVO vo = new LinePointVO();
vo.setCrossId(o.getCrossId());
vo.setCrossName(o.getName());
vo.setCrossType(o.getCrossType());
vo.setGeolocation(WKTUtil.point2location(o.getPoint()));
returnvo;
}).collect(Collectors.toList());
List<LinePointVO> resList = Lists.newArrayList();
if (!startCross.getCrossId().equals(list.get(0).getCrossId())) {
resList.add(startCross);
}
resList.addAll(list);
if (!endCross.getCrossId().equals(resList.get(resList.size() - 1).getCrossId())) {
resList.add(endCross);
}
return resList;
}
/**
* @Description The coordinate points are buffered into a surface (polygon - similar to an ellipse) according to the radius.
* @param point coordinate point-WKT format
* @param r radius-meters
*/
public static Geometry createPointBuffer(String point, double r) {
try {
BigDecimal factor = new BigDecimal(Double.toString(C));
BigDecimal radius = new BigDecimal(Double.toString(r));
double distance = radius.divide(factor, 10, BigDecimal.ROUND_HALF_UP).doubleValue();
Geometry geomPoint = reader.read(point);
Geometry buffer = geomPoint.buffer(distance);
return buffer;
} catch (ParseException e) {
throw new RuntimeException("createPointBuffer ParseException:" + e);
}
}
/**
* @Description The coordinate points are buffered into a ring according to the radius
* @param point coordinate point-WKT format
* @param r radius-meters
*/
public static Geometry createPointBufferToLineRing(String point, double r) {
try {
BigDecimal factor = new BigDecimal(Double.toString(C));
BigDecimal radius = new BigDecimal(Double.toString(r));
double distance = radius.divide(factor, 10, BigDecimal.ROUND_HALF_UP).doubleValue();
Geometry geomPoint = reader.read(point);
Geometry buffer = geomPoint.buffer(distance);
String ring = WKTUtil.polygon2Linearring(buffer.toString());
Geometry lineRing = reader.read(ring);
return lineRing;
} catch (ParseException e) {
throw new RuntimeException("createPointBufferToLineRing ParseException:" + e);
}
}
/**
* @Description Remove two adjacent intersections that are the same
* @param list
*/
private static List<DirectionDTO> removeAdjacentToSameCross(List<DirectionDTO> list) {
List<DirectionDTO> resList = Lists.newArrayList();
for (int i = 0; i < list.size(); i + + ) {
if (CollectionUtils.isEmpty(resList) ||
!resList.get(resList.size() - 1).getCrossId().equals(list.get(i).getCrossId())) {
resList.add(list.get(i));
}
}
return resList;
}