Topic: {Challenge} connect each two points whose distance is shorter than given value

[gile]

Hi,

I know this is a (very) old thread, but after trying the k-d tree route with C#, I've been playing with the divide and conquer one (using xy grid as shown by qjchen) and F#.

The code is quite concise and performances not so bad .

Code - F#: [Select]

1. module ConnectPointChallenge
2.  
3. open Autodesk.AutoCAD.DatabaseServices
4. open Autodesk.AutoCAD.EditorInput
5. open Autodesk.AutoCAD.Geometry
6. open Autodesk.AutoCAD.Runtime
7.  
8. type AcAp = Autodesk.AutoCAD.ApplicationServices.Application
9.  
10. let connectAll (pts: Point3d[]) dist =
11.     let getExtents pts =
12.         Seq.fold(fun (s: Extents3d) p -> s.AddPoint(p); s) (new Extents3d()) pts
13.     let ext = getExtents pts
14.     let xMax, yMax = ext.MaxPoint.X, ext.MaxPoint.Y
15.     let xMin, yMin = ext.MinPoint.X, ext.MinPoint.Y
16.     let col, row = int ((xMax - xMin) / dist) + 2, int ((yMax - yMin) / dist) + 3
17.     let table = Array2D.create col row []
18.     pts |> Seq.iter(fun p ->
19.                 let i, j = int ((p.X - xMin) / dist), int ((p.Y - yMin) / dist) + 1
20.                 table.[i, j] <- p :: table.[i, j])
21.     let dist = dist * dist
22.  
23.     let getConnexions i j =
24.         let sqrDist2d (p1: Point3d) (p2: Point3d) =
25.             (p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y)
26.         let connect pt pts acc =
27.             List.fold(fun s p -> if sqrDist2d pt p <= dist then (pt, p) :: s else s) acc pts
28.         let connectInside pts =
29.             let rec loop acc = function
30.                 | [] -> acc
31.                 | h :: t -> loop (connect h t acc) t
32.             loop [] pts
33.         let connectOutside pts acc =
34.             List.fold(fun s p -> connect p pts s) acc table.[i,j]
35.         table.[i,j]
36.         |> connectInside
37.         |> connectOutside table.[i + 1, j - 1]
38.         |> connectOutside table.[i + 1, j]
39.         |> connectOutside table.[i + 1, j + 1]
40.         |> connectOutside table.[i, j + 1]
41.  
42.     [| for i in 0 .. col - 2 do
43.         for j in 1 .. row - 2 do yield! getConnexions i j |]
44.  
45. [<CommandMethod("ConnectFs")>]
46. let connectFs () =
47.     let sw = new System.Diagnostics.Stopwatch()
48.     let doc = AcAp.DocumentManager.MdiActiveDocument
49.     let db = doc.Database
50.     let ed = doc.Editor
51.     sw.Start()
52.     use ms = SymbolUtilityServices.GetBlockModelSpaceId(db).Open(OpenMode.ForWrite)
53.              :?> BlockTableRecord
54.     let rxc = RXClass.GetClass(typeof<DBPoint>)
55.     let pts = [| for id in ms -> id |]
56.               |> Array.filter(fun id -> id.ObjectClass = rxc)
57.               |> Array.map(fun id ->
58.                     use pt = id.Open(OpenMode.ForRead) :?> DBPoint
59.                     pt.Position)
60.     let t0 = sw.ElapsedMilliseconds
61.     let pairs = connectAll pts 70.0
62.     let t1 = sw.ElapsedMilliseconds
63.     pairs
64.     |> Array.iter (fun (p1, p2) ->
65.         use line = new Line(p1, p2)
66.         ms.AppendEntity(line) |> ignore)
67.     sw.Stop()
68.     let t2 = sw.ElapsedMilliseconds
69.     ed.WriteMessage(
70.         "\nGet points:{0,9}\nConnect points:{1,5}\nDraw lines:{2,9}\nTotal:{3,14}",
71.         t0, t1 - t0, t2 - t1, t2);

Code: [Select]

10K points => 12,718 lines
Elapsed milliseconds:
Get points:       35
Connect points:   21
Draw lines:       56
Total:           112


100k points => 128,026 lines
Elapsed milliseconds:
Get points:      254
Connect points:  272
Draw lines:      633
Total:          1159


1M points => 1,280,741 lines
Elapsed milliseconds:
Get points:     2453
Connect points: 2792
Draw lines:    11748
Total:         16993

[qjchen]

Thank you very much, gile.

It is really quite concise.

I am regret that recently I am too busy to write programs.

I hope I could learn your code carefully for study.