SHARE
TWEET

Untitled

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