//http://forum.unity3d.com/threads/144235-A-Fast-KD-Tree-or-Unity-Alternative
//All rights reserved. Copyright NPSF3000 2012  Attribution Required.

//  I think I have enough data to give an example of how I'd tackle the problem.
//  This is written as a console application in VS because it has a few more features
//  and niceties to reduce my prototyping time.  Feel free to use it as a console app,
//  or port it unity or even windows forms!

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;

namespace TextureFromPoints3
{
    class Program
    {
        const int numSensors = 70000;
        const int textureSize = 1024;
        const int intervals = 0;

        static Random rnd = new Random();

        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("Starting");
                Console.WriteLine();

                var swTotalTime = Stopwatch.StartNew();

                //Step one: get the raw data:
                var sensors = GetData();

                //Step two: put sensors into a searchable collection.
                //I built my own to keep things simple.
                //Of course, it's not well tested.
                var spacialhash = new SimpleSpacialCollection(textureSize, 1);
                foreach (var sensor in sensors) spacialhash.AddSensor(sensor);

                //Now let's map each 'pixel' to a sensor;
                //This basic mapping takes about 0.5 seconds.
                Sensor[,] sensorTexture = new Sensor[textureSize, textureSize];
                var sw = Stopwatch.StartNew();
                for (int x = 0; x < textureSize; x++)
                    for (int y = 0; y < textureSize; y++)
                        sensorTexture[x, y] = spacialhash.GetNearest(x, y);
                sw.Stop();
                Console.WriteLine("Mapped {0} sensors to {1}x{1} pixels in {2}ms", numSensors, textureSize, sw.ElapsedMilliseconds);

                //Now let's generate each texture
                //We use System.Drawing for this - though U3D's Texture2D class should have similar features.
                //This takes about 0.85s an image.
                var textures = new Bitmap[intervals];
                for (int i = 0; i < intervals; i++)
                {
                    var sw1 = Stopwatch.StartNew();
                    var bmp = new Bitmap(textureSize, textureSize);
                    for (int x = 0; x < textureSize; x++)
                        for (int y = 0; y < textureSize; y++)
                        {
                            var sensor = sensorTexture[x, y];
                            bmp.SetPixel(x, y, Color.FromArgb((int)(255 * sensor.data[i]), (int)(255 * sensor.data[i]), (int)(255 * sensor.data[i])));
                        }
                    textures[i] = bmp;
                    sw1.Stop();
                    Console.WriteLine("Created Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
                }

                //Now let us save each image.
                //This takes around 0.02s - though I am on a SSD.
                for (int i = 0; i < intervals; i++)
                {
                    var sw1 = Stopwatch.StartNew();
                    new Bitmap(textures[i]).Save("C:\\" + i + ".png", ImageFormat.Png);
                    Console.WriteLine("Saved Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
                }

                swTotalTime.Stop();

                Console.WriteLine();
                Console.WriteLine("All finished in {0}ms", swTotalTime.ElapsedMilliseconds);
                Console.ReadLine();

                //And that's everything IIRC?
                //Unless theres a major change, I've taken your '30 hours' for 200 textures and 
                //Changed it into:
                //0.5 + (0.8+0.08)*n = 0.5 + (0.85+0.08)*200 = 186.5s
                //Tested and I completed in 188.7ms - and that includes gererating the test data and spacial hash! :P

                //It's late so I'll leave multithreading for tomorrow.
                //It's pretty trvial in .Net, but the libraries I use aren't available in U3D IIRC.

                //Thanks for all the fish.
            }
        }

        private static Sensor[] GetData()
        {
            //  I don't care how you manage it, but I figure you need a sensor
            //  that has a 2d position [corrisponding with the texture co-ords]
            //  and has a array of values that shows teh sensor's value every interval.
            //  So I faked itL
            var sensors = new Sensor[numSensors];

            for (int i = 0; i < numSensors; i++)
            {
                var sensor = new Sensor();
                sensor.position = new Vector2(textureSize);
                sensor.data = Enumerable.Range(0, intervals).Select(_ => (float)rnd.NextDouble()).ToArray();
                sensors[i] = sensor;
            }
            return sensors;
        }

        /* private static bool CheckResults(Vector2[,] lhs, Vector2[,] rhs)
         {
             for (int x = 0; x < textureSize; x++)
                 for (int y = 0; y < textureSize; y++)
                     if (!lhs[x, y].Equals(rhs[x, y]))
                         return false;
             return true;
         }*/

        public struct Sensor
        {
            public Vector2 position;
            public float[] data;
        }

        public struct Vector2
        {
            public float x;
            public float y;

            public Vector2(float x, float y)
            {
                this.x = x;
                this.y = y;
            }

            public Vector2(float randomDistance)
            {
                this.x = (float)rnd.NextDouble() * randomDistance;
                this.y = (float)rnd.NextDouble() * randomDistance;
            }

            public static Vector2 operator -(Vector2 a, Vector2 b)
            {
                return new Vector2(a.x - b.x, a.y - b.y);
            }

            public float sqrMagnitude()
            {
                return x * x + y * y;
            }

            public float sqrDistanceToPoint(Vector2 point)
            {
                var x = this.x - point.x;
                var y = this.y - point.y;
                return x * x + y * y;
            }
        }

        public class SimpleSpacialCollection
        {
            List<Sensor>[,] buckets;
            int bounds;
            int hash;

            public SimpleSpacialCollection(int bounds, int hash)
            {
                this.bounds = bounds;
                this.hash = hash;
                buckets = new List<Sensor>[bounds / hash + 1, bounds / hash + 1];
            }

            public void AddSensor(Sensor sensor)
            {
                GetBucket(sensor.position).Add(sensor);
            }

            List<Sensor> GetBucket(Vector2 v2)
            {
                return GetBucket((int)v2.x, (int)v2.y);
            }

            List<Sensor> GetBucket(int x, int y)
            {
                var bucket = buckets[x / hash, y / hash];
                if (bucket == null)
                {
                    bucket = new List<Sensor>();
                    buckets[x / hash, y / hash] = bucket;
                }
                return bucket;
            }

            public Sensor GetNearest(int pointX, int pointY)
            {
                var candidates = new List<Sensor>();

                int maxX, minX, maxY, minY;

                maxX = minX = pointX / hash;
                maxY = minY = pointY / hash;

                do
                {
                    maxX++; maxY++; minX--; minY--;

                    if (minX < 0) minX = 0;
                    if (minY < 0) minY = 0;
                    if (maxX > buckets.GetLength(0)) maxX = buckets.GetLength(0);
                    if (maxY > buckets.GetLength(1)) maxY = buckets.GetLength(1);

                    for (int x = minX; x < maxX; x++)
                        for (int y = minY; y < maxY; y++)
                        {
                            var bucket = buckets[x, y];
                            if (bucket != null) candidates.AddRange(bucket);
                        }
                } while (candidates.Count == 0);  //Potential Infinite Loop.

                var point = new Vector2(pointX, pointY);

                Sensor nearest = candidates[0];
                float nearestDistance = nearest.position.sqrDistanceToPoint(point);

                for (int i = 1; i < candidates.Count; i++)
                {
                    var candidate = candidates[i];
                    if (candidate.position.sqrDistanceToPoint(point) < nearestDistance)
                    {
                        nearest = candidate;
                        nearestDistance = candidate.position.sqrDistanceToPoint(point);
                    }
                }
                return nearest;
            }
        }
    }
}