PostGIS  2.5.1dev-r@@SVN_REVISION@@

◆ test_median_robustness()

static void test_median_robustness ( void  )
static

Definition at line 1219 of file cu_algorithm.c.

References do_median_test(), LW_FALSE, and LW_TRUE.

Referenced by algorithms_suite_setup().

1220 {
1221  /* A simple implementation of Weiszfeld's algorithm will fail if the median is equal
1222  * to any one of the inputs, during any iteration of the algorithm.
1223  *
1224  * Because the algorithm uses the centroid as a starting point, this situation will
1225  * occur in the test case below.
1226  */
1227  do_median_test("MULTIPOINT ((0 -1), (0 0), (0 1))", "POINT (0 0)", LW_TRUE, 1000);
1228 
1229  /* Same as above but 3D, and shifter */
1230  do_median_test("MULTIPOINT ((1 -1 3), (1 0 2), (2 1 1))", "POINT (1 0 2)", LW_TRUE, 1000);
1231 
1232  /* Starting point is duplicated */
1233  do_median_test("MULTIPOINT ((0 -1), (0 0), (0 0), (0 1))", "POINT (0 0)", LW_TRUE, 1000);
1234 
1235  /* Cube */
1236  do_median_test("MULTIPOINT ((10 10 10), (10 20 10), (20 10 10), (20 20 10), (10 10 20), (10 20 20), (20 10 20), (20 20 20))",
1237  "POINT (15 15 15)", LW_TRUE, 1000);
1238 
1239  /* Some edge cases */
1240  do_median_test("POINT (7 6)", "POINT (7 6)", LW_TRUE, 1000);
1241  do_median_test("POINT (7 6 2)", "POINT (7 6 2)", LW_TRUE, 1000);
1242  do_median_test("MULTIPOINT ((7 6 2), EMPTY)", "POINT (7 6 2)", LW_TRUE, 1000);
1243 
1244  /* Empty input */
1245  do_median_test("MULTIPOINT EMPTY", "POINT EMPTY", LW_FALSE, 1000);
1246  do_median_test("MULTIPOINT (EMPTY)", "POINT EMPTY", LW_FALSE, 1000);
1247  do_median_test("MULTIPOINT EMPTY", "POINT EMPTY", LW_TRUE, 1000);
1248  do_median_test("MULTIPOINT (EMPTY)", "POINT EMPTY", LW_TRUE, 1000);
1249  do_median_test("MULTIPOINT ZM (1 -1 3 1, 1 0 2 7, 2 1 1 1, EMPTY)", "POINT (1 0 2)", LW_TRUE, 1000);
1250 
1251  /* Weighted input */
1252  do_median_test("MULTIPOINT ZM (1 -1 3 1, 1 0 2 7, 2 1 1 1)", "POINT (1 0 2)", LW_TRUE, 1000);
1253  do_median_test("MULTIPOINT ZM (-1 1 -3 1, -1 0 -2 7, -2 -1 -1 1)", "POINT (-1 0 -2)", LW_TRUE, 1000);
1254  do_median_test("MULTIPOINT ZM (-1 1 -3 1, -1 0 -2 7, -2 -1 -1 0.5, -2 -1 -1 0.5)", "POINT (-1 0 -2)", LW_TRUE, 1000);
1255 
1256  /* Point that is replaced by two half-weighted */
1257  do_median_test("MULTIPOINT ZM ((0 -1 0 1), (0 0 0 1), (0 1 0 0.5), (0 1 0 0.5))", "POINT (0 0 0)", LW_TRUE, 1000);
1258  /* Point is doubled and then erased by negative weight */
1259  do_median_test("MULTIPOINT ZM ((1 -1 3 1), (1 0 2 7), (2 1 1 2), (2 1 1 -1))", NULL, LW_TRUE, 1000);
1260  do_median_test("MULTIPOINT ZM ((1 -1 3 1), (1 0 2 7), (2 1 1 2), (2 1 1 -1))", NULL, LW_FALSE, 1000);
1261  /* Weightless input won't converge */
1262  do_median_test("MULTIPOINT ZM ((0 -1 0 0), (0 0 0 0), (0 0 0 0), (0 1 0 0))", NULL, LW_FALSE, 1000);
1263  do_median_test("MULTIPOINT ZM ((0 -1 0 0), (0 0 0 0), (0 0 0 0), (0 1 0 0))", NULL, LW_TRUE, 1000);
1264  /* Negative weight won't converge */
1265  do_median_test("MULTIPOINT ZM ((0 -1 0 -1), (0 0 0 -1), (0 1 0 -1))", NULL, LW_FALSE, 1000);
1266  do_median_test("MULTIPOINT ZM ((0 -1 0 -1), (0 0 0 -1), (0 1 0 -1))", NULL, LW_TRUE, 1000);
1267 
1268  /* Bind convergence too tightly */
1269  do_median_test("MULTIPOINT ((0 0), (1 1), (0 1), (2 2))", "POINT(0.75 1.0)", LW_FALSE, 0);
1270  do_median_test("MULTIPOINT ((0 0), (1 1), (0 1), (2 2))", NULL, LW_TRUE, 1);
1271  /* Unsupported geometry type */
1272  do_median_test("POLYGON((1 0,0 1,1 2,2 1,1 0))", NULL, LW_TRUE, 1000);
1273  do_median_test("POLYGON((1 0,0 1,1 2,2 1,1 0))", NULL, LW_FALSE, 1000);
1274 
1275  /* Median point is included */
1276  do_median_test("MULTIPOINT ZM ("
1277  "(1480 0 200 100),"
1278  "(620 0 200 100),"
1279  "(1000 0 -200 100),"
1280  "(1000 0 -590 100),"
1281  "(1025 0 65 100),"
1282  "(1025 0 -65 100)"
1283  ")",
1284  "POINT (1025 0 -65)", LW_TRUE, 10000);
1285 
1286 #if 0
1287  /* Leads to invalid result (0 0 0) with 80bit (fmulp + faddp) precision. ok with 64 bit float ops */
1288  do_median_test("MULTIPOINT ZM ("
1289  "(0 0 20000 0.5),"
1290  "(0 0 59000 0.5),"
1291  "(0 -3000 -3472.22222222222262644208967685699462890625 1),"
1292  "(0 3000 3472.22222222222262644208967685699462890625 1),"
1293  "(0 0 -1644.736842105263121993630193173885345458984375 1),"
1294  "(0 0 1644.736842105263121993630193173885345458984375 1),"
1295  "(0 48000 -20000 1.3),"
1296  "(0 -48000 -20000 1.3)"
1297  ")",
1298  "POINT (0 0 0)", LW_TRUE, 10000);
1299 #endif
1300 
1301 #if 0
1302  /* Leads to invalid result (0 0 0) with 64bit (vfmadd231sd) precision. Ok with 80 bit float ops */
1303  do_median_test("MULTIPOINT ZM ("
1304  "(0 0 20000 0.5),"
1305  "(0 0 59000 0.5),"
1306  "(0 -3000 -3472.22222222222262644208967685699462890625 1),"
1307  "(0 3000 3472.22222222222262644208967685699462890625 1),"
1308  "(0 -0.00000000000028047739569477638384522295466033823196 -1644.736842105263121993630193173885345458984375 1),"
1309  "(0 0.00000000000028047739569477638384522295466033823196 1644.736842105263121993630193173885345458984375 1),"
1310  "(0 48000 -20000 1.3),"
1311  "(0 -48000 -20000 1.3)"
1312  ")",
1313  "POINT (0 0 0)", LW_TRUE, 10000);
1314 #endif
1315 }
static void do_median_test(char *input, char *expected, int fail_if_not_converged, int iter_count)
#define LW_FALSE
Definition: liblwgeom.h:76
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
Here is the call graph for this function:
Here is the caller graph for this function: