Có lẽ đây là một câu hỏi toán học hơn là một câu hỏi lập trình, nhưng tôi đã cố gắng thực hiện các thuật toán calipers quay trong XNA.Tìm hộp giới hạn định hướng của một Convex Hull trong XNA Sử dụng Calipers quay
Tôi đã suy ra một thân lồi từ tập hợp điểm của tôi bằng cách sử dụng một chuỗi đơn điệu như được mô tả chi tiết trên wikipedia.
Bây giờ tôi đang cố gắng để mô hình thuật toán của tôi để tìm các OBB sau khi một tìm thấy ở đây: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf
Tuy nhiên, tôi không hiểu những gì các phương pháp DOTPR và CROSSPR nó đề cập về trang cuối cùng có nghĩa vụ trở về.
Tôi hiểu cách lấy Sản phẩm Dot của hai điểm và Sản phẩm Chéo hai điểm, nhưng có vẻ như các chức năng này được cho là sẽ trả về Sản phẩm Chấm và Chéo của hai đoạn/cạnh. kiến thức của tôi về toán học được thừa nhận hạn chế nhưng đây là đoán tốt nhất của tôi như những gì các thuật toán đang tìm kiếm
public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB)
{
var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];
float crossProduct1 = CrossProduct(segmentA1, segmentB1);
return crossProduct1;
}
public static float CrossProduct(Vector2 v1, Vector2 v2)
{
return (v1.X * v2.Y - v1.Y * v2.X);
}
public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB)
{
var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];
float dotProduct = Vector2.Dot(segmentA1, segmentB1);
return dotProduct;
}
Tuy nhiên, khi tôi sử dụng các phương pháp đó theo chỉ dẫn trong phần này của mã của tôi ...
while (PolygonDot(polygon, i, j) > 0)
{
j = NextIndex(j, polygon);
}
if (i == 0)
{
k = j;
}
while (PolygonCross(polygon, i, k) > 0)
{
k = NextIndex(k, polygon);
}
if (i == 0)
{
m = k;
}
while (PolygonDot(polygon, i, m) < 0)
{
m = NextIndex(m, polygon);
}
..it trả về chỉ số tương tự cho j, k khi tôi cho nó một tập kiểm tra các điểm:
List<Vector2> polygon = new List<Vector2>()
{
new Vector2(0, 138),
new Vector2(1, 138),
new Vector2(150, 110),
new Vector2(199, 68),
new Vector2(204, 63),
new Vector2(131, 0),
new Vector2(129, 0),
new Vector2(115, 14),
new Vector2(0, 138),
};
Note, mà tôi gọi là polygon.Reverse để đặt những điểm này trong trật tự Counter-chiều kim đồng hồ như ind icated trong tài liệu kỹ thuật từ perdue.edu. Thuật toán của tôi cho việc tìm kiếm một lồi của một tập hợp điểm tạo ra một danh sách các điểm theo thứ tự ngược chiều kim đồng hồ, nhưng giả sử y < 0 cao hơn y> 0 vì khi vẽ đến màn hình 0,0 là góc trên cùng bên trái . Đảo ngược danh sách có vẻ đủ. Tôi cũng loại bỏ các điểm trùng lặp ở cuối.
Sau khi quá trình này, các dữ liệu trở thành:
- Vector2 (115, 14)
- Vector2 (129, 0)
- Vector2 (131, 0)
- Vector2 (204, 63)
- Vector2 (199, 68)
- Vector2 (150, 110)
- Vector2 (1, 138) 0.123.
- Vector2 (0, 138)
thử nghiệm này không thành công trên các vòng đầu tiên khi tôi bằng 0 và j bằng 3. Báo cáo cho thấy chéo sản phẩm của dòng (115,14) đến (204,63) và dòng (204,63) đến (199,68) là 0. Sau đó, tìm thấy rằng sản phẩm dấu chấm của cùng một dòng cũng là 0, vì vậy j và k chia sẻ cùng một chỉ mục.
Ngược lại, khi được tập kiểm tra này: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C%282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29
Mã của tôi trở thành công OBB này: http://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29%2C%285%2C3%29
Tôi đã đọc qua C++ thuật toán tìm thấy trên http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp nhưng tôi quá dày đặc để làm theo nó hoàn toàn.Nó cũng có vẻ rất khác so với chi tiết khác trong bài báo trên.
Có ai biết bước nào tôi bỏ qua hoặc thấy một số lỗi trong mã của tôi để tìm sản phẩm chấm và sản phẩm chéo của hai đoạn đường? Có ai đã triển khai thành công mã này trước đây trong C# và có một ví dụ không?
Đa giác này: Liệt kê đa giác = new List() {new Vector2 (2, 0), mới Vector2 (0, 2), mới Vector2 (2, 4), mới Vector2 (4, 2),}; là ngược chiều kim đồng hồ phải không? 0,2 nằm ở bên trái và xuống từ 2,0. 2,4 ở bên phải và xuống từ 0,2. 4,2 ở bên phải và tăng từ 2,4. 2,0 ở bên trái và lên từ 4,2. Đó là kim cương ngược kim đồng hồ. – MattB
Chờ. Tôi đã làm việc với các trò chơi video quá lâu đến mức tôi quên mọi người thường làm việc ở góc phần tư thứ nhất và không phải là thứ tư nơi giá trị y càng thấp thì giá trị y càng cao. Tôi hy vọng đây là vấn đề của tôi. – MattB
Đó là nó! Cảm ơn bạn rất nhiều. Tôi xấu hổ vì điều đó thật đơn giản. – MattB