#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <random>
#include <chrono>
class stop_watch{
public:
static auto timer(){
return std::chrono::high_resolution_clock::now();
}
static void display_time(const std::chrono::high_resolution_clock::time_point end, const std::chrono::high_resolution_clock::time_point start){
std::cout<< std::chrono::duration_cast<std::chrono::microseconds>(end-start).count() << "\n";
}
};
template <typename T>
T get_median(const std::vector<T>& data) {
int median = data.size() / 2;
return data[median];
}
template <typename T>
void sort_array(std::vector<T>& data, int axis) {
std::sort(data.begin(), data.end(), [&](T& a, T& b) {return (a[axis] < b[axis]); });
}
template <typename T>
struct Node {
T data;
Node* L;
Node* R;
Node* P;
};
template <typename T>
class kd_tree {
private:
Node<T>* Root;
int m_size;
std::vector<Node<T>*> visited_nodes;
Node<T>* stoppage;
public:
kd_tree(const int& size) :Root(nullptr), m_size(size) {}
int get_axis(int axis){
return axis%(m_size);
}
void add_to_tree(const T& val) {
static int counter = 0;
counter++;
if (Root == nullptr) {
Root = new Node<T>();
Root->data = val;
Root->L = Root->R = nullptr;
stoppage = new Node<T>();
Root->P = stoppage;
}
else {
// 3d
int axis = 0;
Node<T>* temp = new Node<T>();
temp->data = val;
temp->P = temp->L = temp->R = nullptr;
Node<T>* current = Root;
while (current->R != nullptr || current->L != nullptr) {
if (temp->data[get_axis(axis)] <= current->data[get_axis(axis)] && current->L != nullptr) {
current = current->L;
axis++;
}
else if (temp->data[get_axis(axis)] <= current->data[get_axis(axis)] && current->L == nullptr) {
current->L = temp;
temp->P = current;
temp->R = temp->L = nullptr;
break;
}
else if (temp->data[get_axis(axis)] > current->data[get_axis(axis)] && current->R != nullptr) {
current = current->R;
axis++;
}
else if (temp->data[get_axis(axis)] > current->data[get_axis(axis)] && current->R == nullptr) {
current->R = temp;
temp->P = current;
temp->R = temp->L = nullptr;
break;
}
}
if (current->L == nullptr && current->R == nullptr) {
if (temp->data[get_axis(axis)] <= current->data[get_axis(axis)]) {
current->L = temp;
temp->P = current;
temp->R = temp->L = nullptr;
}
else {
current->R = temp;
temp->P = current;
temp->R = temp->L = nullptr;
}
}
}
}
bool prune(Node<T>* ptr, T point,float min_distance, int axis) {
float temp_distance = fabs(point[get_axis(axis)] - ptr->data[get_axis(axis)]);
if (min_distance < temp_distance) {
return true;
}
return false;
}
Node<T>* traverse_down(Node<T>* root, Node<T>*& current_best, T p, float& min_dis, int& axis) {
float temp_distance = min_dis;
T temp_point = p;
// which axis to compare points
int temp_axis = axis;
Node<T>* current = root;
if (current->L == nullptr && current->R == nullptr) {
if ((distance(current->data, p) < temp_distance)) {
current_best = current;
min_dis = distance(current->data, p);
return current;
}
else {
return current;
}
}
while (current->R != nullptr || current->L != nullptr) {
//std::cout<< counter++<<"\n";
if (p[get_axis(axis)] <= current->data[get_axis(axis)] && current->L != nullptr) {
current = current->L;
axis++;
}
else if (p[get_axis(axis)] <= current->data[get_axis(axis)] && current->L == nullptr) {
current = current->R;
axis++;
}
else if (p[get_axis(axis)] > current->data[get_axis(axis)] && current->R != nullptr) {
current = current->R;
axis++;
}
else if (p[get_axis(axis)] > current->data[get_axis(axis)] && current->R == nullptr) {
current = current->L;
axis++;
}
}
if (current->L == nullptr && current->R == nullptr) {
if (distance(current->data, p) < temp_distance) {
temp_distance = distance(p, current->data);
temp_point = current->data;
min_dis = temp_distance;
current_best = current;
}
}
return current;
}
bool is_Node_visited(const Node<T>* ptr){
if(visited_nodes.size()!=0){
for(auto& i : visited_nodes){
if(ptr == i){
//std::cout<<3;
return true;
}
}
//std::cout<<2;
return false;
}
//std::cout<<1;
return false;
}
Node<T>* move_up(Node<T>* start, Node<T>* end, Node<T>*& current_best,T p, float& min_distance, int& axis) {
Node<T>* current = start;
Node<T>* previous = start;
T temp_point = start->data;
int temp_axis = axis;
while (current != end) {
if (!prune(current,p,min_distance,axis) && !is_Node_visited(current)) {
visited_nodes.push_back(current);
float temp_distance = distance(current->data, p);
if (temp_distance < min_distance) {
min_distance = temp_distance;
current_best = current;
}
if (current->L == previous && current->R != nullptr) {
//std::cout<<2;
axis++;
return current->R;
}
else if (current->R == previous && current->L != nullptr) {
axis++;
return current->L;
}
}
float temp_distance = distance(current->data, p);
if (temp_distance < min_distance) {
min_distance = temp_distance;
current_best = current;
}
previous = current;
current = current->P;
axis--;
}
return current;
}
T nearest_point(const T p) {
float max = distance(p, Root->data);
int axis = 0;
Node<T>* current_node = Root;
Node<T>* current_best = Root;
Node<T>* temp = Root;
do{
current_node = traverse_down(current_node,current_best, p, max , axis);
current_node = move_up(current_node,stoppage,current_best, p, max, axis);
}while(current_node != stoppage);
this->clear();
return current_best->data;
}
Node<T>* get_Root() {
return Root;
}
void clear(){
visited_nodes.clear();
}
int get_size(){
return m_size;
}
};
template <typename T>
void feed_data(std::vector<T>& data, kd_tree<T>& tree, int axis) {
axis = axis % tree.get_size();
sort_array(data, axis);
int median = data.size() / 2;
tree.add_to_tree(data[median]);
// left vector
if (median >= 1) {
std::vector<T> ldata;
for (int i = 0; i != median; i++) {
ldata.push_back(data[i]);
}
//std::cout<< "l";
//std::cout<<counter_l<<"\n";
feed_data<T>(ldata, tree,(axis+1));
}
if (median >= 1 && data.size() >= 3) {
std::vector<T> rdata;
for (int i = median + 1; i != data.size(); i++) {
rdata.push_back(data[i]);
}
//std::cout<< "r";
//counter_r++;
feed_data<T>(rdata, tree,axis+1);
}
// right vector
//std::cout<<axis<<"\n";
}
struct vec3 {
int x, y, z;
int operator[](int index) {
switch (index) {
case 0:
return x;
case 1:
return y;
case 2:
return z;
default:
return 0;
}
}
friend std::ostream& operator<<(std::ostream& os, const Node<vec3>* p) {
os << p->data.x << "\t" << p->data.y << "\t" << p->data.z << "\n";
return os;
}
friend std::ostream& operator<<(std::ostream& os, const vec3 p) {
os << p.x << "\t" << p.y << "\t" << p.z << "\n";
return os;
}
friend float distance(const vec3& a, const vec3& b) {
return sqrtf((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
friend bool operator == (const vec3& a, const vec3& b) {
return (a.x == b.x && a.y == b.y && a.z == b.z);
}
friend bool operator != (const vec3& a, const vec3& b) {
return !(a == b);
}
};
struct vec2 {
int x, y;
int operator[](int index) {
switch (index) {
case 0:
return x;
case 1:
return y;
default:
return 0;
}
}
friend std::ostream& operator<<(std::ostream& os, const Node<vec2>* p) {
os << p->data.x << "\t" << p->data.y << "\n";
return os;
}
friend std::ostream& operator<<(std::ostream& os, const vec2 p) {
os << p.x << "\t" << p.y << "\n";
return os;
}
friend float distance(const vec2& a, const vec2& b) {
return sqrtf((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
friend bool operator == (const vec2& a, const vec2& b) {
return (a.x == b.x && a.y == b.y);
}
friend bool operator != (const vec2& a, const vec2& b) {
return !(a == b);
}
};
typedef vec3 point3;
typedef vec2 point2;
template<typename T>
T find_nearest(const T& p, std::vector<T>& data) {
float dis = distance(p,data[0]);
T point = data[0];
for (auto& i : data) {
if (distance(i, p) < dis) {
point = i;
dis = distance(i, p);
}
}
return point;
}
int Random() {
static std::uniform_int_distribution<int> distribution(0, 1000);
static std::mt19937 generator;
return distribution(generator);
}
int main()
{
srand(time(NULL));
std::vector<point3> v;
kd_tree<point3> tree(3);
for(int i =0; i!=100000; i++){
point3 r{Random(),Random(),Random()};
v.push_back(r);
}
feed_data<point3>(v, tree,0);
int counter = 0;
for(int i = 0; i!= 10; i++){
point3 r{Random(),Random(),Random()};
point3 brute_force = find_nearest<point3>(r, v);
point3 clever = tree.nearest_point(r);
float d_brute = distance(brute_force, r);
float d_clever = distance(clever, r);
if(clever != brute_force){
counter++;
//std::cout<< "distance with brute is : " << d_brute << "\n";
//std::cout<< "distance with kd_tree is : "<< d_clever << "\n";
std::cout<< r << "\n";
std::cout<< brute_force << "\t" << clever << "\n";
}
}
std::cout<< distance(point3{353,848, 171}, point3{342,836,173}) <<"\n";
std::cout<< distance(point3{353,848, 171}, point3{350,862,179}) <<"\n";
std::cout<<counter;
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}