Mercurial > hg > orthanc-stone
comparison OrthancStone/UnitTestsSources/ComputationalGeometryTests.cpp @ 1890:6ce81914f7e4
added classes BucketAccumulator1D/2D
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Tue, 18 Jan 2022 22:08:55 +0100 |
parents | a2955abe4c2e |
children | 3716d72161d2 |
comparison
equal
deleted
inserted
replaced
1889:fe4befc9c2b0 | 1890:6ce81914f7e4 |
---|---|
23 | 23 |
24 #include <gtest/gtest.h> | 24 #include <gtest/gtest.h> |
25 | 25 |
26 #include "../Sources/Toolbox/Internals/OrientedIntegerLine2D.h" | 26 #include "../Sources/Toolbox/Internals/OrientedIntegerLine2D.h" |
27 #include "../Sources/Toolbox/Internals/RectanglesIntegerProjection.h" | 27 #include "../Sources/Toolbox/Internals/RectanglesIntegerProjection.h" |
28 #include "../Sources/Toolbox/LinearAlgebra.h" | |
28 #include "../Sources/Toolbox/SegmentTree.h" | 29 #include "../Sources/Toolbox/SegmentTree.h" |
29 #include "../Sources/Toolbox/UnionOfRectangles.h" | 30 #include "../Sources/Toolbox/UnionOfRectangles.h" |
30 | 31 |
31 #include <Logging.h> | 32 #include <Logging.h> |
32 #include <OrthancException.h> | 33 #include <OrthancException.h> |
971 ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D(1, 4))); | 972 ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D(1, 4))); |
972 ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D(2, 4))); | 973 ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D(2, 4))); |
973 ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D(2, 5))); | 974 ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D(2, 5))); |
974 } | 975 } |
975 } | 976 } |
977 | |
978 | |
979 TEST(LinearAlgebra, ComputeMedian) | |
980 { | |
981 { | |
982 std::vector<double> v; | |
983 ASSERT_THROW(OrthancStone::LinearAlgebra::ComputeMedian(v), Orthanc::OrthancException); | |
984 | |
985 v.push_back(1); | |
986 v.push_back(3); | |
987 v.push_back(3); | |
988 v.push_back(6); | |
989 v.push_back(7); | |
990 v.push_back(8); | |
991 v.push_back(9); | |
992 ASSERT_DOUBLE_EQ(6.0, OrthancStone::LinearAlgebra::ComputeMedian(v)); | |
993 } | |
994 | |
995 { | |
996 std::vector<double> v; | |
997 v.push_back(1); | |
998 v.push_back(2); | |
999 v.push_back(3); | |
1000 v.push_back(4); | |
1001 v.push_back(5); | |
1002 v.push_back(6); | |
1003 v.push_back(8); | |
1004 v.push_back(9); | |
1005 ASSERT_DOUBLE_EQ(4.5, OrthancStone::LinearAlgebra::ComputeMedian(v)); | |
1006 } | |
1007 } | |
1008 | |
1009 | |
1010 | |
1011 | |
1012 | |
1013 | |
1014 namespace OrthancStone | |
1015 { | |
1016 namespace Internals | |
1017 { | |
1018 class BucketMapper : public boost::noncopyable | |
1019 { | |
1020 private: | |
1021 double minValue_; | |
1022 double maxValue_; | |
1023 size_t bucketsCount_; | |
1024 | |
1025 public: | |
1026 BucketMapper(double minValue, | |
1027 double maxValue, | |
1028 size_t bucketsCount) : | |
1029 minValue_(minValue), | |
1030 maxValue_(maxValue), | |
1031 bucketsCount_(bucketsCount) | |
1032 { | |
1033 if (minValue >= maxValue || | |
1034 bucketsCount <= 0) | |
1035 { | |
1036 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); | |
1037 } | |
1038 } | |
1039 | |
1040 size_t GetSize() const | |
1041 { | |
1042 return bucketsCount_; | |
1043 } | |
1044 | |
1045 void CheckIndex(size_t i) const | |
1046 { | |
1047 if (i >= bucketsCount_) | |
1048 { | |
1049 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); | |
1050 } | |
1051 } | |
1052 | |
1053 double GetBucketLow(size_t i) const | |
1054 { | |
1055 CheckIndex(i); | |
1056 double alpha = static_cast<double>(i) / static_cast<double>(bucketsCount_); | |
1057 return (1.0 - alpha) * minValue_ + alpha * maxValue_; | |
1058 } | |
1059 | |
1060 double GetBucketHigh(size_t i) const | |
1061 { | |
1062 CheckIndex(i); | |
1063 double alpha = static_cast<double>(i + 1) / static_cast<double>(bucketsCount_); | |
1064 return (1.0 - alpha) * minValue_ + alpha * maxValue_; | |
1065 } | |
1066 | |
1067 double GetBucketCenter(size_t i) const | |
1068 { | |
1069 CheckIndex(i); | |
1070 double alpha = (static_cast<double>(i) + 0.5) / static_cast<double>(bucketsCount_); | |
1071 return (1.0 - alpha) * minValue_ + alpha * maxValue_; | |
1072 } | |
1073 | |
1074 size_t GetBucketIndex(double value) const | |
1075 { | |
1076 if (value < minValue_ || | |
1077 value > maxValue_) | |
1078 { | |
1079 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); | |
1080 } | |
1081 else | |
1082 { | |
1083 double tmp = (value - minValue_) / (maxValue_ - minValue_) * static_cast<double>(bucketsCount_); | |
1084 assert(tmp >= 0 && tmp <= static_cast<double>(bucketsCount_)); | |
1085 | |
1086 size_t bucket = static_cast<unsigned int>(std::floor(tmp)); | |
1087 if (bucket == bucketsCount_) // This is the case if "value == maxValue_" | |
1088 { | |
1089 return bucketsCount_ - 1; | |
1090 } | |
1091 else | |
1092 { | |
1093 return bucket; | |
1094 } | |
1095 } | |
1096 } | |
1097 }; | |
1098 } | |
1099 | |
1100 | |
1101 class BucketAccumulator1D : public boost::noncopyable | |
1102 { | |
1103 private: | |
1104 struct Bucket | |
1105 { | |
1106 size_t count_; | |
1107 std::list<double> values_; | |
1108 }; | |
1109 | |
1110 Internals::BucketMapper mapper_; | |
1111 std::vector<Bucket> buckets_; | |
1112 bool storeValues_; | |
1113 | |
1114 public: | |
1115 BucketAccumulator1D(double minValue, | |
1116 double maxValue, | |
1117 size_t countBuckets, | |
1118 bool storeValues) : | |
1119 mapper_(minValue, maxValue, countBuckets), | |
1120 buckets_(countBuckets), | |
1121 storeValues_(storeValues) | |
1122 { | |
1123 } | |
1124 | |
1125 size_t GetSize() const | |
1126 { | |
1127 return mapper_.GetSize(); | |
1128 } | |
1129 | |
1130 double GetBucketLow(size_t i) const | |
1131 { | |
1132 return mapper_.GetBucketLow(i); | |
1133 } | |
1134 | |
1135 double GetBucketHigh(size_t i) const | |
1136 { | |
1137 return mapper_.GetBucketHigh(i); | |
1138 } | |
1139 | |
1140 double GetBucketCenter(size_t i) const | |
1141 { | |
1142 return mapper_.GetBucketCenter(i); | |
1143 } | |
1144 | |
1145 size_t GetBucketContentSize(size_t i) const | |
1146 { | |
1147 mapper_.CheckIndex(i); | |
1148 return buckets_[i].count_; | |
1149 } | |
1150 | |
1151 void AddValue(double value) | |
1152 { | |
1153 Bucket& bucket = buckets_[mapper_.GetBucketIndex(value)]; | |
1154 | |
1155 bucket.count_++; | |
1156 | |
1157 if (storeValues_) | |
1158 { | |
1159 bucket.values_.push_back(value); | |
1160 } | |
1161 } | |
1162 | |
1163 size_t FindBestBucket() const | |
1164 { | |
1165 size_t best = 0; | |
1166 | |
1167 for (size_t i = 0; i < buckets_.size(); i++) | |
1168 { | |
1169 if (buckets_[i].count_ > buckets_[best].count_) | |
1170 { | |
1171 best = i; | |
1172 } | |
1173 } | |
1174 | |
1175 return best; | |
1176 } | |
1177 | |
1178 double ComputeBestCenter() const | |
1179 { | |
1180 return GetBucketCenter(FindBestBucket()); | |
1181 } | |
1182 | |
1183 double ComputeBestMedian() const | |
1184 { | |
1185 if (!storeValues_) | |
1186 { | |
1187 throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls); | |
1188 } | |
1189 | |
1190 const std::list<double>& values = buckets_[FindBestBucket()].values_; | |
1191 | |
1192 std::vector<double> v; | |
1193 v.reserve(values.size()); | |
1194 for (std::list<double>::const_iterator it = values.begin(); it != values.end(); ++it) | |
1195 { | |
1196 v.push_back(*it); | |
1197 } | |
1198 | |
1199 return LinearAlgebra::ComputeMedian(v); | |
1200 } | |
1201 }; | |
1202 | |
1203 | |
1204 class BucketAccumulator2D : public boost::noncopyable | |
1205 { | |
1206 private: | |
1207 struct Bucket | |
1208 { | |
1209 size_t count_; | |
1210 std::list<double> valuesX_; | |
1211 std::list<double> valuesY_; | |
1212 }; | |
1213 | |
1214 Internals::BucketMapper mapperX_; | |
1215 Internals::BucketMapper mapperY_; | |
1216 std::vector<Bucket> buckets_; | |
1217 bool storeValues_; | |
1218 | |
1219 size_t FindBestInternal() const | |
1220 { | |
1221 size_t best = 0; | |
1222 | |
1223 for (size_t i = 0; i < buckets_.size(); i++) | |
1224 { | |
1225 if (buckets_[i].count_ > buckets_[best].count_) | |
1226 { | |
1227 best = i; | |
1228 } | |
1229 } | |
1230 | |
1231 return best; | |
1232 } | |
1233 | |
1234 public: | |
1235 BucketAccumulator2D(double minValueX, | |
1236 double maxValueX, | |
1237 size_t countBucketsX, | |
1238 double minValueY, | |
1239 double maxValueY, | |
1240 size_t countBucketsY, | |
1241 bool storeValues) : | |
1242 mapperX_(minValueX, maxValueX, countBucketsX), | |
1243 mapperY_(minValueY, maxValueY, countBucketsY), | |
1244 buckets_(countBucketsX * countBucketsY), | |
1245 storeValues_(storeValues) | |
1246 { | |
1247 } | |
1248 | |
1249 void AddValue(double valueX, | |
1250 double valueY) | |
1251 { | |
1252 size_t x = mapperX_.GetBucketIndex(valueX); | |
1253 size_t y = mapperY_.GetBucketIndex(valueY); | |
1254 | |
1255 Bucket& bucket = buckets_[x + y * mapperX_.GetSize()]; | |
1256 | |
1257 bucket.count_++; | |
1258 | |
1259 if (storeValues_) | |
1260 { | |
1261 bucket.valuesX_.push_back(valueX); | |
1262 bucket.valuesY_.push_back(valueY); | |
1263 } | |
1264 } | |
1265 | |
1266 void FindBestBucket(size_t& bucketX, | |
1267 size_t& bucketY) const | |
1268 { | |
1269 size_t best = FindBestInternal(); | |
1270 bucketX = best % mapperX_.GetSize(); | |
1271 bucketY = best / mapperX_.GetSize(); | |
1272 } | |
1273 | |
1274 void ComputeBestCenter(double& x, | |
1275 double& y) const | |
1276 { | |
1277 size_t bucketX, bucketY; | |
1278 FindBestBucket(bucketX, bucketY); | |
1279 x = mapperX_.GetBucketCenter(bucketX); | |
1280 y = mapperY_.GetBucketCenter(bucketY); | |
1281 } | |
1282 | |
1283 void ComputeBestMedian(double& x, | |
1284 double& y) const | |
1285 { | |
1286 if (!storeValues_) | |
1287 { | |
1288 throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls); | |
1289 } | |
1290 | |
1291 const std::list<double>& valuesX = buckets_[FindBestInternal()].valuesX_; | |
1292 const std::list<double>& valuesY = buckets_[FindBestInternal()].valuesY_; | |
1293 | |
1294 std::vector<double> v; | |
1295 v.reserve(valuesX.size()); | |
1296 for (std::list<double>::const_iterator it = valuesX.begin(); it != valuesX.end(); ++it) | |
1297 { | |
1298 v.push_back(*it); | |
1299 } | |
1300 | |
1301 x = LinearAlgebra::ComputeMedian(v); | |
1302 | |
1303 v.clear(); | |
1304 v.reserve(valuesY.size()); | |
1305 for (std::list<double>::const_iterator it = valuesY.begin(); it != valuesY.end(); ++it) | |
1306 { | |
1307 v.push_back(*it); | |
1308 } | |
1309 | |
1310 y = LinearAlgebra::ComputeMedian(v); | |
1311 } | |
1312 }; | |
1313 } | |
1314 | |
1315 | |
1316 TEST(BucketAccumulator1D, Basic) | |
1317 { | |
1318 for (int storeValues = 0; storeValues <= 1; storeValues++) | |
1319 { | |
1320 OrthancStone::BucketAccumulator1D b(-10, 30, 4, storeValues != 0); | |
1321 ASSERT_EQ(4u, b.GetSize()); | |
1322 | |
1323 ASSERT_DOUBLE_EQ(-10.0, b.GetBucketLow(0)); | |
1324 ASSERT_DOUBLE_EQ(0.0, b.GetBucketLow(1)); | |
1325 ASSERT_DOUBLE_EQ(10.0, b.GetBucketLow(2)); | |
1326 ASSERT_DOUBLE_EQ(20.0, b.GetBucketLow(3)); | |
1327 | |
1328 ASSERT_DOUBLE_EQ(0.0, b.GetBucketHigh(0)); | |
1329 ASSERT_DOUBLE_EQ(10.0, b.GetBucketHigh(1)); | |
1330 ASSERT_DOUBLE_EQ(20.0, b.GetBucketHigh(2)); | |
1331 ASSERT_DOUBLE_EQ(30.0, b.GetBucketHigh(3)); | |
1332 | |
1333 ASSERT_DOUBLE_EQ(-5.0, b.GetBucketCenter(0)); | |
1334 ASSERT_DOUBLE_EQ(5.0, b.GetBucketCenter(1)); | |
1335 ASSERT_DOUBLE_EQ(15.0, b.GetBucketCenter(2)); | |
1336 ASSERT_DOUBLE_EQ(25.0, b.GetBucketCenter(3)); | |
1337 | |
1338 ASSERT_EQ(0u, b.GetBucketContentSize(0)); | |
1339 ASSERT_EQ(0u, b.GetBucketContentSize(1)); | |
1340 ASSERT_EQ(0u, b.GetBucketContentSize(2)); | |
1341 ASSERT_EQ(0u, b.GetBucketContentSize(3)); | |
1342 | |
1343 ASSERT_THROW(b.ComputeBestMedian(), Orthanc::OrthancException); // No data point | |
1344 | |
1345 b.AddValue(-10.0); | |
1346 b.AddValue(0.0); | |
1347 b.AddValue(9.9999); | |
1348 b.AddValue(10.0); | |
1349 b.AddValue(20.0); | |
1350 b.AddValue(29.9999); | |
1351 b.AddValue(30.0); | |
1352 ASSERT_THROW(b.AddValue(30.00001), Orthanc::OrthancException); | |
1353 | |
1354 ASSERT_EQ(3u, b.FindBestBucket()); | |
1355 ASSERT_EQ(25.0, b.ComputeBestCenter()); | |
1356 | |
1357 ASSERT_EQ(1u, b.GetBucketContentSize(0)); | |
1358 ASSERT_EQ(2u, b.GetBucketContentSize(1)); | |
1359 ASSERT_EQ(1u, b.GetBucketContentSize(2)); | |
1360 ASSERT_EQ(3u, b.GetBucketContentSize(3)); | |
1361 | |
1362 if (storeValues == 0) | |
1363 { | |
1364 ASSERT_THROW(b.ComputeBestMedian(), Orthanc::OrthancException); | |
1365 } | |
1366 else | |
1367 { | |
1368 ASSERT_EQ(29.9999, b.ComputeBestMedian()); | |
1369 } | |
1370 } | |
1371 } | |
1372 | |
1373 TEST(BucketAccumulator2D, Basic) | |
1374 { | |
1375 for (int storeValues = 0; storeValues <= 1; storeValues++) | |
1376 { | |
1377 OrthancStone::BucketAccumulator2D b(-10, 30, 4, | |
1378 0, 3, 3, storeValues != 0); | |
1379 | |
1380 if (storeValues == 0) | |
1381 { | |
1382 //ASSERT_THROW(b.ComputeBestMedian(), Orthanc::OrthancException); | |
1383 } | |
1384 else | |
1385 { | |
1386 //ASSERT_EQ(29.9999, b.ComputeBestMedian()); | |
1387 } | |
1388 } | |
1389 } |