the convex hull. an exercise in orientation and visibility.
insert a random set of points by mouse click.
press key when ready.
big point is the pivot, the one that sees them all.
dashed polygon is the polar ordering of all the points from pivot's viewpoint.
click to start over again.
<<
class Point2D
{
float x;
float y;
Point2D(){
this.x = x;
this.y = y;
}
Point2D (float X,float Y){
x = X;
y = Y;
}
void display(){
ellipseMode(CENTER_RADIUS);
ellipse(x, y, 2, 2);
}
}
class Triangle2D
{
Point2D A, B, C;
Triangle2D (Point2D A, Point2D B, Point2D C){ // constructor
this.A = A;
this.B = B;
this.C = C;
} // closes method
Triangle2D (float x1, float y1, float x2, float y2, float x3, float y3){ // constructor
this.A = new Point2D(x1,y1);
this.B = new Point2D(x2,y2);
this.C = new Point2D(x3,y3);
} // closes method
void display(){
line(A.x, A.y, B.x, B.y);
line(B.x, B.y, C.x, C.y);
line(C.x, C.y, A.x, A.y);
A.display();
B.display();
C.display();
}
void displayLines(){
line(A.x, A.y, B.x, B.y);
line(B.x, B.y, C.x, C.y);
line(C.x, C.y, A.x, A.y);
}
void displayPoints(){
A.display();
B.display();
C.display();
}
void displayFill(){
triangle(A.x, A.y, B.x, B.y, C.x, C.y);
}
}
class Vector2D
{
Point2D A;
float angle, magnitude;
Vector2D (Point2D A, float angle, float magnitude){ // constructor
this.A = A;
this.angle = angle;
this.magnitude = magnitude;
} // closes method
Vector2D (float x,float y, float angle, float magnitude){ // constructor
this.A = new Point2D(x,y);
this.angle = angle;
this.magnitude = magnitude;
} // closes method
void display(){
line(A.x, A.y, A.x + ( magnitude * sin(angle) ), A.y + ( magnitude * cos(angle) ) );
A.display();
}
void displayEnd(){
Point2D B;
B = new Point2D(A.x + ( magnitude * sin(angle) ), A.y + ( magnitude * cos(angle) ) );
B.display();
}
Point2D startPoint(){
return (A);
}
Point2D endPoint(){
Point2D B;
B = new Point2D(A.x + ( magnitude * sin(angle) ), A.y + ( magnitude * cos(angle) ) );
return (B);
}
}
class Polygon2D
{ int vertices;
Point2D[] A;
Polygon2D (int vertices, Point2D[ ]A ){ // constructor
this.vertices = vertices;
this.A = new Point2D[vertices];
for (int i = 0; i < vertices; i++){
this.A[i] = A[i];
}
} // closes method
void display(){
for (int i = 0; i < vertices; i++){
int k = (i + 1) % (vertices);
line(A[i].x, A[i].y, A[k].x , A[k].y );
A[i].display();
}
}
}
class DashLine
{
int xA;
int xB;
int yA;
int yB;
int dashLenght;
DashLine (int startX,int endX,int startY,int endY, int dashLn)
{
xA=startX;
xB=endX;
yA=startY;
yB=endY;
dashLenght=dashLn;
}
void display(){
float lineLenghtX = xB-xA;
float lineLenghtY = yB-yA;
float lineLenght = sqrt( sq(lineLenghtX) + sq(lineLenghtY) );
int n = floor( ((lineLenght/dashLenght)+1)/2 );
float dashX = lineLenghtX /(2*n - 1);
float dashY = lineLenghtY /(2*n - 1);
for(int i=0;i<=n-1;i++){
line(xA+(2*i*dashX), yA+(2*i*dashY), xA+((2*i+1)*dashX), yA+((2*i+1)*dashY));
}
}
}
Point2D midPoint(Point2D X,Point2D Y){
Point2D mid;
mid = new Point2D( X.x +( (Y.x-X.x)/2 ), X.y +( (Y.y-X.y)/2 ) ); // fun to change any of this 2 for a 3
return (mid);
}
Point2D randomChoice(Point2D X, Point2D Y, Point2D Z){
float r = random(0,3);
Point2D rand;
if (r < 1f)
rand = new Point2D( Y.x, Y.y );
else{
if(r < 2f)
rand = new Point2D( X.x, X.y );
else
rand = new Point2D( Z.x, Z.y );
}
return (rand);
}
Point2D randomPoint(){
float rx = random(0,1);
float ry = random(0,1);
Point2D rand;
rand = new Point2D( width * rx, height * ry );
return (rand);
}
float area2(Point2D A, Point2D B, Point2D C)
{
return (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
}
boolean insideTriangle(Point2D A, Point2D B, Point2D C, Point2D P){
// ABC is assumed to be counterclockwise
return
area2(A, B ,P ) >= 0 &&
area2(B, C, P) >= 0 &&
area2(C, A, P) >= 0;
}
boolean ccw (Point2D[] P)
{ int n = P.length, k=0;
for (int i=0; i
Source code: convexHull_0f
Built with Processing