package lujing;
|
|
import java.util.ArrayList;
|
import java.util.Collections;
|
import java.util.Comparator;
|
import java.util.List;
|
|
import org.locationtech.jts.geom.Coordinate;
|
import org.locationtech.jts.geom.Geometry;
|
import org.locationtech.jts.geom.LinearRing;
|
import org.locationtech.jts.geom.Polygon;
|
import org.locationtech.jts.geom.TopologyException;
|
import org.locationtech.jts.operation.buffer.BufferParameters;
|
|
import lujing.Lunjingguihua.PathSegment;
|
|
/**
|
* Utility class that produces spiral mowing paths by iteratively offsetting a safe area polygon.
|
* 优化版：改进路径生成逻辑，减少空驶距离，优化路径连续性
|
*/
|
public final class luoxuan {
|
|
private static final int MAX_ITERATIONS = 512;
|
private static final double AREA_EPSILON = 1e-2;
|
private static final double LENGTH_EPSILON = 1e-6;
|
private static final double MIN_BUFFER_RATIO = 0.6; // 最小缓冲比例
|
|
private luoxuan() {
|
}
|
|
/**
|
* Generate optimized spiral mowing paths with improved continuity
|
*/
|
public static List<PathSegment> generateOptimizedSpiralPath(Geometry safeArea, double laneWidth) {
|
if (safeArea == null || safeArea.isEmpty() || !Double.isFinite(laneWidth) || laneWidth <= 0) {
|
return Collections.emptyList();
|
}
|
|
// 1. 清理几何体，确保有效性
|
Geometry working = cleanGeometry(safeArea);
|
if (working.isEmpty()) {
|
return Collections.emptyList();
|
}
|
|
// 2. 提取主多边形（选择面积最大的）
|
Polygon mainPolygon = extractMainPolygon(working);
|
if (mainPolygon == null) {
|
return Collections.emptyList();
|
}
|
|
// 3. 计算螺旋路径
|
List<PathSegment> segments = new ArrayList<>();
|
Coordinate cursor = clone(findOptimalStartPoint(mainPolygon));
|
Geometry currentLayer = mainPolygon; // start from the outer boundaryand peel inwards
|
|
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
|
Geometry layerGeometry = cleanGeometry(currentLayer);
|
if (layerGeometry == null || layerGeometry.isEmpty()) {
|
break;
|
}
|
|
List<Polygon> polygons = extractPolygons(layerGeometry);
|
if (polygons.isEmpty()) {
|
break;
|
}
|
polygons.sort(Comparator.comparingDouble(Polygon::getArea).reversed());
|
|
try {
|
for (Polygon polygon : polygons) {
|
LinearRing outer = polygon.getExteriorRing();
|
if (outer == null || outer.getNumPoints() < 4) {
|
continue;
|
}
|
|
cursor = processRing(outer.getCoordinates(), true, cursor, segments);
|
|
for (int holeIndex = 0; holeIndex < polygon.getNumInteriorRing(); holeIndex++) {
|
LinearRing hole = polygon.getInteriorRingN(holeIndex);
|
if (hole == null || hole.getNumPoints() < 4) {
|
continue;
|
}
|
cursor = processRing(hole.getCoordinates(), false, cursor, segments);
|
}
|
}
|
} catch (TopologyException ex) {
|
break;
|
}
|
|
if (!canShrinkFurther(polygons, laneWidth)) {
|
break;
|
}
|
|
Geometry nextLayer;
|
try {
|
nextLayer = layerGeometry.buffer(
|
-laneWidth,
|
BufferParameters.DEFAULT_QUADRANT_SEGMENTS,
|
BufferParameters.CAP_FLAT
|
);
|
} catch (TopologyException ex) {
|
break;
|
}
|
|
if (nextLayer.isEmpty() || nextLayer.getArea() < AREA_EPSILON) {
|
break;
|
}
|
|
double areaDelta = Math.abs(layerGeometry.getArea() - nextLayer.getArea());
|
if (areaDelta <= AREA_EPSILON) {
|
break;
|
}
|
|
currentLayer = nextLayer;
|
}
|
|
// 4. 优化路径连接
|
optimizePathConnections(segments);
|
|
// 5. 标记端点
|
markEndpoints(segments);
|
|
return segments;
|
}
|
|
/**
|
* Backward compatible entry that delegates to the optimized implementation.
|
*/
|
public static List<PathSegment> generateSpiralPath(Geometry safeArea, double laneWidth) {
|
return generateOptimizedSpiralPath(safeArea, laneWidth);
|
}
|
|
/**
|
* 清理几何体，确保有效性
|
*/
|
private static Geometry cleanGeometry(Geometry geometry) {
|
if (geometry == null) return null;
|
try {
|
return geometry.buffer(0.0);
|
} catch (Exception e) {
|
return geometry;
|
}
|
}
|
|
/**
|
* 提取主多边形（面积最大的）
|
*/
|
private static Polygon extractMainPolygon(Geometry geometry) {
|
List<Polygon> polygons = extractPolygons(geometry);
|
if (polygons.isEmpty()) return null;
|
|
// 按面积排序，选择最大的
|
polygons.sort((p1, p2) -> Double.compare(p2.getArea(), p1.getArea()));
|
return polygons.get(0);
|
}
|
|
/**
|
* 寻找最优起点（离多边形中心最近的点）
|
*/
|
private static Coordinate findOptimalStartPoint(Polygon polygon) {
|
if (polygon == null) return null;
|
|
Coordinate center = polygon.getCentroid().getCoordinate();
|
LinearRing ring = polygon.getExteriorRing();
|
Coordinate[] coords = ring.getCoordinates();
|
|
Coordinate nearest = coords[0];
|
double minDist = Double.MAX_VALUE;
|
|
for (Coordinate coord : coords) {
|
double dist = coord.distance(center);
|
if (dist < minDist) {
|
minDist = dist;
|
nearest = coord;
|
}
|
}
|
|
return nearest;
|
}
|
|
/**
|
* 优化路径连接，减少空驶距离
|
*/
|
private static void optimizePathConnections(List<PathSegment> segments) {
|
if (segments == null || segments.size() < 2) {
|
return;
|
}
|
|
List<PathSegment> optimized = new ArrayList<>(segments.size());
|
PathSegment previous = null;
|
|
for (PathSegment segment : segments) {
|
if (segment == null || segment.start == null || segment.end == null) {
|
continue;
|
}
|
if (isDegenerate(segment)) {
|
continue;
|
}
|
|
if (previous != null
|
&& previous.isMowing == segment.isMowing
|
&& equals2D(previous.start, segment.start)
|
&& equals2D(previous.end, segment.end)) {
|
continue; // 跳过重复段
|
}
|
|
optimized.add(segment);
|
previous = segment;
|
}
|
|
segments.clear();
|
segments.addAll(optimized);
|
}
|
|
/**
|
* 检查是否可以继续缓冲
|
*/
|
private static boolean canShrinkFurther(List<Polygon> polygons, double bufferDistance) {
|
if (polygons == null || polygons.isEmpty()) {
|
return false;
|
}
|
|
for (Polygon polygon : polygons) {
|
if (polygon == null || polygon.isEmpty()) {
|
continue;
|
}
|
|
double width = polygon.getEnvelopeInternal().getWidth();
|
double height = polygon.getEnvelopeInternal().getHeight();
|
double minDimension = Math.min(width, height);
|
|
if (minDimension <= bufferDistance * 2 * MIN_BUFFER_RATIO) {
|
return false;
|
}
|
}
|
|
return true;
|
}
|
|
/**
|
* 标记起点和终点
|
*/
|
private static void markEndpoints(List<PathSegment> segments) {
|
if (segments == null || segments.isEmpty()) {
|
return;
|
}
|
|
// 寻找第一个割草段作为起点
|
PathSegment firstMowing = null;
|
for (PathSegment seg : segments) {
|
if (seg != null && seg.isMowing) {
|
firstMowing = seg;
|
break;
|
}
|
}
|
|
// 寻找最后一个割草段作为终点
|
PathSegment lastMowing = null;
|
for (int i = segments.size() - 1; i >= 0; i--) {
|
PathSegment seg = segments.get(i);
|
if (seg != null && seg.isMowing) {
|
lastMowing = seg;
|
break;
|
}
|
}
|
|
if (firstMowing != null) {
|
firstMowing.setAsStartPoint();
|
}
|
if (lastMowing != null && lastMowing != firstMowing) {
|
lastMowing.setAsEndPoint();
|
}
|
}
|
|
/**
|
* 检查线段是否退化（长度过小）
|
*/
|
private static boolean isDegenerate(PathSegment segment) {
|
if (segment == null || segment.start == null || segment.end == null) {
|
return true;
|
}
|
double dx = segment.start.x - segment.end.x;
|
double dy = segment.start.y - segment.end.y;
|
return Math.hypot(dx, dy) <= LENGTH_EPSILON;
|
}
|
|
/**
|
* 提取多边形（与原方法相同）
|
*/
|
private static List<Polygon> extractPolygons(Geometry geometry) {
|
if (geometry == null || geometry.isEmpty()) {
|
return Collections.emptyList();
|
}
|
|
List<Polygon> result = new ArrayList<>();
|
|
if (geometry instanceof Polygon) {
|
result.add((Polygon) geometry);
|
} else if (geometry instanceof org.locationtech.jts.geom.MultiPolygon) {
|
org.locationtech.jts.geom.MultiPolygon mp = (org.locationtech.jts.geom.MultiPolygon) geometry;
|
for (int i = 0; i < mp.getNumGeometries(); i++) {
|
Geometry g = mp.getGeometryN(i);
|
if (g instanceof Polygon) {
|
result.add((Polygon) g);
|
}
|
}
|
} else if (geometry instanceof org.locationtech.jts.geom.GeometryCollection) {
|
org.locationtech.jts.geom.GeometryCollection gc = (org.locationtech.jts.geom.GeometryCollection) geometry;
|
for (int i = 0; i < gc.getNumGeometries(); i++) {
|
Geometry child = gc.getGeometryN(i);
|
result.addAll(extractPolygons(child));
|
}
|
}
|
|
return result;
|
}
|
|
/**
|
* 复制坐标
|
*/
|
private static Coordinate clone(Coordinate source) {
|
return source == null ? null : new Coordinate(source.x, source.y);
|
}
|
|
/**
|
* 比较两个坐标是否相同（2D）
|
*/
|
private static boolean equals2D(Coordinate a, Coordinate b) {
|
if (a == b) return true;
|
if (a == null || b == null) return false;
|
return a.distance(b) <= LENGTH_EPSILON;
|
}
|
|
private static Coordinate processRing(Coordinate[] coords,
|
boolean forward,
|
Coordinate cursor,
|
List<PathSegment> segments) {
|
if (coords == null || coords.length < 4) {
|
return cursor;
|
}
|
|
List<Coordinate> base = new ArrayList<>(coords.length - 1);
|
for (int i = 0; i < coords.length - 1; i++) {
|
Coordinate cloned = clone(coords[i]);
|
if (cloned != null) {
|
base.add(cloned);
|
}
|
}
|
|
if (base.size() < 2) {
|
return cursor;
|
}
|
|
if (!forward) {
|
Collections.reverse(base);
|
}
|
|
int startIndex = 0;
|
if (cursor != null) {
|
startIndex = findNearestIndex(base, cursor);
|
}
|
|
List<Coordinate> ordered = new ArrayList<>(base.size());
|
for (int i = 0; i < base.size(); i++) {
|
int index = (startIndex + i) % base.size();
|
ordered.add(clone(base.get(index)));
|
}
|
|
Coordinate firstCoord = ordered.get(0);
|
if (cursor != null && !equals2D(cursor, firstCoord)) {
|
PathSegment transfer = new PathSegment(clone(cursor), clone(firstCoord), false);
|
if (!isDegenerate(transfer)) {
|
segments.add(transfer);
|
}
|
}
|
|
for (int i = 0; i < ordered.size(); i++) {
|
Coordinate start = ordered.get(i);
|
Coordinate end = ordered.get((i + 1) % ordered.size());
|
if (equals2D(start, end)) {
|
continue;
|
}
|
PathSegment mowing = new PathSegment(clone(start), clone(end), true);
|
segments.add(mowing);
|
}
|
|
return clone(firstCoord);
|
}
|
|
private static int findNearestIndex(List<Coordinate> coordinates, Coordinate reference) {
|
if (coordinates == null || coordinates.isEmpty() || reference == null) {
|
return 0;
|
}
|
double bestDistance = Double.MAX_VALUE;
|
int bestIndex = 0;
|
for (int i = 0; i < coordinates.size(); i++) {
|
Coordinate candidate = coordinates.get(i);
|
if (candidate == null) {
|
continue;
|
}
|
double distance = reference.distance(candidate);
|
if (distance < bestDistance) {
|
bestDistance = distance;
|
bestIndex = i;
|
}
|
}
|
return bestIndex;
|
}
|
}
|
