A fail case

[mpadge]

The following data give an apparently wrong result:

x = {189, 189, 189, 190, 190, 190, 191, 191, 191, 191, 191, 192, 192, 192, 192, 193, 193, 193, 193, 193, 193, 194, 194, 194, 194, 194, 194, 195, 195, 195, 195, 195, 195, 195, 196, 196, 196, 196, 196, 196, 196, 197, 197, 197, 197, 197, 197, 197, 198, 198, 198, 198, 198, 198, 199, 199, 199, 199, 199, 199, 199, 200, 200, 200, 200, 200, 201, 201, 201, 201, 201, 202, 202, 202, 202, 203, 203, 203, 203, 204, 204, 204, 204, 205, 205, 205, 205, 206, 206, 206, 206, 207, 207, 207, 207, 208, 208, 208, 208, 209, 209, 209, 209, 210, 210, 210, 210, 211, 211, 211, 211, 211, 212, 212, 212, 212, 213, 213, 213, 213, 213, 214, 214, 214, 214, 214, 215, 215, 215, 215, 215, 215, 216, 216, 216, 216, 216, 217, 217, 217, 217, 218, 218, 218, 218, 218, 219, 219, 219, 219, 220, 220, 220, 221, 221, 221, 221, 222, 222, 222, 223, 223, 223, 223, 224, 224, 224, 224, 225, 225, 225, 225, 226, 226, 226, 226, 227, 227, 227, 228, 228, 228, 229, 229, 229, 230, 230, 231, 231, 231, 232, 232, 232, 233, 233, 233, 234, 234, 234, 235, 235, 235, 236, 236, 236, 237, 237, 237, 238, 238, 238, 239, 239, 239, 239, 240, 240, 240, 241, 241, 241, 242, 242, 242, 243, 243, 243, 244, 244, 245, 245, 245, 246, 246, 246, 247, 247, 248, 248, 248, 249, 249, 249, 250, 250, 251, 251, 251, 252, 252, 253, 253, 253, 254, 254, 254, 255, 255, 256, 256, 256, 257, 257, 257, 258, 258, 258, 259, 259, 259, 260, 260, 260, 261, 261, 261, 261, 262, 262, 262, 263, 263, 263, 264, 264, 265, 265, 265, 265, 266, 266, 266, 267, 267, 267, 268, 268, 268, 268, 269, 269, 269, 269, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 273, 273, 273, 274, 274, 274, 274, 275, 275, 275, 276, 276, 276, 276, 277, 277, 277, 278, 278, 278, 278, 279, 279, 279, 279, 280, 280, 280, 281, 281, 281, 281, 282, 282, 282, 283, 283, 283, 284, 284, 284, 285, 285, 285, 286, 286, 286, 287, 287, 287, 288, 288, 288, 288, 289, 289, 289, 290, 290, 290, 291, 291, 291, 292, 292, 292, 293, 293, 293, 294, 294, 294, 295, 295, 295, 296, 296, 296, 297, 297, 297, 297, 298, 298, 298, 299, 299, 299, 299, 300, 300, 300, 301, 301, 302, 302, 302, 303, 303, 303, 304, 304, 304, 305, 305, 305, 305, 305, 305, 306, 306, 306, 306, 306, 306, 306, 307, 307, 307, 307, 307, 307, 307, 308, 308, 308, 308, 308, 308, 308, 309, 309, 309, 309, 309, 309, 309, 309, 310, 310, 310, 310, 310, 310, 310, 310, 311, 311, 311, 311, 311, 311, 311, 311, 312, 312, 312, 312, 312, 313, 313, 313, 313, 313, 313, 314, 314, 314, 314, 314, 315, 315, 315, 315, 315, 315, 315, 316, 316, 316, 316, 316, 317, 317, 317, 317, 317, 317, 318, 318, 318, 318, 318, 319, 319, 319, 319, 319, 320, 320, 320, 320, 320, 320, 321, 321, 321, 321, 322, 322, 322, 322, 322, 323, 323, 323, 323, 324, 324, 324, 324, 325, 325, 325, 325, 325, 326, 326, 326, 326, 326, 327, 327, 327, 327, 327, 328, 328, 328, 328, 328, 329, 329, 329, 329, 329, 330, 330, 330, 330, 330, 331, 331, 331, 331, 331, 332, 332, 332, 332, 332, 333, 333, 333, 333, 333, 334, 334, 334, 334, 334, 335, 335, 335, 335, 335, 336, 336, 336, 336, 336, 336, 337, 337, 337, 337, 337, 338, 338, 338, 338, 338, 339, 339, 339, 339, 340, 340, 340, 340, 341, 341, 341, 341, 342, 342, 342, 342, 342, 343, 343, 343, 343, 344, 344, 344, 344, 345, 345, 345, 345, 346, 346, 346, 346, 347, 347, 347, 347, 348, 348, 348, 348, 349, 349, 349, 349, 350, 350, 350, 351, 351, 351, 351, 351, 352, 352, 352, 352, 353, 353, 353, 353, 354, 354, 354, 354, 355, 355, 355, 355, 355, 356, 356, 356, 356, 357, 357, 357, 357, 358, 358, 358, 358, 359, 359, 359, 359, 359, 360, 360, 360, 360, 361, 361, 361, 361, 361, 362, 362, 362, 362, 363, 363, 363, 363, 363, 364, 364, 364, 364, 365, 365, 365, 365, 365, 366, 366, 366, 366, 367, 367, 367, 367, 368, 368, 368, 368, 369, 369, 369, 369, 369, 370, 370, 370, 370, 371, 371, 371, 371, 372, 372, 372, 372, 373, 373, 373, 373, 374, 374, 374, 374, 374, 375, 375, 375, 376, 376, 376, 376, 376, 377, 377, 377, 377, 378, 378, 378, 378, 379, 379, 379, 379, 380, 380, 380, 380, 380, 381, 381, 381, 381, 382, 382, 382, 382, 382, 383, 383, 383, 383, 384, 384, 384, 384, 384, 385, 385, 385, 385, 386, 386, 386, 386, 386, 387, 387, 387, 387, 388, 388, 388, 388, 389, 389, 389, 389, 390, 390, 390, 390, 391, 391, 391, 391, 392, 392, 392, 393, 393, 393, 393, 394, 394, 394, 394, 395, 395, 395, 395, 396, 396, 396, 396, 397, 397, 397, 397, 398, 398, 398, 398, 398, 399, 399, 399, 399, 399, 400, 400, 400, 400, 400, 401, 401, 401, 401, 401, 402, 402, 402, 402, 402, 403, 403, 403, 403, 404, 404, 404, 404, 404, 405, 405, 405, 405, 406, 406, 406, 406, 406, 407, 407, 407, 407, 408, 408, 408, 408, 408, 409, 409, 409, 409, 409, 410, 410, 410, 410, 410, 411, 411, 411, 411, 411, 412, 412, 412, 412, 413, 413, 413, 413, 413, 414, 414, 414, 414, 414, 415, 415, 415, 415, 416, 416, 416, 416, 417, 417, 417, 417, 417, 417, 418, 418, 418, 418, 418, 419, 419, 419, 419, 419, 420, 420, 420, 420, 420, 421, 421, 421, 421, 421, 421, 422, 422, 422, 422, 422, 422, 422, 423, 423, 423, 423, 423, 423, 424, 424, 424, 424, 424, 425, 425, 425, 425, 425, 426, 426, 426, 426, 427, 427, 427, 427, 427}

y = {1124, 1129, 1134, 1126, 1131, 1136, 1126, 1131, 1136, 1142, 1147, 1127, 1133, 1138, 1144, 1124, 1129, 1135, 1140, 1145, 1151, 1125, 1130, 1136, 1141, 1146, 1152, 1125, 1131, 1136, 1141, 1147, 1152, 1157, 1128, 1134, 1139, 1145, 1150, 1155, 1161, 1128, 1137, 1142, 1147, 1153, 1158, 1163, 1126, 1142, 1147, 1153, 1158, 1163, 1125, 1130, 1147, 1152, 1157, 1163, 1168, 1128, 1152, 1157, 1162, 1168, 1128, 1152, 1157, 1162, 1168, 1128, 1155, 1161, 1166, 1126, 1156, 1161, 1166, 1125, 1130, 1164, 1169, 1126, 1132, 1166, 1171, 1126, 1131, 1165, 1171, 1126, 1131, 1166, 1171, 1127, 1132, 1166, 1172, 1127, 1132, 1167, 1172, 1126, 1132, 1169, 1174, 1126, 1131, 1170, 1175, 1180, 1130, 1170, 1175, 1181, 1129, 1134, 1173, 1178, 1184, 1128, 1133, 1173, 1178, 1183, 1127, 1132, 1172, 1178, 1183, 1188, 1131, 1172, 1178, 1183, 1188, 1131, 1174, 1179, 1185, 1127, 1132, 1178, 1183, 1188, 1131, 1136, 1183, 1188, 1130, 1136, 1185, 1128, 1134, 1184, 1189, 1132, 1182, 1187, 1129, 1134, 1184, 1189, 1129, 1135, 1184, 1189, 1130, 1135, 1184, 1190, 1132, 1137, 1187, 1192, 1135, 1185, 1190, 1134, 1185, 1190, 1134, 1186, 1191, 1135, 1187, 1132, 1137, 1188, 1133, 1138, 1189, 1134, 1185, 1190, 1135, 1186, 1191, 1136, 1186, 1192, 1136, 1185, 1191, 1135, 1140, 1189, 1134, 1139, 1188, 1133, 1138, 1186, 1191, 1137, 1184, 1189, 1135, 1140, 1187, 1135, 1140, 1187, 1136, 1183, 1188, 1137, 1184, 1134, 1139, 1186, 1136, 1183, 1188, 1138, 1185, 1134, 1140, 1187, 1137, 1184, 1189, 1139, 1186, 1135, 1183, 1188, 1137, 1185, 1134, 1139, 1187, 1136, 1184, 1189, 1138, 1186, 1135, 1140, 1188, 1136, 1183, 1189, 1135, 1140, 1188, 1134, 1140, 1187, 1133, 1139, 1186, 1132, 1138, 1185, 1190, 1137, 1184, 1189, 1135, 1184, 1190, 1135, 1185, 1130, 1135, 1184, 1190, 1134, 1183, 1189, 1132, 1137, 1187, 1129, 1135, 1183, 1188, 1131, 1136, 1184, 1190, 1132, 1137, 1186, 1128, 1134, 1183, 1188, 1132, 1182, 1187, 1129, 1134, 1184, 1127, 1132, 1182, 1188, 1129, 1180, 1185, 1126, 1132, 1182, 1187, 1128, 1133, 1183, 1124, 1129, 1134, 1185, 1125, 1131, 1181, 1186, 1126, 1131, 1182, 1123, 1128, 1180, 1186, 1126, 1179, 1185, 1124, 1179, 1184, 1123, 1129, 1183, 1122, 1128, 1182, 1121, 1127, 1181, 1121, 1126, 1180, 1120, 1125, 1179, 1185, 1124, 1178, 1184, 1123, 1177, 1183, 1123, 1178, 1183, 1123, 1179, 1184, 1123, 1179, 1184, 1122, 1177, 1182, 1120, 1126, 1180, 1119, 1124, 1178, 1117, 1122, 1176, 1182, 1119, 1124, 1179, 1116, 1121, 1177, 1182, 1121, 1177, 1182, 1121, 1178, 1116, 1122, 1178, 1116, 1122, 1179, 1118, 1174, 1179, 1101, 1106, 1111, 1117, 1122, 1178, 1097, 1102, 1107, 1113, 1118, 1175, 1180, 1097, 1103, 1108, 1113, 1119, 1174, 1179, 1097, 1102, 1107, 1113, 1118, 1174, 1179, 1092, 1098, 1103, 1108, 1114, 1119, 1174, 1180, 1091, 1096, 1102, 1107, 1113, 1118, 1173, 1179, 1089, 1094, 1100, 1105, 1110, 1116, 1121, 1176, 1085, 1090, 1096, 1101, 1174, 1082, 1087, 1092, 1098, 1172, 1177, 1083, 1088, 1094, 1099, 1174, 1077, 1082, 1087, 1093, 1098, 1173, 1179, 1079, 1084, 1090, 1095, 1175, 1074, 1079, 1085, 1090, 1171, 1177, 1075, 1080, 1086, 1169, 1174, 1072, 1077, 1083, 1088, 1172, 1070, 1075, 1080, 1086, 1171, 1176, 1073, 1078, 1083, 1172, 1068, 1074, 1079, 1169, 1175, 1070, 1075, 1169, 1174, 1068, 1074, 1168, 1174, 1065, 1070, 1076, 1168, 1173, 1063, 1068, 1073, 1167, 1172, 1061, 1067, 1072, 1167, 1172, 1060, 1066, 1071, 1166, 1172, 1060, 1065, 1071, 1166, 1171, 1060, 1065, 1071, 1167, 1172, 1056, 1061, 1066, 1163, 1168, 1052, 1058, 1063, 1162, 1168, 1051, 1057, 1062, 1162, 1168, 1051, 1056, 1062, 1162, 1167, 1051, 1056, 1061, 1161, 1166, 1049, 1054, 1059, 1158, 1163, 1168, 1050, 1055, 1060, 1161, 1166, 1049, 1054, 1157, 1163, 1168, 1051, 1057, 1160, 1165, 1049, 1054, 1158, 1164, 1048, 1054, 1155, 1160, 1045, 1050, 1152, 1158, 1163, 1048, 1151, 1156, 1161, 1047, 1052, 1154, 1159, 1044, 1050, 1152, 1157, 1044, 1049, 1151, 1157, 1044, 1049, 1151, 1156, 1043, 1048, 1149, 1155, 1044, 1049, 1150, 1155, 1045, 1146, 1151, 1042, 1047, 1145, 1151, 1156, 1046, 1144, 1149, 1154, 1045, 1050, 1146, 1152, 1043, 1049, 1145, 1150, 1043, 1048, 1142, 1148, 1153, 1046, 1140, 1145, 1150, 1045, 1138, 1144, 1149, 1044, 1137, 1142, 1147, 1043, 1048, 1137, 1143, 1148, 1044, 1133, 1138, 1144, 1041, 1046, 1134, 1139, 1144, 1043, 1048, 1134, 1140, 1040, 1046, 1131, 1136, 1142, 1043, 1128, 1134, 1139, 1040, 1046, 1130, 1135, 1141, 1042, 1127, 1132, 1137, 1041, 1046, 1129, 1135, 1039, 1044, 1127, 1132, 1037, 1043, 1124, 1130, 1135, 1040, 1122, 1127, 1132, 1039, 1044, 1124, 1130, 1037, 1042, 1123, 1128, 1036, 1041, 1121, 1127, 1035, 1040, 1120, 1125, 1130, 1040, 1119, 1124, 1034, 1039, 1118, 1123, 1128, 1039, 1115, 1120, 1126, 1037, 1042, 1117, 1122, 1035, 1040, 1115, 1121, 1033, 1038, 1114, 1119, 1124, 1037, 1109, 1114, 1120, 1033, 1039, 1111, 1116, 1122, 1035, 1040, 1112, 1117, 1031, 1037, 1107, 1112, 1118, 1033, 1039, 1109, 1114, 1031, 1036, 1105, 1111, 1116, 1033, 1103, 1108, 1113, 1031, 1036, 1105, 1110, 1030, 1036, 1104, 1109, 1031, 1036, 1104, 1110, 1032, 1100, 1105, 1110, 1034, 1100, 1105, 1030, 1035, 1099, 1105, 1030, 1035, 1099, 1104, 1031, 1036, 1098, 1104, 1031, 1036, 1097, 1102, 1030, 1036, 1095, 1100, 1030, 1035, 1091, 1096, 1101, 1032, 1037, 1089, 1095, 1100, 1031, 1037, 1088, 1093, 1099, 1032, 1038, 1088, 1093, 1099, 1033, 1038, 1089, 1094, 1099, 1035, 1040, 1087, 1093, 1031, 1037, 1083, 1088, 1094, 1035, 1040, 1084, 1089, 1032, 1038, 1080, 1086, 1091, 1036, 1042, 1081, 1086, 1033, 1038, 1076, 1082, 1087, 1033, 1039, 1076, 1082, 1087, 1036, 1042, 1077, 1082, 1088, 1038, 1043, 1077, 1082, 1087, 1039, 1044, 1076, 1081, 1035, 1041, 1046, 1075, 1081, 1038, 1043, 1072, 1077, 1082, 1041, 1046, 1074, 1079, 1039, 1045, 1071, 1076, 1039, 1044, 1062, 1068, 1073, 1079, 1043, 1061, 1067, 1072, 1077, 1044, 1060, 1065, 1071, 1076, 1043, 1060, 1065, 1071, 1076, 1044, 1050, 1055, 1060, 1066, 1071, 1040, 1046, 1051, 1056, 1062, 1067, 1073, 1044, 1049, 1055, 1060, 1065, 1071, 1043, 1048, 1054, 1059, 1064, 1045, 1050, 1056, 1061, 1066, 1047, 1052, 1057, 1063, 1043, 1048, 1054, 1059, 1065}

The result then looks like this:

The V8 version gives the expected result like this:

You should be able to copy-paste those data into a main fn to reproduce ... Any help would be greatly appreciated. Thanks again!

[sadaszewski]

Looks interesting. I will look into this in a few days. Might be a good opportunity to add unit tests and verify each function against V8 version. Were parameters the same in both versions? How was the convex hull computed for the CPP version?

[mpadge]

They were both concavity = 1, lengthThreshold = 0. The CPP hull was computer with my own wrapper (as part of an R package buried here, where this line ensures that the above values are stored as <double>).

[sadaszewski]

Using the Python wrapper on your data I obtain different results. Not saying they are perfect / the same as V8 but they look more reasonable. Would be good to agree on common testing code.

I used the following:

from concaveman import concaveman2d
from scipy.spatial import ConvexHull
import numpy as np

x = [189, 189, 189, 190, 190, 190, 191, 191, 191, 191, 191, 192, 192, 192, 192, 193, 193, 193, 193, 193, 193, 194, 194, 194, 194, 194, 194, 195, 195, 195, 195, 195,$

y = [1124, 1129, 1134, 1126, 1131, 1136, 1126, 1131, 1136, 1142, 1147, 1127, 1133, 1138, 1144, 1124, 1129, 1135, 1140, 1145, 1151, 1125, 1130, 1136, 1141, 1146, 115$

pts = list(zip(x, y))
pts = np.array(pts)
h = ConvexHull(pts)

cc = concaveman2d(pts, h.vertices, 1, 10)

concaveman2d(pts, h.vertices, 1, 10)

concaveman2d(pts, h.vertices, 1, 0)

[mpadge]

Thanks for investigating, and i can confirm that the python code works:

That was enough to prompt me to dig deeper into my wrapper and work out that it was my mistake anyway. Result now looks like this:

Sorry about that, and thanks again!

[sadaszewski]

Nice. Thank you for this and for your kind words about my work. I still think it would be good to comprehensively test V8 vs. CPP. I will remember this when I have some free time.

[mpadge]

Hi @sadaszewski just wanted to let you know that i've done the benchmarking here, with very clear results as expected. Your C++ implementation is 6-7 times faster than the .js version. Feel free to use/abuse that result and associated code as you like. Nice work!

[sadaszewski]

Hi @mpadge, many thanks - your input is much appreciated. C++ is definitely the winner here, so easy to call from anywhere and so fast. When C++20 modules land I foretell a great Renaissance for C++ :)