KD-Tree Implementation

General FreeBASIC programming questions.
Post Reply
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

KD-Tree Implementation

Post by Andrew Lindsay »

Hello,
Does anyone know of a basic KD-Tree algorithm for Freebasic that will allow me to find the nearest spatial point (nearest neighbour) from a dataset of tens of thousands of datapoints?

I want to find the nearest point on a path (given by a list of X,Y coordinates). I've seen an implementation of KD-Trees in Python, but I'd like to add the ability to do this in my program and not have to shell out or try to interface to python.

Any assistance would be appreciated.

Regards

Andrew
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: KD-Tree Implementation

Post by D.J.Peters »

You can use a quadtree also !

The quadtree can be found here: viewtopic.php?p=294656

Joshy
Last edited by D.J.Peters on Sep 16, 2022 7:30, edited 1 time in total.
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: KD-Tree Implementation

Post by D.J.Peters »

I added a circle shape for a query range and chnaged particle to a PathNode !
you can store in the quadtree any kind of nodes but a node must have x and y position at least.

The quadtree can be found here: viewtopic.php?p=294656

Joshy
Last edited by D.J.Peters on Sep 16, 2022 7:31, edited 2 times in total.
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

Re: KD-Tree Implementation

Post by Andrew Lindsay »

Thank you. I will examine the code and see how it works for me.
Your help is greatly appreciated!

Regards

Andrew
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

Re: KD-Tree Implementation

Post by Andrew Lindsay »

OK - So I have tried to implement my own data into the tree, but have not had a great deal of success.

Here is my Driver program (I copied the routines into a separate include file, which worked for your version.

I seem to load about 150 items into the tree, then everything crashes.

Code: Select all

#include "KDTree.bi"
#include "GetLinesInFile.bi"


dim as tCircle    cirRange
dim as tPathNode found(any)
dim as boolean bRedrawTree=true
dim as boolean bRedrawRange=false
dim as single minX, minY, maxX, maxY

' Load in the data for the Bayu Undan Pipeline to be placed into the
' KD-Tree structure.

dim as long lBayuData      ' Number of Entries for Bayu Undan KP Data
Dim as long lNGEPData      ' Number of Entried for Nearshore GEP KP Data
dim as long fBayuData      ' File handle for Bayu Undan Data File
dim as long fNGEPData      ' File handle for Nearshore GEP KP Data
dim as long i
dim as single Xpt, Ypt
Dim as single NGEPPath()
dim as single dRadii

Print "Reading in Files"
Print "BU Route"

fBayuData = Freefile
Open "BUKP_1m_Adjacent.csv" for input as #fBayuData
lBayuData = get_lines_in_file("BUKP_1m_Adjacent.csv")
Print "Total lines in BU Route - " + str$(lBayuData)
sleep 5
Print "Finding extent of data"
input #fBayuData, Xpt, Ypt

for i = 2 to lBayuData
    input #fBayuData, Xpt, Ypt
    if Xpt < minX then
        minX = Xpt
    end if
    if Xpt > maxX then
        maxX = Xpt
    end if
    if Ypt < minY then
        minY = Ypt
    end if
    if Ypt > maxY then
        maxY = Ypt
    end if
next

print "Min X - " + str$(minX)
print "Min Y - " + str$(minY)
print "Max X - " + str$(maxX)
print "Max y - " + str$(maxY)

close #fBayuData
sleep 5
Print "Creating Quadtree"

var tree = tQuadTree(1,tRectangle(tVector2f(minX,minY),tVector2f(maxX,maxY))) ' This appears to be where the data for the extents go???

Print "Quadtree created"

'Everything goes well up until here I think

sleep 5

Print "Loading Bayu Data into Quadtree"
sleep 5
Print "GO"
fBayuData = Freefile
Open "BUKP_1m_Adjacent.csv" for input as #fBayuData
for i = 1 to lBayuData
    Print ".";                                                                                                    ' It falls over here after about 100 iterations
    input #fBayuData, Xpt, Ypt
    tree.insert(tPathNode(Xpt, Ypt))
next

Print "Data loaded"
sleep 20
    
fNGEPData = freefile
Open "N1-06.xyz" for input as #fNGEPData
lNGEPData = get_lines_in_file("N1-06.xyz")

redim NGEPPath(lNGEPData,2)

for i = 1 to lNGEPData
    input #fNGEPData, Xpt, Ypt
    NGEPPath(i, 1) = Xpt
    NGEPPath(i, 2) = Ypt
next


Close #fBayuData
close #fNGEPData 

Erase found
dRadii = 25000
cirRange = tCircle(tVector2f(NGEPPath(1,1), NGEPPath(1,2)), dRadii)
tree.query(cirRange, found())
print str$(NGEPPath(1,1)), str$(NGEPPath(1,2)), str$(ubound(found)) + " Elements found"


while inkey()=""

wend
Any assistance with where I am going wrong, or not understanding the implementation would be greatly appreciated.

regards

Andrew
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

Re: KD-Tree Implementation

Post by Andrew Lindsay »

Here are parts of the sample files

BUKP_1m_Adjacent.csv

Code: Select all

598300.3853,8671122.309
598301.0832,8671121.592
598301.7811,8671120.876
598302.4789,8671120.16
598303.1768,8671119.444
598303.8747,8671118.728
598304.5726,8671118.011
598304.568,8671118.016
598305.2663,8671117.3
598305.9646,8671116.584
598306.6629,8671115.869
598307.3612,8671115.153
598308.0595,8671114.437
598308.7578,8671113.721
598309.4561,8671113.005
598310.1544,8671112.29
598310.8527,8671111.574
598311.551,8671110.858
598312.2493,8671110.142
598312.9476,8671109.426
598312.948,8671109.426
598313.6442,8671108.708
598314.3404,8671107.99
598315.0366,8671107.272
598315.7327,8671106.555
598316.4289,8671105.837
598317.1251,8671105.119
598317.8213,8671104.401
598318.5175,8671103.683
598319.2137,8671102.965
598319.9098,8671102.247
598320.606,8671101.53
598321.3022,8671100.812
598321.298,8671100.816
598321.9876,8671100.092
598322.6772,8671099.368
598323.3667,8671098.643
598324.0563,8671097.919
598324.7459,8671097.195
598325.4355,8671096.471
598326.125,8671095.747
598326.8146,8671095.022
598327.5042,8671094.298
598328.1938,8671093.574
598328.8834,8671092.85
598329.5729,8671092.125
598330.2625,8671091.401
598330.258,8671091.406
598330.9401,8671090.675
598331.6222,8671089.943
598332.3043,8671089.212
598332.9864,8671088.481
598333.6685,8671087.75
598334.3506,8671087.018
598335.0327,8671086.287
598335.7148,8671085.556
598336.397,8671084.825
598337.0791,8671084.093
598337.7612,8671083.362
598338.4433,8671082.631
598338.4479,8671082.626
598339.1274,8671081.892
598339.8069,8671081.159
598340.4864,8671080.425
598341.1659,8671079.691
598341.8454,8671078.958
598342.5248,8671078.224
598343.2043,8671077.49
598343.8838,8671076.757
598344.5633,8671076.023
598345.2428,8671075.289
598345.9223,8671074.555
598346.6018,8671073.822
598346.5979,8671073.826
598347.2788,8671073.094
598347.9596,8671072.361
598348.6405,8671071.629
598349.3214,8671070.896
598350.0022,8671070.164
598350.6831,8671069.432
598351.3639,8671068.699
598352.0448,8671067.967
598352.7257,8671067.234
598353.4065,8671066.502
598354.0874,8671065.769
598354.7683,8671065.037
598355.4491,8671064.305
598355.4479,8671064.306
598356.1278,8671063.573
598356.8078,8671062.839
598357.4877,8671062.106
598358.1676,8671061.373
598358.8476,8671060.64
598359.5275,8671059.906
598360.2074,8671059.173
598360.8874,8671058.44
598361.5673,8671057.707
598362.2473,8671056.973
598362.9272,8671056.24
598363.6071,8671055.507
598363.6078,8671055.506
598364.283,8671054.768
598364.9581,8671054.031
598365.6333,8671053.293
598366.3084,8671052.555
598366.9836,8671051.818
598367.6587,8671051.08
598368.3339,8671050.342
598369.0091,8671049.605
598369.6842,8671048.867
598370.3594,8671048.129
598371.0345,8671047.392
598371.7097,8671046.654
598371.7078,8671046.656
598372.379,8671045.915
598373.0503,8671045.174
598373.7215,8671044.432
598374.3928,8671043.691
598375.064,8671042.95
598375.7353,8671042.209
598376.4065,8671041.467
598376.4078,8671041.466
598377.0773,8671040.723
598377.7468,8671039.98
598378.4163,8671039.238
598379.0858,8671038.495
598379.7553,8671037.752
598380.4249,8671037.009
598380.4178,8671037.017
598381.0855,8671036.273
598381.7532,8671035.528
598382.421,8671034.784
598383.0887,8671034.039
598383.7564,8671033.295
598384.4241,8671032.551
598385.0918,8671031.806
598385.7596,8671031.062
598386.4273,8671030.317
598387.095,8671029.573
598387.7627,8671028.828
598388.4304,8671028.084
598388.4278,8671028.087
598389.0962,8671027.343
598389.7646,8671026.599
598390.433,8671025.856
598391.1014,8671025.112
598391.7698,8671024.368
598392.4382,8671023.624
598393.1067,8671022.88
598393.7751,8671022.137
598394.4435,8671021.393
598395.1119,8671020.649
598395.7803,8671019.905
598396.4487,8671019.161
598397.1171,8671018.418
598397.1177,8671018.417
598397.7876,8671017.675
598398.4576,8671016.932
598399.1275,8671016.19
598399.7974,8671015.447
598400.4674,8671014.705
598401.1373,8671013.962
598401.8072,8671013.22
598402.4771,8671012.478
598403.1471,8671011.735
598403.817,8671010.993
598404.4869,8671010.25
598405.1569,8671009.508
598405.1577,8671009.507
598405.8293,8671008.766
598406.501,8671008.025
598407.1726,8671007.284
598407.8443,8671006.543
598408.5159,8671005.803
598409.1875,8671005.062
598409.8592,8671004.321
598410.5308,8671003.58
598411.2024,8671002.839
598411.8741,8671002.098
598412.5457,8671001.357
598413.2174,8671000.616
598413.889,8670999.876
598413.8877,8670999.877
598414.5602,8670999.137
598415.2328,8670998.397
598415.9053,8670997.657
598416.5779,8670996.917
598417.2504,8670996.177
598417.923,8670995.437
598418.5955,8670994.697
598419.2681,8670993.957
598419.9406,8670993.216
598420.6131,8670992.476
598421.2857,8670991.736
598421.9582,8670990.996
598421.9576,8670990.997
598422.6262,8670990.253
598423.2948,8670989.51
598423.9634,8670988.766
598424.632,8670988.022
598425.3006,8670987.279
598425.9692,8670986.535
598426.6378,8670985.792
598427.3064,8670985.048
598427.975,8670984.304
598428.6436,8670983.561
598429.3122,8670982.817
598429.9808,8670982.073
598429.9776,8670982.077
598430.6392,8670981.327
598431.3007,8670980.577
598431.9623,8670979.827
598432.6239,8670979.077
598433.2854,8670978.328
598433.947,8670977.578
598434.6086,8670976.828
598435.2701,8670976.078
598435.9317,8670975.328
598436.5933,8670974.578
598437.2548,8670973.828
598437.9164,8670973.078
598437.9176,8670973.077
598438.5738,8670972.322
598439.23,8670971.568
598439.8862,8670970.813
598440.5424,8670970.059
598441.1986,8670969.304
598441.8548,8670968.549
598442.511,8670967.795
598443.1672,8670967.04
598443.8234,8670966.286
598444.4796,8670965.531
598445.1358,8670964.777
598445.792,8670964.022
598445.7876,8670964.027
598446.4385,8670963.268
598447.0893,8670962.509
598447.7402,8670961.749
598448.391,8670960.99
598449.0419,8670960.231
598449.6927,8670959.472
598450.3436,8670958.713
598450.9944,8670957.953
598451.6453,8670957.194
598452.2962,8670956.435
598452.947,8670955.676
598453.5979,8670954.917
598453.5975,8670954.917
598454.2458,8670954.156
598454.8941,8670953.394
598455.5425,8670952.633
598456.1908,8670951.872
598456.8391,8670951.11
598457.4874,8670950.349
598458.1357,8670949.587
598458.784,8670948.826
598459.4324,8670948.065
598460.0807,8670947.303
598460.729,8670946.542
598461.3773,8670945.781
598462.0256,8670945.019
598462.0275,8670945.017
598462.6743,8670944.254
598463.3211,8670943.492
598463.9679,8670942.729
598464.6147,8670941.966
598465.2615,8670941.204
598465.9083,8670940.441
598466.5551,8670939.678
598467.2019,8670938.916
598467.8487,8670938.153
598468.4955,8670937.39
598469.1423,8670936.628
598469.7891,8670935.865
598469.7875,8670935.867
598470.4347,8670935.105
598471.0819,8670934.342
598471.7291,8670933.58
598472.3764,8670932.818
598473.0236,8670932.055
598473.6708,8670931.293
598473.6675,8670931.297
598474.3157,8670930.536
598474.9639,8670929.774
598475.612,8670929.013
598476.2602,8670928.251
598476.9084,8670927.49
598477.5566,8670926.728
598477.5575,8670926.727
598478.2058,8670925.966
598478.8541,8670925.204
598479.5024,8670924.443
598480.1508,8670923.682
598480.7991,8670922.92
598481.4474,8670922.159
598482.0957,8670921.397
598482.744,8670920.636
598483.3923,8670919.875
598484.0406,8670919.113
598484.6889,8670918.352
N1-06.xyz

Code: Select all

598748.40000000,8670737.90000000,-53.61,0.000000
598748.99331126,8670737.09502687,-53.61,1.000000
598749.58662252,8670736.29005373,-53.60,2.000000
598750.17993378,8670735.48508059,-53.60,3.000000
598750.77324504,8670734.68010746,-53.60,4.000000
598751.36655630,8670733.87513432,-53.60,5.000000
598751.95986756,8670733.07016119,-53.61,6.000000
598752.55317882,8670732.26518805,-53.61,7.000000
598753.14649008,8670731.46021491,-53.61,8.000000
598753.73980134,8670730.65524178,-53.61,9.000000
598754.33311260,8670729.85026864,-53.60,10.000000
598754.92642386,8670729.04529551,-53.59,11.000000
598755.51973512,8670728.24032237,-53.57,12.000000
598756.11304638,8670727.43534924,-53.56,13.000000
598756.70635764,8670726.63037610,-53.56,14.000000
598757.29966890,8670725.82540297,-53.55,15.000000
598757.89298015,8670725.02042983,-53.53,16.000000
598758.48629141,8670724.21545669,-53.51,17.000000
598759.07960267,8670723.41048356,-53.51,18.000000
598759.67291393,8670722.60551042,-53.53,19.000000
598760.26622519,8670721.80053729,-53.53,20.000000
598760.85953645,8670720.99556415,-53.53,21.000000
598761.45284771,8670720.19059102,-53.53,22.000000
598762.04615897,8670719.38561788,-53.52,23.000000
598762.63947023,8670718.58064475,-53.50,24.000000
598763.23278149,8670717.77567161,-53.49,25.000000
598763.82609275,8670716.97069847,-53.48,26.000000
598764.41940401,8670716.16572534,-53.46,27.000000
598765.01271527,8670715.36075220,-53.46,28.000000
598765.60602653,8670714.55577907,-53.46,29.000000
598766.19933779,8670713.75080593,-53.46,30.000000
598766.79264905,8670712.94583279,-53.45,31.000000
598767.38596031,8670712.14085966,-53.44,32.000000
598767.97927157,8670711.33588652,-53.43,33.000000
598768.57258283,8670710.53091339,-53.43,34.000000
598769.16589409,8670709.72594025,-53.42,35.000000
598769.75920535,8670708.92096712,-53.41,36.000000
598770.35251661,8670708.11599398,-53.41,37.000000
598770.94582787,8670707.31102085,-53.42,38.000000
598771.53913913,8670706.50604771,-53.42,39.000000
598772.13245039,8670705.70107457,-53.41,40.000000
598772.72576165,8670704.89610144,-53.39,41.000000
598773.31907291,8670704.09112830,-53.39,42.000000
598773.91238417,8670703.28615517,-53.39,43.000000
598774.50569543,8670702.48118203,-53.38,44.000000
598775.09900669,8670701.67620890,-53.38,45.000000
598775.69231795,8670700.87123576,-53.38,46.000000
598776.28562921,8670700.06626263,-53.38,47.000000
598776.87894046,8670699.26128949,-53.37,48.000000
598777.47225172,8670698.45631635,-53.36,49.000000
598778.06556298,8670697.65134322,-53.35,50.000000
598778.65887424,8670696.84637008,-53.33,51.000000
598779.25218550,8670696.04139695,-53.33,52.000000
598779.84549676,8670695.23642381,-53.33,53.000000
598780.43880802,8670694.43145067,-53.33,54.000000
598781.03211928,8670693.62647754,-53.32,55.000000
598781.62543054,8670692.82150440,-53.31,56.000000
598782.21874180,8670692.01653127,-53.29,57.000000
598782.81205306,8670691.21155813,-53.29,58.000000
598783.40536432,8670690.40658500,-53.29,59.000000
598783.99867558,8670689.60161186,-53.29,60.000000
598784.59198684,8670688.79663873,-53.29,61.000000
598785.18529810,8670687.99166559,-53.28,62.000000
598785.77860936,8670687.18669245,-53.29,63.000000
598786.37192062,8670686.38171932,-53.30,64.000000
598786.96523188,8670685.57674618,-53.30,65.000000
598787.55854314,8670684.77177305,-53.29,66.000000
598788.15185440,8670683.96679991,-53.27,67.000000
598788.74516566,8670683.16182678,-53.27,68.000000
598789.33847692,8670682.35685364,-53.26,69.000000
598789.93178818,8670681.55188050,-53.26,70.000000
598790.52509944,8670680.74690737,-53.26,71.000000
598791.11841070,8670679.94193423,-53.27,72.000000
598791.71172196,8670679.13696110,-53.28,73.000000
598792.30503322,8670678.33198796,-53.27,74.000000
598792.89834448,8670677.52701483,-53.26,75.000000
598793.49165574,8670676.72204169,-53.26,76.000000
598794.08496700,8670675.91706855,-53.27,77.000000
598794.67827826,8670675.11209542,-53.26,78.000000
598795.27158952,8670674.30712228,-53.25,79.000000
598795.86490077,8670673.50214915,-53.26,80.000000
598796.45821203,8670672.69717601,-53.27,81.000000
598797.05152329,8670671.89220288,-53.28,82.000000
598797.64483455,8670671.08722974,-53.27,83.000000
598798.23814581,8670670.28225661,-53.26,84.000000
598798.83145707,8670669.47728347,-53.25,85.000000
598799.42476833,8670668.67231033,-53.25,86.000000
598800.01807959,8670667.86733720,-53.26,87.000000
598800.61139085,8670667.06236406,-53.27,88.000000
598801.20470211,8670666.25739093,-53.28,89.000000
598801.79801337,8670665.45241779,-53.29,90.000000
598802.39132463,8670664.64744466,-53.29,91.000000
598802.98463589,8670663.84247152,-53.30,92.000000
598803.57794715,8670663.03749838,-53.30,93.000000
598804.17125841,8670662.23252525,-53.29,94.000000
598804.76456967,8670661.42755211,-53.28,95.000000
598805.35788093,8670660.62257898,-53.27,96.000000
598805.95119219,8670659.81760584,-53.27,97.000000
598806.54450345,8670659.01263271,-53.27,98.000000
598807.13781471,8670658.20765957,-53.28,99.000000
598807.73112597,8670657.40268643,-53.28,100.000000
598808.32443723,8670656.59771330,-53.29,101.000000
598808.91774849,8670655.79274016,-53.29,102.000000
598809.51105975,8670654.98776703,-53.29,103.000000
598810.10437101,8670654.18279389,-53.28,104.000000
598810.69768227,8670653.37782076,-53.26,105.000000
598811.29099353,8670652.57284762,-53.26,106.000000
598811.88430479,8670651.76787448,-53.27,107.000000
598812.47761605,8670650.96290135,-53.28,108.000000
598813.07092731,8670650.15792821,-53.28,109.000000
598813.66423857,8670649.35295508,-53.28,110.000000
598814.25754983,8670648.54798194,-53.28,111.000000
598814.85086108,8670647.74300881,-53.27,112.000000
598815.44417234,8670646.93803567,-53.27,113.000000
598816.03748360,8670646.13306254,-53.26,114.000000
598816.63079486,8670645.32808940,-53.26,115.000000
598817.22410612,8670644.52311626,-53.26,116.000000
598817.81741738,8670643.71814313,-53.28,117.000000
598818.41072864,8670642.91316999,-53.29,118.000000
598819.00403990,8670642.10819686,-53.29,119.000000
598819.59735116,8670641.30322372,-53.29,120.000000
598820.19066242,8670640.49825059,-53.29,121.000000
598820.78397368,8670639.69327745,-53.29,122.000000
598821.37728494,8670638.88830431,-53.29,123.000000
598821.97059620,8670638.08333118,-53.28,124.000000
598822.56390746,8670637.27835804,-53.28,125.000000
598823.15721872,8670636.47338491,-53.27,126.000000
598823.75052998,8670635.66841177,-53.27,127.000000
598824.34384124,8670634.86343864,-53.27,128.000000
598824.93715250,8670634.05846550,-53.26,129.000000
598825.53046376,8670633.25349236,-53.26,130.000000
598826.12377502,8670632.44851923,-53.26,131.000000
598826.71708628,8670631.64354609,-53.26,132.000000
598827.31039754,8670630.83857296,-53.26,133.000000
598827.90370880,8670630.03359982,-53.27,134.000000
598828.49702006,8670629.22862669,-53.26,135.000000
598829.09033132,8670628.42365355,-53.26,136.000000
598829.68364258,8670627.61868042,-53.26,137.000000
598830.27695384,8670626.81370728,-53.26,138.000000
598830.87026510,8670626.00873414,-53.27,139.000000
598831.46357636,8670625.20376101,-53.28,140.000000
598832.05688762,8670624.39878787,-53.29,141.000000
598832.65019888,8670623.59381474,-53.28,142.000000
598833.24351013,8670622.78884160,-53.27,143.000000
598833.83682139,8670621.98386846,-53.26,144.000000
598834.43013265,8670621.17889533,-53.25,145.000000
598835.02344391,8670620.37392219,-53.26,146.000000
598835.61675517,8670619.56894906,-53.27,147.000000
598836.21006643,8670618.76397592,-53.27,148.000000
598836.80337769,8670617.95900279,-53.26,149.000000
598837.39668895,8670617.15402965,-53.26,150.000000
598837.99000021,8670616.34905652,-53.26,151.000000
598838.58331147,8670615.54408338,-53.27,152.000000
598839.17662273,8670614.73911024,-53.30,153.000000
598839.76993399,8670613.93413711,-53.31,154.000000
598840.36324525,8670613.12916397,-53.29,155.000000
598840.95655651,8670612.32419084,-53.29,156.000000
598841.54986777,8670611.51921770,-53.31,157.000000
598842.14317903,8670610.71424457,-53.33,158.000000
598842.73649029,8670609.90927143,-53.34,159.000000
598843.32980155,8670609.10429830,-53.31,160.000000
598843.92311281,8670608.29932516,-53.29,161.000000
598844.51642407,8670607.49435202,-53.31,162.000000
598845.10973533,8670606.68937889,-53.32,163.000000
598845.70304659,8670605.88440575,-53.32,164.000000
598846.29635785,8670605.07943262,-53.31,165.000000
598846.88966911,8670604.27445948,-53.32,166.000000
598847.48298037,8670603.46948634,-53.34,167.000000
598848.07629163,8670602.66451321,-53.32,168.000000
598848.66960289,8670601.85954008,-53.31,169.000000
598849.26291415,8670601.05456694,-53.31,170.000000
598849.85622541,8670600.24959380,-53.34,171.000000
598850.44953667,8670599.44462067,-53.35,172.000000
598851.04284793,8670598.63964753,-53.34,173.000000
598851.63615919,8670597.83467440,-53.33,174.000000
598852.22947044,8670597.02970126,-53.32,175.000000
598852.82278170,8670596.22472812,-53.32,176.000000
598853.41609296,8670595.41975499,-53.31,177.000000
598854.00940422,8670594.61478185,-53.33,178.000000
598854.60271548,8670593.80980872,-53.36,179.000000
598855.19602674,8670593.00483558,-53.34,180.000000
598855.78933800,8670592.19986245,-53.31,181.000000
598856.38264926,8670591.39488931,-53.31,182.000000
598856.97596052,8670590.58991618,-53.34,183.000000
598857.56927178,8670589.78494304,-53.36,184.000000
598858.16258304,8670588.97996990,-53.33,185.000000
598858.75589430,8670588.17499677,-53.30,186.000000
598859.34920556,8670587.37002363,-53.30,187.000000
598859.94251682,8670586.56505050,-53.32,188.000000
598860.53582808,8670585.76007736,-53.34,189.000000
598861.12913934,8670584.95510423,-53.35,190.000000
598861.72245060,8670584.15013109,-53.32,191.000000
598862.31576186,8670583.34515795,-53.32,192.000000
598862.90907312,8670582.54018482,-53.35,193.000000
598863.50238438,8670581.73521168,-53.37,194.000000
598864.09569564,8670580.93023855,-53.36,195.000000
598864.68900690,8670580.12526541,-53.34,196.000000
598865.28231816,8670579.32029228,-53.33,197.000000
598865.87562942,8670578.51531914,-53.31,198.000000
598866.46894068,8670577.71034600,-53.29,199.000000
598867.06225194,8670576.90537287,-53.29,200.000000
598867.65556320,8670576.10039973,-53.28,201.000000
598868.24887446,8670575.29542660,-53.26,202.000000
598868.84218572,8670574.49045346,-53.26,203.000000
598869.43549698,8670573.68548033,-53.28,204.000000
598870.02880824,8670572.88050719,-53.30,205.000000
598870.62211950,8670572.07553406,-53.28,206.000000
598871.21543075,8670571.27056092,-53.26,207.000000
598871.80874201,8670570.46558778,-53.26,208.000000
598872.40205327,8670569.66061465,-53.27,209.000000
598872.99536453,8670568.85564151,-53.29,210.000000
598873.58867579,8670568.05066838,-53.28,211.000000
598874.18198705,8670567.24569524,-53.26,212.000000
598874.77529831,8670566.44072211,-53.25,213.000000
598875.36860957,8670565.63574897,-53.24,214.000000
598875.96192083,8670564.83077583,-53.25,215.000000
598876.55523209,8670564.02580270,-53.26,216.000000
598877.14854335,8670563.22082956,-53.26,217.000000
598877.74185461,8670562.41585643,-53.26,218.000000
598878.33516587,8670561.61088329,-53.26,219.000000
598878.92847713,8670560.80591016,-53.26,220.000000
598879.52178839,8670560.00093702,-53.26,221.000000
598880.11509965,8670559.19596388,-53.25,222.000000
598880.70841091,8670558.39099075,-53.23,223.000000
598881.30172217,8670557.58601761,-53.21,224.000000
598881.89503343,8670556.78104448,-53.20,225.000000
598882.48834469,8670555.97607134,-53.20,226.000000
598883.08165595,8670555.17109821,-53.20,227.000000
598883.67496721,8670554.36612507,-53.20,228.000000
598884.26827847,8670553.56115193,-53.20,229.000000
598884.86158973,8670552.75617880,-53.20,230.000000
598885.45490099,8670551.95120566,-53.20,231.000000
598886.04821225,8670551.14623253,-53.19,232.000000
598886.64152351,8670550.34125939,-53.19,233.000000
598887.23483477,8670549.53628626,-53.19,234.000000
598887.82814603,8670548.73131312,-53.20,235.000000
598888.42145729,8670547.92633999,-53.20,236.000000
598889.01476855,8670547.12136685,-53.18,237.000000
598889.60807981,8670546.31639371,-53.17,238.000000
598890.20139106,8670545.51142058,-53.17,239.000000
598890.79470232,8670544.70644744,-53.16,240.000000
598891.38801358,8670543.90147431,-53.15,241.000000
598891.98132484,8670543.09650117,-53.15,242.000000
598892.57463610,8670542.29152804,-53.15,243.000000
598893.16794736,8670541.48655490,-53.16,244.000000
598893.76125862,8670540.68158176,-53.17,245.000000
598894.35456988,8670539.87660863,-53.18,246.000000
598894.94788114,8670539.07163549,-53.18,247.000000
598895.54119240,8670538.26666236,-53.17,248.000000
598896.13450366,8670537.46168922,-53.18,249.000000
598896.72781492,8670536.65671609,-53.17,250.000000
598897.32112618,8670535.85174295,-53.16,251.000000
598897.91443744,8670535.04676981,-53.15,252.000000
598898.50774870,8670534.24179668,-53.15,253.000000
598899.10105996,8670533.43682354,-53.14,254.000000
598899.69437122,8670532.63185041,-53.14,255.000000
598900.28768248,8670531.82687727,-53.15,256.000000
598900.88099374,8670531.02190414,-53.16,257.000000
598901.47430500,8670530.21693100,-53.16,258.000000
598902.06761626,8670529.41195787,-53.15,259.000000
598902.66092752,8670528.60698473,-53.14,260.000000
598903.25423878,8670527.80201159,-53.12,261.000000
598903.84755004,8670526.99703846,-53.09,262.000000
598904.44086130,8670526.19206532,-53.09,263.000000
598905.03417256,8670525.38709219,-53.10,264.000000
598905.62748382,8670524.58211905,-53.10,265.000000
598906.22079508,8670523.77714591,-53.10,266.000000
598906.81410634,8670522.97217278,-53.09,267.000000
598907.40741760,8670522.16719964,-53.09,268.000000
598908.00072886,8670521.36222651,-53.08,269.000000
598908.59404011,8670520.55725337,-53.07,270.000000
598909.18735137,8670519.75228024,-53.04,271.000000
598909.78066263,8670518.94730710,-53.04,272.000000
598910.37397389,8670518.14233397,-53.06,273.000000
598910.96728515,8670517.33736083,-53.07,274.000000
598911.56059641,8670516.53238769,-53.07,275.000000
598912.15390767,8670515.72741456,-53.07,276.000000
598912.74721893,8670514.92244142,-53.08,277.000000
598913.34053019,8670514.11746829,-53.09,278.000000
598913.93384145,8670513.31249515,-53.11,279.000000
598914.52715271,8670512.50752202,-53.11,280.000000
598915.12046397,8670511.70254888,-53.10,281.000000
598915.71377523,8670510.89757575,-53.10,282.000000
598916.30708649,8670510.09260261,-53.09,283.000000
598916.90039775,8670509.28762947,-53.08,284.000000
598917.49370901,8670508.48265634,-53.08,285.000000
598918.08702027,8670507.67768320,-53.07,286.000000
598918.68033153,8670506.87271007,-53.06,287.000000
598919.27364279,8670506.06773693,-53.06,288.000000
598919.86695405,8670505.26276379,-53.06,289.000000
598920.46026531,8670504.45779066,-53.05,290.000000
598921.05357657,8670503.65281752,-53.05,291.000000
598921.64688783,8670502.84784439,-53.06,292.000000
598922.24019909,8670502.04287125,-53.06,293.000000
598922.83351035,8670501.23789812,-53.05,294.000000
598923.42682161,8670500.43292498,-53.06,295.000000
598924.02013287,8670499.62795185,-53.06,296.000000
598924.61344413,8670498.82297871,-53.06,297.000000
598925.20675539,8670498.01800557,-53.06,298.000000
598925.80006665,8670497.21303244,-53.08,299.000000
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: KD-Tree Implementation

Post by D.J.Peters »

(sorry about my bad written english but I understand and read english very well)

I can try to help but I need to know your needs

the file BUKP_1m_Adjacent.csv has 2D coords (perfect for a QuadTree)
what is the meaning of this x,y coords and do you need to know the nearest coord if you select one of them ?

the file N1-06.xyz has 4 coords per row what is the meaning of them and what your needs ?

Joshy
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: KD-Tree Implementation

Post by dodicat »

Try this from first principles.
your original task
" allow me to find the nearest spatial point (nearest neighbour) from a dataset of ..."

Using your N1-06.xyz above, in the same folder as this test code:

Code: Select all


Type pt
      As Double x,y,z,k
End Type

#define irange(f,l) Int(Rnd*(((l)+1)-(f))+(f))
#define frange(first,last)  Rnd * (last - first) + first
#define sep(p1,p2) sqr((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y))
#macro StringToVector(p,z...)
#macro spl()
s+=","
For n As Long=0 To Len(s)-1
      t+=Chr(s[n])
      If s[n]=44 Then
            Redim Preserve db(Ubound(db)+1)
            db(Ubound(db))=Val(t)
            t=""
      End If
Next n
#endmacro
Scope
      Dim As String t
      Redim As Double db()
      Dim As Long count
      Var s=z
      spl()
      p=Type<pt>(db(0),db(1),db(2),db(3))
End Scope
#endmacro

Function map(a As Double,b As Double,x As Double,c As Double,d As Double) As Double
      Return ((d)-(c))*((x)-(a))/((b)-(a))+(c)
End Function


Function closest Overload(clr() As pt,v As Long) As Long
      Dim As Long res
      #define dist(p1,p2) Sqr((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y))' + (p1.z-p2.z)*(p1.z-p2.z)
      Dim As Double dt=1e20
      For n As Long=Lbound(clr) To Ubound(clr)
            If v=n Then Continue For
            Var distance=dist(clr(n),clr(v))
            If dt> distance Then dt = distance:res=n 'catch the smallest
      Next n
      Return res
End Function


Function closest Overload(clr() As pt,v As pt) As Ulong
      #define dist(p1,p2) Sqr((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y))
      Dim As Ulong res
      Dim As Double dt=1e20
      For n As Long=Lbound(clr) To Ubound(clr)
            Var distance=dist(clr(n),v)
            If dt> distance Then dt = distance:res=n 'catch the smallest
      Next n
      Return res
End Function


Function Split(StringToSplit As String,delim As String, array() As String) As Ulong 'by grindstone
	Dim As String text = StringToSplit
	Dim As Ulong b = 1, e = 1 
	Dim As Ulong x 
	Var L=Len(delim)
      Redim Array(1 to Len(StringToSplit)) 
	Do Until e = 0
		x += 1
		e = Instr(e + 1, text, delim) 
		array(x) = Mid(text, b, e - b) 
		b = e + L 
      Loop
	Redim Preserve array(1 to x)
	Return x 
End Function

Function loadfile(filename As String) As String
      Dim As Long  f=Freefile
      If Open (filename For Binary Access Read As #f)=0 Then
            Dim As String text
            If Lof(f) > 0 Then
                  text = String(Lof(f), 0)
                  Get #f, , text
            End If
            Close #f
            Return text
      Else
            Print filename;" not found":Sleep:End
      End If
End Function

Dim As Integer xres=20,yres=20
Randomize
Redim As pt a(1 To 10000000)
For n As Long=1 To Ubound(a)
      a(n)=Type(Rnd*20,Rnd*20,Rnd*20,Rnd*20)
Next n
Print "speed test, 10 million random points"
Var i=closest(a(),27)
Print "point(27)"
Print a(27).x,a(27).y,a(27).z,a(27).k
Print "closest to point(27)"
Print a(i).x,a(i).y,a(i).z,a(i).k
Print "which is point(";i;")"
Print "seperation",sep(a(27),a(i))
Print
Print "Get closest to point(10,10,. . .)"
i=closest(a(),Type<pt>(10,10))
Print a(i).x,a(i).y,a(i).z,a(i).k
Print "which is point(";i;")"
Print "seperation",sep(a(i),Type<pt>(10,10))

Print
Print "End of speed test, press a key to load vectors from file"
Sleep

Dim As String g
g=loadfile("N1-06.xyz")
Redim As String s()
split(g,Chr(10),s())

'change file to vectors
Dim As pt pts(1 To Ubound(s))
For n As Long=1 To Ubound(pts)
      StringToVector(pts(n),s(n))     
Next
For n As Long=1 To Ubound(pts)
      Print n,pts(n).x,pts(n).y,pts(n).z,pts(n).k
Next

'find area extremities of array
Dim As Double minx=1e10,maxx=-1e10,miny=1e10,maxy=-1e10
For n As Long =Lbound(pts) To Ubound(pts)
      If minx>pts(n).x Then minx=pts(n).x
      If maxx<pts(n).x Then maxx=pts(n).x
      If miny>pts(n).y Then miny=pts(n).y
      If maxy<pts(n).y Then maxy=pts(n).y
Next n

Print
For k As Long=1 To 5
      Var r=irange(Lbound(pts),Ubound(pts))
      i=closest(pts(),r)
      Print "point chosen array(";r;")"
      Print pts(r).x,pts(r).y,pts(r).z,pts(r).k
      Print
      Print "closest to the point = array(";i;")"
      Print pts(i).x,pts(i).y,pts(i).z,pts(i).k
      Print "seperation",sep(pts(r),pts(i))
      Dim As Double x=frange(minx,maxx)
      Dim As Double y=frange(miny,maxy)
      Print "random point "
      Print x,y
      Dim As pt p=Type<pt>(x,y)
      i=closest(pts(),p)
      Print "closest to the point"' = array(";i;")"
      Print pts(i).x,pts(i).y,pts(i).z,pts(i).k
      Print "which is point(";i;")"
      Print "seperation",sep(p,pts(i))
      
      Print"_________________________"
      
      
Next k
Var ratio= (maxx-minx)/(maxy-miny)
Print "done, press a key"

Sleep
Dim As Long w,h
Screenres 500,500/ratio
Windowtitle "Press any key or escape"
Screeninfo w,h
Dim As Double xpos,ypos
Do
      Var x=frange(minx,maxx)
      Var y=frange(miny,maxy)
      Dim As pt p=Type<pt>(x,y)
      For n As Long=Lbound(pts) To Ubound(pts)
            xpos=map(minx,maxx,pts(n).x,0,w)
            ypos=map(miny,maxy,pts(n).y,0,h)
            Pset(xpos,ypos)
      Next n
      xpos=map(minx,maxx,p.x,0,w)
      ypos=map(miny,maxy,p.y,0,h)
      Var tmpx=xpos,tmpy=ypos
      Circle(tmpx,tmpy),2,4,,,,f
      i=closest(pts(),p)
      xpos=map(minx,maxx,pts(i).x,0,w)
      ypos=map(miny,maxy,pts(i).y,0,h)
      Line(tmpx,tmpy)-(xpos,ypos)
      Locate 2,2
      Print "Distance from pipeline ";sep(pts(i),p)
      Sleep
      Cls
Loop Until Inkey=Chr(27)

 
Last edited by dodicat on Sep 16, 2022 18:20, edited 4 times in total.
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

Re: KD-Tree Implementation

Post by Andrew Lindsay »

D.J.Peters wrote: Sep 16, 2022 10:17 (sorry about my bad written english but I understand and read english very well)

I can try to help but I need to know your needs

the file BUKP_1m_Adjacent.csv has 2D coords (perfect for a QuadTree)
what is the meaning of this x,y coords and do you need to know the nearest coord if you select one of them ?

the file N1-06.xyz has 4 coords per row what is the meaning of them and what your needs ?

Joshy
Thanks. So, the BUKP is a route of a pipeline, using UTM coordinates, so yes, just X-Y

The N1-06.XYZ has the following datasets for each row.

X, Y, Z, KP

Where X,Y is UTM coordinates, Z is the water depth and distance from start in metres.

For an X,y coordinate from the N1-06 file, I want to find the nearest BUKP coordinate, and the distance to that point.

So to draw a comparison to the sample program you provided. The BUKP datapoints I want to load into the KD-Tree, then using X-Y coordinates from the N1-06 file, find the nearest coordinates and distance to the BUKP file. (Note that I have compiled the two files so the coordinates of both the BUKP file and N1-06 file are reasonably close).

Regards

Andrew
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: KD-Tree Implementation

Post by dodicat »

I have adjusted my code (from first principles) to suit.
I have taken the distance between the two points in question, i.e. a chosen set of co-ordinates from the array of points(from the file) to the nearest point in the array to this chosen point.
You can of course just choose co-ordinates and get the closest array point, the function is overloaded.
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

Re: KD-Tree Implementation

Post by Andrew Lindsay »

Thanks Dodi, I will look at your code also. Though I'm wanting to figure out why Joshy's code only works for his example and not mine.

I can actually get his code to compile and work if I make the following adjustment

Code: Select all

var tree = tQuadTree(2,tRectangle(tVector2f(minX,minY),tVector2f(maxX,maxY)))
'var tree = tQuadTree(1,tRectangle(tVector2f(0,0),tVector2f(maxX,maxY)))
I'm not sure why this works and I'd like to understand.

Regards
Andrew
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: KD-Tree Implementation

Post by D.J.Peters »

@Andrew Lindsay I worked on the quadtree the last 12 hours.
Looks like the new result are very stable now.
I removed everything unnecessary types (tVector2i, tVector2f, tCircle, tRectangle)
Most interesting for you I added functions to get the nearest node and it's distance to a point x,y inside a circle or rectangle.

Use only the latest stable implementation (I fixed a really hard to find bug) and try the posted examples also.
link is the same: QuadTree

TIP: Your posted coords are big numbers but the dimensions / region are small
for example if you read the coords from a file get the minX, maxX, minY, maxY and then create the tree
var w = maxX - minX
var h = maxY - minY
var tree = tQuadTree(5, minX,minY, w,h)

Now you can insert all your coords in the tree and do any distance queries

The trick are if you like to draw the tree or use the mouse to get the nearest nodes you must use the "Window()" command after ScreenRes() !
screenres anyWidth,anyHeight,32,2
screenset 1,0

window screen (minX, minY)-( maxX, maxY)

from this point all QuadTree drawing works as expected (all coords automatic scaled to the screen)
the only step you have to do is rescale the mouse coords to the tree coords but FreeBASIC does the job for you
var px = pmap(mouseX,2)
var py = pmap(mouseY,3)
bFoundNearest = tree.query(px,py,found,distance)
...

Let me know if you run in to trouble but take a look to the posted examples at first please.

Happy coding :-)

Joshy
Lost Zergling
Posts: 534
Joined: Dec 02, 2011 22:51
Location: France

Re: KD-Tree Implementation

Post by Lost Zergling »

I'm thinking of another option. It will not compete with the solutions of dodicat and DJ Peters, nevertheless, it may offers an alternative. By using LZLE, it must be possible to use the abscissas as keys and in the first column (of tags) the ordinates as values ​​in an L1 list. Then, using the 'copycat' property/method, we create a second (sorted) list which is an index on the ordinate column of the first list. Finding the nearest neighbors therefore becomes a matter of two nested loops: one on an interval of L2, yes a "Follow" and (optionnally) a loop on an interval of L1, Checking ordinates on L1 in a computed range.
In wich case third list storing results could merge duplicates.
This solution would have the advantage of being very flexible in terms of optimization (insertion of keys in whole numbers or chosen to 'calibrate' the traversal of the intervals by the loops, traversal of the second loop might be dynamic of the interval of the first , plus a relatively agnostic and dynamic solution to the size of numbers and dimensions), but probably very slow and resource intensive in comparison.
By indexing a tree list onto a tree list we then might obtain a quad tree feature equivalent.
Edited due to some confusion between algo logic optimization and distance computation.
Andrew Lindsay
Posts: 17
Joined: Jan 08, 2016 20:33

Re: KD-Tree Implementation

Post by Andrew Lindsay »

LZ - I'll be perfectly honest, and say that I only understood about half of those words, and not necessarily in that order.

Thanks for your thoughts. But your suggestions are well over my head.

Regards

Andrew
Lost Zergling
Posts: 534
Joined: Dec 02, 2011 22:51
Location: France

Re: KD-Tree Implementation

Post by Lost Zergling »

@Andrew. You're right. I should have thought the algo before posting. Indeed just drafts, perhaps some ideas, but they're not structured.
Sorry do not have time to really play with it or think seriously about it. Perhaps am I seeking useless complexity.
I should have been a thick less optimistic before posting my ideas.
Post Reply