20inline bool isFlagSet(uint32_t dbFlags, uint32_t flag) {
21 return (dbFlags & flag) != 0;
66 std::vector<int32_t> kVector(numBins+1);
67 decimal binWidth = (max - min) / numBins;
72 for (int32_t i = 0; i < (int32_t)values.size(); i++) {
74 assert(values[i] >= values[i-1]);
76 assert(values[i] >= min);
77 assert(values[i] <= max);
78 long thisBin = (long)ceil((values[i] - min) / binWidth);
80 assert(thisBin <= numBins);
82 for (
long bin = lastBin; bin < thisBin; bin++) {
87 for (
long bin = lastBin; bin <= numBins; bin++) {
88 kVector[bin] = values.size();
92 int32_t lastBinVal = -1;
93 for (
const int32_t &bin : kVector) {
94 assert(bin >= lastBinVal);
105 for (
const int32_t &bin : kVector) {
120 binWidth = (max - min) / numBins;
131 assert(maxQueryDistance > minQueryDistance);
132 if (maxQueryDistance >= max) {
133 maxQueryDistance = max -
DECIMAL(0.00001);
135 if (minQueryDistance <= min) {
136 minQueryDistance = min +
DECIMAL(0.00001);
138 if (minQueryDistance > max || maxQueryDistance < min) {
142 long lowerBin = BinFor(minQueryDistance);
143 long upperBin = BinFor(maxQueryDistance);
144 assert(upperBin >= lowerBin);
145 assert(upperBin <= numBins);
148 int lowerIndex = bins[lowerBin-1];
149 if (lowerIndex >= numValues) {
155 *upperIndex = bins[upperBin];
160long KVectorIndex::BinFor(
decimal query)
const {
161 long result = (long)ceil((query - min) / binWidth);
163 assert(result <= numBins);
177 std::vector<KVectorPair> result;
178 for (int16_t i = 0; i < (int16_t)catalog.size(); i++) {
179 for (int16_t k = i+1; k < (int16_t)catalog.size(); k++) {
188 result.push_back(pair);
200 std::vector<int32_t> kVector(numBins+1);
205 std::vector<decimal> distances;
208 distances.push_back(pair.distance);
223 int numPatternStarsPerFov) {
231 std::vector<uint16_t> patternStarInds{0};
233 for (
size_t i = 1; i < catalog.size(); i++) {
234 const Vec3& vec = catalog[i].spatial;
239 int numPatternStarsInFov = 0;
240 for (uint16_t j : patternStarInds) {
242 if (angle < starMinSepRad) {
246 if (angle < maxFovRad / 2 && ++numPatternStarsInFov >= numPatternStarsPerFov) {
253 patternStarInds.push_back(i);
256 return patternStarInds;
278 return catalogIndices_[tetraCatalogInd];
282 std::vector<TetraPattern> res;
288 if (tableRow[0] == 0 && tableRow[1] == 0) {
291 res.push_back(tableRow);
306 return num < low ? low : num > high ? high : num;
315 decimal minQueryDistance,
decimal maxQueryDistance,
const int16_t **end)
const {
319 long upperIndex = -1;
320 long lowerIndex = index.QueryLiberal(minQueryDistance, maxQueryDistance, &upperIndex);
321 *end = &pairs[upperIndex * 2];
322 return &pairs[lowerIndex * 2];
326 decimal minQueryDistance,
decimal maxQueryDistance,
const int16_t **end)
const {
337 long liberalUpperIndex;
338 long liberalLowerIndex = index.QueryLiberal(minQueryDistance, maxQueryDistance, &liberalUpperIndex);
342 while (liberalLowerIndex < liberalUpperIndex
343 && catalog[pairs[liberalLowerIndex*2]].spatial * catalog[pairs[liberalLowerIndex*2+1]].spatial >= maxQueryCos
345 { liberalLowerIndex++; }
348 while (liberalLowerIndex < liberalUpperIndex
350 && catalog[pairs[(liberalUpperIndex-1)*2]].spatial * catalog[pairs[(liberalUpperIndex-1)*2+1]].spatial <= minQueryCos
352 { liberalUpperIndex--; }
354 *end = &pairs[liberalUpperIndex * 2];
355 return &pairs[liberalLowerIndex * 2];
360 return index.NumValues();
365 std::vector<decimal> result;
366 for (
int i = 0; i <
NumPairs(); i++) {
367 if (pairs[i*2] == star || pairs[i*2+1] == star) {
368 result.push_back(
AngleUnit(catalog[pairs[i*2]].spatial, catalog[pairs[i*2+1]].spatial));
377 const std::vector<uint16_t>& catalogPatternStarInds,
378 int numEdgeRatioBins) {
382 const size_t numPatternStars = catalogPatternStarInds.size();
385 auto spatial = [&](
size_t tetraInd) ->
const Vec3& {
386 return catalog[catalogPatternStarInds[tetraInd]].spatial;
391 std::vector<bool> available(numPatternStars,
true);
393 std::vector<TetraPattern> patterns;
395 for (
size_t firstStarInd = 0; firstStarInd < numPatternStars; firstStarInd++) {
396 available[firstStarInd] =
false;
398 const Vec3& v = spatial(firstStarInd);
401 std::vector<uint16_t> nearbyStars;
402 for (
size_t starId = 0; starId < numPatternStars; starId++) {
403 if (!available[starId])
continue;
404 if (v * spatial(starId) > cosMaxFov) {
405 nearbyStars.push_back(starId);
409 while (combos.
next()) {
410 const std::vector<int>& idx = combos.
indices();
414 nearbyStars[idx[2]]};
418 [&](
int i) ->
const Vec3& {
return spatial(patt[i]); },
422 patterns.push_back(patt);
427 std::cerr <<
"Tetra found " << patterns.size() <<
" patterns" << std::endl;
429 size_t patternTableSize = 2 * patterns.size() + 1;
430 std::vector<TetraPattern> patternTable(patternTableSize);
435 std::vector<int> binnedEdgeRatios;
436 for (
decimal edgeRatio : edgeRatios) {
437 binnedEdgeRatios.push_back(
int(edgeRatio * numEdgeRatioBins));
441 TetraFindPatternIndex(binnedEdgeRatios.data(), binnedEdgeRatios.size(), numEdgeRatioBins, patternTableSize);
442 for (
size_t probeStep = 0; probeStep < patternTableSize; probeStep++) {
443 size_t index = (patternInd + probeStep * probeStep) % patternTableSize;
444 if (patternTable[index][0] == 0 && patternTable[index][1] == 0) {
445 patternTable[index] = patt;
459 for (uint16_t ind : catalogPatternStarInds) {
488 assert(magicValue != 0);
491 if (curMagicValue == 0) {
497 #ifdef LOST_FLOAT_MODE
499 std::cerr <<
"LOST was compiled in float mode. This database was serialized in double mode and is incompatible." << std::endl;
504 std::cerr <<
"LOST was compiled in double mode. This database was serialized in float mode and is incompatible." << std::endl;
510 assert(dbLength > 0);
513 if (curMagicValue == magicValue) {
514 return curSubDatabasePointer;
529 std::copy(multiDbEntry.bytes.cbegin(), multiDbEntry.bytes.cend(), std::back_inserter(ser->
buffer));
const std::vector< int > & indices() const
A data structure enabling constant-time range queries into fixed numerical data.
KVectorIndex(DeserializeContext *des)
Construct from serialized buffer.
long QueryLiberal(decimal minQueryDistance, decimal maxQueryDistance, long *upperIndex) const
Finds all the entries in the given range, and possibly a few just outside the range on the ends.
const unsigned char * SubDatabasePointer(int32_t magicValue) const
MultiDatabase memory layout:
long NumPairs() const
Exact number of stored pairs.
std::vector< decimal > StarDistances(int16_t star, const Catalog &) const
Return the distances from the given star to each star it's paired with in the database (for debugging...
PairDistanceKVectorDatabase(DeserializeContext *des)
Create the database from a serialized buffer.
static const int32_t kMagicValue
Magic value to use when storing inside a MultiDatabase.
const int16_t * FindPairsExact(const Catalog &, decimal min, decimal max, const int16_t **end) const
const int16_t * FindPairsLiberal(decimal min, decimal max, const int16_t **end) const
Return at least all the star pairs whose inter-star distance is between min and max.
std::vector< unsigned char > buffer
uint16_t CatalogIndex(int tetraCatalogInd) const
TetraPattern GetPattern(size_t index) const
std::vector< TetraPattern > GetPatternMatches(size_t index) const
TetraDatabase(DeserializeContext *des)
static const int32_t kMagicValue
Magic value to use when storing inside a MultiDatabase.
uint64_t PatternTableSize() const
Three dimensional vector with decimaling point components.
#define MULTI_DB_FLOAT_FLAG
Stores "inner angles" between star triples.
void SerializeKVectorIndex(SerializeContext *ser, const std::vector< decimal > &values, decimal min, decimal max, long numBins)
K-vector index layout.
bool AllPairsWithinFov(int numStars, SpatialAccessor spatial, decimal cosMaxFov)
void SerializePadding(SerializeContext *ser)
size_t TetraFindPatternIndex(const int *patternEdgeRatios, size_t numRatios, int numEdgeRatioBins, size_t tableSize)
decimal AngleUnit(const Vec3 &vec1, const Vec3 &vec2)
Calculate the inner angle, in radians, between two /unit/ vectors.
decimal DegToRad(decimal deg)
std::vector< MultiDatabaseEntry > MultiDatabaseDescriptor
const T * DeserializeArray(DeserializeContext *des, long arrLength)
return an array of items as a pointer. Will point into the buffer (mmap style).
bool CompareKVectorPairs(const KVectorPair &p1, const KVectorPair &p2)
decimal Angle(const Vec3 &vec1, const Vec3 &vec2)
Calculate the inner angle, in radians, between two vectors.
void SerializeTetraDatabase(SerializeContext *ser, const Catalog &catalog, decimal maxFovDeg, const std::vector< uint16_t > &catalogPatternStarInds, int numEdgeRatioBins)
std::vector< decimal > TetraEdgeRatios(int numStars, SpatialAccessor spatial)
std::vector< KVectorPair > CatalogToPairDistances(const Catalog &catalog, decimal minDistance, decimal maxDistance)
pair K-vector database layout.
T DeserializePrimitive(DeserializeContext *des)
void SerializePairDistanceKVector(SerializeContext *ser, const Catalog &catalog, decimal minDistance, decimal maxDistance, long numBins)
Serialize a pair-distance KVector into buffer.
bool isFlagSet(uint32_t dbFlags, uint32_t flag)
void SerializePrimitive(SerializeContext *ser, const T &val)
std::vector< uint16_t > TetraPreprocessCatalog(const Catalog &catalog, const decimal maxFovDeg, int numPatternStarsPerFov)
std::array< uint16_t, TetraConstants::numPatternStars > TetraPattern
void DeserializePadding(DeserializeContext *des)
Move the cursor forward past any padding that would appear before a value of type T.
void SerializeMultiDatabase(SerializeContext *ser, const MultiDatabaseDescriptor &dbs, uint32_t flags)
decimal Clamp(decimal num, decimal low, decimal high)
Return the value in the range [low,high] which is closest to num.
std::vector< CatalogStar > Catalog
static constexpr int numPatternStars