Search for an oriented convex hull restriction box in XNA using rotating calipers

Question

This may be a mathematical question rather than a programming one, but I tried to implement the rotating caliper algorithm in XNA.

I deduced the convex hull from my set of points using the monotone chain described in detail on Wikipedia.

Now I'm trying to simulate my algorithm to find the OBB after found here: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

However, I do not understand how the DOTPR and CROSSPR methods that he mentions on the last page should be returned.

I understand how to get Dot Product of two points and Cross Product of two points, but it seems that these functions should return Dot and Cross Products of two edge / line segments. My knowledge of mathematics is admittedly limited, but this is my best guess as to what the algorithm is looking for

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; } 

However, when I use these methods, as indicated in this part of my code ...

  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 returns the same index for j, k when I give it a test set of points:

  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 that I call polygon.Reverse to place these points in counterclockwise order, as indicated in the whitepaper from perdue.edu. My search algorithm for the convex hull of a point set generates a list of points in counterclockwise order, but does this assuming that y <0 is higher than y> 0, because when drawing to the screen 0.0 there is an upper left corner. Overriding the list seems sufficient. I also delete the duplicate at the end.

After this process, the data becomes:

• Vector2 (115, 14)
• Vector2 (129, 0)
• Vector2 (131, 0)
• Vector2 (204, 63)
• Vector2 (199, 68)
• Vector2 (150, 110)
• Vector2 (1, 138)
• Vector2 (0, 138)

This test fails in the first cycle, when I is 0 and j is 3. It finds that the cross product of the line (115.14) - (204.63) and the line (204.63) - (199.68) is 0. Then we find that the point product of the same lines is also 0, so j and k have the same index.

In contrast, when this test suite: 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

My code successfully returns this OBB: 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

I read the C ++ algorithm found at http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp , but I'm too dense to follow it completely. It also seems to be very different from the other described in the above article.

Does anyone know which step I am missing or see an error in my code to search for a point product and cross product two segments? Has anyone successfully implemented this code before in C # and has an example?

Answer 1

Dots and vectors as data structures are essentially the same thing; both consist of two floats (or three if you work in three dimensions). Therefore, when asked to take the point product of the edges, I suppose that means that the point-to-point vectors are defined by the edges. The code you provided does just that.

Your CrossProduct implementation seems to be correct (see Wolfram MathWorld ). However, in PolygonCross and PolygonDot I think you should not normalize segments. This will affect the return value of PolygonDot and PolygonCross . By removing the extra calls on Vector2.Normalize , you can speed up your code and reduce the amount of noise in floating point values. However, normalization is not related to the correctness of the code you inserted, since it compares the results with zero.

Please note that the document you are referring to assumes that the vertices of the polygon are indicated in counterclockwise order (page 5, the first paragraph after “Start comments”), but your polygon example is defined clockwise. Therefore PolygonCross(polygon, 0, 1) is negative and you get the same value for j and k .

Answer 2

I guess DOTPR is a normal vector point product, crosspr is cross-product. dotproduct will return a normal number, crossproduct will return a vector that is perpendicular to the two specified vectors. (basic vector math, wikipedia check)

they are actually defined in the document, since DOTPR (i, j) returns the dotproduct of vectors from vertex i to i + 1 and j to j + 1. the same for CROSSPR, but with a cross product.