Trying to make life worth

Wednesday, December 14, 2016

How to Find Minimum Area Bounding Rectangle for given 3D Polygon ?

I have an arbitrary polygon as shown in Pic with co-planar Vertices's A,B,C,D,E,F,G,H in 3 D coordinate System. This Polygon is about to arbitrary axis.
Step 1. Rotate Arbitrary Polygon in X-Y Plane[Bounding-rectangle of 3D Polygon]
Step 2. Pick 1 edge and align this edge with the X axis(use Destination Vector " Vector3(1, 0, 0); // X-axis for align Edge Along X-axis " and Edge Direction as Source Vector. Compute Rotation Matrix and Save as EdgeAlignX-Axis Matrix to Rotate back Rectangle in Step 4). Use the min/max x,y to find the bounding rectangle. Compute Area and store in list, Do the same for remaining edges in  polygon. Pick the rectangle with the minimum Area.

Step 3.  Generate Minimum Bounding Rectangle by using min max.
bottomleftCorner = new Vector3(minXYZ[0], minXYZ[1], pointarr[0].z);
bottomRightCorner = new Vector3(maxXYZ[0], minXYZ[1], pointarr[0].z);
topLeftCorner = new Vector3(minXYZ[0], maxXYZ[1], pointarr[0].z);
topRightCorner = new Vector3(maxXYZ[0], maxXYZ[1], pointarr[0].z);

Note:- set Z-value of Bounding Rectangle Equal to Rotated Polygon Z Value for Perfect Align. Instead of Min Z and Max Z. 
Step 4. Rotate Computed Bounding rectangle Reverse of Edge Align X-Axis Matrix.

step 5.  rotate Bounding rectangle back to Original polygon direction by using reverse of Rotation matrix.








No comments:

Post a Comment