I have a grid of 150000 x 150000 points, and I have a list of points corresponding the x,y coordinates of a shape that make up a slightly imperfect hexagon or pentagon. I'm trying to figure out a more efficient manner to find the vertices (corners) of the polygon.
I could average all data points in the set to find my center, which would be O(n) for processing, and then compare that center against all data points in the set to find those with the furthest distance, also O(n), so O(2n) as far as total complexity, but I'm hoping to find something faster.
Thanks in advance!
Data points, as an example:
399917,105258
399935,105263
399953,105269
399972,105275
399990,105281
400008,105287
400062,105288
400116,105288
400170,105289
400225,105289
400279,105290
400333,105290
400369,105285
400405,105279
400441,105274
400477,105268
400513,105263
400548,105257
400530,105251
400512,105245
400494,105239
400475,105233
400457,105228
400439,105222
400385,105221
400331,105221
400277,105220
400222,105220
400168,105219
400114,105219
400078,105224
400042,105230
400006,105235
399971,105241
399935,105246
399899,105252