练习 修改的一个凸包程序

csharp

用了 高飞版主 Lisp版的 Graham 扫描算法，用 Stack<T>维护一个凸包

1. using System;
   
2. using System.Collections.Generic;
   
3. using System.Diagnostics;
   
4. using System.Linq;
   
5. using Autodesk.AutoCAD.ApplicationServices;
   
6. using Autodesk.AutoCAD.DatabaseServices;
   
7. using Autodesk.AutoCAD.EditorInput;
   
8. using Autodesk.AutoCAD.Geometry;
   
9. using Autodesk.AutoCAD.Runtime;
   
10. using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;[assembly: CommandClass(typeof(AutoCAD_CSharp_plug_in13.MyCommands))]namespace AutoCAD_CSharp_plug_in13
    
11. {
    
12.     public class MyCommands
    
13.     {
    
14.         private Point2d _p0;        private bool Clockwise(Point2d p1, Point2d p2, Point2d p3)
    
15.         {
    
16.             return ((p2.X  - p3.X  )*(p2.Y   - p1.Y  ) - (p2.X  - p1.X )*(p2.Y   - p3.Y  )) > -1e-6;
    
17.         }
    
18.         //按角度
    
19.         private double Cosine(Point2d pt)
    
20.         {
    
21.             double d = _p0.GetDistanceTo(pt);
    
22.             return d == 0.0 ? 1.0 : Math.Round((pt.Y - _p0.Y)/d, 9);
    
23.         }
    
24.       
    
25.         private Point2d[] ConvexHull(List<Point2d> pts)
    
26.         {
    
27.             _p0 = pts.OrderBy(p => p.X).ThenBy(p => p.Y).Last( );//最右边点
    
28.             pts = pts.OrderByDescending(p => Cosine(p)).ThenBy(p => _p0.GetDistanceTo(p)).ToList();//按角度及距离排序
    
29.             Stack<Point2d> outPoint2Ds = new Stack<Point2d>();
    
30.             outPoint2Ds.Push(_p0);
    
31.             outPoint2Ds.Push(pts[1]);
    
32.             bool tf = true;
    
33.             for (int i = 2; i < pts.Count ; i++)
    
34.             {
    
35.                 Point2d n = pts[i];
    
36.                 Point2d p = outPoint2Ds.Pop();//出栈 car
    
37.                 Point2d q = outPoint2Ds.Pop();//取第一个 cadr
    
38.                 while (tf && Clockwise(n, p, q))
    
39.                 {
    
40.                     if (outPoint2Ds.Count > 1)
    
41.                     {
    
42.                         p = q;//出栈
    
43.                         q = outPoint2Ds.Pop() ;//car
    
44.                         
    
45.                     }
    
46.                     else
    
47.                     {
    
48.                         tf = false;
    
49.                     }
    
50.                 }
    
51.                 outPoint2Ds.Push(q);
    
52.                 outPoint2Ds.Push(p);
    
53.                 outPoint2Ds.Push(n);
    
54.                 tf = true;
    
55.             }
    
56.             return outPoint2Ds.ToArray() ;
    
57.         }        [CommandMethod("Test")]
    
58.         public void Test()
    
59.         {
    
60.             Document doc = AcAp.DocumentManager.MdiActiveDocument;
    
61.             Database db = doc.Database;
    
62.             Editor ed = doc.Editor;
    
63.             TypedValue[] filter = new TypedValue[1] {new TypedValue(0, "POINT")};
    
64.             PromptSelectionResult psr = ed.GetSelection(new SelectionFilter(filter));
    
65.             if (psr.Status != PromptStatus.OK) return;
    
66.             using (Transaction tr = db.TransactionManager.StartTransaction())
    
67.             using (Polyline pline = new Polyline())
    
68.             {
    
69.                 List<Point2d> pts = new List<Point2d>();
    
70.                 foreach (SelectedObject so in psr.Value)
    
71.                 {
    
72.                     DBPoint dbPt = (DBPoint) tr.GetObject(so.ObjectId, OpenMode.ForRead);
    
73.                     pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));
    
74.                 }
    
75.                 Stopwatch watch = new Stopwatch();
    
76.                 watch.Restart();
    
77.                 Point2d [] npts = ConvexHull(pts);
    
78.                 watch.Stop();
    
79.                 ed.WriteMessage("\nTime = " + watch.Elapsed.TotalMilliseconds.ToString());
    
80.                 for (int i = 0; i < npts.Length ; i++)
    
81.                 {
    
82.                     pline.AddVertexAt(i, npts[i], 0.0, 0.0, 0.0);
    
83.                 }
    
84.                 pline.Closed = true;
    
85.                 pline.SetDatabaseDefaults();
    
86.                 BlockTableRecord btr = (BlockTableRecord) tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);
    
87.                 btr.AppendEntity(pline);
    
88.                 tr.AddNewlyCreatedDBObject(pline, true);
    
89.                 tr.Commit();
    
90.             }
    
91.         }
    
92.     }
    
93. }

using System;<br /> using System.Collections.Generic;<br /> using System.Diagnostics;<br /> using System.Linq;<br /> using Autodesk.AutoCAD.ApplicationServices;<br /> using Autodesk.AutoCAD.DatabaseServices;<br /> using Autodesk.AutoCAD.EditorInput;<br /> using Autodesk.AutoCAD.Geometry;<br /> using Autodesk.AutoCAD.Runtime;<br /> using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;[assembly: CommandClass(typeof(AutoCAD_CSharp_plug_in13.MyCommands))]namespace AutoCAD_CSharp_plug_in13<br /> {<br />     public class MyCommands<br />     {<br />         private Point2d _p0;        private bool Clockwise(Point2d p1, Point2d p2, Point2d p3)<br />         {<br />             return ((p2.X  - p3.X  )*(p2.Y   - p1.Y  ) - (p2.X  - p1.X )*(p2.Y   - p3.Y  )) > -1e-6;<br />         }<br />         //按角度<br />         private double Cosine(Point2d pt)<br />         {<br />             double d = _p0.GetDistanceTo(pt);<br />             return d == 0.0 ? 1.0 : Math.Round((pt.Y - _p0.Y)/d, 9);<br />         }<br />        <br />         private Point2d[] ConvexHull(List<Point2d> pts)<br />         {<br />             _p0 = pts.OrderBy(p => p.X).ThenBy(p => p.Y).Last( );//最右边点<br />             pts = pts.OrderByDescending(p => Cosine(p)).ThenBy(p => _p0.GetDistanceTo(p)).ToList();//按角度及距离排序<br />             Stack<Point2d> outPoint2Ds = new Stack<Point2d>();<br />             outPoint2Ds.Push(_p0);<br />             outPoint2Ds.Push(pts[1]);<br />             bool tf = true;<br />             for (int i = 2; i < pts.Count ; i++)<br />             {<br />                 Point2d n = pts[i];<br />                 Point2d p = outPoint2Ds.Pop();//出栈 car<br />                 Point2d q = outPoint2Ds.Pop();//取第一个 cadr<br />                 while (tf && Clockwise(n, p, q))<br />                 {<br />                     if (outPoint2Ds.Count > 1)<br />                     {<br />                         p = q;//出栈<br />                         q = outPoint2Ds.Pop() ;//car<br />                         <br />                     }<br />                     else<br />                     {<br />                         tf = false;<br />                     }<br />                 }<br />                 outPoint2Ds.Push(q);<br />                 outPoint2Ds.Push(p);<br />                 outPoint2Ds.Push(n);<br />                 tf = true;<br />             }<br />             return outPoint2Ds.ToArray() ;<br />         }        [CommandMethod("Test")]<br />         public void Test()<br />         {<br />             Document doc = AcAp.DocumentManager.MdiActiveDocument;<br />             Database db = doc.Database;<br />             Editor ed = doc.Editor;<br />             TypedValue[] filter = new TypedValue[1] {new TypedValue(0, "POINT")};<br />             PromptSelectionResult psr = ed.GetSelection(new SelectionFilter(filter));<br />             if (psr.Status != PromptStatus.OK) return;<br />             using (Transaction tr = db.TransactionManager.StartTransaction())<br />             using (Polyline pline = new Polyline())<br />             {<br />                 List<Point2d> pts = new List<Point2d>();<br />                 foreach (SelectedObject so in psr.Value)<br />                 {<br />                     DBPoint dbPt = (DBPoint) tr.GetObject(so.ObjectId, OpenMode.ForRead);<br />                     pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));<br />                 }<br />                 Stopwatch watch = new Stopwatch();<br />                 watch.Restart();<br />                 Point2d [] npts = ConvexHull(pts);<br />                 watch.Stop();<br />                 ed.WriteMessage("\nTime = " + watch.Elapsed.TotalMilliseconds.ToString());<br />                 for (int i = 0; i < npts.Length ; i++)<br />                 {<br />                     pline.AddVertexAt(i, npts[i], 0.0, 0.0, 0.0);<br />                 }<br />                 pline.Closed = true;<br />                 pline.SetDatabaseDefaults();<br />                 BlockTableRecord btr = (BlockTableRecord) tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);<br />                 btr.AppendEntity(pline);<br />                 tr.AddNewlyCreatedDBObject(pline, true);<br />                 tr.Commit();<br />             }<br />         }<br />     }<br /> }

st788796

命令: TEST
选择对象: 指定对角点: 找到 143208 个

选择对象:

Time = 309.4958

不错

csharp

好像 q 先不用出栈，减少入栈、出栈次数

csharp

为什么有时候不对，多数时候对呢？
入栈和出栈不对，再修改

csharp

终于找到原因了，原来是 Math.Round 舍多了！

q3_2006

C#程序怎么用?和LISP一样吗??

csharp

刚试了试
命令: NETLOAD
命令: TEST
选择对象: 指定对角点: 找到 145152 个

选择对象:

Time = 200.7578

单位是毫秒

csharp

最终版

1. using System;
   
2. using System.Collections;
   
3. using System.Collections.Generic;
   
4. using System.Diagnostics;
   
5. using System.Linq;
   
6. using Autodesk.AutoCAD.ApplicationServices;
   
7. using Autodesk.AutoCAD.DatabaseServices;
   
8. using Autodesk.AutoCAD.EditorInput;
   
9. using Autodesk.AutoCAD.Geometry;
   
10. using Autodesk.AutoCAD.Interop.Common;
    
11. using Autodesk.AutoCAD.Runtime;
    
12. using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;
    
13. using Exception = System.Exception;
    
14. 
    
15. [assembly: CommandClass(typeof(AutoCAD_CSharp_plug_in13.MyCommands))]
    
16. 
    
17. namespace AutoCAD_CSharp_plug_in13
    
18. {
    
19.     public class MyCommands
    
20.     {
    
21.       
    
22.         private Point2d _p0;
    
23. 
    
24.         private bool Clockwise(Point2d p1, Point2d p2, Point2d p3)
    
25.         {
    
26.             return ((p2.X  - p3.X  )*(p2.Y   - p1.Y  ) - (p2.X  - p1.X )*(p2.Y   - p3.Y  )) > -1e-6;
    
27.         }
    
28.         //按角度
    
29.         private double Cosine(Point2d pt)
    
30.         {
    
31.             double d = _p0.GetDistanceTo(pt);
    
32.             return d == 0.0 ? 1.0 : (pt.Y - _p0.Y) / d;//sin
    
33.         }
    
34.       
    
35.         private Point2d[] ConvexHull(List<Point2d> pts)
    
36.         {
    
37.             _p0 = pts.OrderBy(p => p.X).ThenBy(p => p.Y).Last( );//最右边点
    
38.             pts = pts.OrderByDescending(p => Cosine(p)).ThenBy
    
39.                 (p => _p0.GetDistanceTo(p)).ToList();//按角度及距离排序
    
40. 
    
41.             Stack<Point2d> outPoint2Ds = new Stack<Point2d>();
    
42. 
    
43.             outPoint2Ds.Push(_p0);
    
44.             outPoint2Ds.Push(pts[1]);
    
45. 
    
46.             bool tf = true;
    
47.             for (int i = 2; i < pts.Count ; i++)
    
48.             {
    
49.                 Point2d n = pts[i];
    
50. 
    
51.                 Point2d p = outPoint2Ds.Pop();
    
52.                 Point2d q = outPoint2Ds.Peek()  ;
    
53. 
    
54.                 while (tf && Clockwise(n, p, q))
    
55.                 {
    
56.                   
    
57.                     if (outPoint2Ds.Count > 1)
    
58.                     {
    
59.                         outPoint2Ds.Pop();
    
60.                         p = q;
    
61.                         q = outPoint2Ds.Peek() ;
    
62.                        
    
63.                     }
    
64.                     else
    
65.                     {
    
66.                         tf = false;
    
67.                     }
    
68.                 }
    
69.                 outPoint2Ds.Push(p);
    
70.                 outPoint2Ds.Push(n);
    
71.                 tf = true;
    
72.             }
    
73.             return outPoint2Ds.ToArray() ;
    
74.         }
    
75. 
    
76.         [CommandMethod("Test")]
    
77.         public void Test()
    
78.         {
    
79.             Document doc = AcAp.DocumentManager.MdiActiveDocument;
    
80.             Database db = doc.Database;
    
81.             Editor ed = doc.Editor;
    
82.             TypedValue[] filter = new TypedValue[1] {new TypedValue(0, "POINT")};
    
83.             PromptSelectionResult psr = ed.GetSelection(new SelectionFilter(filter));
    
84.             if (psr.Status != PromptStatus.OK) return;
    
85.             using (Transaction tr = db.TransactionManager.StartTransaction())
    
86.             using (Polyline pline = new Polyline())
    
87.             {
    
88.                 List<Point2d> pts = new List<Point2d>();
    
89.                 Stopwatch watch = new Stopwatch();
    
90.                 watch.Restart();
    
91.                 foreach (SelectedObject so in psr.Value)
    
92.                 {
    
93.                     //DBPoint dbPt = (DBPoint) tr.GetObject(so.ObjectId, OpenMode.ForRead);
    
94.                     DBPoint dbPt = (DBPoint) so.ObjectId.GetObject(OpenMode.ForRead);
    
95.                     pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));
    
96.                 }
    
97.                 watch.Stop();
    
98.                 ed.WriteMessage("\nGet Points Used Time = " + watch.Elapsed.TotalSeconds.ToString());
    
99.                 watch.Restart();
    
100.                 Point2d [] npts = ConvexHull(pts);
     
101.                 watch.Stop();
     
102.                 ed.WriteMessage("\nGet Hull Used Time = " + watch.Elapsed.TotalSeconds.ToString());
     
103.                 for (int i = 0; i < npts.Length ; i++)
     
104.                 {
     
105.                     pline.AddVertexAt(i, npts[i], 0.0, 0.0, 0.0);
     
106.                 }
     
107.                 pline.Closed = true;
     
108.                 pline.SetDatabaseDefaults();
     
109.                 BlockTableRecord btr = (BlockTableRecord) tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);
     
110.                 btr.AppendEntity(pline);
     
111.                 tr.AddNewlyCreatedDBObject(pline, true);
     
112.                 tr.Commit();
     
113.             }
     
114.         }
     
115.     }
     
116. }
     

using System;<br /> using System.Collections;<br /> using System.Collections.Generic;<br /> using System.Diagnostics;<br /> using System.Linq;<br /> using Autodesk.AutoCAD.ApplicationServices;<br /> using Autodesk.AutoCAD.DatabaseServices;<br /> using Autodesk.AutoCAD.EditorInput;<br /> using Autodesk.AutoCAD.Geometry;<br /> using Autodesk.AutoCAD.Interop.Common;<br /> using Autodesk.AutoCAD.Runtime;<br /> using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;<br /> using Exception = System.Exception;<br /> <br /> [assembly: CommandClass(typeof(AutoCAD_CSharp_plug_in13.MyCommands))]<br /> <br /> namespace AutoCAD_CSharp_plug_in13<br /> {<br />     public class MyCommands<br />     {<br />        <br />         private Point2d _p0;<br /> <br />         private bool Clockwise(Point2d p1, Point2d p2, Point2d p3)<br />         {<br />             return ((p2.X  - p3.X  )*(p2.Y   - p1.Y  ) - (p2.X  - p1.X )*(p2.Y   - p3.Y  )) > -1e-6;<br />         }<br />         //按角度<br />         private double Cosine(Point2d pt)<br />         {<br />             double d = _p0.GetDistanceTo(pt);<br />             return d == 0.0 ? 1.0 : (pt.Y - _p0.Y) / d;//sin<br />         }<br />        <br />         private Point2d[] ConvexHull(List<Point2d> pts)<br />         {<br />             _p0 = pts.OrderBy(p => p.X).ThenBy(p => p.Y).Last( );//最右边点<br />             pts = pts.OrderByDescending(p => Cosine(p)).ThenBy<br />                 (p => _p0.GetDistanceTo(p)).ToList();//按角度及距离排序<br /> <br />             Stack<Point2d> outPoint2Ds = new Stack<Point2d>();<br /> <br />             outPoint2Ds.Push(_p0);<br />             outPoint2Ds.Push(pts[1]);<br /> <br />             bool tf = true;<br />             for (int i = 2; i < pts.Count ; i++)<br />             {<br />                 Point2d n = pts[i];<br /> <br />                 Point2d p = outPoint2Ds.Pop();<br />                 Point2d q = outPoint2Ds.Peek()  ;<br /> <br />                 while (tf && Clockwise(n, p, q))<br />                 {<br />                    <br />                     if (outPoint2Ds.Count > 1)<br />                     {<br />                         outPoint2Ds.Pop();<br />                         p = q;<br />                         q = outPoint2Ds.Peek() ;<br />                        <br />                     }<br />                     else<br />                     {<br />                         tf = false;<br />                     }<br />                 }<br />                 outPoint2Ds.Push(p);<br />                 outPoint2Ds.Push(n);<br />                 tf = true;<br />             }<br />             return outPoint2Ds.ToArray() ;<br />         }<br /> <br />         [CommandMethod("Test")]<br />         public void Test()<br />         {<br />             Document doc = AcAp.DocumentManager.MdiActiveDocument;<br />             Database db = doc.Database;<br />             Editor ed = doc.Editor;<br />             TypedValue[] filter = new TypedValue[1] {new TypedValue(0, "POINT")};<br />             PromptSelectionResult psr = ed.GetSelection(new SelectionFilter(filter));<br />             if (psr.Status != PromptStatus.OK) return;<br />             using (Transaction tr = db.TransactionManager.StartTransaction())<br />             using (Polyline pline = new Polyline())<br />             {<br />                 List<Point2d> pts = new List<Point2d>();<br />                 Stopwatch watch = new Stopwatch();<br />                 watch.Restart();<br />                 foreach (SelectedObject so in psr.Value)<br />                 {<br />                     //DBPoint dbPt = (DBPoint) tr.GetObject(so.ObjectId, OpenMode.ForRead);<br />                     DBPoint dbPt = (DBPoint) so.ObjectId.GetObject(OpenMode.ForRead);<br />                     pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));<br />                 }<br />                 watch.Stop();<br />                 ed.WriteMessage("\nGet Points Used Time = " + watch.Elapsed.TotalSeconds.ToString());<br />                 watch.Restart();<br />                 Point2d [] npts = ConvexHull(pts);<br />                 watch.Stop();<br />                 ed.WriteMessage("\nGet Hull Used Time = " + watch.Elapsed.TotalSeconds.ToString());<br />                 for (int i = 0; i < npts.Length ; i++)<br />                 {<br />                     pline.AddVertexAt(i, npts[i], 0.0, 0.0, 0.0);<br />                 }<br />                 pline.Closed = true;<br />                 pline.SetDatabaseDefaults();<br />                 BlockTableRecord btr = (BlockTableRecord) tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);<br />                 btr.AppendEntity(pline);<br />                 tr.AddNewlyCreatedDBObject(pline, true);<br />                 tr.Commit();<br />             }<br />         }<br />     }<br /> }<br />

命令:  TEST

选择对象: 指定对角点: 找到 580608 个

选择对象:
Get Points Used Time = 5.1831026
Get Hull Used Time = 0.9569396

csharp

1.                 foreach (ObjectId  so in psr.Value.GetObjectIds() )
   
2.                 {
   
3.                     //DBPoint dbPt = (DBPoint) tr.GetObject(so.ObjectId, OpenMode.ForRead);
   
4.                     DBPoint dbPt = (DBPoint) so.GetObject(OpenMode.ForRead);
   
5.                     pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));
   
6.                 }
   

                foreach (ObjectId  so in psr.Value.GetObjectIds() )<br />                 {<br />                     //DBPoint dbPt = (DBPoint) tr.GetObject(so.ObjectId, OpenMode.ForRead);<br />                     DBPoint dbPt = (DBPoint) so.GetObject(OpenMode.ForRead);<br />                     pts.Add(new Point2d(dbPt.Position.X, dbPt.Position.Y));<br />                 }<br />

再改进一句后的效果
命令: TEST

选择对象: 指定对角点: 找到 580608 个

选择对象:

Get Points Used Time = 1.6647834
Get Hull Used Time = 0.9625319

dnbcgrass

应该将
   watch.Restart();
改为
   watch.Reset();
   watch.Start();
谢谢分享！{:soso_e163:}{:soso_e179:}{:soso_e179:}{:soso_e179:}
试了一下。的确很快。
选择对象: 指定对角点: 找到 1002072 个
选择对象:
Get Points Used Time = 9.9183639
Get Hull Used Time = 3.3560182

dnbcgrass

速度比Lee Mac那个Convex Hull.vlx快10倍以上！:lol