Thấy thì đơn giản sao làm mãi không có giải pháp tối ưu:
Em có hai cái hình chữ nhật:
var cn1={x1:100,y1:100,x2:200,y2:200}
var cn2={x1:a,y1:b,x2:c,y2:d}
lam sao lay ra cai giao nhau cua chung??
anh chi em co giai thuat nao giup voi?
Thấy thì đơn giản sao làm mãi không có giải pháp tối ưu:
Em có hai cái hình chữ nhật:
var cn1={x1:100,y1:100,x2:200,y2:200}
var cn2={x1:a,y1:b,x2:c,y2:d}
lam sao lay ra cai giao nhau cua chung??
anh chi em co giai thuat nao giup voi?
Chia làm các trường hợp:
Vẽ ra giấy rồi dùng toán thôi.
var Rec={
x1:0,
y1:0,
x2:0,
y2:0,
init:function(x1,y1,x2,y2){
this.x1=x1;
this.y1=y1;
this.x2=x2;
this.y2=y2;
},
width:function(){
return this.x2-this.x1;
},
height:function(){
return this.y2-this.y1;
},
intersect:function(r){
return {x1:1,y1:1,x2:10,y2:10}
},
contains:function(x,y){
},
}
Coi đơn giản mà cũng chua ghê, nhiều trường hợp quá
Cái đoạn code trên là đi vào bế tắc…
Viết tiếng Việt có dấu đi bạn.
Bài này thuật giải khá là hay, mình tìm một số trên mạng, các trường đại học nước ngoài cũng đưa ra một vài bài nhưng công thức toán không hà, đọc không hiểu gì, nên mình tự giải cho xong.
Bước 1 : Dùng một công thức gọi là overlap để xác định hai rectangle ngoài nhau return 0;
Bước 2 : là lúc nào cũng có tồn tại 2 cặp điểm bao gồm các trường hợp như sau
Có thể for là hơi cùi bắp nhưng thấy cái laptop cùi bắp của mình cũng chạy tốt
Ứng dụng thêm : Để tìm collistion event của 2 đối tượng Rectangle trong game.
Hình ảnh tham khảo như sau :
http://vibigaba.esy.es/hinh_anh/rec_chu_thap.png
http://vibigaba.esy.es/hinh_anh/rec_chua_nhau.png
http://vibigaba.esy.es/hinh_anh/rec_ngoai_nhau.png
http://vibigaba.esy.es/hinh_anh/rec_one_to_two_point.png
Cần share code thì đưa cái mail mình share cho nhé.
hcn là 2 chiều, làm 1 chiều trước, rồi thêm 1 chiều nữa là ra hcn
1 chiều là bài toán tìm phần giao của 2 đoạn [a, b] và [c, d]. Nếu b < c hoặc d < a thì ko giao. Ngược lại thì đoạn giao là [max(a,c), min(b,d)]. Xong chiều Ox rồi thêm chiều Oy nữa là xong cái hcn
ko biết đúng ko
Input: HCN((a,A), (b,B)), HCN((c,C), (d,D)) (tọa độ đỉnh trên bên trái, tọa độ đỉnh dưới bên phải)
x1 = max(a,c)
x2 = min(b,d)
y1 = max(A,C)
y2 = min(B,D)
nếu x2 <= x1 hoặc y2 <= y1 thì ko giao,
ngược lại trả về HCN((x1,y1), (x2,y2))
hay bạn, nhưng tại sao lại đúng không?
để mình test;
Bạn làm mình nhớ đến một ông Thầy lúc xưa: ổng nói thế này các bạn đừng tưởng lập trình viên chuyên nghiệp là viết một lèo cái code là run luôn đâu? phải thế này : viết một dòng code xong run 1 cái, viết một dòng run một cái…hix
Xàm. Làm gì có chuyện viết 1 dòng run 1 cái
=> Thuật toán đơn giản nhất:
HinhChuNhat
có 4 thông số: MinX
, MinY
, MaxX
, MaxY
và hàm tạo 4 thông số (X1, X2, Y1, Y2)
. Việc đảm bảo MaxY
≥ MinY
cũng như MaxX
≥ MinX
được thực hiện trong hàm tạoA
và B
nếu A.MaxY
< B.MinY
hoặc B.MaxY
< A.MinY
hoặc A.MaxX
< B.MinX
hoặc B.MaxX
< A.MinX
thì trả về một hình chữ nhật null
X1 = Max(A.MinX, B.MinX)
, X2 = Min(A.MaxX, B.MaxX)
, Y1 = Max(A.MinY, B.MinY)
, Y2 = Min(A.MaxY, B.MaxY)
Đây là code C# của mình:
using System;
namespace FindRect
{
class Rectangle
{
public int MinX { get; private set; }
public int MaxX { get; private set; }
public int MinY { get; private set; }
public int MaxY { get; private set; }
public Rectangle(int X1, int X2, int Y1, int Y2)
{
MinX = Math.Min(X1, X2);
MaxX = Math.Max(X1, X2);
MinY = Math.Min(Y1, Y2);
MaxY = Math.Max(Y1, Y2);
}
}
class RectFinder
{
Rectangle Intersection(Rectangle A, Rectangle B)
{
if (A.MinX > B.MaxX)
return null;
if (B.MinX > A.MaxX)
return null;
if (A.MinY > B.MaxY)
return null;
if (B.MinY > A.MaxY)
return null;
return new Rectangle(Math.Min(A.MaxX, B.MaxX), Math.Max(A.MinX, B.MinX), Math.Min(A.MaxY, B.MaxY), Math.Max(A.MinY, B.MinY));
}
}
}
Chạy ra hả bạn, cho mình xem luôn hình chụp cái màn hình luôn với bạn
Phần trên thì thấy ok còn cái dòng
return new Rectangle(Math.Min(A.MaxX, B.MaxX), Math.Max(A.MinX, B.MinX), Math.Min(A.MaxY, B.MaxY), Math.Max(A.MinY, B.MinY));
Mình thấy nghi nghi.
Đơn giản thôi. Nếu có giao nhau thì phần giao nhau sẽ nằm trong min của 2 max và max của 2 min.
bạn test chua?
đoạn code tui dài hơn bạn 10 lần
Phạm vi áp dụng topic này là các hình chữ nhật thường ( các cạnh song song với trục tung hoặc trục hoành ) Còn trường hợp hình chữ nhật xoay chưa bàn tới…
Nâng tầm bài toán lên 1 chút, lấy phần giao của 2 đa giác lồi.
Đây chỉ là thuật toán của riêng phần giao nhau, chứ không phải là cả một chương trình như của bạn nên nó chỉ có đến thế thôi. Còn để viết chương trình mô tả thì cũng phức tạp, mà mình thì không học javascript nên không hiểu và sửa code của bạn được, phải viết chương trình mới bằng C# vậy
http://vibigaba.esy.es/hinh_anh/rec_sai_point1.png
hy vọng là mình sai
Cái đoạn dưới cùng có vấn đề
còn cái trên thì ok.
hello Mr Trần Hoàn, thank you for your exactly code, this is test code full
A ⋂ B http://www.boost.org/doc/libs/1_64_0/libs/geometry/doc/html/geometry/reference/algorithms/intersection/intersection_3.html
A – B http://www.boost.org/doc/libs/1_64_0/libs/geometry/doc/html/geometry/reference/algorithms/difference/difference_3.html
A ⋃ B http://www.boost.org/doc/libs/1_64_0/libs/geometry/doc/html/geometry/reference/algorithms/union_/union__3.html
hổng chơi, xài thư viện cho khỏe Lồi lõm hay có lỗ đều chơi tuốt
Bài toán tổng quát:
Cho một tập N đối tượng, liệu có 2 đối tượng nào giao nhau hay không?(Đối tượng ở đây có thể là đường, đoạn thẳng, hình tròn, chữ nhật hay bất kỳ đối tượng hình học nào) . Làm mấy bài này chắc nổ đầu mất.
Note: M.Shamos và D.Hoey đã để xuất thuật giải cho bài toán này :v