Topic: -={ challenge }=- points in a circle

[Jeremy]

It is amazing to me how the simplest of things can have subtleties to them that I never thought about before. Consider the problem of creating a list of equally spaced points on a circle. Normally like most of you I have done the following:

Code: [Select]

(defun circle-points (cp  ;center point of circle of points
                      rad ;the radius of the circle of points
                      n   ;number of points on the circle
                      sa  ;start angle of where to begin
                      /  cnt ca ptlist
                      )
  (setq ca (/ (* 2 pi) n))
  (setq cnt 0)
  (repeat n
    (setq ptlist (cons (polar cp (+ (* cnt ca) sa) rad) ptlist))
    (setq cnt (1+ cnt))
  )
  ptlist
)

Pretty straightforward stuff, iterate through the points one by one and construct a list. We also took care to multiply the angle increment instead of adding it so that we wouldn't get a larger accumulating error. Is this the most efficient means of solving our problem? We are using a trig function for every point that we calculate and that is always wasteful. If we were calculating an even number of points it is clear that we could calculate half of them and then obtain the other half by merely changing the sign of the first group of points. Here is a function to do that

Code: [Select]

(defun even-circle-points (cp  ;center point of circle of points
                           rad ;the radius of the circle of points
                           n   ;number of points on the circle
                           sa  ;start angle of where to begin
                           /  cnt ca ptlist
                           )
  (if (zerop (rem n 2)) ;if we have an even number of points
    (progn
     (setq ca (/ (* 2 pi) n))
     (setq cnt 0)
     (repeat (/ n 2)  ;only do trig on half of the points
       (setq ptlist (cons (polar cp (+ (* cnt ca) sa) rad) ptlist))
       (setq cnt (1+ cnt))
     )
     (setq ptlist (reverse ptlist)) ;put the points in the order we found them
     (append ptlist
             (reverse (mapcar '(lambda (p)(mapcar '- p)) ptlist)))
  ))
)

I want you to think about whether we have exhausted our options yet. Are there other things that could be done to reduce calculations further? What are your solutions? I will provide more of mine if I don't see anyone else discovering them. Maybe you'll do better than me.

[chlh_jd]

Code: [Select]

(defun ss:ecp (cp rad n sa / ca pts)
  (if (zerop (rem n 2))
    (progn
      (setq ca (/ (* 2 pi) n))
      (repeat (/ n 2)
(setq pts (cons (polar cp sa rad) pts)
      sa (+ sa ca))
      )
      (setq pts (reverse pts))
      (append pts (mapcar '(lambda (p) (mapcar '+ cp (mapcar '- cp p))) pts))
    )
  )
)
(defun c:test (/ en n sa ent cp rad pts)
  (setq en (car (entsel "\nSelect a circle"))
n  (getint "\nDevide Numbers (Even) :")
sa (getreal "\nStart angle (°) :")
  )
  (if (and en n sa)
    (progn
      (setq sa (* (/ sa 180.) pi)
    ent (entget en)
    cp (cdr (assoc 10 ent))
    rad (cdr (assoc 40 ent))
      )
      (setq pts (ss:ecp cp rad n sa))
      (draw-pl (list pts (cons 62 1)))
      (entmake (list (cons 0 "LINE") (cons 10 (list 0 0 0)) (cons 11 (car pts))))
    )
  )
  (princ)
)
(defun draw-pl (lst)
  (entmake
    (append
      (list (cons 0 "LWPOLYLINE")
(cons 100  "AcDbEntity")
(cons 100  "AcDbPolyline")
    (cons 90 (length (car lst)))
       )     
      (mapcar (function (lambda (x) (cons 10 x))) (car lst))
      (list (cons 70 1))
      (cdr lst)
    )
  )
)


[David Bethel]

You could just do the full math with each iteration:

Code: [Select]

(defun cir-ptsl (cp rad n sa / i pl)
  (setq i 0)
  (repeat n
     (setq pl (cons (polar cp (+ sa (* pi 2 (/ i (float n)))) rad) pl)
            i (1+ i)))
 pl)
-David

[Lee Mac]

Code: [Select]

(defun f ( c r n s / i l )
    (setq i (/ (+ pi pi) n))
    (repeat n
        (setq s (- s i)
              l (cons (list (+ (car c) (* r (cos s))) (+ (cadr c) (* r (sin s)))) l)
        )
    )
)

[Jeremy]

Sorry David, the minute you called the polar function you started using the trig functions and you're still calculating all the points. Same for Lee. Here's a couple of more ideas to think about. First consider all N divisible by 4. We can calculate the first N/4 points and use the perpdot operator to get the 2nd quadrant. After that we can then reflect all of the points by changing signs. Doing it this way cuts our use of trig to only a quarter of the points.

Code: [Select]

;rotate a point by 90 degrees relative to a base point
(defun r90 (bpt p)
  (setq p (mapcar '- p bpt))  ;regularize to the base point
  (setq p (list (- (car p))(cadr p)))  ;rotate by 90
  (mapcar '+ bpt p)  ;return to true coordinates
)

;Change the sign of a number or point
(defun chs (x)(if (listp x)(mapcar '- x)(- x)))

;Remember, this only works for N divisible by 4
(defun mod4-circle-points (cp r n sa / ca cnt ptlist 2nd half)
   (setq ca (/ (+ pi pi) n))
   (setq cnt 0)
   (repeat (/ n 4)
     (setq 1st (cons (polar cp (+ (* cnt ca) sa) r) 1st))
     (setq cnt (1+ cnt))
   )
   (setq 2nd (mapcar 'r90 1st))
   (setq half (append (reverse 1st)(reverse 2nd)))
   (append half
           (reverse (mapcar 'chs half)))
)

But this is not the end! I was reading through Graphics Gems one night and found an algorithm that calculated points by only calculating the sine and cosine of the first point. Since the incrementing angle is constant one can calculate the sine and cosine of the next  point by using arithmetic only. Unfortunately, when I was scanning through the code I forgot where I was at and haven't been able to relocate it again! I will try to find it again and convert it to Autolisp unless someone else is aware of the technique.

[Lee Mac]

Were you perhaps referring to something like Bresenham's Algorithm?

Code: [Select]

(defun circlepoints ( cx cy r / e l x y )
    (setq x (- r)
          y 0.0
          e (- 2.0 (* 2.0 r))
    )
    (while (< x 0.0)
        (setq l
            (cons (list (- cx x) (+ cy y))
                (cons (list (- cx y) (- cy x))
                    (cons (list (+ cx x) (- cy y))
                        (cons (list (+ cx y) (+ cy x)) l)
                    )
                )
            )
        )
        (setq r e)
        (setq e
            (if (< x r)
                (+ e (* 2.0 (setq x (1+ x))) 1)
                (+ e (* 2.0 (setq y (1+ y))) 1)
            )
        )
    )
    l
)

Code: [Select]

(circlepoints 0.0 0.0 5.0)

[Lee Mac]

Actually, this is a better implementation, a translation of the C++ code from here.

Code: [Select]

(defun circlepoints ( cx cy r / e x y )
    (setq e (- r)
          x r
          y 0.0
    )
    (while (<= y x)
        (plot8points cx cy x y)
        (setq e (+ e y)
              y (1+  y)
              e (+ e y)
        )
        (if (<= 0 e)
            (setq x (1- x)
                  e (- e x)
                  e (- e x)
            )
        )
    )
    (princ)
)

(defun plot8points ( cx cy x y )
    (plot4points cx cy x y)
    (if (/= x y) (plot4points cx cy y x))
)

(defun plot4points ( cx cy x y )
    (point (+ cx x) (+ cy y))
    (if (/= x 0.0) (point (- cx x) (+ cy y)))
    (if (/= y 0.0) (point (+ cx x) (- cy y)))
    (if (and (/= x 0.0) (/= y 0.0)) (point (- cx x) (- cy y)))
)

(defun point ( x y )
    (entmakex (list '(0 . "POINT") (list 10 x y)))
)

[Stefan]

Another method

Code: [Select]

(vl-load-com)
(defun c:pcirc (/ p r u n c lst param delta)
  (if
    (and
      (setq p (getpoint    "\nCenter point: "))
      (setq r (getdist p   "\nRadius: "))
      (setq u (getangle p  "\nStart angle: "))
      (setq n (getint      "\nNumber of points: "))
      (setq c (entmakex (list '(0 . "CIRCLE") (cons 10 p) (cons 40 r)))
      )
    )
     (progn
       (setq lst
              (mapcar
                '(lambda (x) (vlax-curve-getPointAtParam c x))
                (repeat n
                  (setq param
                         (cons
                           (+ (cond ((car param))
                                    ((- u (setq delta (/ (* 2. pi) n))))
                              )
                              delta
                           )
                           param
                         )
                  )
                )
              )
       )
       (entdel c)
       (mapcar '(lambda (x) (entmakex (list '(0 . "POINT") (cons 10 x)))) lst)
     )
  )
  (princ)
)

But this will calculate param list and I wonder if this is more convenient than your method

[Lee Mac]

Nice variation Stefan - where efficiency is concerned, you may be better to use the curve function within the repeat loop to calculate the points, then immediately use the entmake to create the points; rather than creating a list of params then iterating through this list again to calculate the points, then iterating through it again to create the points 

[Stefan]

Nice variation Stefan - where efficiency is concerned, you may be better to use the curve function within the repeat loop to calculate the points, then immediately use the entmake to create the points; rather than creating a list of params then iterating through this list again to calculate the points, then iterating through it again to create the points 

Thank you Lee.
I used entmake just to show the result. I think OP want just the list as final result (which my function doesn't do, but I think it is easy to modify for this purpose)