From 7881cef5c3dcea8e6037101db2c3eeb2fd3ba5da Mon Sep 17 00:00:00 2001
From: 826220679@qq.com <826220679@qq.com>
Date: 星期六, 27 十二月 2025 23:42:36 +0800
Subject: [PATCH] 1211
---
src/lujing/YixinglujingNoObstacle.java | 189 +++++++++++++++++++++++++++++++++++++++++++++--
1 files changed, 181 insertions(+), 8 deletions(-)
diff --git a/src/lujing/YixinglujingNoObstacle.java b/src/lujing/YixinglujingNoObstacle.java
index bdda587..31e87d5 100644
--- a/src/lujing/YixinglujingNoObstacle.java
+++ b/src/lujing/YixinglujingNoObstacle.java
@@ -7,6 +7,9 @@
* 淇锛氳В鍐冲嚬澶氳竟褰㈡壂鎻忕嚎璺ㄨ秺杈圭晫鐨勯棶棰橈紝浼樺寲璺緞瀵归綈
*/
public class YixinglujingNoObstacle {
+ // 寮�鍏筹細鏄惁寮哄埗鎵�鏈夐潪浣滀笟杩炴帴娌垮畨鍏ㄨ竟鐣岃璧帮紙閬垮厤浠讳綍鍐呭尯鐩寸嚎璺ㄨ秺锛�
+ // 鏀逛负鍙姩鎬佽缃紝鑷姩渚濇嵁鍦板潡褰㈢姸鍚敤
+ private static boolean FORCE_BOUNDARY_TRAVEL = true;
// 鐢ㄦ硶璇存槑锛堟棤闅滅鐗╄矾寰勮鍒掞級锛�
// - 鏂规硶鐢ㄩ�旓細鏍规嵁鍦板潡杈圭晫銆佸壊鑽夊搴︿笌瀹夊叏杈硅窛锛岀敓鎴愯鐩栧叏鍖哄煙鐨勫壊鑽夎矾寰勩��
// - 鍙傛暟锛�
@@ -37,6 +40,9 @@
// 3. 纭畾鏈�浼樹綔涓氳搴�
double bestAngle = findOptimalAngle(boundary);
+
+ // 3.1 鑷姩鍒ゆ柇鏄惁闇�瑕佸己鍒舵部杈圭晫鏃呰锛堟娴嬪嚬閮�/澶氭鎵弿琛岋級
+ FORCE_BOUNDARY_TRAVEL = shouldForceBoundaryTravel(boundary, mowWidth, bestAngle);
// 4. 鑾峰彇棣栦釜浣滀笟鐐癸紝鐢ㄤ簬瀵归綈鍥磋竟璧风偣
Point firstScanStart = getFirstScanPoint(boundary, mowWidth, bestAngle);
@@ -59,7 +65,10 @@
finalPath.addAll(scanPath);
- // 8. 鏍煎紡鍖栧潗鏍囷細淇濈暀涓や綅灏忔暟
+ // 8. 鏈�缁堝畨鍏ㄥ噣鍖栵細纭繚鎵�鏈夋鍦ㄥ唴缂╄竟鐣屼笂鎴栧唴閮紙鑷姩璐磋竟闃堝�硷級
+ sanitizePath(finalPath, boundary, mowWidth, safeMargin);
+
+ // 9. 鏍煎紡鍖栧潗鏍囷細淇濈暀涓や綅灏忔暟
for (PathSegment segment : finalPath) {
segment.start.x = Math.round(segment.start.x * 100.0) / 100.0;
segment.start.y = Math.round(segment.start.y * 100.0) / 100.0;
@@ -70,6 +79,108 @@
return finalPath;
}
+ // 瀵规墍鏈夎矾寰勬杩涜瀹夊叏鍑�鍖栵細
+ // - 闈炰綔涓氭锛氱粺涓�娌胯竟鐣岃矾寰勬浛鎹�
+ // - 浣滀笟娈碉細鑻ョ鐐瑰湪澶栨垨娈典笌杈圭晫鐩镐氦锛屽惛闄勭鐐瑰埌杈圭晫骞跺悜鍐呬晶鍋忕Щ epsilon
+ private static void sanitizePath(List<PathSegment> segments, List<Point> polygon, double width, double margin) {
+ double epsilon = computeAutoInnerOffset(polygon, width, margin);
+ List<PathSegment> sanitized = new ArrayList<>();
+ for (PathSegment s : segments) {
+ boolean startInside = isPointInPolygon(s.start, polygon);
+ boolean endInside = isPointInPolygon(s.end, polygon);
+ boolean intersects = segmentIntersectsBoundary(s.start, s.end, polygon);
+ if (!s.isMowing) {
+ // 闈炰綔涓氭缁熶竴鏇挎崲涓烘部杈圭晫璺緞
+ List<Point> path = getBoundaryPathWithSnap(s.start, s.end, polygon);
+ for (int i = 0; i < path.size() - 1; i++) {
+ sanitized.add(new PathSegment(path.get(i), path.get(i+1), false));
+ }
+ } else {
+ if (!startInside || !endInside || intersects) {
+ SnapResult s1 = snapToBoundary(s.start, polygon);
+ SnapResult s2 = snapToBoundary(s.end, polygon);
+ Point p1 = pushInsideOnEdge(s1, polygon, epsilon);
+ Point p2 = pushInsideOnEdge(s2, polygon, epsilon);
+ sanitized.add(new PathSegment(p1, p2, true));
+ } else {
+ sanitized.add(s);
+ }
+ }
+ }
+ segments.clear();
+ segments.addAll(sanitized);
+ }
+
+ private static boolean segmentIntersectsBoundary(Point a, Point b, List<Point> polygon) {
+ for (int i = 0; i < polygon.size(); i++) {
+ Point c = polygon.get(i);
+ Point d = polygon.get((i + 1) % polygon.size());
+ // 蹇界暐鍏变韩绔偣鐨勭浉浜�
+ if (isSamePoint(a, c) || isSamePoint(a, d) || isSamePoint(b, c) || isSamePoint(b, d)) continue;
+ if (segmentsIntersect(a, b, c, d)) return true;
+ }
+ return false;
+ }
+
+ // 灏嗚竟鐣屼笂鐨勬姇褰辩偣鍚戝唴渚у亸绉� epsilon
+ private static Point pushInsideOnEdge(SnapResult sr, List<Point> poly, double epsilon) {
+ int i = sr.edgeIndex;
+ Point s = poly.get(i);
+ Point e = poly.get((i + 1) % poly.size());
+ double dx = e.x - s.x, dy = e.y - s.y;
+ double len = Math.hypot(dx, dy);
+ if (len < 1e-6) return sr.onEdge;
+ // 瀵逛簬閫嗘椂閽堬紙CCW锛夊杈瑰舰锛屽乏杞硶鍚戦噺 (-dy, dx) 鎸囧悜鍐呬晶
+ double nx = -dy / len, ny = dx / len;
+ return new Point(sr.onEdge.x + nx * epsilon, sr.onEdge.y + ny * epsilon);
+ }
+
+ // 鑷姩璁＄畻璐磋竟鍐呭亸绉婚槇鍊� epsilon锛氭牴鎹湴鍧楀昂搴︺�佹渶鐭竟銆佸壊鑽夊搴︿笌瀹夊叏杈硅窛缁煎悎浼扮畻
+ private static double computeAutoInnerOffset(List<Point> polygon, double width, double margin) {
+ double minEdge = Double.MAX_VALUE;
+ double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
+ double maxX = -Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
+ for (int i = 0; i < polygon.size(); i++) {
+ Point a = polygon.get(i);
+ Point b = polygon.get((i + 1) % polygon.size());
+ minEdge = Math.min(minEdge, Math.hypot(a.x - b.x, a.y - b.y));
+ minX = Math.min(minX, a.x); minY = Math.min(minY, a.y);
+ maxX = Math.max(maxX, a.x); maxY = Math.max(maxY, a.y);
+ }
+ double diag = Math.hypot(maxX - minX, maxY - minY);
+ // 鍩虹閲忥細鏁板�肩ǔ瀹氶渶瑕佺殑鏈�灏忓唴鍋忕Щ锛堝彇鍓插箙鐨�1%涓庡瑙掔嚎鐨�0.2%涔嬮棿鐨勮緝澶у�硷級
+ double base = Math.max(width * 0.01, diag * 0.002);
+ // 涓婇檺锛氫笉瓒呰繃瀹夊叏杈硅窛鐨�20%涓庡壊骞呯殑10%
+ double upper = Math.min(margin * 0.2, width * 0.1);
+ // 鍙楄竟闀跨害鏉燂細涓嶈秴杩囨渶鐭竟鐨�2%
+ double edgeLimit = minEdge * 0.02;
+ double eps = Math.min(upper, Math.max(base, edgeLimit * 0.5));
+ // 涓嬮檺/涓婇檺鏈�缁堥挸浣嶏細3mm 鍒� 5cm
+ eps = Math.max(0.003, Math.min(eps, 0.05));
+ return eps;
+ }
+
+ // 鏍规嵁鎵弿琛岀殑浜ょ偣鏁伴噺鏉ュ垽鏂槸鍚﹀瓨鍦ㄢ�滃娈佃鈥濓紙>=2娈碉級锛屾湁鍑归儴鎴栫獎閫氶亾鏃跺惎鐢ㄥ己鍒舵部杈圭晫鏃呰
+ private static boolean shouldForceBoundaryTravel(List<Point> polygon, double width, double angle) {
+ List<Point> rotatedPoly = new ArrayList<>();
+ for (Point p : polygon) rotatedPoly.add(rotatePoint(p, -angle));
+ double minY = Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
+ for (Point p : rotatedPoly) { minY = Math.min(minY, p.y); maxY = Math.max(maxY, p.y); }
+
+ int multiSegmentRows = 0;
+ int totalRows = 0;
+ for (double y = minY + width/2; y <= maxY - width/2; y += width) {
+ List<Double> xIntersections = getXIntersections(rotatedPoly, y);
+ if (xIntersections.size() < 2) continue;
+ totalRows++;
+ if (xIntersections.size() >= 4) multiSegmentRows++; // 鍚屼竴琛屽嚭鐜颁袱涓強浠ヤ笂浣滀笟娈�
+ }
+ // 鍙鍑虹幇杩団�滃娈佃鈥濓紝灏卞己鍒舵部杈圭晫鏃呰锛涗篃鍙寜姣斾緥闃堝�艰Е鍙戯紙渚嬪 >=10%锛�
+ if (multiSegmentRows > 0) return true;
+ double ratio = totalRows == 0 ? 0.0 : (double) multiSegmentRows / (double) totalRows;
+ return ratio >= 0.1; // 鍏滃簳闃堝��
+ }
+
private static List<PathSegment> generateGlobalScanPath(List<Point> polygon, double width, double angle, Point currentPos) {
// 鍏堝皾璇曞皢鍑归櫡澶勮涓轰袱涓嫭绔嬪尯鍩燂紝鍒嗕袱娆℃壂鎻忥紝閬垮厤璺ㄥ尯鐩寸嚎杩炴帴
List<PathSegment> all = new ArrayList<>();
@@ -258,24 +369,86 @@
}
private static void addSafeConnection(List<PathSegment> segments, Point start, Point end, List<Point> polygon) {
- if (isSegmentSafe(start, end, polygon)) {
+ if (!FORCE_BOUNDARY_TRAVEL && isSegmentSafe(start, end, polygon)) {
segments.add(new PathSegment(start, end, false));
- } else {
- List<Point> path = getBoundaryPath(start, end, polygon);
- for (int i = 0; i < path.size() - 1; i++) {
- segments.add(new PathSegment(path.get(i), path.get(i+1), false));
- }
+ return;
+ }
+ List<Point> path = getBoundaryPathWithSnap(start, end, polygon);
+ for (int i = 0; i < path.size() - 1; i++) {
+ segments.add(new PathSegment(path.get(i), path.get(i+1), false));
}
}
// 寮哄埗娌胯竟鐣岀粫琛岀殑杩炴帴锛堜笉鍋氱洿绾垮畨鍏ㄥ垽鏂級锛岀敤鏉ュ湪鍚屼竴鎵弿琛岀殑澶氫釜浣滀笟娈典箣闂磋烦杞�
private static void addBoundaryConnection(List<PathSegment> segments, Point start, Point end, List<Point> polygon) {
- List<Point> path = getBoundaryPath(start, end, polygon);
+ List<Point> path = getBoundaryPathWithSnap(start, end, polygon);
for (int i = 0; i < path.size() - 1; i++) {
segments.add(new PathSegment(path.get(i), path.get(i+1), false));
}
}
+ // 灏嗕换鎰忎袱鐐归�氳繃鈥滃惛闄勫埌杈圭晫鈥濆悗娌胯竟鐣屾渶鐭矾寰勮繛鎺�
+ private static List<Point> getBoundaryPathWithSnap(Point start, Point end, List<Point> polygon) {
+ SnapResult s1 = snapToBoundary(start, polygon);
+ SnapResult s2 = snapToBoundary(end, polygon);
+ int n = polygon.size();
+
+ // 鍓嶅悜璺緞锛堥『杈癸級
+ List<Point> pathFwd = new ArrayList<>();
+ pathFwd.add(start);
+ pathFwd.add(s1.onEdge);
+ int curr = s1.edgeIndex;
+ while (curr != s2.edgeIndex) {
+ pathFwd.add(polygon.get((curr + 1) % n));
+ curr = (curr + 1) % n;
+ }
+ pathFwd.add(s2.onEdge);
+ pathFwd.add(end);
+
+ // 鍙嶅悜璺緞锛堥�嗚竟锛�
+ List<Point> pathRev = new ArrayList<>();
+ pathRev.add(start);
+ pathRev.add(s1.onEdge);
+ curr = s1.edgeIndex;
+ while (curr != s2.edgeIndex) {
+ pathRev.add(polygon.get(curr));
+ curr = (curr - 1 + n) % n;
+ }
+ pathRev.add(s2.onEdge);
+ pathRev.add(end);
+
+ return getPathLength(pathFwd) < getPathLength(pathRev) ? pathFwd : pathRev;
+ }
+
+ private static class SnapResult {
+ Point onEdge;
+ int edgeIndex;
+ SnapResult(Point p, int idx) { this.onEdge = p; this.edgeIndex = idx; }
+ }
+
+ // 璁＄畻鐐瑰埌杈圭晫鏈�杩戠殑鎶曞奖鐐逛互鍙婃墍鍦ㄨ竟绱㈠紩
+ private static SnapResult snapToBoundary(Point p, List<Point> poly) {
+ double minD = Double.MAX_VALUE;
+ Point bestProj = p;
+ int bestIdx = -1;
+ for (int i = 0; i < poly.size(); i++) {
+ Point s = poly.get(i);
+ Point e = poly.get((i + 1) % poly.size());
+ double l2 = (s.x - e.x)*(s.x - e.x) + (s.y - e.y)*(s.y - e.y);
+ if (l2 == 0) {
+ double d = Math.hypot(p.x - s.x, p.y - s.y);
+ if (d < minD) { minD = d; bestProj = s; bestIdx = i; }
+ continue;
+ }
+ double t = ((p.x - s.x) * (e.x - s.x) + (p.y - s.y) * (e.y - s.y)) / l2;
+ t = Math.max(0, Math.min(1, t));
+ Point proj = new Point(s.x + t * (e.x - s.x), s.y + t * (e.y - s.y));
+ double d = Math.hypot(p.x - proj.x, p.y - proj.y);
+ if (d < minD) { minD = d; bestProj = proj; bestIdx = i; }
+ }
+ return new SnapResult(bestProj, bestIdx == -1 ? 0 : bestIdx);
+ }
+
private static boolean isSegmentSafe(Point p1, Point p2, List<Point> polygon) {
Point mid = new Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
if (!isPointInPolygon(mid, polygon)) return false;
--
Gitblit v1.10.0