Đến nội dung


Hình ảnh
- - - - -

[Hỏi] Thuật Toán Tìm Mặt 3Dface Chứa Tọa Độ Một Điểm Trong Tập Hợp Các 3Dface


  • Please log in to reply
18 replies to this topic

#1 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 07 November 2015 - 02:01 PM

Em chào các bác!

Em đang viết nâng cấp chương trình nội suy độ cao điểm (biết XY, tìm Z) nằm trong bề mặt 3Dface. Tuy nhiên, phương thức thuật toán của em chậm quá, nếu có quá nhiều 3Dface thì máy đơ. Nó phải xét duyệt từng 3Dface để kiểm tra xem điểm đó có nằm trong hay không thì mới nội suy tọa độ Z. Em có file đính kèm minh họa, các Text màu xanh là Text đã được nội suy dựa vào bề mặt 3Dface đó. Mong được các bác chỉ giáo đưa ra phương án tìm 3Dface chứa điểm tọa độ (đã biết) một cách tối ưu được không ạ?

Chân thành cảm ơn các bác!

 

http://www.cadviet.c...e_chua_diem.dwg


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#2 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 07 November 2015 - 03:21 PM

Bạn lập làm ccw(p1 p2 p3) trả về 1 nếu "đi từ điểm p1 đến p2 và nhìn p3 phía bên trái, trả về -1 nếu bên phải, trả về 0 nếu đi qua. Hàm này là hàn kinh điển, tốc độ rất cao, bạn có thể search trên mạng.

Một điểm nằm trong tam giác khi thỏa mãn 3 điều kiện đồng thời
Ccw(a b p) = ccw (a b c)
Ccw(b c p) = ccw (b c a)
Ccw(c a p) = ccw (c a B)
  • 0

#3 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 07 November 2015 - 03:31 PM

Bạn lập làm ccw(p1 p2 p3) trả về 1 nếu "đi từ điểm p1 đến p2 và nhìn p3 phía bên trái, trả về -1 nếu bên phải, trả về 0 nếu đi qua. Hàm này là hàn kinh điển, tốc độ rất cao, bạn có thể search trên mạng.

Một điểm nằm trong tam giác khi thỏa mãn 3 điều kiện đồng thời
Ccw(a b p) = ccw (a b c)
Ccw(b c p) = ccw (b c a)
Ccw(c a p) = ccw (c a B)

Dạ, anh Hoành chưa hiểu ý em rồi. Hàm đó em có rồi anh ạ!

Nếu duyệt qua từng tam giác thì rất lâu để kiểm tra.

Em đang tìm thuật toán tìm tam giác ấy nhanh anh ạ!

Cảm ơn anh đã trả lời!


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#4 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 07 November 2015 - 03:35 PM

(defun CCW (P1 P2 P /)
  (setq	dX  (- (car P) (car P1))
	dY  (- (cadr P) (cadr P1))
	dX0 (- (car P2) (car P1))
	dY0 (- (cadr P2) (cadr P1))
	d   (- (* dX dY0) (* dY dX0))
  )
  (if (> d 0)
    (setq CCW1 1)
    (setq CCW1 -1)
  )
  CCW1
)

(defun PointInTamgiac (P Ds_3D /)
  (setq KQ nil)
  (setq	P1 (nth 0 Ds_3D)
	P2 (nth 1 Ds_3D)
	P3 (nth 2 Ds_3D)
  )
  (setq C (CCW P2 P3 P))
  (if (and (= (CCW P1 P2 P) C) (= (CCW P3 P1 P) C))
    (setq KQ T)
  )
  KQ
)


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#5 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 07 November 2015 - 06:29 PM

Nếu thế thì bạn thử đông tây y kết hợp như sau:
1. Dùng lệnh zoom object rồi chọn tất cả các 3dface để nhìn toàn bộ các đối tượng 3dface, để select với tham số fence có hiệu lực với toàn bộ các 3dface.
2. Dùng hàm ssget với tham số fence, chọn 2 điểm có x bằng x0 của điểm p. Một trong 2 có y vô cùng lớn, điểm còn lại có y vô cùng bé. Mục đích là chọn các 3dface cắt qua đường thẳng đứng có hoành độ x0 của p.
3. Tương tự với trục y để tìm ra các 3dface giao với đường nằm ngang có tung độ y0 của p.
4. Giao của hai tập chọn ở bước 2 và 3 là các 3dface tiềm năng,hoặc đây chính là 3dface cần tìm luôn.
  • 0

#6 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 07 November 2015 - 06:37 PM

Nếu thế thì bạn thử đông tây y kết hợp như sau:
1. Dùng lệnh zoom object rồi chọn tất cả các 3dface để nhìn toàn bộ các đối tượng 3dface, để select với tham số fence có hiệu lực với toàn bộ các 3dface.
2. Dùng hàm ssget với tham số fence, chọn 2 điểm có x bằng x0 của điểm p. Một trong 2 có y vô cùng lớn, điểm còn lại có y vô cùng bé. Mục đích là chọn các 3dface có giao với đường thẳng đứng có hoành độ x0
3. Tương tự với trục y để tìm ra các 3dface giao với đường nằm ngang có tung độ y0 của p.
4. Giao của hai tập chọn là các 3dface tiềm năng,hoặc đây chính là 3dface cần tìm luôn.

Anh có thể cho em 1 vài ví dụ được không ạ? Em thích ý tưởng của anh rồi ạ! 


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#7 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 07 November 2015 - 06:40 PM

Em đang rất theo dõi bài viết của mình.

Anh có thể cho em 1 ví dụ với 1 điểm Pick vào các 3Dface thì 3Dface đó đổi màu chẳng hạn.

Cái chính em quan tâm là thuật toán. Em áp dụng rất nhiều đấy ạ!

Em cảm ơn anh Hoành!


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#8 tien2005

tien2005

    biết lệnh properties

  • Members
  • PipPipPipPip
  • 257 Bài viết
Điểm đánh giá: 94 (tàm tạm)

Đã gửi 08 November 2015 - 01:29 PM

3D-face  bạn có được từ đâu? Delaunay chăng. Nếu vậy thì đừng chú trọng vào 3dFace mà chú ý vào list tạo ra 3dFace, ở đó ta lấy được 3 đỉnh của tam giác rồi kiểm tra in/out -> nội suy cao độ


  • 0

#9 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 08 November 2015 - 01:56 PM

3D-face  bạn có được từ đâu? Delaunay chăng. Nếu vậy thì đừng chú trọng vào 3dFace mà chú ý vào list tạo ra 3dFace, ở đó ta lấy được 3 đỉnh của tam giác rồi kiểm tra in/out -> nội suy cao độ

Cảm ơn bác Tien2005 đã trả lời!

Đúng là tam giác Delaunay ạ!

Mô hình TIN được tạo một cách độc lập và nếu bản vẽ được tạo rất nhiều mô hình TIN thì việc tìm điểm trong mô hình TIN nào là rất mất thời gian. Do đó em chọn phương thức quét chọn mô hình TIN trực tiếp trên bản vẽ (các tam giác Delaunay) để lọc lấy tam giác chứa điểm tọa độ đã biết (Pick hoặc tọa độ nhập vào). Việc lọc này rất lâu.

Em đang nghiên cứu cách anh Hoành đưa ra vào áp dụng.

Mong bác có sáng kiến giúp em cải tiến tốc độ với ạ!

Cảm ơn bác nhiều!


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#10 tien2005

tien2005

    biết lệnh properties

  • Members
  • PipPipPipPip
  • 257 Bài viết
Điểm đánh giá: 94 (tàm tạm)

Đã gửi 08 November 2015 - 03:39 PM

nếu 3Dface có sẵn thì bạn chọn tất cả rồi  rồi tạo thành list LST cuac cac dxf 11 12 13 ( '(11 12 13) '(11 12 13) '(11 12 13) ...)

nếu 3Dface do lisp của bạn tao nên thì đã có sẵn LST

Để lọc lấy tam giác chứa điểm tọa độ P đã biết (Pick hoặc tọa độ nhập vào) thì sort LST theo khoảng cách P và 11 (or 12, 13) rồi duyệt qua LST để biết tam giác nào chứa P. Việc sort này không mất nhiều hơn thời gian giữa 2 lần click chuột của bạn đâu ^^


  • 0

#11 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 08 November 2015 - 06:33 PM

nếu 3Dface có sẵn thì bạn chọn tất cả rồi  rồi tạo thành list LST cuac cac dxf 11 12 13 ( '(11 12 13) '(11 12 13) '(11 12 13) ...)

nếu 3Dface do lisp của bạn tao nên thì đã có sẵn LST

Để lọc lấy tam giác chứa điểm tọa độ P đã biết (Pick hoặc tọa độ nhập vào) thì sort LST theo khoảng cách P và 11 (or 12, 13) rồi duyệt qua LST để biết tam giác nào chứa P. Việc sort này không mất nhiều hơn thời gian giữa 2 lần click chuột của bạn đâu ^^

Chắc bác Tien2005 chưa hiểu ý em.

Em đã làm theo cách anh Hoành đưa ra và kết quả tương đối ổn ạ! Em chỉ muốn xét duyệt 3DFace ít nhất.

Em chọn cách ssget "C" P1 P2 .....(


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#12 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 08 November 2015 - 06:58 PM

Ý tưởng của anh Hoành khá hay. Em thử kiểu chọn fence như này liệu có nhanh hơn?

- Sort tất cả cạnh của tất cả 3dface để tìm cạnh max (cái này tốn thêm time).

- Chọn fence theo 2 phương vuông góc trong khoảng max đó (cái này làm giảm số lượng face).


  • 1

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#13 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 08 November 2015 - 07:16 PM

Ý tưởng của anh Hoành khá hay. Em thử kiểu chọn fence như này liệu có nhanh hơn?

- Sort tất cả cạnh của tất cả 3dface để tìm cạnh max (cái này tốn thêm time).

- Chọn fence theo 2 phương vuông góc trong khoảng max đó (cái này làm giảm số lượng face).

Em cảm ơn bác!

Cũng là 1 cách giảm đáng kể số lượng 3DFace.

Em lấy 2 điểm có cùng X với điểm Pick. Một điểm Ymin và một điểm Ymax dựa vào Max Min vùng chọn 3DFace.

Có hàm ZoomObj của Lee-Mac.

;; Zoom Object
;; by Lee McDonnell  08.05.2009

;; ARGS:
;; ss  ~  Selection Set

(defun ZmObj  (ss / Minp Maxp lst)
  (vl-load-com)
  (foreach Obj (mapcar 'vlax-ename->vla-object
                 (vl-remove-if 'listp
                   (mapcar 'cadr
                     (ssnamex ss))))
    (vla-getBoundingBox Obj 'Minp 'Maxp)
    (setq lst (cons
                (mapcar 'vlax-safearray->list
                  (list Minp Maxp)) lst)))
  (vla-ZoomWindow
    (vlax-get-acad-object)
      (vlax-3D-point
        (list
          (apply 'min
            (mapcar 'car
              (mapcar 'car lst)))
          (apply 'min
            (mapcar 'cadr
              (mapcar 'car lst))) 0.0))
        (vlax-3D-point
          (list
            (apply 'max
              (mapcar 'car
                (mapcar 'cadr lst)))
            (apply 'max
              (mapcar 'cadr
                (mapcar 'cadr lst))) 0.0))))

  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#14 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 08 November 2015 - 07:25 PM

Ý mình đúng là dùng ssget tham số Fence,
nhưng để tìm p1 p2, không rà qua tất cả các 3dFace mà dùng hàm tìm tọa độ của màn hình hiện tại như sau


(defun VPCords ( )
( (lambda (offset)
( (lambda (viewctr)
(list
(mapcar '- viewctr offset)
(mapcar '+ viewctr offset)
)
)
(getvar "viewctr")
)
)
( (lambda (halfHeight aspectRatio)
(list
(* halfHeight aspectRatio)
halfHeight
)
)
(* 0.5 (getvar "viewsize"))
(apply '/ (getvar "screensize"))
)
)
)

Hàm này trả về một list có 2 phần tử, là 2 tọa độ của góc dưới-trái và góc trên-phải của màn hình hiện tại.
Để sử dụng hàm này, trước hết ta phải dùng lệnh zoom > ob, để chọn tất cả các 3dface có trong bản vẽ, thì hàm này sẽ trả về giá trị của bounding box của các 3dface.
  • 1

#15 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 08 November 2015 - 07:29 PM

Bạn có thể sử dụng lệnh test này để biết hiệu ứng của hàm vpcords:

(defun c:test()
(command ".zoom" "ob" (ssget "X" '((0 . "3DFACE"))) "")
(command ".rectangle" (nth 0 (vpcords)) (nth 1 (vpcords)))
)

  • 1

#16 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 08 November 2015 - 09:17 PM

Sau đây là phần hàm các 3DFace tiềm năng. Hàm này có ưu điểm:
- Mình đã test thì thấy chạy khá nhanh.
- Không phải sử dụng đến các hàm command nên sẽ tương thích hơn với các lisp cũng như không liên quan đến góc nhìn (nếu ở 3D thì hàm ssget tham số fence sẽ cho ra kết quả không đúng)

Cú pháp dùng hàm
(find_potential ss point)
Trong đó:
ss: selection set chứa các 3dface.
point: đối tượng dạng list chứa tọa độ điểm cần xét
Kết quả:
Trả về selection set chứa các 3dface tiềm năng (chỉ 1 hoặc 2 3dface).

 

Gọi lệnh test để thử hàm này.


(defun not_potential_x(p1 p2 p3 p4 p / d1 d2 d3)
(setq d1 (- (car p1) (car p))
d2 (- (car p2) (car p))
d3 (- (car p3) (car p))
d4 (- (car p4) (car p))
)
(or (and (< 0.0 d1) (< 0.0 d2) (< 0.0 d3) (< 0.0 d4))
(and (> 0.0 d1) (> 0.0 d2) (> 0.0 d3) (> 0.0 d4)))
)

(defun not_potential_y(p1 p2 p3 p4 p / d1 d2 d3)
(setq d1 (- (cadr p1) (cadr p))
d2 (- (cadr p2) (cadr p))
d3 (- (cadr p3) (cadr p))
d4 (- (cadr p4) (cadr p))
)
(or (and (< 0.0 d1) (< 0.0 d2) (< 0.0 d3) (< 0.0 d4))
(and (> 0.0 d1) (> 0.0 d2) (> 0.0 d3) (> 0.0 d4)))
)

(defun not_potential(p1 p2 p3 p4 p)
(or (not_potential_x p1 p2 p3 p4 p)
(not_potential_y p1 p2 p3 p4 p))
)

(defun 3dfacetopoints (x)
(if (not (listp x))
(cons x (mapcar 'cdr (vl-remove-if '(lambda(a) (not (member (car a) '(10 11 12 13)))) (entget x))))
nil
)
)

(defun find_potential(ss diemgoc)
(setq lst (ssnamex ss)
lst (mapcar 'cadr lst)
lst (mapcar '3dfacetopoints lst)
lst (vl-remove-if 'null lst)
lst (vl-remove-if '(lambda(a) (not_potential (nth 1 a) (nth 2 a) (nth 3 a) (nth 4 a) diemgoc)) lst)
lst (mapcar 'car lst)
sskq (ssadd)
)
lst
(foreach ent lst
(setq sskq (ssadd ent sskq))
)
sskq
)

(defun c:test( / sskq)
(setq sskq (find_potential (ssget "x" '((0 . "3DFACE"))) (getpoint "\nDiem p: ")))
(sssetfirst sskq sskq)
(princ)
)

Mình định lồng luôn hàm tìm chính xác là 3dface nào, nhưng phát hiện ra hàm PointInTamgiac của bạn thanhduan bị sai, chạy không đúng trong mọi trường hợp.
Vì thế bạn thanhduan sẽ tự sửa hàm PointInTamgiac và lồng vào nhé.


  • 2

#17 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 08 November 2015 - 09:56 PM

Có 1 điều TD cần nhớ thêm là: khi chọn bằng fence thì các linetype của 3dface phải là continuous nhé.


  • 2

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#18 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 09 November 2015 - 01:00 AM

Có 1 điều TD cần nhớ thêm là: khi chọn bằng fence thì các linetype của 3dface phải là continuous nhé.

Em cảm ơn bác Hà nhắc nhở! Hii


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn







#19 thanhduan2407

thanhduan2407

    biết lệnh adcenter

  • Advance Member
  • PipPipPipPipPipPipPip
  • 995 Bài viết
Điểm đánh giá: 223 (khá)

Đã gửi 09 November 2015 - 01:04 AM

Mình định lồng luôn hàm tìm chính xác là 3dface nào, nhưng phát hiện ra hàm PointInTamgiac của bạn thanhduan bị sai, chạy không đúng trong mọi trường hợp.

Vì thế bạn thanhduan sẽ tự sửa hàm PointInTamgiac và lồng vào nhé.

Chương trình em viết cái này ko sai anh ạ! Em cảm ơn anh rất nhiều vì sự nhiệt tình chỉ bảo.

;;;;;;;;;(PointInTamgiac (getpoint) (3Diem3DF_3Point (car (entsel))))
(defun PointInTamgiac (P Ds_3D /)
  (setq KQ nil)
  (setq	P1 (nth 0 Ds_3D)
	P2 (nth 1 Ds_3D)
	P3 (nth 2 Ds_3D)
  )
  (setq C (CCW P2 P3 P))
  (if (and (= (CCW P1 P2 P) C) (= (CCW P3 P1 P) C))
    (setq KQ T)
  )
  KQ
)


(defun CCW (P1 P2 P /)
  (setq	dX  (- (car P) (car P1))
	dY  (- (cadr P) (cadr P1))
	dX0 (- (car P2) (car P1))
	dY0 (- (cadr P2) (cadr P1))
	d   (- (* dX dY0) (* dY dX0))
  )
  (if (> d 0)
    (setq CCW1 1)
    (setq CCW1 -1)
  )
  CCW1
)


;;;;;;;;;;;;(setq klkkl (3Diem3DF_3Point (car (entsel ))))

(defun 3Diem3DF_3Point (Ename_3DF / P10 P11 P12 P13)
;;;;;;;;;;;
  (vl-load-com)
  (setq Danhsachdiem (list))
  (setq Obj3DFace_ (entget Ename_3DF))
  (setq P10 (cdr (assoc 10 Obj3DFace_)))
  (setq P11 (cdr (assoc 11 Obj3DFace_)))
  (setq P12 (cdr (assoc 12 Obj3DFace_)))
  (setq P13 (cdr (assoc 13 Obj3DFace_)))
  (setq	Danhsachdiem
	 (TD:FILTERPOINTDUPLICATE
	   (list P10 P11 P12 P13)
	   0.00000001
	 )
  )
  Danhsachdiem
)


(defun TD:FILTERPOINTDUPLICATE (l fz)
  (if l
    (cons (car l)
	  (TD:FILTERPOINTDUPLICATE
	    (vl-remove-if '(lambda (x) (equal x (car l) fz)) (cdr l))
	    fz
	  )
    )
  )
)


  • 0



Tôi là con kiến bò trên sa mạc kiến thức bao la. Biển học thật rộng lớn