[Nhờ giúp đỡ] Cách vẽ đường line/arc hồi quy tuyến tính từ các điểm có sẵn

[onion911 0]

Kính chào anh em và tiền bối trong diễn đàn! 

 

Hiện tại mình có yêu cầu như sau cần anh em giúp đỡ: Mình có sẵn "n" điểm cho trước (5,6,7 điểm gì đó) và mình cần vẽ 2 trường hợp sau:
1. Trường hợp 1: Vẽ đường thẳng trung bình đi qua các điểm này. Cái này kiểu như vẽ đường hồi quy tuyến tính (ko biết mình sử dụng từ có đúng ko). Anh em xem hình đính kèm ví dụ minh họa ạ.

 

2. Trường hợp 2: Vẽ cung tròn trung bình đi qua các điểm này. . Anh em xem hình đính kèm ví dụ minh họa ạ.

Mong anh em chỉ giúp có lisp hoặc phương án nào vẽ được các đường này ko, hoặc sử dụng phần mềm nào khác.

Em xin cám ơn trước ạ. 

 

 

[Doan Van Ha 3.191]

2 bài toán này hay à nghen!

[tannguyen291 135]

5 giờ trước, Doan Van Ha đã nói:

2 bài toán này hay à nghen!

Bác có hướng nào chưa thế.

Trường hợp 1 em đang nghĩ đến thuật toán brute-force để tìm vector đường thẳng tối ưu nhất cho tập điểm.

Giống Minimum Bounding Box của nàng lê thị mác.

Trường hợp 2 thì em chưa có hướng luôn ạ. :))

[tannguyen291 135]

Lúc nào mình nghĩ tiếp được trường hợp 2 mình lại đăng tiếp.

[cuongtk2 342]

Nếu yêu cầu đường thẳng nằm ngang thì quá dễ, chỉ việc lấy Y trung bình của n điểm. 

Còn nếu là tìm 1 đường thẳng (arc) sao cho tổng khoảng cách từ tập điểm đến đường đó là nhỏ nhất thì cũng đau đầu.

[cuongtk2 342]

Bài

3 giờ trước, tannguyen291 đã nói:

Lúc nào mình nghĩ tiếp được trường hợp 2 mình lại đăng tiếp.

trường hợp của chú là nối 2 điểm xa nhất rồi tịnh tiến sang H trung bình đến ClosedPoint. Sẽ rắc rối hơn nếu khoảng cách xa nhất có nhiều điểm thoả mãn. VD đường chéo hình chữ nhật, hay 2 cạnh tam giác cân. ở đây còn chưa xét đa giác đều.

[onion911 0]

5 giờ trước, tannguyen291 đã nói:

Lúc nào mình nghĩ tiếp được trường hợp 2 mình lại đăng tiếp.

Hay quá anh. Anh có thể chia sẻ nguyên lý anh đang làm được ko ạ.

[onion911 0]

5 giờ trước, cuongtk2 đã nói:

Nếu yêu cầu đường thẳng nằm ngang thì quá dễ, chỉ việc lấy Y trung bình của n điểm. 

Còn nếu là tìm 1 đường thẳng (arc) sao cho tổng khoảng cách từ tập điểm đến đường đó là nhỏ nhất thì cũng đau đầu.

Dạ đúng ý em là vậy đó anh ạ. Hix. Là tìm đường thằng vô hướng (ko phải chỉ mỗi trường hợp nằm ngang, em có sửa lại nội dung hình minh họa rồi ạ)

[tannguyen291 135]

12 giờ trước, cuongtk2 đã nói:

Bài

trường hợp của chú là nối 2 điểm xa nhất rồi tịnh tiến sang H trung bình đến ClosedPoint. Sẽ rắc rối hơn nếu khoảng cách xa nhất có nhiều điểm thoả mãn. VD đường chéo hình chữ nhật, hay 2 cạnh tam giác cân. ở đây còn chưa xét đa giác đều.

em k nối 2 điểm xa nhất. Em dùng thuật toán gần giống minimum bounding box của lê thị mác rồi vẽ đường thẳng theo hình chữ nhật tìm được.

Phương pháp này chỉ đưa ra đáp án gần đúng. K phải tốt nhất.

[tannguyen291 135]

@onion911 trường hợp 2: nếu cung tròn nhỏ hơn 180* và 2 điểm cung tròn chính là 2 điểm xa nhất thì có thể. nếu không phải như vậy thì thuật toán quá mức rắc rối rồi. 

[cuongtk2 342]

2 giờ trước, tannguyen291 đã nói:

em k nối 2 điểm xa nhất. Em dùng thuật toán gần giống minimum bounding box của lê thị mác rồi vẽ đường thẳng theo hình chữ nhật tìm được.

Phương pháp này chỉ đưa ra đáp án gần đúng. K phải tốt nhất.

Cơ sở nào để lựa chọn đường song song với cạnh dài hình chữ nhật vậy em . Em thử test với tam giác đều anh coi. 

Anh có cảm nhận đường này sẽ đi qua trọng tâm của tập điểm.

[tannguyen291 135]

23 phút trước, cuongtk2 đã nói:

Cơ sở nào để lựa chọn đường song song với cạnh dài hình chữ nhật vậy em . Em thử test với tam giác đều anh coi. 

 Anh có cảm nhận đường này sẽ đi qua trọng tâm của tập điểm.

https://lee-mac.com/minboundingbox.html

em dùng thuật toán min box của lee mac để xác định phương đường thằng.

Còn đường thẳng đi qua trọng tâm hay trung điểm là ý kiến chủ quan của mỗi người mà

[onion911 0]

57 phút trước, tannguyen291 đã nói:

@onion911 trường hợp 2: nếu cung tròn nhỏ hơn 180* và 2 điểm cung tròn chính là 2 điểm xa nhất thì có thể. nếu không phải như vậy thì thuật toán quá mức rắc rối rồi. 

Vâng, chỉ cần arc nhỏ hơn 180 độ thôi ạ. 2 điểm cung tròn là 2 điểm xa nhất tức là ý anh là điểm bắt đầu và kết thúc đúng ko ạ.

[cuongtk2 342]

Cái quan trọng nhất: nó đã đúng hay chưa, tại sao em chọn nó. 

[Doan Van Ha 3.191]

Trước đây tôi có đọc 1 thuật toán để "xấp xỉ" các đường thẳng và đường cong, nhưng giờ quên và tìm lại chưa ra. Nó có cơ sở rất thuyết phục chứ không theo kiểu "thích gì chọn nấy" được.
Thuật toán này trong Excel được đưa vào để vẽ đồ thị, từ đó suy ra phương trình, cho các bài toán dạng thống kê dựa vào tập hợp các số đo (xi, yi) thực nghiệm.

[tannguyen291 135]

19 phút trước, cuongtk2 đã nói:

Cái quan trọng nhất: nó đã đúng hay chưa, tại sao em chọn nó. 

thuật toán của em cũng không hoàn toàn chính xác mà. vốn dĩ thằng min box kia chỉ là tính gần đúng. 

Có thể tạo lựa chọn trọng tâm hay trung điểm nhập từ người dùng để thực hiện theo mục đích riêng của từng người mà anh.

[tannguyen291 135]

Trường hợp 2:

 Em cũng đang nghĩ đến việc lấy 2 điểm xa nhất làm startpoint và entpoint sau đó tương ứng với mỗi điểm còn lại là 1 arc. Trung bình cộng đống arc này tìm được ARC cuối.

Nhưng sau khi nghe lý thuyết của bác @Doan Van Ha chắc ý tưởng của em vào sọt rác rồi. :__

[cuongtk2 342]

Anh cũng đọc đâu đó trên augi hay github gì đó về phép nắn thẳng đường zigzag, hoặc là khử nhiễu  gì đó để nhận dạng hình ảnh. Giống như từ chức năng chuyển thành nét bút chì của photoshop. Hoặc nhận dạng line của bản scan.

[tannguyen291 135]

sau khi nghiên cứu một số công thức thì em cũng có đáp án chính xác trường hợp 1:

(defun c:test (/ ss lstpt lst)
  (setq 
    ss (acet-ss-to-list (ssget '((0 . "POINT"))))
    lstpt (mapcar '(lambda (x) (cdr (assoc 10 (entget x)))) ss)
    lst (LinearRegression lstpt)
  )
  (entmakex (list '(0 . "XLINE")
	  '(100 . "AcDbEntity")
	  '(67 . 0)
	  '(100 . "AcDbXline")
	  (cons 10 (car lst))
	  (cons 11 (cadr lst))
    )
  )
  (princ)
)

(defun LinearRegression (lst / lstx lsty mx my ssxy ssxx b1)
  (setq
    lstx (mapcar 'car lst)
    lsty (mapcar 'cadr lst)
    mx (/ (apply '+ lstx) (length lstx))
    my (/ (apply '+ lsty) (length lsty))
    ssxy (apply '+ (mapcar '(lambda (x y) (* (- x mx) (- y my))) lstx lsty))
    ssxx (apply '+ (mapcar '(lambda (x) (expt (- x mx) 2) ) lstx))
    b1 (atan (/ ssxy ssxx))
  )
  (list (list mx my 0) (list (cos b1) (sin b1) 0))
)

nguồn tham khảo

https://www.geeksforgeeks.org/linear-regression-python-implementation/

 

Ps: @cuongtk2 họ dùng trọng tâm đúng như anh nghĩ.

[onion911 0]

30 phút trước, tannguyen291 đã nói:

sau khi nghiên cứu một số công thức thì em cũng có đáp án chính xác trường hợp 1:

(defun c:test (/ ss lstpt lst)
  (setq 
    ss (acet-ss-to-list (ssget '((0 . "POINT"))))
    lstpt (mapcar '(lambda (x) (cdr (assoc 10 (entget x)))) ss)
    lst (LinearRegression lstpt)
  )
  (entmakex (list '(0 . "XLINE")
	  '(100 . "AcDbEntity")
	  '(67 . 0)
	  '(8 . "XLINE")
	  '(100 . "AcDbXline")
	  (cons 10 (car lst))
	  (cons 11 (cadr lst))
    )
  )
  (princ)
)

(defun LinearRegression (lst / lstx lsty mx my ssxy ssxx b1)
  (setq
    lstx (mapcar 'car lst)
    lsty (mapcar 'cadr lst)
    mx (/ (apply '+ lstx) (length lstx))
    my (/ (apply '+ lsty) (length lsty))
    ssxy (apply '+ (mapcar '(lambda (x y) (* (- x mx) (- y my))) lstx lsty))
    ssxx (apply '+ (mapcar '(lambda (x) (expt (- x mx) 2) ) lstx))
    b1 (atan (/ ssxy ssxx))
  )
  (list (list mx my 0) (list (cos b1) (sin b1) 0))
)

nguồn tham khảo

https://www.geeksforgeeks.org/linear-regression-python-implementation/

 

Ps: @cuongtk2 họ dùng trọng tâm đúng như anh nghĩ.

 

Cảm ơn anh đã tìm cách giúp đỡ em ạ. Em load test thử thì sao báo lỗi, ko tạo được line anh ạ

[tannguyen291 135]

cad của bạn cài thiếu express tool.

(defun c:test (/ ss lstpt lst i p)
  (setq ss (ssget '((0 . "POINT"))))
  (repeat (setq i (sslength ss))
    (setq 
      i (1- i)
      p (cdr (assoc 10 (entget (ssname ss i))))
      lstpt (cons p lstpt)
    )
  )
  (setq lst (LinearRegression lstpt))
  (entmakex (list '(0 . "XLINE")
	  '(100 . "AcDbEntity")
	  '(67 . 0)
	  '(100 . "AcDbXline")
	  (cons 10 (car lst))
	  (cons 11 (cadr lst))
    )
  )
  (princ)
)

(defun LinearRegression (lst / lstx lsty mx my ssxy ssxx b1)
  (setq
    lstx (mapcar 'car lst)
    lsty (mapcar 'cadr lst)
    mx (/ (apply '+ lstx) (length lstx))
    my (/ (apply '+ lsty) (length lsty))
    ssxy (apply '+ (mapcar '(lambda (x y) (* (- x mx) (- y my))) lstx lsty))
    ssxx (apply '+ (mapcar '(lambda (x) (expt (- x mx) 2) ) lstx))
    b1 (atan (/ ssxy ssxx))
  )
  (list (list mx my 0) (list (cos b1) (sin b1) 0))
)

Dùng cái này nhé.

[Doan Van Ha 3.191]

Nó cũng loạn xì ngầu. Dưới đây là 1 lisp khác của Stefan BMR. Kết quả hơi khác của @tannguyen291. Đưa lên để tham khảo thêm cho vui

;----- by Stefan BMR
(defun C:TEST ( / vxv ss i n l o d dx dy a)
 (defun vxv (a b) (apply '+ (mapcar '* a b)))
 (if (setq ss (ssget '((0 . "POINT"))))
  (progn
   (repeat (setq i (sslength ss) n i)
    (setq l (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i)))))) l)))
   (setq o (mapcar '/ (apply 'mapcar (cons '+ l)) (list n n))
               d (mapcar '(lambda (a) (mapcar '- o a)) l)
               dx (mapcar 'car d)
               dy (mapcar 'cadr d)
               a (* 0.5 (atan (* 2 (vxv dx dy)) (- (vxv dx dx) (vxv dy dy)))))
   (entmake (list '(0 . "XLINE") '(100 . "AcDbEntity") '(100 . "AcDbXline") '(62 . 1) (cons 10 o) (list 11 (cos a) (sin a) 0.0)))))
 (princ))

[onion911 0]

34 phút trước, tannguyen291 đã nói:

cad của bạn cài thiếu express tool.

(defun c:test (/ ss lstpt lst i p)
  (setq ss (ssget '((0 . "POINT"))))
  (repeat (setq i (sslength ss))
    (setq 
      i (1- i)
      p (cdr (assoc 10 (entget (ssname ss i))))
      lstpt (cons p lstpt)
    )
  )
  (setq lst (LinearRegression lstpt))
  (entmakex (list '(0 . "XLINE")
	  '(100 . "AcDbEntity")
	  '(67 . 0)
	  '(100 . "AcDbXline")
	  (cons 10 (car lst))
	  (cons 11 (cadr lst))
    )
  )
  (princ)
)

(defun LinearRegression (lst / lstx lsty mx my ssxy ssxx b1)
  (setq
    lstx (mapcar 'car lst)
    lsty (mapcar 'cadr lst)
    mx (/ (apply '+ lstx) (length lstx))
    my (/ (apply '+ lsty) (length lsty))
    ssxy (apply '+ (mapcar '(lambda (x y) (* (- x mx) (- y my))) lstx lsty))
    ssxx (apply '+ (mapcar '(lambda (x) (expt (- x mx) 2) ) lstx))
    b1 (atan (/ ssxy ssxx))
  )
  (list (list mx my 0) (list (cos b1) (sin b1) 0))
)

Dùng cái này nhé.

Dạ em cảm ơn. Em test được rồi ạ 

[tannguyen291 135]

Trường hợp 2 em có công thức nhưng mà khó quá nhờ các đại hiệp giải ạ.

Lót dép hóng

0301001.pdf

[tannguyen291 135]

1 giờ} trướ}c, Doan Van Ha đã nói:

Nó cũng loạn xì ngầu. Dưới đây là 1 lisp khác của Stefan BMR. Kết quả hơi khác của @tannguyen291. Đưa lên để tham khảo thêm cho vui

 

;----- by Stefan BMR
(defun C:TEST ( / vxv ss i n l o d dx dy a)
 (defun vxv (a b) (apply '+ (mapcar '* a b)))
 (if (setq ss (ssget '((0 . "POINT"))))
  (progn
   (repeat (setq i (sslength ss) n i)
    (setq l (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i)))))) l)))
   (setq o (mapcar '/ (apply 'mapcar (cons '+ l)) (list n n))
               d (mapcar '(lambda (a) (mapcar '- o a)) l)
               dx (mapcar 'car d)
               dy (mapcar 'cadr d)
               a (* 0.5 (atan (* 2 (vxv dx dy)) (- (vxv dx dx) (vxv dy dy)))))
   (entmake (list '(0 . "XLINE") '(100 . "AcDbEntity") '(100 . "AcDbXline") '(62 . 1) (cons 10 o) (list 11 (cos a) (sin a) 0.0)))))
 (princ))

 

Công thức của em (atan  (/ sumXY  sumXX))

Công thức của họ (* 0.5 (atan (* 2 sumXY) (- sumXX sumYY)))

không hiểu sự khác biệt này ở đâu. Có lẽ vốn công thức tuyến tính hồi quy là dạng tính toán gần đúng.