I'm back at the computational geometry stuff. This time, I want to find the minimum bounding rectangle (MBR) of a given convex hull. I've found a few spots that discuss the pseudo code (using rotating calipers) and then I went looking for source. Like so many times before, the algorithm I want in every example of source code I've found is obscured either by user interface code or simply complexities of the language for dealing with non-standard types. Urgh!!!
However, since the rotating calipers approach can be used for both finding the MBR and determining the intersection of two hulls in linear time, it'll definitely be worth my while to figure out my own implementation (which will be sufficiently obscured by the details of my own non-standard types ;P).
1 comments:
More on languages... It seems that my data structures make rotating calipers a little harrowing - basically requiring reordering my vertices each time. That makes a big dent in the order of the algorithm.
So I decided on a very straight-forward method:
For each segment:
1. Calculate the angle from the x-axis, rotate the entire hull, vertex by vertex so that that segment is axis-aligned.
2. Check each rotated vertex for min/max to find the axis-aligned bounding box.
3. Compare the area of each axis-aligned bounding box to find the minimum area.
4. Save the coordinates, area and theta for the minimum area aabr.
5. When done with each segment, rote at the coordinates of the best aabr back to get the minimum bounding rectangle.
This is O(n*n), but n is small and the loops are very tight. I only save the four extremum or the best aabr and use those to determine the rotated-back mbr coordinates.
Post a Comment