Tìm vị trí trống nhất trong đa giác

[tdvn 53]

Tôi là ngýời ðã viết khá nhiều lisp nhýng có một chủ ðề này tôi chýa lần nào viết thành công. Số là tôi có một hình ða giác bất kỳ (rất phức tạp),

Tôi muốn trình bày trong ða giác này một cụm nội dung gì ðó nhýng vì diện tích cụm này khá lõn nên tôi phải tìm trong ða giác vị trí tốt nhất (tất là vị trí trống nhất, tôi tạm gọi nhý vậy) hoặc giả ða giác này cũng lớn nhýng tôi vẫn muốn tìm vị trí trống nhất ðể ðặt cụm này một cách tự ðộng (nếu ðặt thủ công ai chẳng thấy). Bạn có thể týởng týợng cái lệnh offset của cad. nếu bạn cứ offset mãi cho ðến khi không offset ðýợc nữa, tâm của cái hình cuối cùng (ðýợc offset nhiều lần nhất) chính là vị trí tôi cần tìm. Tôi nghĩ ðây là một CT rất khó, nhýng biết ðâu ðấy có bạn lại nghĩ ra.

[ssg 1104]

Bạn có thể týởng týợng cái lệnh offset của cad. nếu bạn cứ offset mãi cho ðến khi không offset ðýợc nữa, tâm của cái hình cuối cùng (ðýợc offset nhiều lần nhất) chính là vị trí tôi cần tìm.

Dùng thuật giải của chính bạn gợi ý:

1. Chọn giá trị offset ban đầu nhỏ tuỳ ý. Ví dụ di = 1

2. Offset cái đa giác vào trong với giá trị di

3. Nếu kết quả offset thành công, lấy centroid pc của nó và... xoá béng cái kết quả đi. Tăng di lên tuỳ ý, làm lại bước 2, 3...

Khi nào không còn offset được nữa, kết quả là điểm pc nhận được của lần cuối cùng.

 

;;;-------------------------------------------------
(defun centroid(e / re ob p)
(vl-load-com)
(command "region" e "")
(setq
 re (entlast)
 ob (vlax-ename->vla-object re)
 p (vlax-safearray->list (vlax-variant-value (vla-get-Centroid ob)))
)
(command "undo" 1)
p
)
;;;-------------------------------------------------
(defun C:T1( / e1 e p di OK pc) ;;;Cho trong nhat trong da giac
(setq
 e1 (entlast)
 e (car (entsel "\nChon da giac:"))
 p (centroid e)
 di 1 OK nil
)
(while (not OK)
 (command "offset" di e p "")
 (if (equal (entlast) e1)
   (setq OK T)
   (progn
     (setq pc (centroid (entlast)))
     (command "erase" (entlast) "")
     (setq di (1+ di))
   )
 )
)
(command "point" pc)
)
;;;-------------------------------------------------

 

Enjoy!

[elleHCSC 98]

Ồ cách làm này hay đấy, đảm bảo điềm tìm được luôn nằm trong đa giác, nó tốt hơn điểm CentroID của đa giác gốc ban đầu. Tuy nhiên khi chạy nếu là 1 đa giác lớn thì nó offset hơi lâu (di=1). Có thế tính toán tự động lại để sao tìm được một di cho phù hợp ko nhỉ ssg ? điều đó sẽ khiến cho tốc độ chạy nhanh hơn khi gặp phải 1 đa giác lớn.

[nataca 555]

Ồ cách làm này hay đấy, đảm bảo điềm tìm được luôn nằm trong đa giác, nó tốt hơn điểm CentroID của đa giác gốc ban đầu. Tuy nhiên khi chạy nếu là 1 đa giác lớn thì nó offset hơi lâu (di=1). Có thế tính toán tự động lại để sao tìm được một di cho phù hợp ko nhỉ ssg ? điều đó sẽ khiến cho tốc độ chạy nhanh hơn khi gặp phải 1 đa giác lớn.

Lấy Di theo diện tích hoặc chi vi của đa giác

[tdvn 53]

Dùng thuật giải của chính bạn gợi ý:

1. Chọn giá trị offset ban đầu nhỏ tuỳ ý. Ví dụ di = 1

2. Offset cái đa giác vào trong với giá trị di

3. Nếu kết quả offset thành công, lấy centroid pc của nó và... xoá béng cái kết quả đi. Tăng di lên tuỳ ý, làm lại bước 2, 3...

Khi nào không còn offset được nữa, kết quả là điểm pc nhận được của lần cuối cùng.

 

;;;-------------------------------------------------
(defun centroid(e / re ob p)
(vl-load-com)
(command "region" e "")
(setq
 re (entlast)
 ob (vlax-ename->vla-object re)
 p (vlax-safearray->list (vlax-variant-value (vla-get-Centroid ob)))
)
(command "undo" 1)
p
)
;;;-------------------------------------------------
(defun C:T1( / e1 e p di OK pc) ;;;Cho trong nhat trong da giac
(setq
 e1 (entlast)
 e (car (entsel "\nChon da giac:"))
 p (centroid e)
 di 1 OK nil
)
(while (not OK)
 (command "offset" di e p "")
 (if (equal (entlast) e1)
   (setq OK T)
   (progn
     (setq pc (centroid (entlast)))
     (command "erase" (entlast) "")
     (setq di (1+ di))
   )
 )
)
(command "point" pc)
)
;;;-------------------------------------------------

 

Enjoy!

Cám ơn bạn cái giải thuật này. Nhưng có điều nếu đa giác phức tạp như tôi có nói, ví dụ như có cái eo ở giữa như hình bản đồ Việt Nam với khúc ruột miền Trung. Thì đoạn code (setq p (centroid e)) có khi p ở ngoài đa giác làm nó chạy mãi không dừng. Cũng vì có 1 hoặc vài cái eo đó mà đến lúc nào đó, đa giác được offset sẽ tạo thành nhiều cái đa giác nhỏ, lúc đó ta phải chọn cái đa giác nào để đi tiếp. Nếu so sánh diện tích hay chu vi để chọn thì chưa chắc đã tối ưu vì diện tích hoặc chu vi lớn chưa chắc đã trống nhất. Còn nếu cho tất cả các đa giác được sinh ra cùng lúc gặp cái eo mà chạy thì đến lúc nào đó nó sẽ sinh ra tiếp ...

Còn điều nữa, nếu dùng chính lệnh offset mà chạy trong trường hợp số lượng lớn hình cần chạy (ví dụ trong bản đồ địa chính) , sau một lúc nào đó số đối tượng cần xóa (các hình trung gian) sẽ rất lớn, như vậy cũng không tiện lắm. Tôi nghĩ có giải thuật nào chạy hoàn toàn trên tọa độ của đa giác ban đầu cho đến khi tìm được điểm trống nhất thì trả về tọa độ điểm đó.

Cái cách này mình cũng đã thử lập, nhưng có những trường hợp mình không kiểm soát được, nó chạy lung tung.

[Nguyen Hoanh 4670]

Lisp của bác ssg chạy tối ưu với đa giác lồi nói chung. Nhưng khi gặp đa giác lõm thì nhiều trường hợp chưa đúng. Nguồn gốc của sự bất cập này là về phương pháp offset và tìm điểm nằm trong đa giác bằng cách tìm điểm trọng tâm.

 

Xin được đề xuất giải thuật khác cho bài toán này. Thuật toán khá đơn giản: với mọi điểm P nằm trong đa giác, điểm nằm trong vùng rộng nhất sẽ có khoảng cách min từ nó tới biên đa giác là max.

 

Thuật toán dưới đây (lệnh là T2) rà qua tất cả các đỉnh nằm trong đa giác với bước nhảy delta. Tính tất cả khoảng cách min của P tới đa giác. Tìm ra điểm P nào có giá trị này lớn nhất.

 

Để rà qua tất cả các điểm nằm trong đa giác, chúng ta quét 1 tia xline từ ymin của đa giác tới ymax của đa giác. Tìm các điểm giao của xline này với đa giác. Nếu số điểm giao là chẵn (tức là xline cắt đa giác tại điểm điển hình) chúng ta rà lần lượt qua các khoảng cắt nằm trong đa giác. Tính giá trị khoảng cách min từ P đến biên đa giác bằng hàm vlax-curve-getClosestPointTo.

 

(vl-load-com)
(defun GiaoDT (ent1 ent2)
 (setq	ob1 (vlax-ename->vla-object ent1)
ob2 (vlax-ename->vla-object ent2)
 )
 (setq	g (vlax-variant-value
    (vla-IntersectWith ob1 ob2 acExtendNone)
  )
 )
 (if (/= (vlax-safearray-get-u-bound g 1) -1)
   (setq g (vlax-safearray->list g))
   (setq g nil)
 )
 (if g
   (progn
     (setq kq nil
    sd (fix (/ (length g) 3))
     )
     (repeat sd
(setq kq (append kq (list (list (car g) (cadr g) (caddr g))))
      g	 (cdddr g)
)
     )
     kq
   )
   nil
 )
)

(defun c:t2 (/ maxp)
 (setq	pent	  (car (entsel "\nHay vao pline: "))
deltadist (getdist "\nHay vao sai so do tia: ")
deltax	  deltadist
deltay	  deltadist
maxdist	  0.0
bbox	  (vla-getboundingbox (vlax-ename->vla-object pent) 'p1 'p2)
p1	  (vlax-safearray->list p1)
p2	  (vlax-safearray->list p2)
ymin	  (cadr p1)
ymax	  (cadr p2)
cury	  ymin
ttxl	  (list	(cons 0 "XLINE")
		(cons 100 "AcDbEntity")
		(cons 67 0)
		(cons 410 "Model")
		(cons 100 "AcDbXline")
		(list 10 (car p2) cury 0.0)
		(list 11 1.0 0.0 0.0)
	  )
 )
 (setq	xent (entmakex ttxl)
xtt  (entget xent)
 )
 (while (    (setq 
   cury    (+ cury deltay)
     xtt     (subst (list 10 (car p2) cury 0.0) (assoc 10 xtt) xtt))
   (entmod xtt)
   (setq
     lstgiao (giaodt xent pent)
     lstgiao (if lstgiao
	(vl-sort lstgiao
		 '(lambda (x1 x2) (		)
	lstgiao
      )      
   )
   (if	(and (> (length lstgiao) 1)
     (= (length lstgiao) (* 2.0 (/ (length lstgiao) 2)))
)
     (progn
(while (> (length lstgiao) 1)
  (setq	minx	(car (car lstgiao))
	maxx	(car (car (cdr lstgiao)))
	curx	minx
	lstgiao	(cddr lstgiao)
  )
  (while (	    (grdraw (list curx cury) (list curx cury) 1)
    (setq curdist (distance (vlax-curve-getClosestPointTo
			      pent
			      (list curx cury 0.0)
			    )
			    (list curx cury 0.0)
		  )
    )
    (if	(> curdist maxdist)
      (setq maxdist curdist
	    maxp    (list curx cury 0.0)
      )
    )
    (setq curx (+ curx deltax))
  )
)
     )
   )
 )
 (entdel xent)
 (if maxp
   (entmake
     (list (cons 0 "circle") (cons 10 maxp) (cons 40 maxdist))
   )
 )
)

 

Lisp trên sẽ chấm đỏ tại tất cả các điểm mà nó xét. Rồi vẽ một circle có tâm nằm tại điểm thỏa mãn, bán kính là khoảng cách max. Nói cách khác, chương trình sẽ vẽ một circle với bán kính lớn nhất nằm trong đa giác đã cho.

[tdvn 53]

Lisp của bác ssg chạy tối ưu với đa giác lồi nói chung. Nhưng khi gặp đa giác lõm thì nhiều trường hợp chưa đúng. Nguồn gốc của sự bất cập này là về phương pháp offset và tìm điểm nằm trong đa giác bằng cách tìm điểm trọng tâm.

 

Xin được đề xuất giải thuật khác cho bài toán này. Thuật toán khá đơn giản: với mọi điểm P nằm trong đa giác, điểm nằm trong vùng rộng nhất sẽ có khoảng cách min từ nó tới biên đa giác là max.

 

Thuật toán dưới đây (lệnh là T2) rà qua tất cả các đỉnh nằm trong đa giác với bước nhảy delta. Tính tất cả khoảng cách min của P tới đa giác. Tìm ra điểm P nào có giá trị này lớn nhất.

 

Để rà qua tất cả các điểm nằm trong đa giác, chúng ta quét 1 tia xline từ ymin của đa giác tới ymax của đa giác. Tìm các điểm giao của xline này với đa giác. Nếu số điểm giao là chẵn (tức là xline cắt đa giác tại điểm điển hình) chúng ta rà lần lượt qua các khoảng cắt nằm trong đa giác. Tính giá trị khoảng cách min từ P đến biên đa giác bằng hàm vlax-curve-getClosestPointTo.

...

Lisp trên sẽ chấm đỏ tại tất cả các điểm mà nó xét. Rồi vẽ một circle có tâm nằm tại điểm thỏa mãn, bán kính là khoảng cách max. Nói cách khác, chương trình sẽ vẽ một circle với bán kính lớn nhất nằm trong đa giác đã cho.

Mình chạy thử, nó báo thế này.

Command: t2

 

Hay vao pline:

Hay vao sai so do tia: 3

; error: no function definition: VLAX-ENAME->VLA-OBJECT

 

Không biết hàm "VLAX-ENAME->VLA-OBJECT" của cad hay của bạn mà nó chưa tìm được

Mình chưa hiểu thuật toán của bạn lắm, có thể khi chạy được, mình sẽ hiểu.

[Nguyen Hoanh 4670]

Mình chạy thử, nó báo thế này.

Command: t2

 

Hay vao pline:

Hay vao sai so do tia: 3

; error: no function definition: VLAX-ENAME->VLA-OBJECT

 

Không biết hàm "VLAX-ENAME->VLA-OBJECT" của cad hay của bạn mà nó chưa tìm được

Mình chưa hiểu thuật toán của bạn lắm, có thể khi chạy được, mình sẽ hiểu.

sorry, bạn hãy thêm dòng lệnh (vl-load-com) vào code!

[tdvn 53]

sorry, bạn hãy thêm dòng lệnh (vl-load-com) vào code!

Cám ơn bạn rất nhiều. Giải thuật của bạn rất độc. Tôi đã từng nghĩ tới vài cách tương tự nhưng không thể đơn giản như vậy. Nó chạy rất tốt. Mình sẽ cố gắng đọc hiểu giải thuật của bạn để "gia công" thêm cho phù hợp với công việc của mình. Có thể mình sẽ chuyển nó qua ARX. Không biết có đc không.

Một lần nữa cám ơn bác "Nguyen Hoanh" và bác "ssg"