[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[task #15713] Make quad structure to make unique hashes of 4 objects

From: Mohammad Akhlaghi
Subject: [task #15713] Make quad structure to make unique hashes of 4 objects
Date: Sat, 18 Jul 2020 19:56:01 -0400 (EDT)
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Firefox/78.0

Follow-up Comment #22, task #15713 (project gnuastro):

I had a fast look and I am impressed by the comments! Very nice! I really
enjoyed reading them to get a good feeling without having to invest a lot of
mental energy in understanding the coding. This is how a good code should look
like! Good work!

Just one tiny point: since the kd-tree functions will later go into Gnuastro's
library, prefix them with 'gal_kdtree_'. For example 'gal_kdtree_swap' or
'gal_kdtree_find_median' and so on. The same for the structure and macro. 

Now that you are designing the kd-tree library and have the cute little
example 'main' function to test with, let's do the next step too:
reading/writing the kd-tree from/to a file (similar to the index files of This will allow the users to optionally do the matching in
two phases: 

1) Run it once on the raw reference catalogs to generate the kd-trees and
store them in files. For example this can be done in day time (before the
observation run on known areas of the sky during the night). This step will
also be the most time-consuming  (which is OK).

2) Run it a second time on catalogs derived from each image and load the
kd-tree to calculate the image's WCS. This step will be much faster and can be
done during the observation (without delaying that night's other

To do this, we will also need to store the kd-tree in a file. But following
the Unix philosophy, we shouldn't define an obscure binary format, let's just
do it as a simple binary FITS table that is also fast to read. 

Each row in the table can be one node. The first N columns for the N values
along each dimension of each "point" (with type "double"). Then we can have
two extra columns for the indexs of the "left" and "right" nodes (with type
"size_t"). When writing the table, we can convert pointers to indexs and
vice-versa when reading the table. 

You can you add the kd-tree I/O as two high-level functions (maybe called
'gal_kdtree_write' and 'gal_kdtree_read'). I'd be happy to talk over a
share-screen to help with reading/writing FITS tables.

In fact here is a fast brainstorm: how about removing the structure over-all
and just using these columns instead? This will save a lot of time in
reading/writing/debugging. For example, any "swap"ing of the nodes can be done
by changing the "left" and "right" index columns of each row. Also, accessing
any of the right-left nodes through their index is not much slower than using
pointers (the compiler will convert them to a pointer anyway). 

What do you think?


Reply to this item at:


  Message sent via Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]