Skip to content

Instantly share code, notes, and snippets.

@companje companje/ConvexHull.cpp
Last active Aug 29, 2015

Embed
What would you like to do?
ConvexHull in openFrameworks
//by Rick Companje
//based on Greg Borenstein's https://github.com/atduskgreg/Processing-Convex-Hull
#include "ofMain.h"
bool lexicalComparison(const ofPoint& v1, const ofPoint& v2) {
if (v1.x > v2.x) return true;
else if (v1.x < v2.x) return false;
else if (v1.y > v2.y) return true;
else return false;
}
class ofApp : public ofBaseApp {
public:
vector<ofPoint> points,hull;
ofPoint h1,h2,h3;
int currentPoint,direction;
void setup() {
ofSetFrameRate(30);
}
void update() {
}
void draw() {
ofSetColor(255);
ofFill();
for (int i=0; i<points.size(); i++) {
ofCircle(points.at(i),2);
}
ofNoFill();
ofBeginShape();
for (int i=0; i<hull.size(); i++) {
ofVertex(hull.at(i));
}
ofEndShape();
}
void mouseDragged(int x, int y, int button) {
points.push_back(ofPoint(x,y));
}
void mouseReleased(int x, int y, int button) {
hull = getConvexHull(points);
}
bool isRightTurn(ofPoint a, ofPoint b, ofPoint c) {
// use the cross product to determin if we have a right turn
return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) > 0;
}
vector<ofPoint> getConvexHull(vector<ofPoint> points) {
sort(points.begin(), points.end(), lexicalComparison);
vector<ofPoint> hull;
hull.push_back(points.at(0));
hull.push_back(points.at(1));
int currentPoint = 2;
int direction = 1;
for (int i=0; i<1000; i++) { //max 1000 tries
hull.push_back(points.at(currentPoint));
// look at the turn direction in the last three points
h1 = hull.at(hull.size()-3);
h2 = hull.at(hull.size()-2);
h3 = hull.at(hull.size()-1);
// while there are more than two points in the hull
// and the last three points do not make a right turn
while (!isRightTurn(h1, h2, h3) && hull.size() > 2) {
// remove the middle of the last three points
hull.erase(hull.end() - 2);
if (hull.size() >= 3) {
h1 = hull.at(hull.size()-3);
}
h2 = hull.at(hull.size()-2);
h3 = hull.at(hull.size()-1);
}
// going through left-to-right calculates the top hull
// when we get to the end, we reverse direction
// and go back again right-to-left to calculate the bottom hull
if (currentPoint == points.size() -1 || currentPoint == 0) {
direction = direction * -1;
}
currentPoint+= direction;
if (hull.front()==hull.back()) break;
}
return hull;
}
void keyPressed(int key) {
if (key=='c') {
ofBackground(0);
points.clear();
hull.clear();
}
}
};
int main( ){
ofSetupOpenGL(1024,768,OF_WINDOW);
ofRunApp(new ofApp());
}
@companje

This comment has been minimized.

Copy link
Owner Author

commented Oct 26, 2014

the isRightTurn function should use > sign instead of >=.
Update: fixed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.