凸包

Imports Autodesk.AutoCAD.ApplicationServices.Application
Imports Autodesk.AutoCAD.Runtime
Imports Autodesk.AutoCAD.Geometry
Imports Autodesk.AutoCAD.EditorInput
Imports Autodesk.AutoCAD.DatabaseServices
Imports Autodesk.AutoCAD.ApplicationServices
Imports System.Collections.Generic

Namespace ConvexHull '凸包
    Public Class Commands
        Private _p0 As Point2d
        '顺时针
        Private Function Clockwise(ByVal p1 As Point2d, ByVal p2 As Point2d, ByVal p3 As Point2d) As Boolean
            Return ((p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X)) < 0.00000001
        End Function

        Private Function ComparePoints(ByVal p1 As Point2d, ByVal p2 As Point2d) As Integer
            If p1.IsEqualTo(p2) Then
                '点重合
                Return 0
            End If
            Dim d1 As Double = _p0.GetDistanceTo(p1)
            Dim d2 As Double = _p0.GetDistanceTo(p2)
            If d1 = 0.0 Then
                'p1到P0距离为0
                Return -1
            End If
            If d2 = 0.0 Then
                'p2到P0距离为0
                Return 1
            End If
            '夹角
            Dim cos As Double = (p2.X - _p0.X) / d2 - (p1.X - _p0.X) / d1
            If cos < -0.00000001 Then
                Return -1
            End If
            If cos > 0.00000001 Then
                Return 1
            End If
            Return d1.CompareTo(d2)
        End Function

        Private Function ConvexHull(ByVal pts As List(Of Point2d)) As List(Of Point2d)
            _p0 = pts(0)
            Dim i As Integer = 1
            While i < pts.Count
                Dim pt As Point2d = pts(i)
                If pt.Y < _p0.Y OrElse (pt.Y = _p0.Y AndAlso pt.X < _p0.X) Then
                    _p0 = pt
                End If
                i += 1
            End While
            pts.Sort(AddressOf ComparePoints)
            'Dim i As Integer = 1
            i = 1
            While i < pts.Count - 1
                While i > 0 AndAlso Clockwise(pts(i - 1), pts(i), pts(i + 1))
                    pts.RemoveAt(i)
                    i -= 1
                End While
                i += 1
            End While
            Return pts
        End Function

        <CommandMethod("TcTuBao")> _
        Public Sub TcTuBao()
            Dim doc As Document = Autodesk.AutoCAD.ApplicationServices.Application.DocumentManager.MdiActiveDocument
            Dim db As Database = doc.Database
            Dim ed As Editor = doc.Editor
            Dim acTypValAr(0) As TypedValue
            acTypValAr.SetValue(New TypedValue(DxfCode.Start, "POINT"), 0)
            Dim psr As PromptSelectionResult = ed.GetSelection(New SelectionFilter(acTypValAr))
            If psr.Status <> PromptStatus.OK Then
                Return
            End If
            Using tr As Transaction = db.TransactionManager.StartTransaction()
                Using pline As New Polyline()
                    Dim pts As New List(Of Point2d)()
                    For Each so As SelectedObject In psr.Value
                        Dim dbPt As DBPoint = CType(tr.GetObject(so.ObjectId, OpenMode.ForRead), DBPoint)
                        pts.Add(New Point2d(dbPt.Position.X, dbPt.Position.Y))
                    Next
                    Dim i As Integer = 0
                    While i < ConvexHull(pts).Count
                        pline.AddVertexAt(i, pts(i), 0.0, 0.0, 0.0)
                        i += 1
                    End While
                    pline.Closed = True
                    pline.SetDatabaseDefaults()
                    Dim btr As BlockTableRecord = CType(tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite), BlockTableRecord)
                    btr.AppendEntity(pline)
                    tr.AddNewlyCreatedDBObject(pline, True)
                    tr.Commit()
                End Using
            End Using
        End Sub
    End Class
End Namespace