SHARE
TWEET

Untitled

a guest Mar 21st, 2014 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <set>
  2. #include <map>
  3. #include <fstream>
  4. #include <iostream>
  5. #include <chrono>
  6. #include <memory>
  7. #include <vector>
  8. #include <cmath>
  9. #include <list>
  10.  
  11. static std::string IN_FILE = "points_uniq.txt";
  12. static double NORM_ZERO = 1e-9;
  13. static double ZERO = 1e-15;
  14.  
  15. class Point3D {
  16.  
  17. public:
  18.     int id;
  19.  
  20. private:
  21.     double x;
  22.     double y;
  23.     double z;
  24.  
  25. public:
  26.     Point3D() : Point3D(0.0, 0.0, 0.0) {}
  27.     Point3D(int iid, double ix, double iy, double iz) : id(iid), x(ix), y(iy), z(iz) {}
  28.  
  29.     Point3D(double x, double y, double z) :Point3D(-1, x, y, z) {}
  30.  
  31.     bool operator== (const Point3D & x) const {
  32.         return id == x.id;
  33.     }
  34.  
  35.     Point3D neg() const {
  36.         return Point3D(-x, -y, -z);
  37.     }
  38.  
  39.     static Point3D add(std::initializer_list<Point3D> pts) {
  40.         double x = 0.0;
  41.         double y = 0.0;
  42.         double z = 0.0;
  43.         for (const Point3D& pt : pts) {
  44.             x += pt.x;
  45.             y += pt.y;
  46.             z += pt.z;
  47.         }
  48.         return Point3D(x, y, z);
  49.     }
  50.  
  51.     static Point3D sub(const Point3D& a, const Point3D& b) {
  52.         return Point3D(a.x - b.x, a.y - b.y, a.z - b.z);
  53.     }
  54.  
  55.     Point3D mul(double d) const {
  56.         return Point3D(x * d, y * d, z * d);
  57.     }
  58.  
  59.     static double scal(const Point3D& a, const Point3D& b) {
  60.         return a.x * b.x + a.y * b.y + a.z * b.z;
  61.     }
  62.  
  63.     static Point3D prod(const Point3D& a, const Point3D& b) {
  64.         double x = a.y * b.z - a.z * b.y;
  65.         double y = a.z * b.x - a.x * b.z;
  66.         double z = a.x * b.y - a.y * b.x;
  67.  
  68.         return Point3D(x, y, z);
  69.     }
  70.  
  71.     double size() const {
  72.         double d = scal(*this, *this);
  73.         return sqrt(d);
  74.     }
  75.  
  76.     Point3D norm() const {
  77.         double d = size();
  78.         if (d < ZERO)
  79.             return *this;
  80.         return mul(1.0 / d);
  81.     }
  82. };
  83.  
  84. class Line {
  85.  
  86.     Point3D a;
  87.     Point3D b;
  88.     bool mark;
  89.  
  90. public:
  91.     Line(const Point3D& ia, const Point3D& ib): a(ia), b(ib), mark(false) {}
  92.  
  93.     void doMark() {
  94.         mark = !mark;
  95.     }
  96.  
  97.     bool isMark() const {
  98.         return mark;
  99.     }
  100.  
  101.     Point3D beg() const {
  102.         return a;
  103.     }
  104.  
  105.     Point3D end() const {
  106.         return b;
  107.     }
  108.  
  109.     Point3D beg(bool rev) const {
  110.         return rev ? b : a;
  111.     }
  112.  
  113.     Point3D end(bool rev) const {
  114.         return rev ? a : b;
  115.     }
  116.  
  117.     Point3D dir(bool rev) const {
  118.         Point3D d = Point3D::sub(b, a);
  119.         return rev ? d.neg() : d;
  120.     }
  121.  
  122.     void addIDs(std::set<int> & pts) const {
  123.         pts.insert(a.id);
  124.         pts.insert(b.id);
  125.     }
  126. };
  127.  
  128. class Triangle {
  129.  
  130.     Point3D norm;
  131.     std::shared_ptr<Line> a;
  132.     std::shared_ptr<Line> b;
  133.     std::shared_ptr<Line> c;
  134.     bool arev;
  135.     bool brev;
  136.     bool crev;
  137.  
  138. public:
  139.     Triangle(const Point3D& a, const Point3D& b, const Point3D& c, Point3D * p) : Triangle(std::make_shared<Line>(a, b), std::make_shared<Line>(b, c), std::make_shared<Line>(c, a), p) {}
  140.  
  141.     Triangle(std::shared_ptr<Line> a, std::shared_ptr<Line> b, std::shared_ptr<Line> c, Point3D * p) : Triangle(a, b, c, p, false, false) {}
  142.  
  143.     Triangle(std::shared_ptr<Line> ia, std::shared_ptr<Line> ib, std::shared_ptr<Line> ic, Point3D * p, bool iarev, bool icrev) : a(ia), b(ib), c(ic), arev(iarev), crev(icrev), norm(0, 0, 0) {
  144.         brev = a->end(arev) == b->end();
  145.  
  146.         bool ba = a->beg(arev) == c->end(crev);
  147.         bool bb = b->beg(brev) == a->end(arev);
  148.         bool bc = c->beg(crev) == b->end(brev);
  149.         if (!(ba && bb && bc))
  150.             std::cout << "failed ori\n";
  151.  
  152.         Point3D da = a->dir(arev);
  153.         Point3D dc = c->dir(!crev);
  154.  
  155.         Point3D n = Point3D::prod(da, dc);
  156.         if (p != nullptr) {
  157.             double d = Point3D::scal(n, Point3D::sub(*p, a->beg()));
  158.             if (d < 0)
  159.                 n = n.mul(-1);
  160.             if (fabs(d) < NORM_ZERO)
  161.                 std::cout << "inv norm " << d << "\n";
  162.         }
  163.         norm = n.norm();
  164.     }
  165.  
  166.     bool isValid() const {
  167.         return Point3D::scal(norm, norm) > 1e-5;
  168.     }
  169.  
  170.     double getOri(const Point3D& p) const {
  171.         auto diff = Point3D::sub(p, a->beg());
  172.         auto sc = Point3D::scal(norm, diff);
  173.         return sc;
  174.     }
  175.  
  176.     void marklines() {
  177.         a.get()->doMark();
  178.         b.get()->doMark();
  179.         c.get()->doMark();
  180.     }
  181.  
  182.     void addMarked(std::vector<std::shared_ptr<Line>> & bord) {
  183.         if (a.get()->isMark())
  184.             bord.push_back(a);
  185.         if (b.get()->isMark())
  186.             bord.push_back(b);
  187.         if (c.get()->isMark())
  188.             bord.push_back(c);
  189.     }
  190.  
  191.     void addIDs(std::set<int> & pts) {
  192.         a->addIDs(pts);
  193.         b->addIDs(pts);
  194.         c->addIDs(pts);
  195.     }
  196. };
  197.  
  198. class Envelope {
  199.  
  200.     Point3D in;
  201.     std::list<Triangle> tri;
  202.  
  203. public:
  204.     Envelope(const Point3D& iin, std::shared_ptr<Triangle> tr) : in(iin) {
  205.         tri.push_back(*tr);
  206.     }
  207.  
  208.     void addPoint(const Point3D& pt) {
  209.         auto tr = tri.begin();
  210.         auto trEnd = tri.end();
  211.         while (tr != trEnd)
  212.         {
  213.             auto& triangle = *tr;
  214.             if (triangle.getOri(pt) < NORM_ZERO) {
  215.                 tr = tri.erase(tr);
  216.             }
  217.             else {
  218.                 triangle.marklines();
  219.                 ++tr;
  220.             }
  221.         }
  222.  
  223.         std::vector<std::shared_ptr<Line>> bord;
  224.         for (auto& tr : tri)
  225.             tr.addMarked(bord);
  226.  
  227.         std::map<int, std::shared_ptr<Line>> map;
  228.         for (auto lin : bord) {
  229.             Point3D b = lin->beg(false);
  230.             Point3D e = lin->end(false);
  231.  
  232.             std::shared_ptr<Line>& x = map[b.id];
  233.             if (x == nullptr) {
  234.                 x = std::make_shared<Line>(pt, b);
  235.             }
  236.             bool xrev = x->end() == pt;
  237.  
  238.             std::shared_ptr<Line>& z = map[e.id];
  239.             if (z == nullptr) {
  240.                 z = std::make_shared<Line>(e, pt);
  241.             }
  242.             bool zrev = z->beg() == pt;
  243.  
  244.             Triangle tr(x, lin, z, &in, xrev, zrev);
  245.             if (tr.isValid())
  246.                 tri.push_back(tr);
  247.             else
  248.                 std::cout << "inv triangle" << "\n";
  249.             lin->doMark();
  250.         }
  251.     }
  252.  
  253.     size_t getPtCnt() {
  254.         std::set<int> pts;
  255.         for (auto& tr : tri)
  256.             tr.addIDs(pts);
  257.  
  258.         return pts.size();
  259.     }
  260.  
  261.     size_t getTriCnt() {
  262.         return tri.size();
  263.     }
  264.  
  265. };
  266.  
  267. static int ptCnt;
  268.  
  269. Point3D getPoint(std::istream & sc) {
  270.     std::string line;
  271.     std::getline(sc, line);
  272.     if (sc.eof())
  273.         return Point3D();
  274.     double x, y, z;
  275.     if (sscanf(line.c_str(), "%lf %lf %lf", &x, &y, &z) != 3)
  276.         return Point3D();
  277.     return Point3D(++ptCnt, x, y, z);
  278. }
  279.  
  280. Envelope * initEnvelope(std::istream & sc) {
  281.     Point3D a = getPoint(sc);
  282.     Point3D b = getPoint(sc);
  283.  
  284.     std::vector<Point3D> pts;
  285.  
  286.     Point3D c(0.0,0.0,0.0);
  287.  
  288.     std::unique_ptr<Triangle> tr = nullptr;
  289.     while (!sc.eof()) {
  290.         c = getPoint(sc);
  291.         tr.reset(new Triangle(a, b, c, nullptr));
  292.         if (tr->isValid())
  293.             break;
  294.         pts.push_back(c);
  295.     }
  296.  
  297.     // TODO: if !tr valid
  298.     Point3D d(0.0,0.0,0.0);
  299.     while (!sc.eof()) {
  300.         d = getPoint(sc);
  301.         double n = tr->getOri(d);
  302.         if (fabs(n) > NORM_ZERO)
  303.             break;
  304.         pts.push_back(d);
  305.     }
  306.  
  307.     Point3D in = Point3D::add({ a, b, c, d }).mul(1 / 4.0);
  308.     Envelope * env = new Envelope(in, std::make_shared<Triangle>(a, b, c, &in));
  309.     env->addPoint(d);
  310.  
  311.     for (const Point3D& pt : pts)
  312.         env->addPoint(pt);
  313.     return env;
  314. }
  315.  
  316. using namespace std::chrono;
  317.  
  318. int main() {
  319.     ptCnt = 0;
  320.  
  321.     for (int i = 0; i < 20; i++) {
  322.         std::ifstream sc(IN_FILE);
  323.  
  324.         auto start = high_resolution_clock::now();
  325.         Envelope * env = initEnvelope(sc);
  326.  
  327.         while (!sc.eof()) {
  328.             Point3D pt = getPoint(sc);
  329.             if (pt.id >= 0)
  330.                 env->addPoint(pt);
  331.         }
  332.         auto end = high_resolution_clock::now();
  333.         sc.close();
  334.  
  335.         auto diff = duration_cast<duration<double>>(end - start);
  336.  
  337.         std::cout << "poly cnt: " << env->getTriCnt() << " pt cnt: " << ptCnt << " pts: " << env->getPtCnt() << "\n";
  338.  
  339.         delete env;
  340.     }
  341.     return 0;
  342. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top