Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include "ApproxMVBB/MinAreaRectangle.hpp"
00011
00012 namespace ApproxMVBB{
00013 void MinAreaRectangle::compute() {
00014
00015
00016
00017 m_minBox.reset();
00018
00019
00020 if(m_p.cols() == 0) {
00021 return;
00022 }
00023
00024
00025 m_convh.compute();
00026 ApproxMVBB_ASSERTMSG(m_convh.verifyHull(), "Convex hull not ok!")
00027
00028
00029
00030 computeRectangle();
00031
00032
00033 adjustRectangle();
00034 }
00035
00036 void MinAreaRectangle::computeRectangle() {
00037
00038
00039 m_hullIdx = m_convh.getIndices();
00040 unsigned int nPoints = m_hullIdx.size();
00041
00042
00043
00044
00045
00046 if(nPoints == 0) {
00047 return;
00048 } else if( nPoints == 1) {
00049 m_minBox.m_p = m_p.col(m_hullIdx[0]);
00050 m_minBox.m_u.setZero();
00051 m_minBox.m_v.setZero();
00052 return;
00053 } else if(nPoints == 2) {
00054 m_minBox.m_p = m_p.col(m_hullIdx[0]);
00055 m_minBox.m_u = m_p.col(m_hullIdx[1]) - m_p.col(m_hullIdx[0]);
00056 m_minBox.m_v.setZero();
00057 return;
00058 }
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082 m_angles.resize(nPoints);
00083 for(unsigned int i=0; i<nPoints; ++i) {
00084 m_angles[i] = PointFunctions::getAngle(m_p.col(m_hullIdx[i]),
00085 m_p.col(m_hullIdx[(i+1) % nPoints])
00086 );
00087
00088 }
00089
00090
00091 Caliper calipers[4];
00092
00093 calipers[0].m_idx = 0;
00094 calipers[0].m_ptIdx = m_hullIdx[0];
00095
00096 updateCalipers(m_angles[0],calipers);
00097
00098 Box2d box;
00099
00100 getBox(calipers,m_minBox);
00101
00102
00103 for(unsigned int i=1; i<nPoints; ++i) {
00104
00105 updateCalipers(m_angles[i],calipers);
00106
00107 getBox(calipers,box);
00108
00109 if(box.m_area < m_minBox.m_area) {
00110
00111 m_minBox = box;
00112 }
00113 }
00114 }
00115
00116
00117
00118 void MinAreaRectangle::findVertex(Caliper & c) {
00119
00120 PREC matchAngle = c.m_currAngle;
00121
00122
00123 unsigned int currIdx = c.m_idx;
00124
00125 PREC currAngle = m_angles[currIdx];
00126 PREC nextAngle;
00127
00128 unsigned int nPoints = m_hullIdx.size();
00129 bool found = false;
00130 unsigned int i = 0;
00131 while(!found && i < nPoints) {
00132
00133 currIdx = (currIdx + 1) % nPoints;
00134
00135 nextAngle = m_angles[currIdx];
00136
00137
00138
00139
00140 if( nextAngle > currAngle ) {
00141
00142 found = (currAngle < matchAngle && matchAngle <= nextAngle);
00143 } else {
00144
00145
00146
00147
00148
00149 found = (std::abs(currAngle-nextAngle)>1e-10) && (currAngle < matchAngle || matchAngle <= nextAngle);
00150 }
00151
00152 currAngle = nextAngle;
00153 ++i;
00154 }
00155
00156 if(found) {
00157 c.m_idx = currIdx;
00158 c.m_ptIdx = m_hullIdx[currIdx];
00159
00160 } else {
00161 std::stringstream ss;
00162 for(auto & a : m_angles){ ss << a <<",";}
00163 ApproxMVBB_ERRORMSG("Could not find vertex with angle greater than: "
00164 << matchAngle << "in angles: " << ss.str());
00165 }
00166 }
00167
00168 void MinAreaRectangle::getBox(Caliper (&c)[4], Box2d & box) {
00169 using namespace PointFunctions;
00170
00171 box.m_u = intersectLines( m_p.col(c[0].m_ptIdx), c[0].m_currAngle,
00172 m_p.col(c[1].m_ptIdx), c[1].m_currAngle);
00173
00174 box.m_v = intersectLines( m_p.col(c[3].m_ptIdx), c[3].m_currAngle,
00175 m_p.col(c[2].m_ptIdx), c[2].m_currAngle);
00176
00177
00178 box.m_p = intersectLines( m_p.col(c[0].m_ptIdx), c[0].m_currAngle,
00179 m_p.col(c[3].m_ptIdx), c[3].m_currAngle);
00180
00181 box.m_u -= box.m_p;
00182 box.m_v -= box.m_p;
00183 box.m_area = box.m_u.norm()*box.m_v.norm();
00184
00185 }
00186
00187 }