Làm sao lấy phần giao của hai hình chữ nhật

Chia làm các trường hợp:

• Có 1 hình chữ nhật chứa hình chữ nhật còn lại
• 2 hình chữ nhật không chứa nhau:
• 2 hình không liên quan đến nhau
• 2 hình chung cạnh hoặc chung đỉnh
• 1 hình chữ nhật có ít nhất 1 điểm (và không quá 4 điểm) nằm trong hình chữ nhật còn lại.

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…

Coi cai don gian ma cung chua ghe

Viết tiếng Việt có dấu đi bạn.

how play with rectangle

Viết giúp thử 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

• nằm trong nhau
• Chứa từ 1 đến 2 điểm chung
• Hai rectangle tạo thành hình chữ thập (Trường hợp này dễ lọt sổ vì không có đinh chung nào…)
  Lúc này ta sẽ dùng một trục horizon hoặc vertical đễ quét, giả sử mình dùng trục vertical
  +xác định max X, max Y, min X, min Y
  +xác định một danh sách theo Y của 2 rectangle
  Sử dụng vòng lặp for để quét là ra kết quả

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

Một thuật toán hoàn chỉnh tự nghĩ được triển khai bằng C#.

IMG_1192.JPG3264x2448 2.74 MB

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

• Đọc yêu cầu bài toán
• Phân tích bài toán thành các chức năng chương trình
• Phân tích chức năng thành các bài toán nhỏ hơn
• Phân tích các bài toán nhỏ hơn này đên khi không thể phân tích được nữa
• Viết hàm cho các bài toán cực tiểu và test từng hàm đó => Chắc ý ông thầy là như thế
• Ghép các hàm vào chương trình chính và chạy.

=> Thuật toán đơn giản nhất:

1. Xây dựng class 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ạo
2. Với 2 hình chữ nhật A 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
3. Trả về hình chữ nhật mới thông qua hàm tạo với 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:slight_smile:

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

http://plnkr.co/edit/HLhWE9?p=preview

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