HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

N closest points to the reference point

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
referencethepointpointsclosest

Problem

Here is working code to get N closest points to some reference point.

Please help to improve it, specifically by commenting on my use of std algorithms and vectors/iterators manipulations.

Nearest.h

#pragma once

#include 
#include 
#include 
#include 

namespace nearest {

struct Point {
  double x;
  double y;
  double z;

  bool operator==(const Point& rhp) {
    return x == rhp.x && y == rhp.y && z == rhp.z;
  }

};

// Return N closest points to first point in vector in order
std::vector nearestN(const std::vector& points,
                            int N);

// Return N closest points to a reference point, in order - all
// within maximum distance threshold
std::vector nearestN(const std::vector& points,
                            int N,
                            const Point& reference,
                            double distanceThreshold);

}


Nearest.cpp

```
#include "Nearest.h"

using namespace std;

namespace nearest {

// to print Point to cout
std::ostream& operator nearestN(const vector& points, int N) {
if (points.size() == 0) {
vector empty;
return empty;
}
return nearestN(points, N, points[0], INFINITY);
}

vector nearestN(const vector& points,
int N,
const Point& reference,
double distanceThreshold) {

vector temp;
temp.insert(temp.begin(), points.begin(), points.end());

// filtering vector to remove all points far then distance from reference
temp.erase(remove_if(temp.begin(),
temp.end(),
&reference, distanceThreshold{ return ByDistance::dist(p, reference) > distanceThreshold; }),
temp.end());

ByDistance distance = {reference};
sort(temp.begin(), temp.end(), distance);

auto sz = min(static_cast(temp.size()), N);
vector result(sz);

Solution

Faster sorting

If the only purpose of the distance computation is for comparison, then you can speed it up by removing the call to sqrt(). You'll end up comparing the squares of the distances, which is equivalent to comparing the actual distances.

Context

StackExchange Code Review Q#108566, answer score: 11

Revisions (0)

No revisions yet.