Align 2d points to evenly spaced grid

Question

I have xy point data.

# large realistic data, column z is to denote that additional columns are present.
k <- data.frame(x=c(9021,9169,9173,9176,9313,9317,9320,9324,9461,9468,9472,9475,9479,9602,9605,9609,9612,9616,9619,9623,9627,9746,9750,9753,9757,9760,9764,9767,9771,9774,9890,9894,9897,9901,9904,9908,9911,9915,9919,9922,10034,10038,10042,10045,10049,10052,10056,10059,10063,10066,10070,10179,10182,10186,10189,10193,10196,10200,10203,10207,10211,10214,10218,10323,10326,10330,10334,10337,10341,10344,10348,10351,10355,10358,10362,10365,10471,10474,10478,10481,10485,10488,10492,10495,10499,10503,10506,10510,10615,10618,10622,10626,10629,10633,10636,10640,10643,10647,10650,10654,10657,10759,10763,10766,10770,10773,10777,10780,10784,10787,10791,10795,10798,10802,10907,10910,10914,10918,10921,10925,10928,10932,10935,10939,10942,10946,10949,11051,11055,11058,11062,11069,11072,11076,11079,11083,11087,11090,11094,11199,11202,11206,11217,11220,11224,11227,11231,11234,11238,11241,11343,11347,11350,11364,11368,11371,11375,11379,11382,11386,11487,11491,11494,11498,11509,11512,11516,11519,11523,11526,11530,11533,11635,11639,11642,11656,11660,11663,11667,11671,11674,11678,11681,11779,11783,11786,11801,11804,11808,11811,11815,11818,11822,11825,11924,11927,11931,11934,11948,11952,11955,11959,11963,11966,11970,11973,12071,12075,12078,12096,12100,12107,12110,12114,12117,12121,12216,12219,12223,12240,12244,12251,12255,12258,12262,12265,12363,12367,12370,12388,12399,12402,12406,12409,12413,12511,12515,12543,12547,12550,12554,12557,12561,12655,12662,12687,12691,12694,12698,12701,12705,12800,12803,12807,12831,12835,12839,12842,12846,12849,12853,12947,12951,12954,12979,12983,12986,12990,12993,12997,13092,13095,13099,13123,13127,13131,13134,13138,13141,13145,13239,13246,13268,13271,13275,13278,13282,13285,13289,13383,13387,13391,13415,13419,13423,13426,13430,13433,13437,13531,13560,13563,13567,13570,13574,13577,13581,13679,13683,13707,13711,13715,13718,13722,13725,13729,13827,13837,13852,13855,13859,13862,13866,13869,13873,13971,13982,13985,13999,14003,14007,14010,14014,14017,14021,14119,14126,14129,14133,14144,14147,14151,14154,14158,14161,14165,14263,14274,14277,14281,14291,14295,14298,14302,14306,14309,14313,14411,14418,14421,14425,14436,14439,14443,14446,14450,14453,14457,14555,14559,14566,14569,14573,14583,14587,14590,14594,14598,14601,14605,14710,14713,14717,14721,14728,14731,14735,14738,14742,14745,14749,14851,14858,14861,14865,14875,14879,14882,14886,14890,14893,14995,15002,15005,15009,15013,15020,15023,15027,15030,15034,15037,15041,15146,15150,15153,15157,15167,15171,15174,15178,15182,15185,15287,15294,15297,15301,15305,15312,15315,15319,15322,15326,15329,15333,15438,15442,15445,15449,15459,15463,15466,15470,15474,15477,15586,15589,15593,15597,15607,15611,15614,15618,15621,15625,15730,15734,15737,15741,15755,15758,15762,15766,15769,15878,15881,15885,15889,15903,15906,15910,15913,16022,16026,16029,16033,16036,16047,16050,16054,16058,16170,16173,16177,16181,16195,16198,16202,16205,16314,16318,16321,16325,16328,16342,16346,16350,16462,16465,16469,16472,16476,16490,16494,16606,16610,16613,16617,16638,16761,16764,16768,16912,17053,17056),
y=c(10116,10369,10877,11385,10114,10622,11130,11638,10367,11383,11891,12399,12907,9603,10112,10620,11128,11636,12144,12652,13160,9348,9856,10365,10873,11381,11889,12397,12905,13413,9093,9601,10109,10618,11126,11634,12142,12650,13158,13666,8838,9346,9854,10363,10871,11379,11887,12395,12903,13411,13919,8583,9091,9599,10107,10616,11124,11632,12140,12648,13156,13664,14172,8328,8836,9344,9852,10360,10869,11377,11885,12393,12901,13409,13917,14425,8581,9089,9597,10105,10613,11122,11630,12138,12646,13154,13662,14170,8326,8834,9342,9850,10358,10866,11375,11883,12391,12899,13407,13915,14423,8071,8579,9087,9595,10103,10611,11120,11628,12136,12644,13152,13660,14168,8324,8832,9340,9848,10356,10864,11373,11881,12389,12897,13405,13913,14421,8069,8577,9085,9593,10609,11117,11626,12134,12642,13150,13658,14166,8322,8830,9338,10862,11370,11879,12387,12895,13403,13911,14419,8067,8575,9083,11115,11624,12132,12640,13148,13656,14164,7812,8320,8828,9336,10860,11368,11877,12385,12893,13401,13909,14417,8065,8573,9081,11113,11621,12130,12638,13146,13654,14162,14670,7810,8318,8826,10858,11366,11874,12383,12891,13399,13907,14415,7555,8063,8571,9079,11111,11619,12127,12636,13144,13652,14160,14668,7808,8316,8824,11364,11872,12889,13397,13905,14413,14921,7553,8061,8569,11109,11617,12634,13142,13650,14158,14666,7806,8314,8822,11362,12887,13395,13903,14411,14919,8059,8567,12631,13140,13648,14156,14664,15172,7804,8820,12376,12885,13393,13901,14409,14917,7549,8057,8565,12121,12629,13138,13646,14154,14662,15170,7802,8310,8818,12374,12882,13391,13899,14407,14915,7547,8055,8563,12119,12627,13135,13644,14152,14660,15168,7800,8816,11864,12372,12880,13389,13897,14405,14913,7545,8053,8561,12117,12625,13133,13642,14150,14658,15166,7798,11862,12370,12878,13386,13895,14403,14911,8051,8559,12115,12623,13131,13639,14148,14656,15164,8304,9828,11860,12368,12876,13384,13892,14401,14909,8049,9573,10081,12113,12621,13129,13637,14146,14654,15162,8302,9318,9826,10334,11858,12366,12874,13382,13890,14399,14907,8047,9571,10079,10587,12111,12619,13127,13635,14143,14652,15160,8300,9316,9824,10332,11856,12364,12872,13380,13888,14396,14905,8045,8553,9569,10077,10585,12109,12617,13125,13633,14141,14650,15158,9314,9822,10330,10838,11854,12362,12870,13378,13886,14394,14903,8551,9567,10075,10583,12107,12615,13123,13631,14139,14647,8296,9312,9820,10328,10836,11852,12360,12868,13376,13884,14392,14900,9057,9565,10073,10581,12105,12613,13121,13629,14137,14645,8294,9310,9818,10326,10834,11850,12358,12866,13374,13882,14390,14898,9055,9563,10071,10579,12103,12611,13119,13627,14135,14643,9308,9816,10324,10832,12356,12864,13372,13880,14388,14896,9053,9561,10069,10577,12609,13117,13625,14133,14641,9306,9814,10322,10830,12862,13370,13878,14386,9051,9559,10067,10575,11083,12607,13115,13623,14131,9304,9812,10320,10828,12860,13368,13876,14384,9048,9557,10065,10573,11081,13113,13621,14129,9302,9810,10318,10826,11334,13366,13874,9046,9555,10063,10571,13619,10316,10824,11332,11077,10314,10822),
z=c(5170,3008,1278,3242,5303,3679,2346,2655,4014,3603,3074,8430,9030,9502,2904,2467,2540,4220,5209,5686,9509,12682,10859,2708,3843,4992,4239,7609,10008,11969,12834,10559,1613,3191,4072,3914,8710,9445,5194,11957,21317,9474,7220,3710,4580,5123,3294,8464,6401,4138,19993,20984,12033,9990,2856,5579,3465,7889,6407,5790,4217,7578,17867,15412,15180,7723,5171,5832,3776,3689,6727,3598,4180,5351,16039,20809,12121,14731,6162,10189,1916,3156,7031,4372,1196,5696,5855,19267,11821,12288,10140,6854,10257,4306,5541,4854,5452,4247,5914,9236,23438,15789,10598,8034,9032,7758,5454,8681,7067,5193,4914,3568,6971,19288,9750,10302,9430,5333,8817,10530,4308,4173,4378,5032,3196,10084,16835,13116,7522,7207,5115,10380,12771,5116,4196,2987,4056,8674,20284,10203,7871,8755,11816,9129,3925,4214,4251,3140,13405,26802,6124,5273,8359,12302,5346,3920,4855,7416,6944,14029,7972,6290,7753,7538,9343,5075,5597,4402,6228,9310,14786,11591,5140,9413,11127,12700,11603,7466,7325,9621,11085,10823,28765,3563,6606,9421,8153,13936,7908,7282,8518,10073,16704,13871,5733,4766,8509,9413,10921,4912,3367,9681,9806,9769,11716,16866,3635,7158,5140,8095,3360,10925,14422,9381,15579,32535,4700,3312,15846,9336,4547,9944,8044,16929,10509,19533,4338,11157,11408,5009,6998,10292,11602,15677,24772,15183,13616,5552,5700,8596,9686,12366,23290,7019,14600,7008,4787,8252,10094,10676,20111,4719,9446,15883,5059,5449,7181,7762,9456,12285,28779,9313,10371,13650,5287,8459,10359,10117,13263,15087,9902,10469,18459,8689,7333,11289,8941,9429,14278,27701,10151,9397,6925,7864,7101,5507,6816,9051,12135,9666,18304,11104,8587,12261,7561,5910,8131,8948,21402,12427,10563,9396,10317,10225,8015,7312,13515,14264,9607,7532,12427,10637,6444,8304,8787,25400,12302,14248,14277,8809,7790,10035,9915,7428,13377,10008,16307,9475,11867,17056,11031,8974,5415,8423,15429,12546,5972,12416,7770,12123,15289,17328,14201,8160,6064,13348,9620,14855,15120,4775,10668,13791,14122,10864,7966,10618,6437,7653,12269,13586,16718,18406,17622,15056,18267,8667,10747,18998,6372,2969,20017,18149,7620,14801,17323,14046,14606,9554,10127,4944,19180,20933,22142,7925,16383,15703,14864,16675,13253,12308,8101,2556,23235,19556,11919,18936,18906,19018,14236,14166,15887,3931,25848,16728,19696,5233,12545,13745,16962,21135,23452,12711,7225,9180,29045,18858,10602,12216,14497,19155,20060,14481,13903,3071,29928,18618,14688,4095,9797,11025,18327,19918,21721,14146,11624,19284,12045,19807,17008,8054,15264,25969,26441,22019,19465,24911,17517,18072,13534,8367,19256,23282,20279,18468,7153,20950,20857,14065,21344,12236,23933,21274,20006,19900,27264,23469,21167,11525,17526,18528,22247,21405,20576,26138,20584,15763,17693,10297,23039,29677,25818,21771,23685,20641,17438,15394,31967,27674,13915,17105,13809,17793,18349,13920,21056,11275,22746,7457,13039,16672,14722,5307,18416,17722,3695,225,7651,9407,10565,2566,2458,3029,2105,1623,2271))

The points are roughly on a grid.

library(ggplot2)
ggplot(k,aes(x,y))+
  geom_point()+
  coord_fixed()+
  theme_bw()

I want to force them into a perfect grid with a fixed gap (for example 100 or any user defined value) along the x and y axis. I also want to change x and y axis numbers to run consecutively from 1 to n. No points must be lost or gained.

Manually estimated that grid rows and columns are spaced roughly 146 apart.

ggplot(k,aes(x,y))+
  geom_point()+
  geom_hline(yintercept=seq(from=min(k$y),to=max(k$y),by=146),alpha=0.6)+
  geom_vline(xintercept=seq(from=min(k$x),to=max(k$x),by=146),alpha=0.6)+
  coord_fixed()+
  theme_bw()

Answer 1

If the points are already almost evenly spaced, my approach to the solution would be:

1. find the optimal grid spacing on which the points are lying
2. quantize points into the optimal grid by rounding to integer multiples of spacing
3. transform the integer coordinates into another arbitrary grid

First x and y components are transformed via tabulate in order to obtain signals that represent the presence of a point against their coordinates.

Then, a function of cos is minimized to find the optimal distance between points on both x and y coordinates.

attach(k)

X <- tabulate(1 + x - min(x)) > 0
Y <- tabulate(1 + y - min(y)) > 0

fn <- function(z, h) {
  -sum(cos((2 * pi * seq_along(z) - 1)/h) * z)
}

space <- 2:1000

tstX <- Vectorize(function(h) fn(X, h))(space)
tstY <- Vectorize(function(h) fn(Y, h))(space)

data.frame(xgrid = tstX, ygrid = tstY, x = space) |>
  pivot_longer(names_to = "grd", cols = matches("grid")) |>
  ggplot(aes( x = x, y = value)) +
  geom_line(aes(color = grd))

Optimal solutions are given by:

xgrid <- space[which.min(tstX)]
ygrid <- space[which.min(tstY)]

xgrid
#> [1] 146

ygrid
#> [1] 254

The following compares original points vs points rounded off to their optimal grid:

data.frame(xt = min(x) + xgrid * round((x - min(x) + 1)/xgrid),
           yt = min(y) + ygrid * round((y - min(y) + 1)/ygrid),
           x, y) |>
  ggplot() +
  geom_point(aes(xt, yt), color = "red")  +
  geom_point(aes(x,y), color = "black")

Then, the original dataframe is aligned with the grid and scaled to unitary coordinates.

k |>
  mutate(x = round((x - min(x))/xgrid),
         y = round((y - min(y))/ygrid)) |>
  head()

#>  x  y    z
#>1 0 10 5170
#>2 1 11 3008
#>3 1 13 1278
#>4 1 15 3242
#>5 2 10 5303
#>6 2 12 3679

Finally, you can alter the spacing of points by multiplying by a constant (e.g. 100).

# constant x and y spacing
gap <- 100
k |>
  mutate(x = round((x - min(x))/xgrid),
         y = round((y - min(y))/ygrid)) |>
  mutate(x = x * gap, y = y * gap) |>
  head()

#>     x    y    z
#> 1   0 1000 5170
#> 2 100 1100 3008
#> 3 100 1300 1278
#> 4 100 1500 3242
#> 5 200 1000 5303
#> 6 200 1200 3679

To maintain aspect ratio, the last step is updated as such:

# variable x and y spacing
r <- ygrid/xgrid
gap_x <- 100
gap_y <- gap_x*r

k |>
  mutate(x = round((x - min(x))/xgrid),
         y = round((y - min(y))/ygrid)) |>
  mutate(x = x * gap_x, y = y * gap_y) |>
  head()