LOST 0.0.1
LOST: Open-source Star Tracker
Loading...
Searching...
No Matches
star-id.cpp
Go to the documentation of this file.
1#include "star-id.hpp"
2
3#include <assert.h>
4#include <math.h>
5#include <stdlib.h>
6
7#include <algorithm>
8#include <cstdio>
9#include <iostream>
10#include <limits>
11#include <numeric>
12#include <set>
13#include <unordered_map>
14#include <utility>
15#include <vector>
16
18#include "attitude-utils.hpp"
19#include "databases.hpp"
20#include "star-id-private.hpp"
21#include "star-utils.hpp"
22
23namespace lost {
24
25// C(4,2) - 1 = 5 edge ratios per pattern
26static constexpr int kNumEdgeRatios =
28using HashCode = std::array<int, kNumEdgeRatios>;
29
30// Generate all candidate hash codes for the given edge ratios.
31// For each ratio, compute a range of bins that fall within searchRange, then
32// enumerate every combination across all ratios (Cartesian product). Each
33// combination is sorted before insertion so that order-equivalent codes are deduped.
34static std::set<HashCode> GenerateCandidateHashCodes(const std::vector<decimal>& edgeRatios,
35 decimal searchRange,
36 int numBins) {
37 // For each edge ratio, compute the range of bins it could fall into
38 std::array<std::pair<int, int>, kNumEdgeRatios> binRanges;
39 size_t totalCombinations = 1;
40 for (int i = 0; i < kNumEdgeRatios; i++) {
41 int lo = std::max(0, int((edgeRatios[i] - searchRange) * numBins));
42 int hi = std::min(numBins, int((edgeRatios[i] + searchRange) * numBins) + 1);
43 binRanges[i] = {lo, hi};
44 totalCombinations *= (hi - lo);
45 }
46
47 // Enumerate all combinations
48 std::set<HashCode> hashCodes;
49 HashCode currentBins;
50 for (int i = 0; i < kNumEdgeRatios; i++)
51 currentBins[i] = binRanges[i].first;
52
53 for (size_t iter = 0; iter < totalCombinations; iter++) {
54 // Sort before inserting so order-equivalent codes are deduped
55 HashCode sortedBins = currentBins;
56 std::sort(sortedBins.begin(), sortedBins.end());
57 hashCodes.insert(sortedBins);
58
59 for (int binDim = kNumEdgeRatios - 1; binDim >= 0; binDim--) {
60 currentBins[binDim]++;
61 if (currentBins[binDim] < binRanges[binDim].second) break;
62 currentBins[binDim] = binRanges[binDim].first;
63 }
64 }
65 return hashCodes;
66}
67
68// Sort indices by distance of each vector from the centroid of all vectors.
69static std::vector<int> SortByCentroidRadius(const std::vector<int>& indices,
70 const std::vector<Vec3>& vecs) {
71 Vec3 centroid{0, 0, 0};
72 for (const Vec3& v : vecs)
73 centroid = centroid + v;
74 centroid = centroid * (DECIMAL(1.0) / vecs.size());
75
76 std::vector<int> order(indices.size());
77 std::iota(order.begin(), order.end(), 0);
78 std::sort(order.begin(), order.end(), [&](int a, int b) {
79 return (vecs[a] - centroid).MagnitudeSq() < (vecs[b] - centroid).MagnitudeSq();
80 });
81
82 std::vector<int> result;
83 for (int i : order) {
84 result.push_back(indices[i]);
85 }
86
87 return result;
88}
89
90// Pair observed centroids to catalog stars by sorting both sets by distance from centroid.
91static StarIdentifiers PairByCentroidRadius(const std::vector<int>& centroidIndices,
92 const std::vector<Vec3>& observedStarVecs,
93 const std::vector<int>& catalogInds,
94 const std::vector<Vec3>& catalogStarVecs) {
95 std::vector<int> sortedCentroids = SortByCentroidRadius(centroidIndices, observedStarVecs);
96 std::vector<int> sortedCatalog = SortByCentroidRadius(catalogInds, catalogStarVecs);
97
98 StarIdentifiers result;
99 for (int i = 0; i < (int)sortedCentroids.size(); i++) {
100 result.push_back(StarIdentifier(sortedCentroids[i], sortedCatalog[i]));
101 }
102 return result;
103}
104
105// Try all n! ways to pair observed stars with catalog stars. For each pairing, compute an
106// attitude via TRIAD, then measure how well that attitude maps each observed star onto its
107// paired catalog star. We let residual = sum of angular errors, then return the pairing with
108// the lowest residual
109static StarIdentifiers PairByTriadPermutation(const std::vector<int>& centroidIndices,
110 const std::vector<Vec3>& observedStarVecs,
111 const std::vector<int>& catalogInds,
112 const std::vector<Vec3>& catalogStarVecs,
113 const Stars& stars,
114 const Catalog& catalog,
115 const Camera& camera) {
116 const size_t n = observedStarVecs.size();
117 std::vector<int> perm(n);
118 for (size_t i = 0; i < n; i++)
119 perm[i] = i;
120
121 decimal bestResidual = std::numeric_limits<decimal>::max();
122 std::vector<int> bestPerm = perm;
123
124 TriadAlgorithm estimator;
125
126 do {
127 // Assume observed star i corresponds to catalog star perm[i]
128 StarIdentifiers ids;
129 for (size_t i = 0; i < n; i++) {
130 ids.push_back(StarIdentifier(centroidIndices[i], catalogInds[perm[i]]));
131 }
132
133 // Compute attitude from this pairing
134 Attitude att = estimator.Go(camera, stars, catalog, ids);
135 if (!att.IsKnown()) continue;
136
137 // Measure total angular error: rotate each observed star by the attitude
138 // and compare to where the catalog star actually is
139 Quaternion q = att.GetQuaternion().Conjugate();
140 decimal residual = 0;
141 for (size_t i = 0; i < n; i++) {
142 Vec3 rotated = q.Rotate(observedStarVecs[i]);
143 Vec3 expectedVec = catalogStarVecs[perm[i]].Normalize();
144 decimal dot = rotated * expectedVec;
145 dot = std::max(DECIMAL(-1.0), std::min(DECIMAL(1.0), dot));
146 residual += DECIMAL_ACOS(dot);
147 }
148
149 if (residual < bestResidual) {
150 bestResidual = residual;
151 bestPerm = perm;
152 }
153 } while (std::next_permutation(perm.begin(), perm.end()));
154
155 StarIdentifiers result;
156 for (size_t i = 0; i < n; i++) {
157 result.push_back(StarIdentifier(centroidIndices[i], catalogInds[bestPerm[i]]));
158 }
159 return result;
160}
161
162StarIdentifiers TetraStarIdAlgorithm::Go(const unsigned char* database,
163 const Stars& stars,
164 const Catalog& catalog,
165 const Camera& camera) const {
166 MultiDatabase multiDatabase(database);
167 const unsigned char* databaseBuffer =
169 if (databaseBuffer == nullptr) {
170 std::cerr << "Could not get to Tetra database" << std::endl;
171 return {};
172 }
173 DeserializeContext des(databaseBuffer);
174 TetraDatabase tetraDatabase(&des);
175
176 const size_t patternTableSize = tetraDatabase.PatternTableSize();
177 const decimal maxFov = tetraDatabase.MaxFov();
178 const decimal cosMaxFov = DECIMAL_COS(DegToRad(maxFov));
179 const int numEdgeRatioBins = tetraDatabase.NumEdgeRatioBins();
180
181 std::vector<int> centroidIndices(stars.size());
182 std::iota(centroidIndices.begin(), centroidIndices.end(), 0);
183
184 // Sort centroided stars by brightness, high to low. Larger is brighter
185 std::sort(centroidIndices.begin(), centroidIndices.end(), [&stars](int a, int b) {
186 return stars[a].magnitude > stars[b].magnitude;
187 });
188
189 CombinationIterator combos(TetraConstants::numPatternStars, centroidIndices.size());
190
191 while (combos.next()) {
192 const std::vector<int>& comboIndices = combos.indices();
193
194 std::vector<int> selectedCentroidIndices(TetraConstants::numPatternStars);
195 std::vector<Vec3> observedStarVecs(TetraConstants::numPatternStars);
196 for (int i = 0; i < TetraConstants::numPatternStars; i++) {
197 int centroidInd = centroidIndices[comboIndices[i]];
198 selectedCentroidIndices[i] = centroidInd;
199 observedStarVecs[i] = camera.CameraToSpatial(stars[centroidInd].position).Normalize();
200 }
201
202 // Skip if any pair of chosen stars is farther apart than maxFov
203 bool angleAcceptable = AllPairsWithinFov(
205 [&](int i) -> const Vec3& { return observedStarVecs[i]; },
206 cosMaxFov);
207
208 if (!angleAcceptable) {
209 continue;
210 }
211
212 std::vector<decimal> observedEdgeRatios = TetraEdgeRatios(
213 observedStarVecs.size(), [&](int i) -> const Vec3& { return observedStarVecs[i]; });
214
215 std::set<HashCode> hashCodes =
216 GenerateCandidateHashCodes(observedEdgeRatios, patternSearchRange_, numEdgeRatioBins);
217
218 for (const HashCode& code : hashCodes) {
219 size_t hashIndex =
220 TetraFindPatternIndex(code.data(), code.size(), numEdgeRatioBins, patternTableSize);
221 std::vector<TetraPattern> matches = tetraDatabase.GetPatternMatches(hashIndex);
222
223 if (matches.empty()) continue;
224
225 // Find verified matches — patterns whose edge ratios are within match tolerance
226 int numVerified = 0;
227 std::vector<int> catalogInds;
228 std::vector<Vec3> catalogStarVecs;
229 for (const TetraPattern& matchRow : matches) {
230 std::vector<int> candidateInds;
231 std::vector<Vec3> candidateVecs;
232 for (int star : matchRow) {
233 int catalogInd = tetraDatabase.CatalogIndex(star);
234 candidateInds.push_back(catalogInd);
235 candidateVecs.push_back(catalog[catalogInd].spatial);
236 }
237
238 std::vector<decimal> catalogEdgeRatios = TetraEdgeRatios(
239 candidateVecs.size(), [&](int i) -> const Vec3& { return candidateVecs[i]; });
240
241 bool ratiosMatch = true;
242 for (size_t i = 0; i < catalogEdgeRatios.size(); i++) {
243 if (std::abs(catalogEdgeRatios[i] - observedEdgeRatios[i]) >
244 patternMatchTolerance_) {
245 ratiosMatch = false;
246 break;
247 }
248 }
249
250 if (ratiosMatch) {
251 if (numVerified == 0) {
252 catalogInds = std::move(candidateInds);
253 catalogStarVecs = std::move(candidateVecs);
254 }
255 numVerified++;
256 if (numVerified > 1) break;
257 }
258 }
259
260 // Only use the match if it's unique
261 if (numVerified == 1) {
262 if (pairingMode_ == TRIAD_PERMUTATION) {
263 return PairByTriadPermutation(selectedCentroidIndices,
264 observedStarVecs,
265 catalogInds,
266 catalogStarVecs,
267 stars,
268 catalog,
269 camera);
270 } else {
271 return PairByCentroidRadius(
272 selectedCentroidIndices, observedStarVecs, catalogInds, catalogStarVecs);
273 }
274 }
275 }
276 }
277
278 std::cerr << "TETRA FAIL: nothing could be matched" << std::endl;
279 return {};
280}
281
282StarIdentifiers DummyStarIdAlgorithm::Go(const unsigned char *, const Stars &stars,
283 const Catalog &catalog, const Camera &) const {
284 StarIdentifiers result;
285
286 unsigned int randomSeed = 123456;
287 for (int i = 0; i < (int)stars.size(); i++) {
288 result.push_back(StarIdentifier(i, rand_r(&randomSeed) % catalog.size()));
289 }
290
291 return result;
292}
293
295 const unsigned char *database, const Stars &stars, const Catalog &catalog, const Camera &camera) const {
296
297 StarIdentifiers identified;
298 MultiDatabase multiDatabase(database);
299 const unsigned char *databaseBuffer = multiDatabase.SubDatabasePointer(PairDistanceKVectorDatabase::kMagicValue);
300 if (databaseBuffer == NULL) {
301 return identified;
302 }
303 DeserializeContext des(databaseBuffer);
304 PairDistanceKVectorDatabase vectorDatabase(&des);
305
306 for (int i = 0; i < (int)stars.size(); i++) {
307 std::vector<int16_t> votes(catalog.size(), 0);
308 Vec3 iSpatial = camera.CameraToSpatial(stars[i].position).Normalize();
309 for (int j = 0; j < (int)stars.size(); j++) {
310 if (i != j) {
311 // TODO: find a faster way to do this:
312 std::vector<bool> votedInPair(catalog.size(), false);
313 Vec3 jSpatial = camera.CameraToSpatial(stars[j].position).Normalize();
314 decimal greatCircleDistance = AngleUnit(iSpatial, jSpatial);
315 //give a greater range for min-max Query for bigger radius (GreatCircleDistance)
316 decimal lowerBoundRange = greatCircleDistance - tolerance;
317 decimal upperBoundRange = greatCircleDistance + tolerance;
318 const int16_t *upperBoundSearch;
319 const int16_t *lowerBoundSearch = vectorDatabase.FindPairsLiberal(
320 lowerBoundRange, upperBoundRange, &upperBoundSearch);
321 //loop from lowerBoundSearch till numReturnedPairs, add one vote to each star in the pairs in the datastructure
322 for (const int16_t *k = lowerBoundSearch; k != upperBoundSearch; k++) {
323 if ((k - lowerBoundSearch) % 2 == 0) {
324 decimal actualAngle = AngleUnit(catalog[*k].spatial, catalog[*(k+1)].spatial);
325 assert(actualAngle <= greatCircleDistance + tolerance * 2);
326 assert(actualAngle >= greatCircleDistance - tolerance * 2);
327 }
328 if (!votedInPair[*k] || true) {
329 // if (i == 542 && *k == 9085) {
330 // printf("INC, distance %f from query %f to %f\n", greatCircleDistance,
331 // lowerBoundRange, upperBoundRange);
332 // }
333 votes[*k]++;
334 votedInPair[*k] = true;
335 }
336 }
337 // US voting system
338 }
339 }
340 // Find star w most votes
341 int16_t maxVotes = votes[0];
342 int indexOfMax = 0;
343 for (int v = 1; v < (int)votes.size(); v++) {
344 if (votes[v] > maxVotes) {
345 maxVotes = votes[v];
346 indexOfMax = v;
347 }
348 }
349 // if (i == 542) {
350 // for (decimal dist : vectorDatabase.StarDistances(9085, catalog)) {
351 // printf("Actual 9085 distance: %f\n", dist);
352 // }
353 // puts("Debug star.");
354 // for (int i = 0; i < (int)votes.size(); i++) {
355 // if (votes[i] > maxVotes/2) {
356 // printf("Star %4d received %d votes.\n", catalog[i].name, votes[i]);
357 // }
358 // }
359 // printf("Debug star: Actually voted for %d with %d votes\n",
360 // catalog[indexOfMax].name, maxVotes);
361 // }
362 // printf("Max votes: %d\n", maxVotes);
363 //starIndex = i, catalog index = indexOfMax
364 StarIdentifier newStar(i, indexOfMax);
365 // Set identified[i] to value of catalog index of star w most votesr
366 identified.push_back(newStar);
367 }
368 //optimizations? N^2
369 //https://www.researchgate.net/publication/3007679_Geometric_voting_algorithm_for_star_trackers
370 //
371 // Do we have a metric for localization uncertainty? Star brighntess?
372 //loop i from 1 through n
373 std::vector<int16_t> verificationVotes(identified.size(), 0);
374 for (int i = 0; i < (int)identified.size(); i++) {
375 //loop j from i+1 through n
376 for (int j = i + 1; j < (int)identified.size(); j++) {
377 // Calculate distance between catalog stars
378 CatalogStar first = catalog[identified[i].catalogIndex];
379 CatalogStar second = catalog[identified[j].catalogIndex];
380 decimal cDist = AngleUnit(first.spatial, second.spatial);
381
382 Star firstIdentified = stars[identified[i].starIndex];
383 Star secondIdentified = stars[identified[j].starIndex];
384 Vec3 firstSpatial = camera.CameraToSpatial(firstIdentified.position);
385 Vec3 secondSpatial = camera.CameraToSpatial(secondIdentified.position);
386 decimal sDist = Angle(firstSpatial, secondSpatial);
387
388 //if sDist is in the range of (distance between stars in the image +- R)
389 //add a vote for the match
390 if (DECIMAL_ABS(sDist - cDist) < tolerance) {
391 verificationVotes[i]++;
392 verificationVotes[j]++;
393 }
394 }
395 }
396 // Find star w most votes
397 int maxVotes = verificationVotes.size() > 0 ? verificationVotes[0] : 0;
398 for (int v = 1; v < (int)verificationVotes.size(); v++) {
399 if (verificationVotes[v] > maxVotes) {
400 maxVotes = verificationVotes[v];
401 }
402 }
403
404 // If the stars are within a certain range of the maximal number of votes,
405 // we consider it correct.
406 // maximal votes = maxVotes
407 StarIdentifiers verified;
408 int thresholdVotes = maxVotes * 3 / 4;
409 printf("Verification threshold: %d\n", thresholdVotes);
410 for (int i = 0; i < (int)verificationVotes.size(); i++) {
411 if (verificationVotes[i] > thresholdVotes) {
412 verified.push_back(identified[i]);
413 }
414 }
415
416 return verified;
417}
418
419/*
420 * Strategies:
421 * 1. For each star, enumerate all stars which have the same combination of distances to some
422 * other stars, getting down to a hopefully small (<10) list of candidates for each star, then
423 * do a quad-nested loop to correlate them.
424 * 2. Loop through all possible stars in the catalog for star i. Then look at edge ij, using
425 * this to select possible j-th stars. If ever there is not a possible j-th star, continue the
426 * i-loop. When a possible ij combination is found, loop through k stars according to ik. IF
427 * none are found, continue the outer i loop. If some are found, check jk for each one. For each possible ijk triangle,
428 */
429
435public:
441 : pairs(NULL), end(NULL) { };
442
449 PairDistanceInvolvingIterator(const int16_t *pairs, const int16_t *end, int16_t involving)
450 : pairs(pairs), end(end), involving(involving) {
451
452 assert((end-pairs)%2 == 0);
453 ForwardUntilInvolving();
454 };
455
456 // PairDistanceInvolvingIterator operator++() {
457 // PairDistanceInvolvingIterator result(*this);
458 // ++(*this);
459 // return result;
460 // }
461
464 assert(HasValue());
465 pairs += 2;
466 ForwardUntilInvolving();
467 return *this;
468 }
469
471 int16_t operator*() const {
472 return curValue;
473 }
474
476 bool HasValue() {
477 return pairs != end;
478 }
479
480 // bool operator==(const PairDistanceInvolvingIterator &other) const {
481 // return ()other.pairs == pairs;
482 // }
483
484 // bool operator!=(const PairDistanceInvolvingIterator &other) const {
485 // return !(*this == other);
486 // }
487private:
488 const int16_t *pairs;
489 const int16_t *end;
490 int16_t involving;
491 int16_t curValue;
492
494 void ForwardUntilInvolving() {
495 while (pairs != end) {
496 if (pairs[0] == involving) {
497 curValue = pairs[1];
498 return;
499 }
500 if (pairs[1] == involving) {
501 curValue = pairs[0];
502 return;
503 }
504 pairs += 2;
505 }
506 }
507};
508
510 std::vector<int16_t> result;
511 for (; it.HasValue(); ++it) {
512 result.push_back(*it);
513 }
514 return result;
515}
516
530 std::vector<int32_t> offsets;
531 std::vector<int16_t> values;
532};
533
534static void PairDistanceQueryToMap(const int16_t *pairs, const int16_t *end, size_t catalogSize, FlatPairMap *m) {
535 m->offsets.assign(catalogSize + 1, 0);
536 for (const int16_t *p = pairs; p != end; p += 2) {
537 assert(p[0] >= 0 && (size_t)p[0] < catalogSize);
538 assert(p[1] >= 0 && (size_t)p[1] < catalogSize);
539 m->offsets[p[0]]++;
540 m->offsets[p[1]]++;
541 }
542
543 for (auto last = m->offsets.begin(), next = last+1; next != m->offsets.end(); last++, next++) {
544 *next += *last;
545 }
546 m->values.resize(end - pairs);
547
548 for (const int16_t *p = pairs; p != end; p += 2) {
549 m->values[--m->offsets[p[0]]] = p[1];
550 m->values[--m->offsets[p[1]]] = p[0];
551 }
552}
553
554decimal IRUnidentifiedCentroid::VerticalAnglesToAngleFrom90(decimal v1, decimal v2) {
556}
557
563 const Star &otherStar = stars[starId.starIndex];
564 Vec2 positionDifference = otherStar.position - star->position;
565 decimal angleFromVertical = DECIMAL_ATAN2(positionDifference.y, positionDifference.x);
566
567 for (const auto &otherPair : identifiedStarsInRange) {
568 decimal curAngleFrom90 = VerticalAnglesToAngleFrom90(otherPair.first, angleFromVertical);
569 if (curAngleFrom90 < bestAngleFrom90) {
570 bestAngleFrom90 = curAngleFrom90;
571 bestStar1 = starId;
572 bestStar2 = otherPair.second;
573 }
574 }
575
576 identifiedStarsInRange.emplace_back(angleFromVertical, starId);
577}
578
585std::vector<std::vector<IRUnidentifiedCentroid *>::iterator> FindUnidentifiedCentroidsInRange(
586 std::vector<IRUnidentifiedCentroid *> *centroids, const Star &star, const Camera &camera,
587 decimal minDistance, decimal maxDistance) {
588
589 Vec3 ourSpatial = camera.CameraToSpatial(star.position).Normalize();
590
591 decimal minCos = DECIMAL_COS(maxDistance);
592 decimal maxCos = DECIMAL_COS(minDistance);
593
594 std::vector<std::vector<IRUnidentifiedCentroid *>::iterator> result;
595 for (auto it = centroids->begin(); it != centroids->end(); ++it) {
596 Vec3 theirSpatial = camera.CameraToSpatial((*it)->star->position).Normalize();
597 decimal angleCos = ourSpatial * theirSpatial;
598 if (angleCos >= minCos && angleCos <= maxCos) {
599 result.push_back(it);
600 }
601 }
602
603 return result;
604
605 // TODO: optimize by sorting on x-coordinate (like in tracking), or maybe even kd-tree
606
607 // // Find the first centroid that is within range of the given centroid.
608 // auto firstInRange = std::lower_bound(centroids->begin(), centroids->end(), star.position.x - maxDistance,
609 // [](const IRUnidentifiedCentroid &centroid, decimal x) {
610 // return centroid.star.position.x < x;
611 // });
612
613 // // Find the first centroid that is not within range of the given centroid.
614 // auto firstNotInRange = std::lower_bound(firstInRange, centroids->end(), star.position.x + maxDistance,
615 // [](const IRUnidentifiedCentroid &centroid, decimal x) {
616 // return centroid.star.position.x <= x;
617 // });
618
619 // // Copy the pointers to the stars into the result vector.
620 // for (auto it = firstInRange; it != firstNotInRange; ++it) {
621 // decimal distance = Distance(star.position, it->star.position);
622 // if (distance >= minDistance && distance <= maxDistance) {
623 // result.push_back(&*it);
624 // }
625 // }
626}
627
636void AddToAllUnidentifiedCentroids(const StarIdentifier &starId, const Stars &stars,
637 std::vector<IRUnidentifiedCentroid *> *aboveThresholdCentroids,
638 std::vector<IRUnidentifiedCentroid *> *belowThresholdCentroids,
639 decimal minDistance, decimal maxDistance,
640 decimal angleFrom90Threshold,
641 const Camera &camera) {
642
643 std::vector<int16_t> nowBelowThreshold; // centroid indices newly moved above the threshold
644 // don't need to iterate through the centroids that are already below the threshold, for performance.
645 for (auto centroidIt : FindUnidentifiedCentroidsInRange(aboveThresholdCentroids, stars[starId.starIndex], camera, minDistance, maxDistance)) {
646 (*centroidIt)->AddIdentifiedStar(starId, stars);
647 if ((*centroidIt)->bestAngleFrom90 <= angleFrom90Threshold) {
648 belowThresholdCentroids->push_back(*centroidIt);
649 nowBelowThreshold.push_back((*centroidIt)->index);
650 }
651 }
652 // remove all centroids with indices in nowBelowThreshold from aboveThresholdCentroids
653 aboveThresholdCentroids->erase(std::remove_if(aboveThresholdCentroids->begin(), aboveThresholdCentroids->end(),
654 [&nowBelowThreshold](const IRUnidentifiedCentroid *centroid) {
655 return std::find(nowBelowThreshold.begin(), nowBelowThreshold.end(), centroid->index) != nowBelowThreshold.end();
656 }), aboveThresholdCentroids->end());
657}
658
670std::vector<int16_t> IdentifyThirdStar(const PairDistanceKVectorDatabase &db,
671 const Catalog &catalog,
672 int16_t catalogIndex1, int16_t catalogIndex2,
673 decimal distance1, decimal distance2,
674 decimal tolerance) {
675
676 const int16_t *query1End;
677 const int16_t *query1 = db.FindPairsExact(catalog, distance1-tolerance, distance1+tolerance, &query1End);
678
679 const Vec3 &spatial1 = catalog[catalogIndex1].spatial;
680 const Vec3 &spatial2 = catalog[catalogIndex2].spatial;
681 const Vec3 cross = spatial1.CrossProduct(spatial2);
682
683 // Use PairDistanceInvolvingIterator to find catalog candidates for the unidentified centroid from both sides.
684
685 std::vector<int16_t> result;
686 // find all the catalog stars that are in both annuli
687 for (PairDistanceInvolvingIterator candidateIt(query1, query1End, catalogIndex1);
688 candidateIt.HasValue();
689 ++candidateIt) {
690
691 Vec3 candidateSpatial = catalog[*candidateIt].spatial;
692
693 decimal angle2 = AngleUnit(candidateSpatial, spatial2);
694
695 // check distance to second star
696 if (!(angle2 >= distance2-tolerance && angle2 <= distance2+tolerance)) {
697 continue;
698 }
699
700 // check spectrality
701 decimal spectralTorch = cross * candidateSpatial;
702 // if they are nearly coplanar, don't need to check spectrality
703 // TODO: Implement ^^. Not high priority, since always checking spectrality is conservative.
704 if (spectralTorch <= 0) {
705 continue;
706 }
707
708 // we've made it through the gauntlet!
709 result.push_back(*candidateIt);
710 }
711
712 return result;
713}
714
715IRUnidentifiedCentroid *SelectNextUnidentifiedCentroid(std::vector<IRUnidentifiedCentroid *> *aboveThresholdCentroids,
716 std::vector<IRUnidentifiedCentroid *> *belowThresholdCentroids) {
717 if (!belowThresholdCentroids->empty()) {
718 auto result = belowThresholdCentroids->back();
719 belowThresholdCentroids->pop_back();
720 return result;
721 }
722
723 // need to find the best in aboveThreshold, if any
724 auto bestAboveThreshold = std::min_element(aboveThresholdCentroids->begin(), aboveThresholdCentroids->end(),
725 [](const IRUnidentifiedCentroid *a, const IRUnidentifiedCentroid *b) {
726 return a->bestAngleFrom90 < b->bestAngleFrom90;
727 });
728
729 // 10 is arbitrary; but really it should be less than DECIMAL_M_PI_2 when set
730 if (bestAboveThreshold != aboveThresholdCentroids->end() && (*bestAboveThreshold)->bestAngleFrom90 < 10) {
731 auto result = *bestAboveThreshold;
732 aboveThresholdCentroids->erase(bestAboveThreshold);
733 return result;
734 }
735
736 return NULL;
737}
738
740
748 const Stars &stars,
750 const Catalog &catalog,
751 const Camera &camera,
752 decimal tolerance) {
753#ifdef LOST_DEBUG_PERFORMANCE
754 auto startTimestamp = std::chrono::steady_clock::now();
755#endif
756 // initialize all unidentified centroids
757 std::vector<IRUnidentifiedCentroid> allUnidentifiedCentroids;
758 std::vector<IRUnidentifiedCentroid *> aboveThresholdUnidentifiedCentroids;
759 std::vector<IRUnidentifiedCentroid *> belowThresholdUnidentifiedCentroids;
760 allUnidentifiedCentroids.reserve(stars.size());
761 for (size_t i = 0; i < stars.size(); i++) {
762 allUnidentifiedCentroids.push_back(IRUnidentifiedCentroid(stars[i], i));
763 }
764 // add everything from allUnidentifiedCentroids to above threshold
765 aboveThresholdUnidentifiedCentroids.reserve(allUnidentifiedCentroids.size());
766 for (size_t i = 0; i < allUnidentifiedCentroids.size(); i++) {
767 // only add if index is not equal to any starIndex in identifiers already
768 if (std::find_if(identifiers->begin(), identifiers->end(),
769 [&allUnidentifiedCentroids, i](const StarIdentifier &identifier) {
770 return identifier.starIndex == allUnidentifiedCentroids[i].index;
771 }) == identifiers->end()) {
772
773 aboveThresholdUnidentifiedCentroids.push_back(&allUnidentifiedCentroids[i]);
774 }
775 }
776
777 // sort unidentified centroids by x coordinate
778 // Don't need this until we fix the Find thing
779 // std::sort(unidentifiedCentroids.begin(), unidentifiedCentroids.end(),
780 // [](const IRUnidentifiedCentroid &a, const IRUnidentifiedCentroid &b) {
781 // return a.star->position.x < b.star->position.x;
782 // });
783
784 // for each identified star, add it to the list of identified stars for each unidentified centroid within range
785 for (const auto &starId : *identifiers) {
786 AddToAllUnidentifiedCentroids(starId, stars,
787 &aboveThresholdUnidentifiedCentroids, &belowThresholdUnidentifiedCentroids,
788 db.MinDistance(), db.MaxDistance(),
790 camera);
791 }
792
793 int numExtraIdentifiedStars = 0;
794
795 // keep getting the best unidentified centroid and identifying it
796 while (!belowThresholdUnidentifiedCentroids.empty() || !aboveThresholdUnidentifiedCentroids.empty()) {
797 IRUnidentifiedCentroid *nextUnidentifiedCentroid
798 = SelectNextUnidentifiedCentroid(&aboveThresholdUnidentifiedCentroids, &belowThresholdUnidentifiedCentroids);
799 if (nextUnidentifiedCentroid == NULL) {
800 break;
801 }
802
803 // Project next stars to 3d, find angle between them and current unidentified centroid
804 Vec3 unidentifiedSpatial = camera.CameraToSpatial(nextUnidentifiedCentroid->star->position);
805 Vec3 spatial1 = camera.CameraToSpatial(stars[nextUnidentifiedCentroid->bestStar1.starIndex].position);
806 Vec3 spatial2 = camera.CameraToSpatial(stars[nextUnidentifiedCentroid->bestStar2.starIndex].position);
807 decimal d1 = Angle(spatial1, unidentifiedSpatial);
808 decimal d2 = Angle(spatial2, unidentifiedSpatial);
809 decimal spectralTorch = spatial1.CrossProduct(spatial2) * unidentifiedSpatial;
810
811 // find all the catalog stars that are in both annuli
812 // flip arguments for appropriate spectrality.
813 std::vector<int16_t> candidates =
814 spectralTorch > 0
816 catalog,
817 nextUnidentifiedCentroid->bestStar1.catalogIndex,
818 nextUnidentifiedCentroid->bestStar2.catalogIndex,
819 d1, d2, tolerance)
821 catalog,
822 nextUnidentifiedCentroid->bestStar2.catalogIndex,
823 nextUnidentifiedCentroid->bestStar1.catalogIndex,
824 d2, d1, tolerance);
825
826 if (candidates.size() != 1) { // if there is not exactly one candidate, we can't identify the star. Just remove it from the list.
827 if (candidates.size() > 1) {
828 std::cerr << "WARNING: Multiple catalog stars matched during identify remaining stars. This should be rare." << std::endl;
829 }
830 } else {
831 // identify the centroid
832 identifiers->emplace_back(nextUnidentifiedCentroid->index, candidates[0]);
833
834 // update nearby unidentified centroids with the new identified star
835 AddToAllUnidentifiedCentroids(identifiers->back(), stars,
836 &aboveThresholdUnidentifiedCentroids, &belowThresholdUnidentifiedCentroids,
837 db.MinDistance(), db.MaxDistance(),
838 // TODO should probably tune this:
840 camera);
841
842 ++numExtraIdentifiedStars;
843 }
844 }
845
846 // Select() should always empty out this list
847 assert(belowThresholdUnidentifiedCentroids.empty());
848
849#ifdef LOST_DEBUG_PERFORMANCE
850 auto endTimestamp = std::chrono::steady_clock::now();
851 std::cout << "IdentifyRemainingStarsPairDistance took " << std::chrono::duration_cast<std::chrono::microseconds>(endTimestamp - startTimestamp).count() << "us" << std::endl;
852#endif
853
854 return numExtraIdentifiedStars;
855}
856
858 const unsigned char *database, const Stars &stars, const Catalog &catalog, const Camera &camera) const {
859
860 StarIdentifiers identified;
861 MultiDatabase multiDatabase(database);
862 const unsigned char *databaseBuffer = multiDatabase.SubDatabasePointer(PairDistanceKVectorDatabase::kMagicValue);
863 if (databaseBuffer == NULL || stars.size() < 4) {
864 std::cerr << "Not enough stars, or database missing." << std::endl;
865 return identified;
866 }
867 DeserializeContext des(databaseBuffer);
868 PairDistanceKVectorDatabase vectorDatabase(&des);
869
870 // smallest normal single-precision decimal is around 10^-38 so we should be all good. See
871 // Analytic_Star_Pattern_Probability on the HSL wiki for details.
872 decimal expectedMismatchesConstant = DECIMAL_POW(numFalseStars, 4) * DECIMAL_POW(tolerance, 5) / 2 / DECIMAL_POW(DECIMAL_M_PI, 2);
873
874 // this iteration technique is described in the Pyramid paper. Briefly: i will always be the
875 // lowest index, then dj and dk are how many indexes ahead the j-th star is from the i-th, and
876 // k-th from the j-th. In addition, we here add some other numbers so that the pyramids are not
877 // weird lines in wide FOV images. TODO: Select the starting points to ensure that the first pyramids are all within measurement tolerance.
878 int numStars = (int)stars.size();
879 // the idea is that the square root is about across the FOV horizontally
880 int across = floor(sqrt(numStars))*2;
881 int halfwayAcross = floor(sqrt(numStars)/2);
882 long totalIterations = 0;
883
884 FlatPairMap ikMap, irMap;
885
886 int jMax = numStars - 3;
887 for (int jIter = 0; jIter < jMax; jIter++) {
888 int dj = 1+(jIter+halfwayAcross)%jMax;
889
890 int kMax = numStars-dj-2;
891 for (int kIter = 0; kIter < kMax; kIter++) {
892 int dk = 1+(kIter+across)%kMax;
893
894 int rMax = numStars-dj-dk-1;
895 for (int rIter = 0; rIter < rMax; rIter++) {
896 int dr = 1+(rIter+halfwayAcross)%rMax;
897
898 int iMax = numStars-dj-dk-dr-1;
899 for (int iIter = 0; iIter <= iMax; iIter++) {
900 int i = (iIter + iMax/2)%(iMax+1); // start near the center of the photo
901
902 // identification failure due to cutoff
903 if (++totalIterations > cutoff) {
904 std::cerr << "Cutoff reached." << std::endl;
905 return identified;
906 }
907
908 int j = i+dj;
909 int k = j+dk;
910 int r = k+dr;
911
912 assert(i != j && j != k && k != r && i != k && i != r && j != r);
913
914 // TODO: move this out of the loop?
915 Vec3 iSpatial = camera.CameraToSpatial(stars[i].position).Normalize();
916 Vec3 jSpatial = camera.CameraToSpatial(stars[j].position).Normalize();
917 Vec3 kSpatial = camera.CameraToSpatial(stars[k].position).Normalize();
918
919 decimal ijDist = AngleUnit(iSpatial, jSpatial);
920
921 decimal iSinInner = DECIMAL_SIN(Angle(jSpatial - iSpatial, kSpatial - iSpatial));
922 decimal jSinInner = DECIMAL_SIN(Angle(iSpatial - jSpatial, kSpatial - jSpatial));
923 decimal kSinInner = DECIMAL_SIN(Angle(iSpatial - kSpatial, jSpatial - kSpatial));
924
925 // if we made it this far, all 6 angles are confirmed! Now check
926 // that this match would not often occur due to chance.
927 // See Analytic_Star_Pattern_Probability on the HSL wiki for details
928 decimal expectedMismatches = expectedMismatchesConstant
929 * DECIMAL_SIN(ijDist)
930 / kSinInner
931 / std::max(std::max(iSinInner, jSinInner), kSinInner);
932
933 if (expectedMismatches > maxMismatchProbability) {
934 std::cout << "skip: mismatch prob." << std::endl;
935 continue;
936 }
937
938 Vec3 rSpatial = camera.CameraToSpatial(stars[r].position).Normalize();
939
940 // sign of determinant, to detect flipped patterns
941 bool spectralTorch = iSpatial.CrossProduct(jSpatial)*kSpatial > 0;
942
943 decimal ikDist = AngleUnit(iSpatial, kSpatial);
944 decimal irDist = AngleUnit(iSpatial, rSpatial);
945 decimal jkDist = AngleUnit(jSpatial, kSpatial);
946 decimal jrDist = AngleUnit(jSpatial, rSpatial);
947 decimal krDist = AngleUnit(kSpatial, rSpatial); // TODO: we don't really need to
948 // check krDist, if k has been
949 // verified by i and j it's fine.
950
951 // we check the distances with the extra tolerance requirement to ensure that
952 // there isn't some pyramid that's just outside the database's bounds, but
953 // within measurement tolerance of the observed pyramid, since that would
954 // possibly cause a non-unique pyramid to be identified as unique.
955#define _CHECK_DISTANCE(_dist) \
956 if (_dist < vectorDatabase.MinDistance() + tolerance \
957 || _dist > vectorDatabase.MaxDistance() - tolerance) \
958 { continue; }
959 _CHECK_DISTANCE(ikDist);
960 _CHECK_DISTANCE(irDist);
961 _CHECK_DISTANCE(jkDist);
962 _CHECK_DISTANCE(jrDist);
963 _CHECK_DISTANCE(krDist);
964#undef _CHECK_DISTANCE
965
966 const int16_t *ijEnd, *ikEnd, *irEnd;
967 const int16_t *const ijQuery = vectorDatabase.FindPairsLiberal(ijDist - tolerance, ijDist + tolerance, &ijEnd);
968 const int16_t *const ikQuery = vectorDatabase.FindPairsLiberal(ikDist - tolerance, ikDist + tolerance, &ikEnd);
969 const int16_t *const irQuery = vectorDatabase.FindPairsLiberal(irDist - tolerance, irDist + tolerance, &irEnd);
970
971 // If any query is empty no catalog pyramid can match, so skip building the tables.
972 if (ijQuery == ijEnd || ikQuery == ikEnd || irQuery == irEnd)
973 continue;
974
975 PairDistanceQueryToMap(ikQuery, ikEnd, catalog.size(), &ikMap);
976 PairDistanceQueryToMap(irQuery, irEnd, catalog.size(), &irMap);
977
978 int iMatch = -1, jMatch = -1, kMatch = -1, rMatch = -1;
979 for (const int16_t *iCandidateQuery = ijQuery; iCandidateQuery != ijEnd; iCandidateQuery++) {
980 int iCandidate = *iCandidateQuery;
981 // depending on parity, the first or second star in the pair is the "other" one
982 int jCandidate = (iCandidateQuery - ijQuery) % 2 == 0
983 ? iCandidateQuery[1]
984 : iCandidateQuery[-1];
985
986 assert(iCandidate >= 0 && iCandidate < (int)catalog.size());
987 assert(jCandidate >= 0 && jCandidate < (int)catalog.size());
988
989 const Vec3 &iCandidateSpatial = catalog[iCandidate].spatial;
990 const Vec3 &jCandidateSpatial = catalog[jCandidate].spatial;
991
992 Vec3 ijCandidateCross = iCandidateSpatial.CrossProduct(jCandidateSpatial);
993
994 for (int32_t kIdx = ikMap.offsets[iCandidate]; kIdx < ikMap.offsets[iCandidate+1]; kIdx++) {
995 int kCandidate = ikMap.values[kIdx];
996 Vec3 kCandidateSpatial = catalog[kCandidate].spatial;
997 bool candidateSpectralTorch = ijCandidateCross*kCandidateSpatial > 0;
998 // checking the spectral-ity early to fail fast
999 if (candidateSpectralTorch != spectralTorch) {
1000 continue;
1001 }
1002
1003 // small optimization: We can calculate jk before iterating through r, so we will!
1004 decimal jkCandidateDist = AngleUnit(jCandidateSpatial, kCandidateSpatial);
1005 if (jkCandidateDist < jkDist - tolerance || jkCandidateDist > jkDist + tolerance) {
1006 continue;
1007 }
1008
1009 // TODO: if there are no jr matches, there's no reason to
1010 // continue iterating through all the other k-s. Possibly
1011 // enumarete all r matches, according to ir, before this loop
1012 for (int32_t rIdx = irMap.offsets[iCandidate]; rIdx < irMap.offsets[iCandidate+1]; rIdx++) {
1013 int rCandidate = irMap.values[rIdx];
1014 const Vec3 &rCandidateSpatial = catalog[rCandidate].spatial;
1015 decimal jrCandidateDist = AngleUnit(jCandidateSpatial, rCandidateSpatial);
1016 decimal krCandidateDist;
1017 if (jrCandidateDist < jrDist - tolerance || jrCandidateDist > jrDist + tolerance) {
1018 continue;
1019 }
1020 krCandidateDist = AngleUnit(kCandidateSpatial, rCandidateSpatial);
1021 if (krCandidateDist < krDist - tolerance || krCandidateDist > krDist + tolerance) {
1022 continue;
1023 }
1024
1025 // we have a match!
1026
1027 if (iMatch == -1) {
1028 iMatch = iCandidate;
1029 jMatch = jCandidate;
1030 kMatch = kCandidate;
1031 rMatch = rCandidate;
1032 } else {
1033 // uh-oh, stinky!
1034 // TODO: test duplicate detection, it's hard to cause it in the real catalog...
1035 std::cerr << "Pyramid not unique, skipping..." << std::endl;
1036 goto sensorContinue;
1037 }
1038 }
1039 }
1040
1041
1042 }
1043
1044 if (iMatch != -1) {
1045 std::cout.precision(6);
1046 std::cout << "Matched unique pyramid!" << std::endl << "Expected mismatches: " << std::scientific << expectedMismatches << std::endl << std::fixed;
1047 identified.push_back(StarIdentifier(i, iMatch));
1048 identified.push_back(StarIdentifier(j, jMatch));
1049 identified.push_back(StarIdentifier(k, kMatch));
1050 identified.push_back(StarIdentifier(r, rMatch));
1051
1052 int numAdditionallyIdentified = IdentifyRemainingStarsPairDistance(&identified, stars, vectorDatabase, catalog, camera, tolerance);
1053 printf("Identified an additional %d stars.\n", numAdditionallyIdentified);
1054 assert(numAdditionallyIdentified == (int)identified.size()-4);
1055
1056 return identified;
1057 }
1058
1059 sensorContinue:;
1060 }
1061 }
1062 }
1063 }
1064
1065 std::cerr << "Tried all pyramids; none matched." << std::endl;
1066 return identified;
1067}
1068
1069} // namespace lost
The attitude (orientation) of a spacecraft.
A full description of a camera. Enough information to reconstruct the camera matrix and then some.
Definition camera.hpp:9
Vec3 CameraToSpatial(const Vec2 &) const
Gives a point in 3d space that could correspond to the given vector, using the same coordinate system...
Definition camera.cpp:35
A star from the Bright Star Catalog.
Vec3 spatial
The point on the unit sphere where the star lies.
const std::vector< int > & indices() const
StarIdentifiers Go(const unsigned char *database, const Stars &, const Catalog &, const Camera &) const
Actualy perform the star idenification. This is the "main" function for StarIdAlgorithm.
Definition star-id.cpp:282
StarIdentifiers Go(const unsigned char *database, const Stars &, const Catalog &, const Camera &) const
Actualy perform the star idenification. This is the "main" function for StarIdAlgorithm.
Definition star-id.cpp:294
unidentified centroid used in IdentifyRemainingStarsPairDistance The "angles" through here are "trian...
const Star * star
Index into list of all centroids.
StarIdentifier bestStar1
For the pair of other centroids forming the triangular angle closest to 90 degrees,...
void AddIdentifiedStar(const StarIdentifier &starId, const Stars &stars)
When a centroid within range of this centroid is identified, call this function.
Definition star-id.cpp:562
StarIdentifier bestStar2
One star corresponding to bestAngleFrom90.
int16_t index
The other star corresponding to bestAngleFrom90.
const unsigned char * SubDatabasePointer(int32_t magicValue) const
MultiDatabase memory layout:
Given a list of star pairs, finds all those pairs which involve a certain star.
Definition star-id.cpp:434
PairDistanceInvolvingIterator(const int16_t *pairs, const int16_t *end, int16_t involving)
The main constructor.
Definition star-id.cpp:449
PairDistanceInvolvingIterator & operator++()
Move to the next matching pair.
Definition star-id.cpp:463
int16_t operator*() const
Access the curent pair.
Definition star-id.cpp:471
bool HasValue()
Whether the iterator is currently on a value. (false if iteration is complete).
Definition star-id.cpp:476
PairDistanceInvolvingIterator()
Create a "past-the-end" iterator.
Definition star-id.cpp:440
A database storing distances between pairs of stars.
Definition databases.hpp:56
decimal MinDistance() const
Lower bound on stored star pair distances.
Definition databases.hpp:67
static const int32_t kMagicValue
Magic value to use when storing inside a MultiDatabase.
Definition databases.hpp:72
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.
decimal MaxDistance() const
Upper bound on stored star pair distances.
Definition databases.hpp:65
StarIdentifiers Go(const unsigned char *database, const Stars &, const Catalog &, const Camera &) const
Actualy perform the star idenification. This is the "main" function for StarIdAlgorithm.
Definition star-id.cpp:857
A quaternion is a common way to represent a 3d rotation.
Quaternion Conjugate() const
Effectively computes a quaternion representing the inverse rotation of the original.
Records that a certain Star (detected in the image) corresponds to a certain CatalogStar.
int catalogIndex
An index into an array of CatalogStar objects.
int starIndex
An index into an array of Star objects.
A "centroid" detected in an image.
Vec2 position
The (x,y) pixel coordinates in the image (top left is 0,0).
A database storing Tetra star patterns.
uint16_t CatalogIndex(int tetraCatalogInd) const
std::vector< TetraPattern > GetPatternMatches(size_t index) const
decimal MaxFov() const
static const int32_t kMagicValue
Magic value to use when storing inside a MultiDatabase.
uint64_t PatternTableSize() const
int NumEdgeRatioBins() const
StarIdentifiers Go(const unsigned char *database, const Stars &centroids, const Catalog &catalog, const Camera &) const
Actualy perform the star idenification. This is the "main" function for StarIdAlgorithm.
Definition star-id.cpp:162
A fast attitude estimator which only takes into account information from two stars.
Three dimensional vector with decimaling point components.
Vec3 Normalize() const
Create a vector pointing in the same direction with magnitude 1.
Vec3 CrossProduct(const Vec3 &) const
Usual vector cross product.
double decimal
Definition decimal.hpp:8
#define DECIMAL(x)
Definition decimal.hpp:18
#define DECIMAL_POW(base, power)
Definition decimal.hpp:36
#define DECIMAL_M_PI
Definition decimal.hpp:26
#define DECIMAL_M_PI_4
Definition decimal.hpp:28
#define DECIMAL_SIN(x)
Definition decimal.hpp:49
#define DECIMAL_ABS(x)
Definition decimal.hpp:46
#define DECIMAL_M_PI_2
Definition decimal.hpp:27
#define DECIMAL_ATAN2(x, y)
Definition decimal.hpp:55
#define DECIMAL_COS(x)
Definition decimal.hpp:50
#define DECIMAL_ACOS(x)
Definition decimal.hpp:53
LOST starting point.
bool AllPairsWithinFov(int numStars, SpatialAccessor spatial, decimal cosMaxFov)
std::vector< std::vector< IRUnidentifiedCentroid * >::iterator > FindUnidentifiedCentroidsInRange(std::vector< IRUnidentifiedCentroid * > *centroids, const Star &star, const Camera &camera, decimal minDistance, decimal maxDistance)
Return all the unidentified centroids within the requested distance bounds from star.
Definition star-id.cpp:585
const decimal kAngleFrom90SoftThreshold
Definition star-id.cpp:739
std::vector< StarIdentifier > StarIdentifiers
IRUnidentifiedCentroid * SelectNextUnidentifiedCentroid(std::vector< IRUnidentifiedCentroid * > *aboveThresholdCentroids, std::vector< IRUnidentifiedCentroid * > *belowThresholdCentroids)
Definition star-id.cpp:715
size_t TetraFindPatternIndex(const int *patternEdgeRatios, size_t numRatios, int numEdgeRatioBins, size_t tableSize)
std::array< int, kNumEdgeRatios > HashCode
Definition star-id.cpp:28
std::vector< Star > Stars
decimal AngleUnit(const Vec3 &vec1, const Vec3 &vec2)
Calculate the inner angle, in radians, between two /unit/ vectors.
decimal DegToRad(decimal deg)
decimal Angle(const Vec3 &vec1, const Vec3 &vec2)
Calculate the inner angle, in radians, between two vectors.
std::vector< decimal > TetraEdgeRatios(int numStars, SpatialAccessor spatial)
std::vector< int16_t > ConsumeInvolvingIterator(PairDistanceInvolvingIterator it)
Definition star-id.cpp:509
int IdentifyRemainingStarsPairDistance(StarIdentifiers *, const Stars &, const PairDistanceKVectorDatabase &, const Catalog &, const Camera &, decimal tolerance)
Given some identified stars, attempt to identify the rest.
Definition star-id.cpp:747
decimal DecimalModulo(decimal x, decimal mod)
Given a decimal, find it "modulo" another decimal, in the true mathematical sense (not remainder).
std::vector< int16_t > IdentifyThirdStar(const PairDistanceKVectorDatabase &db, const Catalog &catalog, int16_t catalogIndex1, int16_t catalogIndex2, decimal distance1, decimal distance2, decimal tolerance)
Given two already-identified centroids, and the distance from each to an as-yet unidentified third ce...
Definition star-id.cpp:670
std::array< uint16_t, TetraConstants::numPatternStars > TetraPattern
Definition databases.hpp:93
std::vector< CatalogStar > Catalog
void AddToAllUnidentifiedCentroids(const StarIdentifier &starId, const Stars &stars, std::vector< IRUnidentifiedCentroid * > *aboveThresholdCentroids, std::vector< IRUnidentifiedCentroid * > *belowThresholdCentroids, decimal minDistance, decimal maxDistance, decimal angleFrom90Threshold, const Camera &camera)
Given a list of unidentified centroids not yet at the soft threshold, and a list of unidentified cent...
Definition star-id.cpp:636
#define _CHECK_DISTANCE(_dist)
Given the result of a pair-distance kvector query, build a table of stars to other stars that appeare...
Definition star-id.cpp:529
std::vector< int16_t > values
Definition star-id.cpp:531
std::vector< int32_t > offsets
Definition star-id.cpp:530
static constexpr int numPatternStars
A two dimensional vector with decimaling point components.