Here're a C# and a F# implementation of the 'Graham's scan' algorythm to get the convex hull of a 2d points collection.
[EDIT: added a C# implementation using Linq]
C# (targeting NET Framework 2.0 which is the default for A2007 -> A2009).
using System.Collections.Generic;
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;
namespace ConvexHull
{
public class Commands
{
private Point2d _p0;
private bool Clockwise(Point2d p1, Point2d p2, Point2d p3)
{
return ((p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X)) < 1e-9;
}
private int ComparePoints(Point2d p1, Point2d p2)
{
if (p1.IsEqualTo(p2)) return 0;
double d1 = _p0.GetDistanceTo(p1);
double d2 = _p0.GetDistanceTo(p2);
if (d1 == 0.0) return -1;
if (d2 == 0.0) return 1;
double cos = (p2.X - _p0.X) / d2 - (p1.X - _p0.X) / d1;
if (cos < -1e-9) return -1;
if (cos > 1e-9) return 1;
return d1.CompareTo(d2);
}
private List<Point2d> ConvexHull(List<Point2d> pts)
{
_p0 = pts[0];
for (int i = 1; i < pts.Count; i++)
{
Point2d pt = pts[i];
if (pt.Y < _p0.Y || (pt.Y == _p0.Y && pt.X < _p0.X))
_p0 = pt;
}
pts.Sort(ComparePoints);
for (int i = 1; i < pts.Count - 1; i++)
{
while (i > 0 && Clockwise(pts[i - 1], pts[i], pts[i + 1]))
{
pts.RemoveAt(i);
i--;
}
}
return pts;
}
[CommandMethod("ch", CommandFlags.UsePickSet)]
public void testCh()
{
Document doc = AcAp.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;
TypedValue[] filter = new TypedValue[1] { new TypedValue(0, "POINT") };
PromptSelectionResult psr = ed.GetSelection(new SelectionFilter(filter));
if (psr.Status != PromptStatus.OK) return;
using (Transaction tr = db.TransactionManager.StartTransaction())
using (Polyline pline = new Polyline())
{
List<Point2d> pts = new List<Point2d>();
foreach (SelectedObject so in psr.Value)
{
DBPoint dbPt = (DBPoint)tr.GetObject(so.ObjectId, OpenMode.ForRead);
pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));
}
for (int i = 0; i < ConvexHull(pts).Count; i++)
{
pline.AddVertexAt(i, pts[i], 0.0, 0.0, 0.0);
}
pline.Closed = true;
pline.SetDatabaseDefaults();
BlockTableRecord btr = (BlockTableRecord)tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);
btr.AppendEntity(pline);
tr.AddNewlyCreatedDBObject(pline, true);
tr.Commit();
}
}
}
}
C# (using Linq, NET Framework 3 or upper required)
using System;
using System.Collections.Generic;
using System.Linq;
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;
namespace LinqConvexHull
{
public class Commands
{
private Point2d _p0;
private bool Clockwise(Point2d p1, Point2d p2, Point2d p3)
{
return ((p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X)) < 1e-9;
}
private double Cosine(Point2d pt)
{
double d = _p0.GetDistanceTo(pt);
return d == 0.0 ? 1.0 : Math.Round((pt.X - _p0.X) / d, 9);
}
private List<Point2d> ConvexHull(List<Point2d> pts)
{
_p0 = pts.OrderBy(p => p.Y).ThenBy(p => p.X).First();
pts = pts.OrderByDescending(p => Cosine(p)).ThenBy(p => _p0.GetDistanceTo(p)).ToList();
for (int i = 1; i < pts.Count - 1; i++)
{
while (i > 0 && Clockwise(pts[i - 1], pts[i], pts[i + 1]))
{
pts.RemoveAt(i);
i--;
}
}
return pts;
}
[CommandMethod("Test")]
public void Test()
{
Document doc = AcAp.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;
TypedValue[] filter = new TypedValue[1] { new TypedValue(0, "POINT") };
PromptSelectionResult psr = ed.GetSelection(new SelectionFilter(filter));
if (psr.Status != PromptStatus.OK) return;
using (Transaction tr = db.TransactionManager.StartTransaction())
using (Polyline pline = new Polyline())
{
List<Point2d> pts = new List<Point2d>();
foreach (SelectedObject so in psr.Value)
{
DBPoint dbPt = (DBPoint)tr.GetObject(so.ObjectId, OpenMode.ForRead);
pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));
}
pts = ConvexHull(pts);
for (int i = 0; i < pts.Count; i++)
{
pline.AddVertexAt(i, pts[i], 0.0, 0.0, 0.0);
}
pline.Closed = true;
pline.SetDatabaseDefaults();
BlockTableRecord btr = (BlockTableRecord)tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);
btr.AppendEntity(pline);
tr.AddNewlyCreatedDBObject(pline, true);
tr.Commit();
}
}
}
}
F#
module ConvexHull
open Autodesk.AutoCAD.ApplicationServices
open Autodesk.AutoCAD.DatabaseServices
open Autodesk.AutoCAD.EditorInput
open Autodesk.AutoCAD.Geometry
open Autodesk.AutoCAD.Runtime
type AcAp = Autodesk.AutoCAD.ApplicationServices.Application
let clockwise (p1:Point2d) (p2:Point2d) (p3:Point2d) =
(p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X) < 1e-9
let convexHull (pts : Point2d seq) =
let rec fill acc pt =
match acc with
| a :: b :: _ when clockwise b a pt -> fill acc.Tail pt
| _ -> pt :: acc
let p0 = pts
|> Seq.reduce (fun p1 p2 ->
if p2.Y < p1.Y || (p1.Y = p2.Y && p2.X < p1.X) then p2 else p1)
pts
|> List.ofSeq
|> List.sortBy (fun p ->
let d = p0.GetDistanceTo(p)
(Math.Round((p0.X - p.X) / d, 8), d))
|> List.fold fill []
|> List.rev
[<CommandMethod("ch")>]
let Test() =
let doc = AcAp.DocumentManager.MdiActiveDocument
let db = doc.Database
let ed = doc.Editor
let psr = ed.GetSelection(new SelectionFilter([| new TypedValue(0, "POINT") |]))
if psr.Status = PromptStatus.OK then
use tr = db.TransactionManager.StartTransaction()
use pl = new Polyline()
psr.Value
|> Seq.cast<_>
|> Seq.map (fun (so : SelectedObject) ->
let pt = tr.GetObject(so.ObjectId, OpenMode.ForRead) :?> DBPoint
new Point2d(pt.Position.X, pt.Position.Y))
|> convexHull
|> List.fold(fun i p -> pl.AddVertexAt(i, p, 0.0, 0.0, 0.0); i + 1) 0
|> ignore
pl.Closed <- true
pl.SetDatabaseDefaults()
let btr = tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite) :?> BlockTableRecord
btr.AppendEntity(pl) |> ignore
tr.AddNewlyCreatedDBObject(pl, true)
tr.Commit()
target audience:{advanced}