Say Hello ▶

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) {
// code
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!

About :

function polygon(a,b,c,d)
// 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];
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.
Leave a Comment

Post Comment