SHARE
TWEET

Points in a semicircle

a guest Sep 18th, 2015 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <array>
  4. #include <random>
  5. #include <cmath>
  6.  
  7. typedef std::array<double, 2> vector;
  8. typedef std::array<vector, 6> point_list;
  9.  
  10. const auto pi = 4*std::atan(1);
  11.  
  12. double random_uniform(double min, double max)
  13. {
  14.     static std::default_random_engine generator;
  15.     static std::uniform_real_distribution<double> unif_dist; // min = 0, max = 1
  16.  
  17.     return min + (max - min)*unif_dist(generator);
  18. }
  19.  
  20. double distance(const vector& a, const vector& b)
  21. {
  22.     return std::sqrt(std::pow(a[0] - b[0], 2) + std::pow(a[1] - b[1], 2));
  23. }
  24.  
  25. bool inside_semicircle(const vector& p)
  26. {
  27.     return p[1] >= 0 && (distance(p, vector()) <= 1);
  28. }
  29.  
  30. void jostle_points(point_list& pl, double jostle_distance)
  31. {
  32.     for(auto& p : pl)
  33.     {
  34.         while(true)
  35.         {
  36.             auto distance = random_uniform(0, jostle_distance);
  37.             auto angle = random_uniform(0, 2*pi);
  38.  
  39.             auto dx = distance*std::cos(angle);
  40.             auto dy = distance*std::sin(angle);
  41.  
  42.             auto np = p;
  43.             np[0] += dx;
  44.             np[1] += dy;
  45.             if(inside_semicircle(np))
  46.             {
  47.                 p = np;
  48.                 break;
  49.             }
  50.         }
  51.     }
  52. }
  53.  
  54. void write_list(const point_list& pl, std::ostream& os)
  55. {
  56.     for(const auto& p : pl)
  57.     {
  58.         for(auto e : p)
  59.         {
  60.             os << e << ' ';
  61.         }
  62.         os << '\n';
  63.     }
  64.     os << "=====================================================" << std::endl;
  65. }
  66.  
  67. std::ofstream ofs("result.txt");
  68. void write_list(const point_list& pl)
  69. {
  70.     write_list(pl, std::cout);
  71.     write_list(pl, ofs);
  72. }
  73.  
  74. double minimum_distance(const point_list& pl, const vector& p)
  75. {
  76.     auto min_dist = 1e6;
  77.     for(const auto& pi : pl)
  78.     {
  79.         auto dis = distance(pi, p);
  80.         if(dis < min_dist)
  81.         {
  82.             min_dist = dis;
  83.         }
  84.     }
  85.  
  86.     return min_dist;
  87. }
  88.  
  89. double maximum_minimum_distance(const point_list& pl)
  90. {
  91.     auto max_min_distance = 0.0;
  92.  
  93.     auto ds = 0.001;
  94.     for(auto x = -1.0; x <= 1.0; x += ds)
  95.     {
  96.         for(auto y = -1.0; y <= 1.0; y += ds)
  97.         {
  98.             vector point = {{x, y}};
  99.             if( ! inside_semicircle(point))
  100.             {
  101.                 continue;
  102.             }
  103.  
  104.             auto min_distance = minimum_distance(pl, point);
  105.             if(min_distance > max_min_distance)
  106.             {
  107.                 max_min_distance = min_distance;
  108.             }
  109.         }
  110.     }
  111.  
  112.     return max_min_distance;
  113. }
  114.  
  115. int main()
  116. {
  117.     point_list pl;
  118.     for(auto& p : pl)
  119.     {
  120.         p = {{0.0, 0.5}};
  121.     }
  122.     auto min_max_min_dis = 1e6;
  123.     auto jostle_distance = 1.0;
  124.     auto fail_count = 0;
  125.     auto fail_threshold = 1000;
  126.     auto success = false;
  127.  
  128.     write_list(pl);
  129.     while(true)
  130.     {
  131.         auto new_pl = pl;
  132.         jostle_points(new_pl, jostle_distance);
  133.         double max_min_dis = maximum_minimum_distance(new_pl);
  134.         if(max_min_dis < min_max_min_dis)
  135.         {
  136.             pl = new_pl;
  137.             min_max_min_dis = max_min_dis;
  138.             fail_count = 0;
  139.             success = true;
  140.  
  141.             std::cout << "Maximum minimum distance = " << max_min_dis << std::endl;
  142.             ofs       << "Maximum minimum distance = " << max_min_dis << std::endl;
  143.             write_list(pl);
  144.         }
  145.         else
  146.         {
  147.             std::cout << "Fail count (" << jostle_distance << ") = " << ++fail_count << '/' << fail_threshold << '\r';
  148.             if(fail_count >= fail_threshold)
  149.             {
  150.                 if(success)
  151.                 {
  152.                     jostle_distance *= 0.5;
  153.                 }
  154.                 else
  155.                 {
  156.                     jostle_distance *= 2.0;
  157.                 }
  158.                
  159.                 if(jostle_distance < 1e-3 || jostle_distance > 2.0)
  160.                 {
  161.                     break;
  162.                 }
  163.  
  164.                 fail_count = 0;
  165.                 success = false;
  166.                 std::cout << "New jostle distance = " << jostle_distance << std::endl;
  167.             }
  168.         }
  169.     }
  170.  
  171.     return 0;
  172. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top