Chuyển đến nội dung
Diễn đàn CADViet
  • Thông báo

    • Nguyen Hoanh

      CADViet đã hoàn tất nâng cấp   14/09/2017

      Chào các bạn, CADViet đã hoàn tất việc nâng cấp lên phiên bản mới. Tất cả các chức năng đã hoạt động theo kỳ vọng của ban quản trị. Nếu có vấn đề gì cần phản hồi, các bản post ở đây nhé: Trân trọng, Nguyễn Hoành.
thanhduan2407

[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

Các bài được khuyến nghị

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.com/upfiles/5/36665_tim_3dface_chua_diem.dwg

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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)

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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!

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

(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
)

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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 ạ! 

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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!

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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 độ

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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!

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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 ^^

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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 .....(

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Ý 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).

  • Vote tăng 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Ý 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))))

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Ý 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.

  • Vote tăng 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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)))

)

  • Vote tăng 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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é.
  • Vote tăng 2

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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
	  )
    )
  )
)

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Tạo một tài khoản hoặc đăng nhập để nhận xét

Bạn cần phải là một thành viên để lại một bình luận

Tạo tài khoản

Đăng ký một tài khoản mới trong cộng đồng của chúng tôi. Điều đó dễ mà.

Đăng ký tài khoản mới

Đăng nhập

Bạn có sẵn sàng để tạo một tài khoản ? Đăng nhập tại đây.

Đăng nhập ngay


×