/*H************************************************************************************************/

/*!

\File main.cpp

\Description

Hacker's Delight #7 - Nearest Neighbor Search

Given a point cloud of 65535 points or less, your challenge is to return the DISTANCE between

the two closest points in the cloud. In the example below, we have limited the cloud size

to 4095 elements.

\Notes

Please read the RULE and NOTE comments below. Entries that violate RULE(s) will be rejected.

*/

/************************************************************************************************H*/

/* $$RULE: Adding includes is not allowed for this challenge. All submitted code must be within

the START and END tokens (see below).

*/

#include <iostream>

#include <math.h>

#include <time.h>

#include <float.h>

// $$RULE: The preprocessor directive "#define" is not allowed. Use "const" or inline functions.

// $$NOTE: Your entry will be tested on cloud sizes up to 0xffff

const long CLOUD_ELEMENTS = 0xfff;

// $$NOTE: The extents of the data set is for this test-harness only. Actual data may vary.

const float CLOUD_SIZE = 2000.0f;

// $$NOTE: A constant random seed is used here so you may test your answer against the reference solution.

const unsigned long gRandomSeed = 1024;

// Point class. $$RULE: Do not modify.

class PointC

{

public:

float x, y, z;

void Set(float a, float b, float c) { x=a; y=b; z=c; }

void Scale(float s) { x *= s; y *= s; z *= s; }

void Offset(float o) { x += o; y += o; z += o; }

static void Sub(PointC *pOut, PointC *pA, PointC *pB)

{

pOut->x = pA->x - pB->x;

pOut->y = pA->y - pB->y;

pOut->z = pA->z - pB->z;

}

};

// Cloud class. $$RULE: Do not modify.

class CloudC

{

public:

CloudC() { m_pCloud=0; }

~CloudC() { delete [] m_pCloud; m_pCloud = 0; }

PointC * Create(unsigned long uiNumPoints);

inline PointC * GetPointBuffer() { return m_pCloud; }

inline unsigned long GetNumPoints() { return m_numPoints; }

protected:

PointC * m_pCloud;

unsigned long m_numPoints;

};

//

// ----------------- START -----------------

//

/* $$RULE: Replace "Author_Institute" with your full name and institution (company or school)

EXAMPLE: JonDoe_ElectronicArtsTiburon

*/

namespace Author_Institute

{

/******************************************************************************/

/*! GetMinDist

\brief Returns the distance between the two "Nearest Neighbors" in the Cloud.

\param pCloud - CloudC pointer

\return - float.

Please provide a written (English) description of your implementation here.

The more detail, the better!!!

Your submission is the code between the "START" and "END" markers. Please do not

submit the test-harness functions, or the class definitions. You can add 'helper'

functions between the "START" and "END" markers (like the Dot example below).

Your code must compile in MS Visual Studio and run on a standard P4.

Inline asm, SSE, MMX are allowed.

*/

/******************************************************************************/

// Example helper function

static float Dot(PointC *pA, PointC *pB)

{

return ( pA->x * pB->x + pA->y * pB->y + pA->z * pB->z );

}

// Brute force! (You can do better than this)

float GetMinDist(CloudC *pCloud)

{

PointC * pBuffer = pCloud->GetPointBuffer();

unsigned long uiNumPoints = pCloud->GetNumPoints();

float minDist = FLT_MAX;

for (unsigned long i = 0; i < uiNumPoints; i++)

{

for (unsigned long j = i+1; j < uiNumPoints; j++)

{

PointC* ptA = &pBuffer[i];

PointC* ptB = &pBuffer[j];

PointC diff;

PointC::Sub(&diff,ptA,ptB);

float dist = sqrtf(Dot(&diff,&diff));

minDist = (dist < minDist) ? dist : minDist;

}

}

// return the distance between the two closest points

return minDist;

}

} // end namespace

//

// ----------------- END -----------------

//

PointC * CloudC::Create(unsigned long uiNumPoints)

{

PointC *pPt;

srand ( gRandomSeed );

/*

$$NOTE: This example point cloud data is for the Test Harness. You should not assume that

the Grading Harness will be a random distribution, like below. In fact, we plan

on using "real-world" model data (EX: the Stanford Bunny).

http://www.gvu.gatech.edu/people/faculty/greg.turk/bunny/bunny.html

*/

m_pCloud = new PointC[uiNumPoints];

m_numPoints = uiNumPoints;

// Just make a quick cloud of test data

for (pPt = m_pCloud; pPt < (m_pCloud+uiNumPoints); pPt++)

{

pPt->Set( (float)rand(), (float)rand(), (float)rand()); //[0-RAND_MAX]

pPt->Scale(1/(float)RAND_MAX); //[0.0, 1.0]

pPt->Scale(CLOUD_SIZE); //[0.0, CLOUD_SIZE]

pPt->Offset(-CLOUD_SIZE*0.5f); //[-HALF_CLOUD_SIZE, HALF_CLOUD_SIZE]

pPt->Scale(2.0f); //[-CLOUD_SIZE, CLOUD_SIZE]

}

return m_pCloud;

}

int main (int argc, char * const argv[])

{

CloudC *pCloud = new CloudC();

pCloud->Create(CLOUD_ELEMENTS);

printf("Min distance between any two points is %f\n",Author_Institute::GetMinDist(pCloud));

return 0;

}