Tìm đường bao HCN
Để áp dụng thuật toán tìm hình chữ nhật nhỏ nhất có thể xoay (Rotated Minimum Bounding Rectangle) với Point3d của AutoCAD .NET API, chúng ta cần tích hợp thuật toán đã trình bày ở trên với các lớp và phương thức của API AutoCAD. Dưới đây là cách triển khai thuật toán sử dụng Point3d trong AutoCAD .NET API, kèm theo ví dụ hoàn chỉnh.
Mục tiêu:
- Nhập vào một danh sách các Point3d (tọa độ 3D trong AutoCAD).
- Tìm hình chữ nhật nhỏ nhất có thể xoay trong mặt phẳng 2D (giả sử các điểm nằm trên cùng một mặt phẳng, thường là mặt phẳng XY).
- Trả về thông tin về hình chữ nhật (tọa độ, góc xoay, diện tích).
1 Thêm class Point2dSimple.cs
Lưu mã sau dưới dạng tệp tin Point2dSimple.cs
Code:
namespace AJS_MinRec_Bound
{
public class Point2dSimple
{
public double X { get; set; }
public double Y { get; set; }
public Point2dSimple(double x, double y)
{
X = x;
Y = y;
}
}
}Tính toán
2 Thêm class Rectangle.cs
Lưu mã sau dưới dạng tệp tin Rectangle.cs
Code:
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Geometry;
using System;
using System.Collections.Generic;
using System.Linq;
namespace AJS_MinRec_Bound
{
public class Rectangle
{
public double MinX { get; set; }
public double MinY { get; set; }
public double MaxX { get; set; }
public double MaxY { get; set; }
public double Angle { get; set; } // Góc xoay (radian)
public double Area { get; set; }
public Polyline GetPolyline()
{
Point3d[] corners = new Point3d[4];
corners[0] = new Point3d(MinX * Math.Cos(Angle) - MinY * Math.Sin(Angle), MinX * Math.Sin(Angle) + MinY * Math.Cos(Angle), 0);
corners[1] = new Point3d(MaxX * Math.Cos(Angle) - MinY * Math.Sin(Angle), MaxX * Math.Sin(Angle) + MinY * Math.Cos(Angle), 0);
corners[2] = new Point3d(MaxX * Math.Cos(Angle) - MaxY * Math.Sin(Angle), MaxX * Math.Sin(Angle) + MaxY * Math.Cos(Angle), 0);
corners[3] = new Point3d(MinX * Math.Cos(Angle) - MaxY * Math.Sin(Angle), MinX * Math.Sin(Angle) + MaxY * Math.Cos(Angle), 0);
var pl = RectangleHelper.FromVertexs(corners);
pl.Closed = true;
return pl;
}
}
public static class RectangleHelper
{
public static Polyline FromVertexs(params Point3d[] pts)
{
Polyline pl = default;
if (pts.Length > 1)
{
pl = new Polyline(pts.Length);
int i = 0;
foreach (Point3d p in pts)
pl.AddVertexAt(Math.Min(System.Threading.Interlocked.Increment(ref i), i - 1), new Point2d(p.X, p.Y), 0, 0, 0);
}
return pl;
}
// Tính tích chéo của 2 vector
private static double CrossProduct(Point2dSimple O, Point2dSimple A, Point2dSimple B)
{
return (A.X - O.X) * (B.Y - O.Y) - (A.Y - O.Y) * (B.X - O.X);
}
// Tìm bao lồi bằng Graham Scan
private static List<Point2dSimple> FindConvexHull(List<Point2dSimple> points)
{
if (points.Count <= 1) return points;
points.Sort((a, b) => a.X == b.X ? a.Y.CompareTo(b.Y) : a.X.CompareTo(b.X));
List<Point2dSimple> hull = new List<Point2dSimple>();
foreach (var p in points)
{
while (hull.Count >= 2 && CrossProduct(hull[hull.Count - 2], hull[hull.Count - 1], p) <= 0)
hull.RemoveAt(hull.Count - 1);
hull.Add(p);
}
int lowerCount = hull.Count;
for (int i = points.Count - 2; i >= 0; i--)
{
while (hull.Count > lowerCount && CrossProduct(hull[hull.Count - 2], hull[hull.Count - 1], points[i]) <= 0)
hull.RemoveAt(hull.Count - 1);
hull.Add(points[i]);
}
hull.RemoveAt(hull.Count - 1);
return hull;
}
// Tìm hình chữ nhật nhỏ nhất có thể xoay
public static Polyline FindRotatedRectangle(this IEnumerable<Point3d> points)
{
return points.Select(x => new Point2dSimple(x.X, x.Y)).ToList().FindRotatedMBR().GetPolyline();
}
public static Polyline FindRectangle(this IEnumerable<Point3d> points)
{
if (points == null || points.Count() == 0)
throw new ArgumentException("Danh sách điểm không được rỗng");
// Khởi tạo giá trị ban đầu từ điểm đầu tiên
double minX = points.ElementAt(0).X;
double maxX = points.ElementAt(0).X;
double minY = points.ElementAt(0).Y;
double maxY = points.ElementAt(0).Y;
// Duyệt qua tất cả các điểm để tìm min/max
foreach (var point in points)
{
if (point.X < minX) minX = point.X;
if (point.X > maxX) maxX = point.X;
if (point.Y < minY) minY = point.Y;
if (point.Y > maxY) maxY = point.Y;
}
return new Rectangle
{
MinX = minX,
MinY = minY,
MaxX = maxX,
MaxY = maxY
}.GetPolyline();
}
public static Rectangle FindRotatedMBR(this IEnumerable<Point3d> points)
{
return points.Select(x => new Point2dSimple(x.X, x.Y)).ToList().FindRotatedMBR();
}
// Tìm hình chữ nhật nhỏ nhất có thể xoay
private static Rectangle FindRotatedMBR(this List<Point2dSimple> points)
{
if (points == null || points.Count == 0)
throw new ArgumentException("Danh sách điểm không được rỗng");
List<Point2dSimple> hull = FindConvexHull(points);
if (hull.Count < 3)
throw new ArgumentException("Cần ít nhất 3 điểm không thẳng hàng");
double minArea = double.MaxValue;
Rectangle result = new Rectangle();
for (int i = 0; i < hull.Count; i++)
{
int j = (i + 1) % hull.Count;
Point2dSimple edge = new Point2dSimple(hull[j].X - hull[i].X, hull[j].Y - hull[i].Y);
double angle = Math.Atan2(edge.Y, edge.X);
double minX = double.MaxValue, maxX = double.MinValue;
double minY = double.MaxValue, maxY = double.MinValue;
foreach (var p in hull)
{
double rotatedX = p.X * Math.Cos(-angle) - p.Y * Math.Sin(-angle);
double rotatedY = p.X * Math.Sin(-angle) + p.Y * Math.Cos(-angle);
minX = Math.Min(minX, rotatedX);
maxX = Math.Max(maxX, rotatedX);
minY = Math.Min(minY, rotatedY);
maxY = Math.Max(maxY, rotatedY);
}
double area = (maxX - minX) * (maxY - minY);
if (area < minArea - 1e-5)
{
minArea = area;
result = new Rectangle
{
MinX = minX,
MinY = minY,
MaxX = maxX,
MaxY = maxY,
Angle = angle,
Area = area
};
}
}
return result;
}
}
}Giải thích thuật toán sử dụng:
- Bước 1: Tìm bao lồi (Convex Hull):
- Sử dụng thuật toán Graham Scan để tìm tập hợp các điểm bao ngoài cùng của danh sách điểm.
- Độ phức tạp: O(n log n), với n là số điểm.
- Bước 2: Rotating Calipers:
- Duyệt qua từng cạnh của bao lồi.
- Với mỗi cạnh:
- Xác định góc xoay của cạnh so với trục X.
- Xoay tất cả các điểm ngược lại góc này để đưa về hệ tọa độ song song với cạnh.
- Tìm MinX, MaxX, MinY, MaxY trong hệ tọa độ mới.
- Tính diện tích hình chữ nhật và giữ lại nếu nhỏ hơn diện tích nhỏ nhất tìm được.
- Kết quả:
- Trả về hình chữ nhật có diện tích nhỏ nhất với góc xoay tương ứng.
Cách sử dụng
3 Thêm class myCommands.cs
Lưu mã sau dưới dạng tệp tin myCommands.cs
Code:
// (C) Copyright 2025 by
//
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System.Collections.Generic;
using System.Linq;
// This line is not mandatory, but improves loading performances
[assembly: CommandClass(typeof(AJS_MinRec_Bound.MyCommands))]
namespace AJS_MinRec_Bound
{
// This class is instantiated by AutoCAD for each document when
// a command is called by the user the first time in the context
// of a given document. In other words, non static data in this class
// is implicitly per-document!
public class MyCommands
{
[CommandMethod("FindRectangle", CommandFlags.Modal)]
public void cmd_Find_Rectangle() // This method can have any name
{
Document doc = Autodesk.AutoCAD.ApplicationServices.Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;
ed.WriteMessage("\nFind minimun Rectangle Boundary | AJS - www.lisp.vn");
var psr = ed.GetSelection(new SelectionFilter(new TypedValue[] { new TypedValue(0, "*Line") }));
if (psr.Status != PromptStatus.OK)
{
ed.WriteMessage("\nNo selected object.");
return;
}
using (var tr = db.TransactionManager.StartTransaction())
{
var btr = tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite) as BlockTableRecord;
var pts = new List<Point3d>();
var cvs = psr.Value.GetObjectIds().Select(x => tr.GetObject(x, Autodesk.AutoCAD.DatabaseServices.OpenMode.ForRead) as Curve)
.Where(x => x != null && x.Bounds.HasValue).ToList();
foreach (var c in cvs)
{
pts.Add(c.StartPoint);
pts.Add(c.EndPoint);
}
if (pts.Count > 3)
{
var pl = pts.FindRotatedRectangle();
if (pl != null)
{
pl.ColorIndex = 1;
btr.AppendEntity(pl);
tr.AddNewlyCreatedDBObject(pl, true);
}
var plrec = pts.FindRectangle();
if (plrec != null)
{
plrec.ColorIndex = 3;
btr.AppendEntity(plrec);
tr.AddNewlyCreatedDBObject(plrec, true);
}
}
tr.Commit();
}
}
}
}Link tải (GitHub)
---------------------------------------------------------------------------------------------
Mọi thông tin xin liên hệ Fanpage AutoLISP Thật là đơn giản!
Cảm ơn bạn đã theo dõi!
Không có nhận xét nào:
Đăng nhận xét