Đến nội dung

Hình ảnh

Điểm thuộc đa giác và điểm thuộc đa diện

- - - - -

  • Please log in to reply
Chủ đề này có 11 trả lời

#1
nguyen_hung

nguyen_hung

    Đại lãn

  • Thành viên
  • 299 Bài viết
Bài này xét trên hệ tọa độ Decarte vuông góc.
*Trong mặt phằng
- Cho tọa độ các đỉnh của một đa giác lồi, cho tọa độ 1 điểm. Tìm giả thuật xác định định điểm đã cho có thuộc miền trong đa giác không ?
- Cho phương trình một đường cong khép kín và tọa độ một điểm, tìm giải thuật xác định điểm đó có thuộc miền trong của đường cong không ?
*Tương tự trong không gian
- Cho tọa độ các đỉnh của 1 đa diện lồi, cho tọa độ 1 điểm. Tìm giải thuật xác định điểm đó có thuộc miền trong của đa diện không ?
- Cho phương trình mặt giới nội (không biết dùng từ có chính xác không ) và tọa độ một điểm, tìm giải thuật xác định điểm đó cỏ nằm trong mặt không ?

Hướng giả quyết của em là chia nhỏ đa giác thành các tam giác, rồi xét dần từng tam giác, nhưng chưa có giải thuật cho tam giác. Tương tụ cho đa diện, chia nhỏ đa diện thành tứ diện. Đối với phương trình đường cong khép kín, thì có phương trình sắn nên không phải chia, mà chia cũng không biết lấy gì làm chuẩn để chia. Có Phương trình thì có thể xác định được có thuộc đường hay mặt không, nhưng chưa xác định được có thuộc miền trong không ?

#2
logichoc2000

logichoc2000

    vì một tương lai tươi sáng

  • Thành viên
  • 192 Bài viết
nguyen_hung viết

Trong mặt phằng
- Cho tọa độ các đỉnh của một đa giác lồi, cho tọa độ 1 điểm. Tìm giả thuật xác định định điểm đã cho có thuộc miền trong đa giác không ?
- Cho phương trình một đường cong khép kín và tọa độ một điểm, tìm giải thuật xác định điểm đó có thuộc miền trong của đường cong không ?


Tui nghĩ như sau : Lấy 1 điểm mà ta biết nó nằm trong hoặc ngoài . Qua điểm này và điểm cần biết vẽ 1 dt. (Giả sử điểm nằm ngoài ) .Nếu dt cắt đa giác thì điểm cần xd nằm trong , ngược lại thì nằm ngoài . Với đường cong khép kín ta làm tương tự .
Mãi mãi một tình yêu

#3
nguyen_hung

nguyen_hung

    Đại lãn

  • Thành viên
  • 299 Bài viết
Vậy cách này cần xác định đoạn thẳng có căt các cạnh của đa giác không. Nhưng khi cho tọa độ bất kì thì làm sao tìm ra nhanh chóng một điểm nằm trong đa giác được ?

#4
vuhung

vuhung

    Spectrum IT

  • Thành viên
  • 266 Bài viết

Vậy cách này cần xác định đoạn thẳng có căt các cạnh của đa giác không. Nhưng khi cho tọa độ bất kì thì làm sao tìm ra nhanh chóng một điểm nằm trong đa giác được ?

Mình nghĩ chọn điểm thỏa mãn và tương tự cho các trục khác là ok, giả sử đa giác đó lồi.

Cách khác là chọn 1 điểm với tọa độ lớn hơn tất cả các tọa đổ của các điểm thì chắc chắc điểm này sẽ nằm ngoài. Với điểm nằm ngoài thì thuật toán cũng tương tự.

hfa
Hình đã gửi

#5
nguyen_hung

nguyen_hung

    Đại lãn

  • Thành viên
  • 299 Bài viết
Vậy cách của anh Vuhung giải được đa giác và đa diện rồi, khỏi chia đa giác với đa diện thành tam giác và tứ diện.
Em giới hạn lại một ít về đường cong. Ta quy ước "đường cong lồi là đương cong mà khi ta vẽ tiếp tuyến tại bất kì điểm nào thuộc đường cong, thì toàn bộ đường cong nằm thuộc 1 nửa mặt phẳng có bờ là tiếp tuyến đó"
Với giới hạn này thì em có cách sau : Chọn 2 điểm tùy ý trên đường cong, sau đó xác định trung điểm của đọan thẳng nối hai điểm đó. Trung điểm đó sẽ thuộc miền trong của đường cong.

#6
vuhung

vuhung

    Spectrum IT

  • Thành viên
  • 266 Bài viết

Với giới hạn này thì em có cách sau : Chọn 2 điểm tùy ý trên đường cong, sau đó xác định trung điểm của đọan thẳng nối hai điểm đó. Trung điểm đó sẽ thuộc miền trong của đường cong.

Bạn nhớ là cách đó đúng và chỉ đúng với đa diện lồi thôi nhé!

Thực tế mình thấy đường cong có thể đưa về đường gấp khúc bằng cách xấp xỉ các cung nhỏ thành một đoạn thẳng.
Hình đã gửi

#7
hoang

hoang

    Thượng sĩ

  • Thành viên
  • 233 Bài viết
De xac dinh mot diem co nam trong da giac hay khong ban co the tinh tong cac goc dinh huong ma diem nay nhin cac canh cua da giac bang cong cu tich vo huong chia do dai.Neu tong nay vuot qua 360 degree thi no se nam ngoai, nguoc lai nam trong.
Voi da dien thi co le la co cong thuc tinh goc khoi qua the tich cua hinh non,tat nhien la truong hop da dien phuc tap hon rat nhieu.
hoanglovely

#8
vuhung

vuhung

    Spectrum IT

  • Thành viên
  • 266 Bài viết

De xac dinh mot diem co nam trong da giac hay khong ban co the tinh tong cac goc dinh huong ma diem nay nhin cac canh cua da giac bang cong cu tich vo huong chia do dai.Neu tong nay vuot qua 360 degree thi no se nam ngoai, nguoc lai nam trong.
Voi da dien thi co le la co cong thuc tinh goc khoi qua the tich cua hinh non,tat nhien la truong hop da dien phuc tap hon rat nhieu.

hi hoang,

1. Nếu một điểm nằm trên một cạnh của đa giác( nghĩa là không phải nằm trong), tổng các góc cũng bằng 360 độ
2. Nếu điểm nằm ngoài thì tổng các góc có hướng bằng 0 đúng không nhỉ?
Hình đã gửi

#9
hoang

hoang

    Thượng sĩ

  • Thành viên
  • 233 Bài viết
Cong nhan la tieu chuan dua ra cua minh la chua chinh xac, cung tai minh chi dua vao truc giac chu khong co cm chat che.Nhung ma doi viec xac dinh thi co le cung khong can phai qua chinh xac nhu toan hoc phan biet trong voi tren canh .Hinh nhu co tieu chuan de xac dinh dua vao tich vo huong gi day ma so luong phep tinh can lam ti le voi so dinh cua da giac thoi ma
public static boolean isInside(Point point,Polygon polygon){}
public static void main(String[] args){
Polygon polygon=new Polygon(Point[]);
Point point;
System.out.println(isInside(point,polygon));
}
hoanglovely

#10
necromancer

necromancer

    Lính mới

  • Thành viên
  • 8 Bài viết
"*Trong mặt phằng
- Cho tọa độ các đỉnh của một đa giác lồi, cho tọa độ 1 điểm. Tìm giả thuật xác định định điểm đã cho có thuộc miền trong đa giác không ?"

Nối lần lượt điểm đã cho với các đỉnh của đa giác. Điểm đã cho nằm trong đa giác lồi khi tổng diện tích của các tam giác bằng diện tích đa giác lồi.

Lưu ý: Diện tích của đa giác lồi (x1, y1),...(xn,yn) với điểm 1,2,...n theo chiều kim đồng hồ (hoặc ngược chiều kim đồng hồ) được tính như sau:

S = Tổng ( (x(i+1 mod n)-x(i)) * (y(i+1 mod n) + y(i)) / 2 ) với i = 1..n

Với công thức trên, ta có thể dễ dàng tính diện tích của tam giác và đa giác lồi.

Cách tính này có lợi điểm là bị sai số do thao tác trên số thực.


Còn mấy câu còn lại thì chưa biết giải thế nào cho hay :wub:
Thân.

#11
necromancer

necromancer

    Lính mới

  • Thành viên
  • 8 Bài viết
Sorry,
Cách tính này có lợi điểm là KHÔNG bị sai số do thao tác trên số thực. :-(

#12
exe

exe

    Lính mới

  • Thành viên
  • 1 Bài viết

Bài này xét trên hệ tọa độ Decarte vuông góc.
*Trong mặt phằng
- Cho tọa độ các đỉnh của một đa giác lồi, cho tọa độ 1 điểm. Tìm giả thuật xác định định điểm đã cho có thuộc miền trong đa giác không ?
- Cho phương trình một đường cong khép kín và tọa độ một điểm, tìm giải thuật xác định điểm đó có thuộc miền trong của đường cong không ?
*Tương tự trong không gian
- Cho tọa độ các đỉnh của 1 đa diện lồi, cho tọa độ 1 điểm. Tìm giải thuật xác định điểm đó có thuộc miền trong của đa diện không ?
- Cho phương trình mặt giới nội (không biết dùng từ có chính xác không ) và tọa độ một điểm, tìm giải thuật xác định điểm đó cỏ nằm trong mặt không ?

Hướng giả quyết của em là chia nhỏ đa giác thành các tam giác, rồi xét dần từng tam giác, nhưng chưa có giải thuật cho tam giác. Tương tụ cho đa diện, chia nhỏ đa diện thành tứ diện. Đối với phương trình đường cong khép kín, thì có phương trình sắn nên không phải chia, mà chia cũng không biết lấy gì làm chuẩn để chia. Có Phương trình thì có thể xác định được có thuộc đường hay mặt không, nhưng chưa xác định được có thuộc miền trong không ?

Mấy bài này nói chung khá đơn giản. Có cuốn sách cơ bản rất tốt cho các loại thuật toán hình học là cuốn Computational Geometry của 4 tác giả người Hà Lan là Marc de Berg, Marc de .., Schwartzkopf. Các bạn có thể tham khảo được.
Mấy bài này có thể qui về dạng tóan gọi là Linear Programming- tức là gỉai xem điểm X đã có thỏa mãn các bất phương trình của mọi nửa mặt phẳng (trường hợp không gian 2 chiều) giao nhau tạo nên đa diện lồi đó hay không.
Bởi vì một đa diện lồi có thể biển diễn như sau:
Xét trong không gian d chiều, số các đỉnh của |P| = n
P = conv(P) = { :wacko: a_{i}x_{i} :beer R^{d} | :beat a_{i} = 1 , a_{i} :beer 0 :beer i }

hoặc P = { x :beer R^{d} : Ax :wub: z, A :beer R^{md}, z :beer R^{m} }

Cách biểu diễn trên gọi là V-Description của một đa diện d chiều (d- Polytop). Cách biểu diễn dưới gọi là H-description. Người ta còn gọi tắt chúng là V-Polytop và H-Polytop.
Các bạn để ý thì cách trên mô tả rằng: nếu một điểm nằm trong một đa diện, thì nó thỏa mãn tổ hợp lồi (khác với tổ hợp tuyến tính) của các đỉnh đa diện. Ví dụ: điểm x = (1/2, 1/2) thỏa mãn tổ hợp lồi của hai điểm x1 =(0,0), x2= (1,1) như sau: 1/2.x1 + 1/2.x2 = x (chu' y': tổng của 1/2 + 1/2 = 1- đây là tính chất quan trọng của tổ hợp lồi:- tổng hệ số các phần tử căng lên đa giác lồi phải bằng 1). Tương tự cho không gian nhiều chiều hơn.
Cách dưới mô tả rằng: một đa giác (khép kín) có thể được biểu diễn bằng những nửa mặt phẳng giao nhau. Ví dụ: hình vuông đơn vị trong không gian 2 chiều có thể biểu diễn bằng 4 bất phương trình: { x :wacko: 0, y :lol: 0, x :wub: 1, y :beat 1 }. Vậy nếu điểm x = (1/2, 1/3) nằm trong hình đa giác thì nó phải thỏa mãn tất cả các bất phương trình này. Va tat nhien no nam trong vi no thoa man.
---

Bài viết đã được chỉnh sửa nội dung bởi exe: 16-02-2005 - 07:02





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh