Câu hỏi
Ngoc
26/04/2013 21:39
Hỏi về kĩ thuật lập trình C++ theo hướng đối tượng?
Vấn đề tôi gặp phải là làm sao tô màu đường biên của phần giao nhau của hai hình . Ví dụ tô đường biên của phần giao nhau của hai đa giác . Hỏi mọi người có biết hàm nào trong C++ làm việc đó ko . Hay có biết thuật toán nào giải quyết vất đề trên mà làm việc trong borland C++ hay visual studio C++ 6.0
TungNo1
26/04/2013 21:39
manhlinh
26/04/2013 21:39
Danh sách câu trả lời (2)
TungNo1
26/04/2013 21:39
Phần này khó nhỉ, bạn hỏi trong diễn đàn lập trình nhé
manhlinh
26/04/2013 21:39
Giải thuật đầu tiên bạn phải nghiên cứu chính là giải thuật xén đa giác.
Tư tưởng như sau :
Input :
Cho một đa giác A bất kỳ có n đỉnh, thứ tự các định bố trí theo chiều kim đồng hồ chẳng hạn. Cho một đa giác B có m đỉnh cũng được bố trí theo chiều kim đồng hồ như vậy.
Output:
Đa giác là phần giao của 2 đa giác C.
Tư tưởng như sau :
Với mỗi cạnh của đa giác B, xem nó cắt đa giác A ở những cạnh nào giao điểm là bao nhiêu.
Nếu cạnh xác định bởi 2 đỉnh B,B[i+1] của đa giác B cắt cạnh A[j],A[j+1]. (Chú ý là cắt cạnh,không phải cắt đường thẳng) Khi đó:
+)Nếu đỉnh A chẳng hạn nằm ở phía bên kia so với vùng giao thì thay A bởi giao điểm đó Ta được đa giác A' mới. (Chính vì vậy mà ta phải chọn chiều biểu diễn các đa giác không thì khôn thể nào xác định được bên nào là phần giao).
Chú ý là nếu có giao điểm của 1 cạnh đa giác B với đa giác A thì luôn luôn có tối thiểu 2 giao điểm do đó. Sau khi thay A bởi giao điểm thứ nhất, người ta chèn giao điểm thứ 2 vào vị trí của A[i+1]. Bạn cứ vẽ hình ra sẽ thấy.
Lần lượt như vậy sẽ xén dần được đa giác cần tìm và phần giao của chúng.
Khi đó để tô mầu cho miền kín ta áp dụng thuật toán Tô Màu đường Biên hoặc tô màu Theo Dòng Quét.
Input : Đa giác C
OutPut: Đa giác C đã tô màu.
Tô màu theo đường biên khá đơn giản bằng đệ quy hoặc khi đa khử đệ quy ta dùng Stack, nhưng không hiệu quả.Sách Đồ Họa Máy Tính nào cũng có bạn có thể tham khảo.
Còn tô màu theo dòng Quét thì nhanh nhất,hiệu quả nhất.
Input : Một đa giác P cần tô màu
OutPut : Đa giác P đã được tô màu. P bắt đầu từ P[0] (đễ quen với chỉ số mảng trong C++ và VC++)
Thuật toán như sau: (Bạn có thể tham khảo trong các giáo trình đồ họa máy tính).
1.Với các đỉnh P, tìm yMin và yMax của đa giác (tức là giới hạn tung độ các đỉnh của đa giác).
2.For (k = yMin; k<=yMax;k++)
{
For each cạnh của P,P[i+1]
if (( k>=min(P.y,P[i+1].y)&&(k<=max(P,P[... //Có giao điểm
{
Tìm giao điểm T;
AET.Add(T) ;//Danh sách các giao điểm
}
Sort(AET); //Sắp sếp các giao điểm theo chiều tăng của x.
For each cạnh AET[j] , AET[j+1]
if (j%2==0) Line(AET[j],AET[j+1],color) ; //Nếu j chẵn thì vẽ đường thẳng với color là màu cần tô.
}
3. Tô lại toàn bộ cạnh của đa giác P ban đầu.
For each cạnh P,P[i+1] Line(P,P[i+1],color);
Sẽ phát sinh một số trường hợp đó là khi PP[i+1] song song với đường thẳng đang xét y=k sẽ bị sai với thuật toán trên. Hoặc khi giao điểm tìm được là trùng với đỉnh của đa giác thì cũng sẽ sai.
Tư tưởng như sau :
Input :
Cho một đa giác A bất kỳ có n đỉnh, thứ tự các định bố trí theo chiều kim đồng hồ chẳng hạn. Cho một đa giác B có m đỉnh cũng được bố trí theo chiều kim đồng hồ như vậy.
Output:
Đa giác là phần giao của 2 đa giác C.
Tư tưởng như sau :
Với mỗi cạnh của đa giác B, xem nó cắt đa giác A ở những cạnh nào giao điểm là bao nhiêu.
Nếu cạnh xác định bởi 2 đỉnh B,B[i+1] của đa giác B cắt cạnh A[j],A[j+1]. (Chú ý là cắt cạnh,không phải cắt đường thẳng) Khi đó:
+)Nếu đỉnh A chẳng hạn nằm ở phía bên kia so với vùng giao thì thay A bởi giao điểm đó Ta được đa giác A' mới. (Chính vì vậy mà ta phải chọn chiều biểu diễn các đa giác không thì khôn thể nào xác định được bên nào là phần giao).
Chú ý là nếu có giao điểm của 1 cạnh đa giác B với đa giác A thì luôn luôn có tối thiểu 2 giao điểm do đó. Sau khi thay A bởi giao điểm thứ nhất, người ta chèn giao điểm thứ 2 vào vị trí của A[i+1]. Bạn cứ vẽ hình ra sẽ thấy.
Lần lượt như vậy sẽ xén dần được đa giác cần tìm và phần giao của chúng.
Khi đó để tô mầu cho miền kín ta áp dụng thuật toán Tô Màu đường Biên hoặc tô màu Theo Dòng Quét.
Input : Đa giác C
OutPut: Đa giác C đã tô màu.
Tô màu theo đường biên khá đơn giản bằng đệ quy hoặc khi đa khử đệ quy ta dùng Stack, nhưng không hiệu quả.Sách Đồ Họa Máy Tính nào cũng có bạn có thể tham khảo.
Còn tô màu theo dòng Quét thì nhanh nhất,hiệu quả nhất.
Input : Một đa giác P cần tô màu
OutPut : Đa giác P đã được tô màu. P bắt đầu từ P[0] (đễ quen với chỉ số mảng trong C++ và VC++)
Thuật toán như sau: (Bạn có thể tham khảo trong các giáo trình đồ họa máy tính).
1.Với các đỉnh P, tìm yMin và yMax của đa giác (tức là giới hạn tung độ các đỉnh của đa giác).
2.For (k = yMin; k<=yMax;k++)
{
For each cạnh của P,P[i+1]
if (( k>=min(P.y,P[i+1].y)&&(k<=max(P,P[... //Có giao điểm
{
Tìm giao điểm T;
AET.Add(T) ;//Danh sách các giao điểm
}
Sort(AET); //Sắp sếp các giao điểm theo chiều tăng của x.
For each cạnh AET[j] , AET[j+1]
if (j%2==0) Line(AET[j],AET[j+1],color) ; //Nếu j chẵn thì vẽ đường thẳng với color là màu cần tô.
}
3. Tô lại toàn bộ cạnh của đa giác P ban đầu.
For each cạnh P,P[i+1] Line(P,P[i+1],color);
Sẽ phát sinh một số trường hợp đó là khi PP[i+1] song song với đường thẳng đang xét y=k sẽ bị sai với thuật toán trên. Hoặc khi giao điểm tìm được là trùng với đỉnh của đa giác thì cũng sẽ sai.
Trả lời câu hỏi
Câu hỏi lĩnh vực Lập trình
Rao vặt Siêu Vip