Through the Interface

Solving a fun little geometry problem in C# and F#

, , ,

A colleague set me a fun little geometry-related challenge a couple of days ago: to write C# and F# applications to make AutoCAD draw lines between a number of points spaced evenly around the circumference of a circle.

Lines between points

Here's the first C# version I wrote, which makes use of a function to collect the various points before indexing into the collection from a nested loop:

using Autodesk.AutoCAD.ApplicationServices;

using Autodesk.AutoCAD.Runtime;

using Autodesk.AutoCAD.DatabaseServices;

using Autodesk.AutoCAD.Geometry;

using System;

 

namespace CircleOfLines

{

  public class Commands

  {

    public static Point3dCollection pointsOnCircle(

      Point3d center, double radius, int n

    )

    {

      double alpha = Math.PI * 2 / n;

      Point3dCollection pts = new Point3dCollection();

 

      for (int i = 0; i < n; i++)

      {

        double theta = alpha * i;

        Point3d pt =

          new Point3d(

            center.X + Math.Cos(theta) * radius,

            center.Y + Math.Sin(theta) * radius,

            center.Z

          );

        pts.Add(pt);

      }

      return pts;

    }

 

    [CommandMethod("CSCIR")]

    public void CreateLinesBetweenPoints()

    {

      Database db =

        HostApplicationServices.WorkingDatabase;

      Transaction tr =

        db.TransactionManager.StartTransaction();

 

      using (tr)

      {

        BlockTable bt =

          (BlockTable)tr.GetObject(

            db.BlockTableId,

            OpenMode.ForRead

          );

        BlockTableRecord btr =

          (BlockTableRecord)tr.GetObject(

            bt[BlockTableRecord.ModelSpace],

            OpenMode.ForWrite

          );

 

        int n = 19;

        Point3dCollection pts =

          pointsOnCircle(new Point3d(0, 0, 0), 5.0, n);

        for (int i = 0; i < n; i++)

        {

          for (int j = i + 1; j < n; j++)

          {

            Line ln = new Line(pts[i], pts[j]);

            btr.AppendEntity(ln);

            tr.AddNewlyCreatedDBObject(ln, true);

          }

        }

        tr.Commit();

      }

    }

  }

}

I also wrote a "flattened" version in C# using a more linear approach (avoiding the function definition/call), although ultimately I believe the prior version to be more realistic:

using Autodesk.AutoCAD.ApplicationServices;

using Autodesk.AutoCAD.Runtime;

using Autodesk.AutoCAD.DatabaseServices;

using Autodesk.AutoCAD.Geometry;

using System;

 

namespace CircleOfLines

{

  public class Commands2

  {

    [CommandMethod("CSCIR2")]

    public void CreateLinesBetweenPoints2()

&#
160;   {

      Database db =

        HostApplicationServices.WorkingDatabase;

      Transaction tr =

        db.TransactionManager.StartTransaction();

 

      using (tr)

      {

        BlockTable bt =

          (BlockTable)tr.GetObject(

            db.BlockTableId,

            OpenMode.ForRead

          );

        BlockTableRecord btr =

          (BlockTableRecord)tr.GetObject(

            bt[BlockTableRecord.ModelSpace],

            OpenMode.ForWrite

          );

 

        int n = 19;

        Point3d center = new Point3d(0, 0, 0);

        double radius = 5.0;

        double alpha = Math.PI * 2 / n;

 

        for (int i = 0; i < n; i++)

        {

          double theta = alpha * i;

          Point3d pt1 =

            new Point3d(

              center.X + Math.Cos(theta) * radius,

              center.Y + Math.Sin(theta) * radius,

              center.Z

            );

 

          for (int j = i + 1; j < n; j++)

          {

            double theta2 = alpha * j;

            Point3d pt2 =

              new Point3d(

                center.X + Math.Cos(theta2) * radius,

                center.Y + Math.Sin(theta2) * radius,

                center.Z

              );

            Line ln = new Line(pt1, pt2);

            btr.AppendEntity(ln);

            tr.AddNewlyCreatedDBObject(ln, true);

          }

        }

        tr.Commit();

      }

    }

  }

}

And finally I provided a really "functional" version (in the sense that it uses Functional Programming techniques – all three versions are functional, of course 😉 in F#. This avoids any use of direct iteration, preferring to use data pipelining and recursion, although the recursion gets changed to iteration in the generated IL by the F# compiler's tail call optimization.

module CircleOfLines

 

open Autodesk.AutoCAD.ApplicationServices

open Autodesk.AutoCAD.Runtime

open Autodesk.AutoCAD.DatabaseServices

open Autodesk.AutoCAD.Geometry

open System

 

let rec circPoints acc (cen : Point3d) rad alpha n =

  if n <= 0 then

    acc

  else

    let theta = alpha * (float)n

    let pt =

      new Point3d

        (cen.X + Math.Cos(theta) * rad,

        cen.Y + Math.Sin(theta) * rad,

        cen.Z)

    circPoints (pt :: acc) cen rad alpha (n-1)

 

let pointsOnCircle cen rad n =

  let alpha = Math.PI * 2.0 / (float)n

  circPoints [] cen rad alpha n

 

let rec fromAtoBs acc pt1 pts =

  match pts with

  | [] -> acc

  | pt2::t ->

    let ln = new Line(pt1,pt2)

    fromAtoBs (ln :: acc) pt1 t

 

let linesFromPoint start endpts = fromAtoBs [] start endpts

 

let rec fromAsToBs acc pts =

  match pts with

  | [] -> acc

  | h :: t ->

    fromAsToBs (linesFromPoint h t @ acc) t

 

let linesBetweenPoints pts = fromAsToBs [] pts

 

[<CommandMethod("FSCIR")>]

let createLinesBetweenPoints() =

 

  let db = HostApplicationServices.WorkingDatabase

  use tr = db.TransactionManager.StartTransaction()

 

  let bt =

    tr.GetObject

      (db.BlockTableId,OpenMode.ForRead)

    :?> BlockTable

 

  let ms =

    tr.GetObject

      (bt.[BlockTableRecord.ModelSpace],

      OpenMode.ForWrite)

    :?> BlockTableRecord

 

  let addToDatabase ent =

    ms.AppendEntity(ent) |> ignore

    tr.AddNewlyCreatedDBObject(ent, true)

 

  pointsOnCircle (new Point3d(0.0, 0.0, 0.0)) 5.0 19

  |> linesBetweenPoints

  |> List.map addToDatabase

  |> ignore

 

  tr.Commit()

All versions do the same thing and actually have similar numbers of lines of code (although that would probably be different if I were formatting to a broader page width than fits on my blog, of course).

Update

Thanks for MichaelGG for the comment helping refine the F# implementation. Here's the updated code which is, indeed, a good few lines shorter:

module CircleOfLines

 

open Autodesk.AutoCAD.ApplicationServices

open Autodesk.AutoCAD.Runtime

open Autodesk.AutoCAD.DatabaseServices

open Autodesk.AutoCAD.Geometry

open System

 

let pointsOnCircle (cen: Point3d) rad n =

  let alpha = Math.PI * 2.0 / (float)n

  let calcPoint n =

    let theta = alpha * (float)(n + 1)

    Point3d(cen.X + Math.Cos theta * rad,

      cen.Y + Math.Sin theta * rad,

      cen.Z)

  List.init n calcPoint

 

let linesFromPoint start endpts =

  endpts |> List.map(fun x -> new Line(start, x)) |> List.rev

 

let rec fromAsToBs acc pts =

  match pts with

  | [] -> acc

  | h :: t ->

   
fromAsToBs (linesFromPoint h t @ acc) t

 

let linesBetweenPoints pts = fromAsToBs [] pts

 

[<CommandMethod("FSCIR")>]

let createLinesBetweenPoints() =

 

  let db = HostApplicationServices.WorkingDatabase

  use tr = db.TransactionManager.StartTransaction()

 

  let bt =

    tr.GetObject

      (db.BlockTableId,OpenMode.ForRead)

    :?> BlockTable

 

  let ms =

    tr.GetObject

      (bt.[BlockTableRecord.ModelSpace],

      OpenMode.ForWrite)

    :?> BlockTableRecord

 

  let addToDatabase ent =

    ms.AppendEntity(ent) |> ignore

    tr.AddNewlyCreatedDBObject(ent, true)

 

  pointsOnCircle (new Point3d(0.0, 0.0, 0.0)) 5.0 19

  |> linesBetweenPoints

  |> List.map addToDatabase

  |> ignore

 

  tr.Commit()

Oh, and thanks to Jason Davies I now know I've been plotting a complete graph. Which is even easier to plot using Wolfram Alpha than it is using C# or F# inside AutoCAD. 😉

  1. Jason Davies Avatar
    Jason Davies

    This is known as a 'complete graph'. Here's my JavaScript-based take on the matter: jasondavies.com/complete-graphs/

    Reply
  2. Kean Walmsley Avatar
    Kean Walmsley

    Cool - thanks, Jason! 🙂

    Kean

    Reply
  3. MichaelGG Avatar
    MichaelGG

    Neat. The F# would be considerably shorter if you used the built in functions instead of rolling them by hand :). For instance:

    let linesFromPoint start endpts =
    endpts |> List.map(fun x -> Line(start, x))
    |> List.rev

    and

    let pointsOnCircle (cen: Point3d) rad n =
    let alpha = Math.PI * 2.0 / (float)n
    let calcPoint n =
    let theta = alpha * (float)(n + 1)
    Point3d(cen.X + Math.Cos theta * rad,
    cen.Y + Math.Sin theta * rad,
    cen.Z)
    List.init n calcPoint

    Reply
  4. Kean Walmsley Avatar
    Kean Walmsley

    Excellent - that is much nicer.

    Thanks, Michael!

    Kean

    Reply
  5. Art Scott Avatar
    Art Scott

    Thanks.

    You are a natural teacher/mentor/professor.

    Reply
  6. neo Avatar
    neo

    thanks for solving the problem

    Reply
  7. Adrian Avatar
    Adrian

    I like Cay Horstman's solution in Scala.

    weblogs.java.net/blog/cayhorstmann/archive/2010/11/12/geometry-problem-scala-0

    Reply
  8. Kean Walmsley Avatar
    Kean Walmsley

    Yes, very nice. And an approach that would be relatively easy to implement using F#, too, I believe.

    I have to say it's a shame about the slightly preachy tone of the post: if I'd realised that my 30 minutes spent helping out a colleague would fuel a religious discussion, I might have spent more time on it. 🙂

    Kean

    Reply
  9. Charles Avatar
    Charles

    cay's approach translates directly into C# as well. Here is a version that draws onto the WPF canvas:

    namespace zzDrawCompleteGraph
    {
    using System;
    using System.Collections.Generic;
    using System.Windows.Controls;
    using WpfLine = System.Windows.Shapes.Line;

    class CompleteGraph
    {
    private Size size;

    public void Draw(Canvas canvasPanel)
    {
    size = new Size(canvasPanel.Height, canvasPanel.Width);
    var n = 19;

    // Draw lines onto canvas
    foreach (var line in GetLines(n))
    {
    var wpfLine = new WpfLine();
    wpfLine.Stroke = System.Windows.Media.Brushes.LightSteelBlue;
    wpfLine.StrokeThickness = 1;
    wpfLine.X1 = line.A.A;
    wpfLine.X2 = line.B.A;
    wpfLine.Y1 = line.A.B;
    wpfLine.Y2 = line.B.B;
    canvasPanel.Children.Add(wpfLine);
    }
    }

    private IEnumerable<pair> GetPairs(int n)
    {
    for (var i = 0; i <= n; i++)
    {
    for (var j = 0; j <= n; j++)
    {
    if (i < j)
    {
    yield return new Pair(i, j);
    }
    }
    }
    }

    private IEnumerable<point> GetPoints(int n)
    {
    for (var i = 0; i <= n; i++)
    {
    yield return NewPoint(i, n, size.B);
    }
    }

    private IEnumerable<line> GetLines(int n)
    {
    foreach (var pair in GetPairs(n))
    {
    foreach (var start in GetPoints(n))
    {
    foreach (var end in GetPoints(n))
    {
    yield return new Line(start, end);
    }
    }
    }
    }

    private Point NewPoint(int i, int n, double width)
    {
    return new Point(
    Convert.ToInt32(((Math.Cos(2 * Math.PI * i / n ) + 1) * width / 2)),
    Convert.ToInt32(((Math.Sin(2 * Math.PI * i / n ) + 1) * width / 2)));
    }
    }

    // Supporting types
    class Pair : BinaryValue<int> { public Pair(int i, int j) : base(i, j) { } }
    class Point : BinaryValue<int> { public Point(int x, int y) : base(x, y) { } }
    class Line : BinaryValue<point> { public Line(Point start, Point end) : base(start, end) { } }
    class Size : BinaryValue<double> { public Size(double height, double width) : base(height, width) { } }

    class BinaryValue <t>
    {
    public BinaryValue(T a, T b)
    {
    this.A = a;
    this.B = b;
    }
    public T A { get; set; }
    public T B { get; set; }
    }
    }

    Reply
  10. Gilles Chanteau Avatar
    Gilles Chanteau

    Hi,
    A little more concise F# way using a comprehension and the Seq.unfold function

    let linesFromPoint start endpts =
    endpts |> List.map(fun x -> new Line(start, x))

    let linesOfCircle (cen: Point3d) rad n =
    let alpha = Math.PI * 2.0 / float n
    [for i in 0 .. n - 1 ->
    new Point3d(cen.X + cos (float i * alpha) * rad,
    cen.Y + sin (float i * alpha) * rad,
    cen.Z)]
    |> Seq.unfold(function
    | h::t -> Some(linesFromPoint h t, t)
    | _ -> None)
    |> Seq.concat

    Then, just call:

    linesOfCircle Point3d.Origin 5.0 19
    |> Seq.iter addToDatabase

    Reply
  11. Gilles Chanteau Avatar
    Gilles Chanteau

    May be more suitable this way:

    let polar (pt: Point3d) angle dist =
    new Point3d(pt.X + cos angle * dist, pt.Y + sin angle * dist, pt.Z)

    let linesOfCircle (cen: Point3d) rad n =
    let alpha = Math.PI * 2.0 / float n
    [for i in 0 .. n - 1 -> polar cen (float i * alpha) rad]
    |> Seq.unfold(function
    | h::t -> Some(List.map(fun x -> new Line(h, x)) t, t)
    | _ -> None)
    |> Seq.concat

    Reply
  12. Kean Walmsley Avatar
    Kean Walmsley

    Merci, Gilles. 🙂

    Kean

    Reply

Leave a Reply to Charles Cancel reply

Your email address will not be published. Required fields are marked *