 Author Topic: =={challenge}==Find the maximum inscribed circle  (Read 12897 times)

0 Members and 1 Guest are viewing this topic.

chlh_jd

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #30 on: July 27, 2012, 01:56:21 PM »
Perhaps , When the grid division is not small enough in step1 ,  ALL close to the max-dia zone from step1 must be calculated in step2  ?

Is very important to the value of (step1)
If there are areas of similar size could potentially contain the maximum circle, it is appropriate to increase this value, to the detriment of the time required.
Increasing the value of (repeat N (grid_2) (Point_center)) is then refined the position of point searched.

(grid_1) ---> subdivision = step1 x step1

(grid_2) ---> subdivision = step2 x step2
Wonderful explanation, GP, Thank you very much.

chlh_jd

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #31 on: July 27, 2012, 02:34:24 PM »
Stefan，Excellent!! Both of you are geniuses!
1+

I guess, AutoCAD has its own regulations on the offset curve .

chlh_jd

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #32 on: July 27, 2012, 02:41:23 PM »
matrix take shape and fill it with a brush matrix
then add up the numbers and find the position of the greatest number.
Excellent algorithm !
Look forward to further implementation .

Does it has been used in the AutoCAD Core Applications ? Re: =={challenge}==Find the maximum inscribed circle
« Reply #33 on: July 27, 2012, 11:34:22 PM »
matrix take shape and fill it with a brush matrix
then add up the numbers and find the position of the greatest number.
Excellent algorithm !
Look forward to further implementation .

Does it has been used in the ?

Yes, I have used this algorithm in one of the commercial programs. I can not publish the code here, and details of use. But I have shown the way!

I do not work in the autodesk, though, I am now a member of the ADN.
I think that these algorithms are not used in AutoCAD Core Applications, but can not be sure...

chlh_jd

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #34 on: July 28, 2012, 02:34:16 AM »
Yes, I have used this algorithm in one of the commercial programs. I can not publish the code here, and details of use. But I have shown the way!
Depth explanation of the grid method , Thanks again .
I think that these algorithms are not used in AutoCAD Core Applications, but can not be sure...
In some old acad versions , I miss seen that boundary can be created by two method , one is Filling Method , another is Ray Method . Re: =={challenge}==Find the maximum inscribed circle
« Reply #35 on: July 28, 2012, 03:04:00 AM »
"Ray Method" is a method for determining the inside or the outside.
In their programs, I use another method to determine the inside or the outside. It does not require checking the intersection and running quickly.

need to check the direction of a polyline, the angle between the direction of the polyline and the first derivative. If 0 < A < pi and polyline counter-clockwise, the point is inside. If the nearest point on the polyline gets on top, should be repeated to a neighboring segment. further

PS. ray method sometimes gives an error - if the beam passes through the tangent to the path and not falling into one point of intersection gives the...
therefore, I developed another method that works fast enough...
« Last Edit: July 28, 2012, 03:07:12 AM by ElpanovEvgeniy »

chlh_jd

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #36 on: July 29, 2012, 02:47:33 PM »
"Ray Method" is a method for determining the inside or the outside.
In their programs, I use another method to determine the inside or the outside. It does not require checking the intersection and running quickly.

need to check the direction of a polyline, the angle between the direction of the polyline and the first derivative. If 0 < A < pi and polyline counter-clockwise, the point is inside. If the nearest point on the polyline gets on top, should be repeated to a neighboring segment. further

PS. ray method sometimes gives an error - if the beam passes through the tangent to the path and not falling into one point of intersection gives the...
therefore, I developed another method that works fast enough...
Thanks ElpanovEvgeniy .
Agree with you , but I have not understood that how to determine which point's and how many point's First derivative in the Curve ?
For polygon ,  one by one ; For Polyline (contained arcs) or other type curve ?

Faster

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #37 on: July 29, 2012, 10:29:31 PM »
According to ElpanovEvgeniy's algorithm,I wrote the following codes:
Code - Auto/Visual Lisp: [Select]
1. (defun PtInPOLY-P  (POLY PT / CP PL PARAM DEV A)
2.   (defun LM:ListClockwise-p ( lst )
3.         (apply '+
4.                     (lambda ( a b )
5.                         (- (* (car b) (cadr a)) (* (car a) (cadr b)))
6.                     )
7.                 )
8.                 lst (cons (last lst) lst)
9.             )
10.         )
11.     )
12. )
13.
14.
15.   (cond
16.     ((equal pt
17.             (setq cp (vlax-curve-getclosestpointto poly pt))
18.             1e-8))
19.     (t
20.      (setq pl
21.               'cdr
22.               (vl-remove-if-not
23.                 '(lambda (x) (= 10 (car x)))
24.                 (entget poly)
25.                 )
26.               )
27.            )
28.      (setq param (vlax-curve-getparamatpoint poly cp))
29.      (if (not (setq dev (vlax-curve-getFirstDeriv poly param)))
30.                             poly
31.                             (setq param (+ 1e-8 param)))))
32.                      poly
33.                      (setq param (- param 1e-8 1e-8))))
34.          )
35.        )
36.      (setq cp (vlax-curve-getpointatparam poly param))
37.      (setq a (- (angle cp pt) (angle '(0 0 0) dev)))
38.      (if (MINUSP a)
39.        (setq a (+ a pi pi)))
40.      (if (LM:ListClockwise-p pl)
41.        (> a pi)
42.        (< a pi)
43.        )
44.      )
45.     )
46.   )
47. Re: =={challenge}==Find the maximum inscribed circle
« Reply #38 on: July 29, 2012, 11:44:16 PM »
good code
It does not take into account details.
1. As I said, if the closest point falls on the top, you need to jointly consider both segments.
2. check the direction of a polyline, written by Lee does not work with polylines having arc segments.
« Last Edit: July 29, 2012, 11:59:31 PM by ElpanovEvgeniy » Re: =={challenge}==Find the maximum inscribed circle
« Reply #39 on: July 29, 2012, 11:53:25 PM »
Direction and Reverse lwpolyline Faster

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #40 on: July 30, 2012, 02:41:24 AM »
good code
It does not take into account details.
1. As I said, if the closest point falls on the top, you need to jointly consider both segments.
2. check the direction of a polyline, written by Lee does not work with polylines having arc segments.
Thank you  ElpanovEvgeniy!
This is improved version:
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.
Code - Auto/Visual Lisp: [Select]
1. (defun PtInPOLY-P  (POLY PT        /       CP      LW
2.                                    MINP    MAXP    MINX    MINY
3.                                    MAXX    MAXY    X       Y
4.                                    LST     CLOCKWISEP      ENDPARAM
5.                                    CURVELENGTH     PARAM   DIST
6.                                    D1      D2      DEV     A)
7.   (cond
8.     ((equal pt
9.             (setq cp (vlax-curve-getclosestpointto poly pt))
10.             1e-8))
11.     ((progn
12.          (setq lw (vlax-ename->vla-object POLY))
13.          'MinP
14.          'MaxP)
15.        (setq MinP (vlax-safearray->list MinP))
16.        (setq MaxP (vlax-safearray->list MaxP))
17.        (setq minx (car MinP)
18.              miny (cadr MinP)
19.              maxx (car MaxP)
20.              maxy (cadr MaxP)
21.              x    (car pt)
22.              y    (cadr pt)
23.              )
24.        (or (< x minx)
25.            (> x maxx)
26.            (< y miny)
27.            (> y maxy)
28.            )
29.        )
30.      NIL
31.      )
32.     (t
33.      (setq
34.        lst (mapcar
35.                (lambda (x)
36.                    lw
37.                    )
38.                  )
39.                )
40.              (list minp
41.                    (list minx maxy)
42.                    MaxP
43.                    (list maxx miny)
44.                    )
45.              )
46.        )
47.      (setq ClockwiseP
48.             (if (or
49.                   (<= (car lst) (cadr lst) (caddr lst) (cadddr lst))
50.                   (<= (cadr lst) (caddr lst) (cadddr lst) (car lst))
51.                   (<= (caddr lst) (cadddr lst) (car lst) (cadr lst))
52.                   (<= (cadddr lst) (car lst) (cadr lst) (caddr lst))
53.                   ) ;_  or
54.               t
55.               ) ;_  if
56.            )
57.      (setq endparam    (vlax-curve-getendparam poly)
58.            curvelength (vlax-curve-getDistAtParam poly endparam)
59.            )
60.      (setq param (vlax-curve-getparamatpoint poly cp)
61.            dist  (vlax-curve-getDistAtParam poly param)
62.            )
63.      (if (equal param (fix param) 1e-8)
64.          (setq d1 (- dist 1e-8))
65.          (if (minusp d1)
66.            (setq d1 (+ curvelength d1))
67.            )
68.          (setq d2 (+ dist 1e-8))
69.          (if (> d2 curvelength)
70.            (setq d2 (- d2 curvelength)))
71.          (if (< (distance pt (vlax-curve-getpointatdist poly d1))
72.                 (distance pt (vlax-curve-getpointatdist poly d2))
73.                 )
74.            (setq param (vlax-curve-getparamatdist poly d1))
75.            (setq param (vlax-curve-getparamatdist poly d2))
76.            )
77.          )
78.        )
79.      (setq dev (vlax-curve-getFirstDeriv poly param)
80.            cp  (vlax-curve-getpointatparam poly param)
81.            )
82.      ;|(setq a (- (angle cp pt) (angle '(0 0 0) dev)))
83.      (if (MINUSP a)
84.        (setq a (+ a pi pi)))
85.      (if ClockwiseP
86.        (> a pi)
87.        (< a pi)
88.        )|;
89.   ;;Another alternative judge method
90.        (=       ClockwiseP
91.         (
92.          (lambda (p1 p2 p3)
93.            (<
94.              (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1)))
95.              (* (- (cadr p2) (cadr p1)) (- (car p3) (car p1)))
96.              )
97.            )
98.           pt
99.           cp
100.           (mapcar '+ cp dev)
101.           )
102.         )
103.      )
104.     )
105.   )
106.
« Last Edit: July 31, 2012, 01:48:22 AM by Faster » Re: =={challenge}==Find the maximum inscribed circle
« Reply #41 on: July 30, 2012, 03:49:55 AM »
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.

which direction this lwpolyline?

The code Lee will give the wrong direction...

Faster

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #42 on: July 30, 2012, 04:09:42 AM »
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.

which direction this lwpolyline?

The code Lee will give the wrong direction...
I see, thank you very much.

chlh_jd

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #43 on: July 30, 2012, 11:41:17 AM »
This is improved version:
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.
Hi Faster , good codes.
Test not ok for Self-intersecting curves , I post the test dwg .

Faster

• Guest Re: =={challenge}==Find the maximum inscribed circle
« Reply #44 on: July 30, 2012, 08:45:59 PM »
This is improved version:
I wondered why the function "LM:ListClockwise-p " does not work with polylines having arc segments.
Hi Faster , good codes.
Test not ok for Self-intersecting curves , I post the test dwg .
I think ElpanovEvgeniy's  algorithm for Self-intersecting curves may be invalid!
« Last Edit: July 30, 2012, 11:19:52 PM by Faster »