Geometry Puzzler
Jun 27, 09
For the love of puzzlers, try your hand at the following math problem:
You are given four 2-dimensional co-ordinates in a random order. What is the simplest method to draw the enclosing polygon created by joining the points?
Answers should be written in C-like syntax or pseudo code, without library dependencies, and should not include any visual methods. You can simply return an array of co-ordinates that, when followed in order, will draw the proper polygon.
For example:
function polygon(p1, p2, p3, p4) {
polygon( [x1,y1] , [x2,y2] , [x3,y3] , [x4,y4] );
The winning entry will be used in a 3D game released for amoebaOS, and will be credited within the game for their contribution!
Good luck and have fun!
You are given four 2-dimensional co-ordinates in a random order. What is the simplest method to draw the enclosing polygon created by joining the points?
Answers should be written in C-like syntax or pseudo code, without library dependencies, and should not include any visual methods. You can simply return an array of co-ordinates that, when followed in order, will draw the proper polygon.
For example:
function polygon(p1, p2, p3, p4) {
// code
return [ p3, p2, p4, p1];
}return [ p3, p2, p4, p1];
polygon( [x1,y1] , [x2,y2] , [x3,y3] , [x4,y4] );
The winning entry will be used in a 3D game released for amoebaOS, and will be credited within the game for their contribution!
Good luck and have fun!
{
// Make the list of points into an array:
p = [a,b,c,d];
// Find the midpoint
mp = [0,0];
for(i=0; i<4; i++)
{
mp[0] += p[i][0];
mp[1] += p[i][1];
}
mp[0] = mp[0] / 4; // Dividing the total x's and y's by 4
mp[1] = mp[1] / 4; // results in the mid-point
// Now that we have the mid-point, get the angle between
// each point and the mid-point
angles = [0,0,0,0];
for(i=0;i<4;i++)
{
angle = atan2(p[i][0]-mp[0], p[i][1]-mp[1]);
angles[i] = angle;
}
// Sort the points by increasing angle
p.sortBy(increasingAngle); // I can't really think of a very language independent way to do this.
return p; // Return the array
}
Unfortunately, this technique uses atan2(), so it's something that you would only want to do once and not every single frame.