daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  main.cpp
  3. //  cg5
  4. //
  5. //  Created by Kate Repekh on 3/23/19.
  6. //  Copyright © 2019 Kate Repekh. All rights reserved.
  7. //
  8. #ifdef __APPLE_CC__
  9. #include <GLUT/glut.h>
  10. #else
  11. #include <GL/glut.h>
  12. #endif
  13. #include <iostream>
  14. #include "Point.hpp"
  15.  
  16. const int maxNumOfPointsToDivide = 6;
  17.  
  18. void drawPoint(Point p) {
  19.     glColor3f(0.0, 0.0, 1.0);
  20.     glPointSize(5);
  21.     glBegin(GL_POINTS);
  22.     glVertex2f(p.getX(), p.getY());
  23.     glEnd();
  24.     glFlush();
  25. }
  26.  
  27. void drawPoints(std::vector<Point> points) {
  28.     glColor3f(1.0, 1.0, 1.0);
  29.     glPointSize(2);
  30.     glBegin(GL_POINTS);
  31.     for (int i = 0; i < points.size(); ++i)
  32.         glVertex2f(points[i].getX(),points[i].getY());
  33.     glEnd();
  34.     glFlush();
  35. }
  36.  
  37. void drawPolygon(std::vector<Point> points, float color) {
  38.     std::cout << "----------------" << std::endl;
  39.     glColor3f(float(rand())/RAND_MAX, float(rand())/RAND_MAX, float(rand())/RAND_MAX);
  40.     glPointSize(3);
  41.     glBegin(GL_LINES);
  42.     for (int i = 0; i < points.size() - 1; ++i) {
  43.         std::cout << points[i].getX() << " " << points[i].getY() << std::endl;
  44.         glVertex2f(points[i].getX(), points[i].getY());
  45.         glVertex2f(points[i+1].getX(), points[i+1].getY());
  46.     }
  47.     std::cout << points[points.size()-1].getX() << " " << points[points.size()-1].getY() << std::endl;
  48.     std::cout << "----------------" << std::endl;
  49.     glEnd();
  50.     glFlush();
  51. }
  52.  
  53. std::vector<Point> jarvisHull(std::vector<Point> points) {
  54.     std::cout << "---jarvis---" << std::endl;
  55.     for (int i = 0; i < points.size(); ++i)
  56.         points[i].print();
  57.     std::cout << "---" << std::endl;
  58.     Point lowestPoint = Point::getLowestPoint(points);
  59.     Point highestPoint = Point::getHighestPoint(points);
  60.     std::vector<Point> hull;
  61.     hull.push_back(highestPoint);
  62.     if (points.size() == 3) {
  63.         hull.push_back(lowestPoint);
  64.         Point middlePoint = lowestPoint;
  65.         for (int i = 0; i < 3; ++i)
  66.             if (!points[i].equals(highestPoint) && !points[i].equals(lowestPoint))
  67.                 middlePoint = points[i];
  68.         hull.push_back(middlePoint);
  69.         if (!Point::isRightPoint(lowestPoint, highestPoint, middlePoint))
  70.             std::swap(hull[1], hull[2]);
  71.         hull.push_back(highestPoint);
  72.         return hull;
  73.     }
  74.    
  75.     std::vector<Point> leftPoints = Point::getRightPoints(highestPoint, lowestPoint, points);
  76.     leftPoints.push_back(lowestPoint);
  77.     if (leftPoints.size() > 1) {
  78.         leftPoints.push_back(lowestPoint);
  79.         Point curPoint = highestPoint;
  80.         std::cout << "cur point: ";
  81.         curPoint.print();
  82.         while (!curPoint.equals(lowestPoint)) {
  83.             curPoint.print();
  84.             float minPolarAngle = 3 * M_PI;
  85.             Point closestPoint = leftPoints[0];
  86.             for (std::vector<Point>::iterator it = leftPoints.begin(); it != leftPoints.end(); ++it) {
  87.                 it->print();
  88.                 float polarAngle = it->getPolarAngle(curPoint);
  89.                 std::cout << polarAngle << std::endl;
  90.                 if (polarAngle < minPolarAngle && curPoint.getY() > it->getY() && !it->equals(curPoint)) {
  91.                     minPolarAngle = polarAngle;
  92.                     closestPoint = *it;
  93.                 }
  94.             }
  95.             if (minPolarAngle == 3 * M_PI)
  96.                 std::cout << "ERROR: NO CLOSE LEFT POINT FOUND" << std::endl;
  97.             hull.push_back(closestPoint);
  98.             curPoint = closestPoint;
  99.             std::cout << "cur point: ";
  100.             curPoint.print();
  101.         }
  102.     }
  103.    
  104.     std::vector<Point> rightPoints = Point::getRightPoints(lowestPoint, highestPoint, points);
  105.     rightPoints.push_back(highestPoint);
  106.     if (rightPoints.size() > 1) {
  107.         rightPoints.push_back(highestPoint);
  108.         Point curPoint = lowestPoint;
  109.         std::cout << "cur point: ";
  110.         curPoint.print();
  111.         while (!curPoint.equals(highestPoint)) {
  112.             float minPolarAngle = 3 * M_PI;
  113.             Point closestPoint = rightPoints[0];
  114.             for (std::vector<Point>::iterator it = rightPoints.begin(); it != rightPoints.end(); ++it) {
  115.                 it->print();
  116.                 float polarAngle = it->getPolarAngle(curPoint);
  117.                 std::cout << polarAngle << std::endl;
  118.                 if (polarAngle < minPolarAngle && curPoint.getY() < it->getY() && !it->equals(curPoint)) {
  119.                     minPolarAngle = polarAngle;
  120.                     closestPoint = *it;
  121.                 }
  122.             }
  123.             if (minPolarAngle == 3 * M_PI)
  124.                 std::cout << "ERROR: NO CLOSE RIGHT POINT FOUND" << std::endl;
  125.             hull.push_back(closestPoint);
  126.             curPoint = closestPoint;
  127.             std::cout << "cur point: ";
  128.             curPoint.print();
  129.         }
  130.     }
  131.     return hull;
  132. }
  133.  
  134. std::vector<Point> grahamScan(std::vector<Point> points) {
  135.     points.insert(points.begin(), points[points.size()-1]);
  136.     std::cout << "-----graham scan-----" << std::endl;
  137.     for (int i = 0; i < points.size(); ++i)
  138.         points[i].print();
  139.     int M = 2;
  140.     for (int i = 3; i < points.size(); ++i) {
  141.         while (Point::getSignedTriangleArea(points[M-1], points[M], points[i]) <= 0)
  142.             --M;
  143.         ++M;
  144.         std::cout << "swapping these points " << M << " and " << i << std::endl;
  145.         points[M].print();
  146.         points[i].print();
  147.         std::swap(points[M], points[i]);
  148.     }
  149.     std::cout << "M" << M << std::endl;
  150.     points = std::vector<Point>(points.begin(), points.begin() + M + 1);
  151.     return points;
  152. }
  153.  
  154. std::vector<Point> mergeHulls(std::vector<Point> s1, std::vector<Point> s2) {
  155.     std::cout << "s1:" << std::endl;
  156.     glLineWidth(3);
  157.     drawPolygon(s1, 0.0);
  158.     std::cout << "s2:" << std::endl;
  159.     drawPolygon(s2, 0.5);
  160.     Point leftPoint1 = Point::getLeftPoint(s1);
  161.     Point leftPoint2 = Point::getLeftPoint(s2);
  162.     if (leftPoint1.getX() > leftPoint2.getX())
  163.         std::swap(s1, s2);
  164.     Point p = Point::getCentroid(s1[0], s1[1], s1[2]);
  165.     std::cout << "centroid: ";
  166.     p.print();
  167.     drawPoint(p);
  168.     if (!p.isInsidePolygon(s2)) {
  169.         std::cout << "centroid is outside of s2" << std::endl;
  170.         for (int i = 0; i < s2.size() - 1; ++i)
  171.             if (Point::getSignedTriangleArea(p, s2[i], s2[i+1]) < 0) {
  172.                 s2.erase(s2.begin() + i);
  173.                 --i;
  174.             }
  175.     }
  176.     s1.pop_back();
  177.     if (s2[0].equals(s2[s2.size()-1]))
  178.         s2.pop_back();
  179.     s1.insert(s1.end(), s2.begin(), s2.end());
  180.     std::cout << "-----before sort-----" << std::endl;
  181.     for (int i = 0; i < s1.size(); ++i)
  182.         s1[i].print();
  183.     Point lowestPoint = Point::getLowestPoint(s1);
  184.     lowestPoint = Point(lowestPoint.getX(), lowestPoint.getY()-0.01);
  185.     sort(s1.begin(), s1.end(), [lowestPoint](Point &a, Point &b) {
  186.                                 return a.getPolarAngle(lowestPoint) <
  187.                                        b.getPolarAngle(lowestPoint);});
  188.     std::cout << "-----after sort-----" << std::endl;
  189.     for (int i = 0; i < s1.size(); ++i)
  190.         s1[i].print();
  191.     return grahamScan(s1);
  192. }
  193.  
  194. std::vector<Point> divideAndRule(std::vector<Point> points) {
  195.     if (points.size() <= maxNumOfPointsToDivide)
  196.         return jarvisHull(points);
  197.     std::vector<Point> s1, s2;
  198.     for (int i = 0; i < points.size(); ++i)
  199.         if (i % 2 == 0)
  200.             s1.push_back(points[i]);
  201.         else
  202.             s2.push_back(points[i]);
  203.     return mergeHulls(divideAndRule(s1), divideAndRule(s2));
  204. }
  205.  
  206. void init(std::vector<Point> &points) {
  207.     points = std::vector<Point>();
  208.     points.push_back(Point(0.9, 0.0));//
  209.     points.push_back(Point(0.8, 0.1));
  210.     points.push_back(Point(0.0, 0.21));//
  211.     points.push_back(Point(0.1, 0.15));
  212.     points.push_back(Point(0.3, 0.45));//
  213.     points.push_back(Point(0.6, 0.6));//
  214.     points.push_back(Point(0.2, 0.5));
  215.     points.push_back(Point(0.5, 0.6));
  216.     points.push_back(Point(0.7, 0.7));
  217.     points.push_back(Point(-0.1, 0.8));
  218.     points.push_back(Point(0.4, 0.9));
  219.     drawPoints(points);
  220. }
  221.  
  222. void drawCoordinates() {
  223.     glColor3f(1.0, 1.0, 1.0);
  224.     for(float i = -1.0; i < 1.0; i+=0.1) {
  225.         glBegin(GL_LINES);
  226.        
  227.         glVertex2f(i, 0.01f);
  228.         glVertex2f(i, -0.01f);
  229.        
  230.         glVertex2f(0.01f,  i);
  231.         glVertex2f(-0.01f, i);
  232.         glEnd();
  233.         glFlush();
  234.     }
  235. }
  236.  
  237. void display() {
  238.    
  239.     glClear(GL_COLOR_BUFFER_BIT);
  240.    
  241.     glColor3f(1.0, 0.0, 0.0);
  242.     glBegin(GL_LINES);
  243.    
  244.     glVertex2f(-4.0, 0.0f);
  245.     glVertex2f(4.0, 0.0f);
  246.    
  247.     glVertex2f(4.0, 0.0f);
  248.     glVertex2f(3.0, -1.0f);
  249.     glEnd();
  250.     glFlush();
  251.    
  252.     glColor3f(0.0, 1.0, 0.0);
  253.     glBegin(GL_LINES);
  254.     glVertex2f(0.0, -4.0f);
  255.     glVertex2f(0.0, 4.0f);
  256.    
  257.     glVertex2f(0.0, 4.0f);
  258.     glVertex2f(1.0, 3.0f);
  259.    
  260.     glVertex2f(0.0, 4.0f);
  261.     glVertex2f(-1.0, 3.0f);
  262.     glEnd();
  263.     glFlush();
  264.    
  265.     drawCoordinates();
  266.     std::vector<Point> points;
  267.     init(points);
  268.     std::vector<Point> hull = divideAndRule(points);
  269.     glLineWidth(2);
  270.     drawPolygon(hull, 1.0);
  271.     init(points);
  272. }
  273.  
  274. int main(int argc, char** argv) {
  275.     srand(time(0));
  276.    
  277.     glutInit(&argc, argv);
  278.     glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  279.    
  280.     glutInitWindowPosition(80, 80);
  281.     glutInitWindowSize(800, 800);
  282.     glutCreateWindow("Quick Hull");
  283.    
  284.     glutDisplayFunc(display);
  285.    
  286.     glutMainLoop();
  287. }
  288.  
  289.  
  290. //
  291. //  Point.hpp
  292. //  cg6
  293. //
  294. //  Created by Kate Repekh on 3/23/19.
  295. //  Copyright © 2019 Kate Repekh. All rights reserved.
  296. //
  297.  
  298. #ifndef Point_hpp
  299. #define Point_hpp
  300.  
  301. #include <vector>
  302. #include <cmath>
  303. #include <iostream>
  304.  
  305. class Point {
  306.    
  307. private:
  308.     float x;
  309.     float y;
  310.    
  311. public:
  312.     Point (float x, float y);
  313.     float getX();
  314.     float getY();
  315.     float getPolarAngle(Point zero);
  316.     static Point getCentroid(Point a, Point b, Point c);
  317.     bool equals(Point anotherPoint);
  318.     bool isInsidePolygon(std::vector<Point> vertices);
  319.     void print();
  320.     static float getSignedTriangleArea(Point a, Point b, Point c);
  321.     static Point getLeftPoint(std::vector<Point> points);
  322.     static Point getRightPoint(std::vector<Point> points);
  323.     static Point getHighestPoint(std::vector<Point> points);
  324.     static Point getLowestPoint(std::vector<Point> points);
  325.     static Point getPointFarthestFromLine(Point a, Point b, std::vector<Point> points);
  326.     static std::vector<Point> getRightPoints(Point a, Point b, std::vector<Point> points);
  327.     static bool isRightPoint(Point a, Point b, Point point);
  328. };
  329.  
  330. #endif /* Point_hpp */
  331.  
  332.  
  333. //
  334. //  Point.cpp
  335. //  cg6
  336. //
  337. //  Created by Kate Repekh on 3/23/19.
  338. //  Copyright © 2019 Kate Repekh. All rights reserved.
  339. //
  340.  
  341. #include "Point.hpp"
  342.  
  343. Point::Point(float _x, float _y) {
  344.     x = _x;
  345.     y = _y;
  346. }
  347.  
  348. float Point::getX() {
  349.     return x;
  350. }
  351.  
  352. float Point::getY() {
  353.     return y;
  354. }
  355.  
  356. float Point::getPolarAngle(Point zero) {
  357.     float newx = x - zero.getX();
  358.     float newy = y - zero.getY();
  359.     if (newx > 0) {
  360.         if (newy >= 0)
  361.             return atan(newy/newx);
  362.         else
  363.             return atan(newy/newx) + 2 * M_PI;
  364.     }
  365.     else if (newx < 0)
  366.         return atan(newy/newx) + M_PI;
  367.     else if (newy > 0)
  368.         return M_PI / 2;
  369.     else return 3 * M_PI / 2;
  370. }
  371.  
  372. Point Point::getLowestPoint(std::vector<Point> points) {
  373.     Point lowestPoint = points[0];
  374.     for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
  375.         if (it->getY() < lowestPoint.getY())
  376.             lowestPoint = *it;
  377.     std::cout << "lowest point: " << lowestPoint.getX() << " " << lowestPoint.getY() << std::endl;
  378.     return lowestPoint;
  379. }
  380.  
  381. Point Point::getHighestPoint(std::vector<Point> points) {
  382.     Point highestPoint = points[0];
  383.     for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
  384.         if (it->getY() > highestPoint.getY())
  385.             highestPoint = *it;
  386.     std::cout << "highest point: " << highestPoint.getX() << " " << highestPoint.getY() << std::endl;
  387.     return highestPoint;
  388. }
  389.  
  390. Point Point::getLeftPoint(std::vector<Point> points) {
  391.     Point leftPoint = points[0];
  392.     for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
  393.         if (it->getX() < leftPoint.getX())
  394.             leftPoint = *it;
  395.     std::cout << "left point: " << leftPoint.getX() << " " << leftPoint.getY() << std::endl;
  396.     return leftPoint;
  397. }
  398.  
  399. Point Point::getRightPoint(std::vector<Point> points) {
  400.     Point rightPoint = points[0];
  401.     for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
  402.         if (it->getX() > rightPoint.getX())
  403.             rightPoint = *it;
  404.     std::cout << "right point: " << rightPoint.getX() << " " << rightPoint.getY() << std::endl;
  405.     return rightPoint;
  406. }
  407.  
  408. Point Point::getPointFarthestFromLine(Point a, Point b, std::vector<Point> points) {
  409.     float A = (a.getY() - b.getY()) / (b.getX() - a.getX());
  410.     float C = - A * a.getX() - a.getY();
  411.     Point farthestPoint = points[0];
  412.     float maxDistance = fabs(A * farthestPoint.getX() + farthestPoint.getY() + C) / sqrt(A*A + 1);
  413.     for (std::vector<Point>::iterator it = points.begin()+1; it != points.end(); ++it) {
  414.         float curDistance = fabs(A * it->getX() + it->getY() + C) / sqrt(A*A + 1);
  415.         if (curDistance > maxDistance) {
  416.             farthestPoint = *it;
  417.             maxDistance = curDistance;
  418.         }
  419.     }
  420.     std::cout << "farthest point: " << farthestPoint.getX() << " " << farthestPoint.getY() << std::endl;
  421.     return farthestPoint;
  422. }
  423.  
  424. bool Point::isRightPoint(Point a, Point b, Point point) {
  425.     float K = (a.getY() - b.getY()) / (a.getX() - b.getX());
  426.     float B = a.getY() - K * a.getX();
  427.     float x = (point.getY() - B) / K;
  428.     if (a.getY() > b.getY())
  429.         return x > point.getX();
  430.     else return x < point.getX();
  431. }
  432.  
  433. bool Point::equals(Point anotherPoint) {
  434.     return (x == anotherPoint.getX() && y == anotherPoint.getY());
  435. }
  436.  
  437. std::vector<Point> Point::getRightPoints(Point a, Point b, std::vector<Point> points) {
  438.     std::cout << "line:\nfrom " << a.getX() << " " << a.getY() << "\nto " << b.getX() << " " << b.getY() << std::endl;
  439.     std::vector<Point> rightPoints;
  440.     for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)
  441.         if (isRightPoint(a, b, *it) && !it->equals(a) && !it->equals(b)) {
  442.             std::cout << it->getX() << it->getY() << std::endl;
  443.             rightPoints.push_back(*it);
  444.         }
  445.     std::cout << "that were all right points" << std::endl;
  446.     return rightPoints;
  447. }
  448.  
  449. void Point::print() {
  450.     std::cout << x << " " << y << std::endl;
  451. }
  452.  
  453. Point Point::getCentroid(Point a, Point b, Point c) {
  454.     return Point((a.getX() + b.getX() + c.getX()) / 3.0,
  455.                  (a.getY() + b.getY() + c.getY()) / 3.0);
  456. }
  457.  
  458. float Point::getSignedTriangleArea(Point p1, Point p2, Point p3) {
  459.     return (p2.getX() - p1.getX())*(p3.getY() - p1.getY()) - (p2.getY() - p1.getY())*(p3.getX() - p1.getX());
  460. }
  461.  
  462. bool Point::isInsidePolygon(std::vector<Point> vertices) {
  463.     for (int i = 0; i < vertices.size() - 1; ++i) {
  464.         float area = getSignedTriangleArea(*this, vertices[i], vertices[i+1]);
  465.         if (area < 0)
  466.             return false;
  467.     }
  468.     return true;
  469. }
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