package lujing;
|
|
import java.util.ArrayList;
|
import java.util.Collections;
|
import java.util.List;
|
|
/**
|
* 凸形草地路径规划 (围边优化版)
|
* 优化重点：围边坐标对齐扫描起点、全路径连贯性
|
*/
|
public class AoxinglujingNoObstacle {
|
|
private static final double EPSILON = 1e-6;
|
|
public static class Point {
|
public double x, y;
|
public Point(double x, double y) { this.x = x; this.y = y; }
|
@Override
|
public String toString() { return String.format("%.6f,%.6f", x, y); }
|
}
|
|
public static class PathSegment {
|
public Point start, end;
|
public boolean isMowing;
|
public PathSegment(Point start, Point end, boolean isMowing) {
|
this.start = start; this.end = end; this.isMowing = isMowing;
|
}
|
}
|
|
/**
|
* 对外主接口
|
*/
|
public static List<PathSegment> planPath(String boundaryCoordsStr, String mowingWidthStr, String safetyMarginStr) {
|
List<Point> originalPolygon = parseCoords(boundaryCoordsStr);
|
double width = Double.parseDouble(mowingWidthStr);
|
double margin = Double.parseDouble(safetyMarginStr);
|
|
return planPathCore(originalPolygon, width, margin);
|
}
|
|
/**
|
* 核心路径规划逻辑
|
*
|
* @param originalPolygon 原始多边形顶点列表
|
* @param width 割草宽度
|
* @param margin 安全边距
|
* @return 规划好的路径段列表
|
*/
|
private static List<PathSegment> planPathCore(List<Point> originalPolygon, double width, double margin) {
|
if (originalPolygon.size() < 3) return new ArrayList<>();
|
|
// 1. 确保逆时针并进行安全内缩
|
ensureCCW(originalPolygon);
|
List<Point> workArea = shrinkPolygon(originalPolygon, margin);
|
if (workArea.size() < 3) return new ArrayList<>();
|
|
// 2. 预计算最优角度和填充路径的第一个点
|
double bestAngle = findOptimalScanAngle(workArea);
|
Point firstScanStart = getFirstScanStartPoint(workArea, bestAngle, width);
|
|
// 3. 对齐围边起点：让围边的最后一个点刚好连接扫描填充的起点
|
List<Point> alignedWorkArea = alignBoundaryToStart(workArea, firstScanStart);
|
|
List<PathSegment> finalPath = new ArrayList<>();
|
|
// 4. 【第一阶段】添加围边坐标路径
|
for (int i = 0; i < alignedWorkArea.size(); i++) {
|
Point p1 = alignedWorkArea.get(i);
|
Point p2 = alignedWorkArea.get((i + 1) % alignedWorkArea.size());
|
finalPath.add(new PathSegment(p1, p2, true));
|
}
|
|
// 5. 【第二阶段】生成内部弓字形路径
|
// 从围边闭合点（alignedWorkArea.get(0)）开始连接
|
Point currentPos = alignedWorkArea.get(0);
|
List<PathSegment> zigZagLines = generateZigZagPath(workArea, bestAngle, width, currentPos);
|
|
finalPath.addAll(zigZagLines);
|
|
return finalPath;
|
}
|
|
/**
|
* 寻找弓字形的第一条线的起点
|
*
|
* @param polygon 多边形顶点列表
|
* @param angle 扫描角度
|
* @param width 割草宽度
|
* @return 扫描起点的坐标
|
*/
|
private static Point getFirstScanStartPoint(List<Point> polygon, double angle, double width) {
|
List<Point> rotated = rotatePolygon(polygon, -angle);
|
double minY = Double.MAX_VALUE;
|
for (Point p : rotated) minY = Math.min(minY, p.y);
|
|
double startY = minY + width + EPSILON;
|
List<Double> xIntersections = getXIntersections(rotated, startY);
|
if (xIntersections.isEmpty()) return polygon.get(0);
|
|
Collections.sort(xIntersections);
|
return rotatePoint(new Point(xIntersections.get(0), startY), angle);
|
}
|
|
/**
|
* 重组多边形顶点，使得索引0的点最靠近填充起点
|
*
|
* @param polygon 多边形顶点列表
|
* @param target 目标点（填充起点）
|
* @return 重组后的多边形顶点列表
|
*/
|
private static List<Point> alignBoundaryToStart(List<Point> polygon, Point target) {
|
int bestIdx = 0;
|
double minDist = Double.MAX_VALUE;
|
for (int i = 0; i < polygon.size(); i++) {
|
double d = Math.hypot(polygon.get(i).x - target.x, polygon.get(i).y - target.y);
|
if (d < minDist) {
|
minDist = d;
|
bestIdx = i;
|
}
|
}
|
List<Point> aligned = new ArrayList<>();
|
for (int i = 0; i < polygon.size(); i++) {
|
aligned.add(polygon.get((bestIdx + i) % polygon.size()));
|
}
|
return aligned;
|
}
|
|
/**
|
* 生成弓字形扫描路径
|
*
|
* @param polygon 多边形顶点列表
|
* @param angle 扫描角度
|
* @param width 割草宽度
|
* @param startPoint 起始点
|
* @return 弓字形路径段列表
|
*/
|
private static List<PathSegment> generateZigZagPath(List<Point> polygon, double angle, double width, Point startPoint) {
|
List<PathSegment> result = new ArrayList<>();
|
List<Point> rotated = rotatePolygon(polygon, -angle);
|
|
double minY = Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
|
for (Point p : rotated) {
|
minY = Math.min(minY, p.y);
|
maxY = Math.max(maxY, p.y);
|
}
|
|
Point currentPos = startPoint;
|
boolean leftToRight = true;
|
// 起点从 minY + width 开始，因为边缘已经围边割过
|
for (double y = minY + width; y < maxY - width / 2; y += width) {
|
List<Double> xInt = getXIntersections(rotated, y);
|
if (xInt.size() < 2) continue;
|
Collections.sort(xInt);
|
|
double xStart = leftToRight ? xInt.get(0) : xInt.get(xInt.size() - 1);
|
double xEnd = leftToRight ? xInt.get(xInt.size() - 1) : xInt.get(0);
|
|
Point pS = rotatePoint(new Point(xStart, y), angle);
|
Point pE = rotatePoint(new Point(xEnd, y), angle);
|
|
// 添加过渡段 (如果是从围边切换过来或者换行)
|
if (Math.hypot(currentPos.x - pS.x, currentPos.y - pS.y) > 0.05) {
|
result.add(new PathSegment(currentPos, pS, false));
|
}
|
result.add(new PathSegment(pS, pE, true));
|
currentPos = pE;
|
leftToRight = !leftToRight;
|
}
|
return result;
|
}
|
|
/**
|
* 获取扫描线与多边形的交点X坐标列表
|
*
|
* @param rotatedPoly 旋转后的多边形
|
* @param y 扫描线的Y坐标
|
* @return 交点X坐标列表
|
*/
|
private static List<Double> getXIntersections(List<Point> rotatedPoly, double y) {
|
List<Double> xIntersections = new ArrayList<>();
|
int n = rotatedPoly.size();
|
for (int i = 0; i < n; i++) {
|
Point p1 = rotatedPoly.get(i);
|
Point p2 = rotatedPoly.get((i + 1) % n);
|
if ((p1.y <= y && p2.y > y) || (p2.y <= y && p1.y > y)) {
|
double x = p1.x + (y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
|
xIntersections.add(x);
|
}
|
}
|
return xIntersections;
|
}
|
|
// --- 几何基础工具 ---
|
|
/**
|
* 多边形内缩（计算安全工作区域）
|
*
|
* @param polygon 原始多边形
|
* @param margin 内缩距离
|
* @return 内缩后的多边形
|
*/
|
private static List<Point> shrinkPolygon(List<Point> polygon, double margin) {
|
List<Point> result = new ArrayList<>();
|
int n = polygon.size();
|
for (int i = 0; i < n; i++) {
|
Point pPrev = polygon.get((i - 1 + n) % n);
|
Point pCurr = polygon.get(i);
|
Point pNext = polygon.get((i + 1) % n);
|
|
double d1x = pCurr.x - pPrev.x, d1y = pCurr.y - pPrev.y;
|
double l1 = Math.hypot(d1x, d1y);
|
double d2x = pNext.x - pCurr.x, d2y = pNext.y - pCurr.y;
|
double l2 = Math.hypot(d2x, d2y);
|
|
double n1x = -d1y / l1, n1y = d1x / l1;
|
double n2x = -d2y / l2, n2y = d2x / l2;
|
|
double bx = n1x + n2x, by = n1y + n2y;
|
double bLen = Math.hypot(bx, by);
|
if (bLen < EPSILON) { bx = n1x; by = n1y; }
|
else { bx /= bLen; by /= bLen; }
|
|
double cosHalf = n1x * bx + n1y * by;
|
double d = margin / Math.max(cosHalf, 0.1);
|
result.add(new Point(pCurr.x + bx * d, pCurr.y + by * d));
|
}
|
return result;
|
}
|
|
/**
|
* 寻找最优扫描角度（使扫描线数量最少）
|
*
|
* @param polygon 多边形
|
* @return 最优角度（弧度）
|
*/
|
private static double findOptimalScanAngle(List<Point> polygon) {
|
double minH = Double.MAX_VALUE;
|
double bestA = 0;
|
for (int i = 0; i < polygon.size(); i++) {
|
Point p1 = polygon.get(i), p2 = polygon.get((i + 1) % polygon.size());
|
double angle = Math.atan2(p2.y - p1.y, p2.x - p1.x);
|
double h = calculatePolygonHeightAtAngle(polygon, angle);
|
if (h < minH) { minH = h; bestA = angle; }
|
}
|
return bestA;
|
}
|
|
/**
|
* 计算多边形在特定角度下的高度（投影长度）
|
*
|
* @param poly 多边形
|
* @param angle 角度
|
* @return 高度
|
*/
|
private static double calculatePolygonHeightAtAngle(List<Point> poly, double angle) {
|
double minY = Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
|
double sin = Math.sin(-angle), cos = Math.cos(-angle);
|
for (Point p : poly) {
|
double ry = p.x * sin + p.y * cos;
|
minY = Math.min(minY, ry); maxY = Math.max(maxY, ry);
|
}
|
return maxY - minY;
|
}
|
|
/**
|
* 旋转点
|
*
|
* @param p 点
|
* @param angle 旋转角度
|
* @return 旋转后的点
|
*/
|
private static Point rotatePoint(Point p, double angle) {
|
double c = Math.cos(angle), s = Math.sin(angle);
|
return new Point(p.x * c - p.y * s, p.x * s + p.y * c);
|
}
|
|
/**
|
* 旋转多边形
|
*
|
* @param poly 多边形
|
* @param angle 旋转角度
|
* @return 旋转后的多边形
|
*/
|
private static List<Point> rotatePolygon(List<Point> poly, double angle) {
|
List<Point> res = new ArrayList<>();
|
for (Point p : poly) res.add(rotatePoint(p, angle));
|
return res;
|
}
|
|
/**
|
* 确保多边形顶点为逆时针顺序
|
*
|
* @param poly 多边形
|
*/
|
private static void ensureCCW(List<Point> poly) {
|
double s = 0;
|
for (int i = 0; i < poly.size(); i++) {
|
Point p1 = poly.get(i), p2 = poly.get((i + 1) % poly.size());
|
s += (p2.x - p1.x) * (p2.y + p1.y);
|
}
|
if (s > 0) Collections.reverse(poly);
|
}
|
|
/**
|
* 解析坐标字符串
|
*
|
* @param s 坐标字符串 (格式: "x1,y1;x2,y2;...")
|
* @return 点列表
|
*/
|
private static List<Point> parseCoords(String s) {
|
List<Point> list = new ArrayList<>();
|
for (String p : s.split(";")) {
|
String[] xy = p.split(",");
|
if (xy.length >= 2) list.add(new Point(Double.parseDouble(xy[0]), Double.parseDouble(xy[1])));
|
}
|
return list;
|
}
|
}
|
