Software Programming

Kunuk Nykjaer

Archive for the ‘Visualization’ Category

Favorite material design button with or without JS

leave a comment »

I am having fun creating things at Codepen.io.

I have created a toggle button with JS and without using JS.
For the non-JS version I used the radio-button hack technique with stacked radio buttons.

Without JS

 

With JS

Advertisements

Written by kunuk Nykjaer

March 10, 2016 at 4:57 pm

Posted in Css, Javascript, Visualization

Tagged with

Being creative – Making logos with css

leave a comment »

My latest hobby is to find logos as images and re-create them with css and responsive design.
I have added mouse over effects to make the logos dynamic.
You can resize the width of the browser window and you should see the logos adapts to the screen width.

Build for modern browsers, tested with latest Chrome and Firefox
(I don’t want to spend too much time with browser-testing in my leisure time).

Here are some of the results.

Written by kunuk Nykjaer

April 4, 2015 at 10:15 pm

Posted in Css, Visualization

Tagged with ,

From json data to responsive design example

leave a comment »

Synopsis:

Somebody (your boss or customer) comes to you and says:
‘Create a web page which displays this data and the design must be responsive. I will give you a REST API to a service.’

If you work with front-end tasks, you probably would now be thinking JavaScript templating, Media queries and a JavasScript library to work with the REST API (maybe jQuery?).

In my previous blog I gave hello world code demo of Handlebars. I will continue with Handlebars and this time use data from an external source and also think in responsive design.

All these wonders (freely) available in the Internet available. I Use:

  • WordPress.com for blogging
  • Gist for sharing code samples
  • Codepen.io for making web page prototypes
  • Various Javascript libraries to help me ‘get the job done’


For this example I will use.


 

Demo

Try to resize the screen width and see how the content adapts.


 

Data structure

This is the given data source structure which is to be parsed and rendered on a web page. A list of news with title, date, link, author and categories.


 

Styling

Mobile first approach. Style for smallest device first and gradually adjust the styling for the larger devices. The breakpoint sizes are the same as used in the Bootstrap 3 framework.

Literally make your browser the same width as the smallest device. Start the styling with that size. You will notice there are not much space. Usually that means you use all the width space available and stack the items below each other. You focus on the the essential which is (usually) the content. You hide or minimize navigational items, minimize images, cut part of content or designs which are less important.
For the increasing screen sizes the items can be aligned horizontally and there are more rooms for adding ’empty’ spaces, larger images, bigger menus. That’s the usual approach.

As you go up in screen size override the styling. Here I have added debug information of the target device.
e.g.

#rendered .title::after {
    content: ' - Phone';
}

I start with 100% width (default value). As the devices increases the text size increases and the width percentage reduces.


 

Markup

This is more or less the same as my Helloworld example. The markup is the template.


 

Scripting

Here I fetch the data and parse it to the template and add a couple of Handlebars formatter helpers. In case something goes wrong I use stub data to render the display.

 

Written by kunuk Nykjaer

January 10, 2015 at 10:32 pm

Lego Kaizen at work

leave a comment »

I have been working a couple of years now using agile methodologies (Scrum).

I started in a new team recently where they use the Scrum methodology.

The team works in the spirit of agile mindset and is constantly finding small improvements. Besides the daily scrum tasks we have the flexibility to take upon Kaizen tasks with the purpose of improving the daily workflow which are not necessarily related to the user stories.

The next thing recently just introduced are the ability to flag your current mode at your desk.

  • Green – Available if you have questions or want help
  • Yellow – Only contact me if it is important
  • Red – Busy at the moment

You take a lego piece and display your current mode.
lego

With this hopefully the team can be more effective where communications is directed at those available and the busy ones have ability to flag that they want to be left alone to complete their tasks without being disturbed.

Written by kunuk Nykjaer

February 17, 2014 at 10:38 pm

Posted in Visualization

Tagged with ,

K-nearest neighbor in 2D dimension space

with 3 comments

K-nearest neighbor

There are miscellaneous algorithms for searching nearest neighbors.

An alternative method is to use grid indexing strategy.
Slowly expand the grid boxes from the center to find the k-nearest neighbors.
The grid is used as a filtering mechanism to reduce the search space.

This works fast for distributed data across the space and is a good alternative algorithm for dynamic data that changes position frequently.

Reference links:

Project implemented in C# is available at Github:
A survey of techniques for fixed radius near neighbor searching:

knn

The origin is in ring 0.
The origin can anywhere in the box and the distance to test on first iteration must be at least 1 x grid distance. The first iteration starts with data from ring 0 and 1.

The algorithm goes like this:

i = 0
Point origin
list currRing = empty
list nextRing = empty
list temp
while all rings not explored
   i = i + 1
   temp = empty
   for all point in nextRing test distance between origin and point
       if distance is within i * grid put it in currRing
       else put it in temp

   nextRing = empty
   Add all from temp to nextRing

   temp = empty
   if(i==1) temp = points from ring 0 and ring 1
   else temp = points from ring i

   For all point in temp test distance between origin and point
       if distance is within i * grid put it in currRing
       else put it in nextRing

   If there are at least k points in currRing then exit while loop
end while loop

if currRing count is < k then add all from nextRing to currRing

sort currRing by distance
take first k from currRing


knn example

Grid version algorithm:
Apply algorithm described above.
Searching: O(n * m) where m is grid cells and k << n.

Naive version algorithm:
For origin point check the distance to every other point.
Take k first items sorted by distance.
Searching: O(n log n)

Written by kunuk Nykjaer

January 21, 2013 at 9:36 pm

Single detection in 2D dimension

leave a comment »

Single detection

Here I define single detection as data which has a certain minimum distance to every other data.
It can be used for anomaly detection or outlier detection of data set. It can also be used for collision detection.

Reference links:

Project implemented in C# is available at Github:
A survey of techniques for fixed radius near neighbor searching:

Given a list of points in 2D dimension how can you find the ones which are not close to the other points?

I will include my Big O notation calculations and some test runs of the implementations.

There is a naive implementation in O(n2).
There are also better alternatives which runs faster than the naive version.

First generate a grid of squares like this and put all your data in the grid according to their positions in the dimension.

grid layout

In the figure above there is a single item illustrated with a red dot inside the blue box.

For anomaly detection iterate the grid boxes and find those which has a single item inside a box. Those items are candidate as an anomaly item. If there are multiple items inside the blue box then it cannot be a candidate as an anomaly item because of the distance constraint. The candidate can be anywhere inside the box, thus the outer circle shows which areas that must be examined. If there is no other item inside the outer circle, then we know the candidate is an anomaly. On worst case 20 boxes must be examined as illustrated above.


Euclidean distance
is used.
The relation between the max distance and grid square distance can be calculated using Pythagoras.
Max Distance = c
Grid box distance = a

c2 = a2 + a2 => a = sqrt( (c2) / 2)

Naive version algorithm:
For all the points check the distance to every other point.
Searching: O(n2)

Grid version algorithm:
Insert all the items in the grid buckets.
Take the neighbor items of the candidate item’s grid. You will select items from 20 boxes as a worst case. Then iterate all the items and test the distance. If all the distance are above the maximum allowed then the candidate is detected as an anomaly.

This algorithm is much better than the naive version, runs very fast and is relatively simple to implement. Each grid box is a bucket of items. Use a Hash table for each bucket.
Inserting the items into the grids take O(n). Removing and inserting an item takes O(1).
Searching for anomalies take O(m * n).

If there are A anomalies in the data set and m grids this algorithm will run in:
Initialization: O(n + m) + Searching: O(m * A * n/A) => O(m * n)

K-d tree with nearest neighbor algorithm:
Insert all the items in the grid buckets takes O(n).
Do also apply a K-d tree data structure. From the candidate item’s in the box apply the first nearest neighbor algorithm. If the distance is above maximum allowed then it is detected as an anomaly.

It take O(n log n) time to generate the K-d tree. The nearest neighbor search takes
O(log n).
Removing and inserting an item takes O(log n). If there are A anomalies in the data set and m grids then searching for anomalies take O(m * A * log n).

This algorithm will run in:
initialization: O(m + n * log n) + Searching: O(m * A * log n)

Test results
With my test runs of items randomly distributed data the grid version performs best. The naive version is very slow. The K-d Tree version is much faster than the naive version.

I found this C# K-d Tree implementation with nearest neighbor search which I used for testing the algorithm.

Sample picture:
test result


The test runs are the time to detect the anomalies, the searching running time.
The data structure initialization is not included.
For n = 1.000.000.
K-d Tree it took about 30 seconds.
Grid and Naive about 2 seconds.

Random distributed, n = 100
Algorithm:     Milli seconds:   Single detection found:
NeighborGrid       12                   40
K-d Tree          128                   40
Naive               2                   40


Random distributed, n = 10.000
Algorithm:     Milli seconds:   Single detection found:
NeighborGrid       141                  8384
K-d Tree          2543                  8384
Naive            36421                  8384


Random distributed, n = 20.000
Grid: 4286 x 3572
MaxDistance: 0.2

Algorithm:     Milli seconds:   Single detection found:
NeighborGrid       1434                   18682
K-d Tree           5878                   18682
Naive             129401                  18682


Random distributed, n = 30.000
Grid: 1705 x 1421
MaxDistance: 0.5

Algorithm:     Milli seconds:   Single detection found:
NeighborGrid        521                     27100
K-d Tree            7936                    27100
Naive               slow                  


grid size is smaller thus the NeighborGrid runs fast.


Random distributed, n = 50.000
Grid: 4286 x 3572
MaxDistance: 0.2

Algorithm:     Milli seconds:   Single detection found:
NeighborGrid        1472                   42268
K-d Tree           13361                   42268
Naive              very slow                  


Random distributed, n = 1.000.000
Grid: 1705 x 1421
MaxDistance: 0.5

Algorithm:     Milli seconds:   Single detection found:
NeighborGrid           983              35824
K-d Tree             23966              35824
Naive              forever                  


Conclusion
These are just sample runs from random distributed data.
If the number of anomalies were very high and the data set were different then the K-d Tree algorithm might run faster. I would guess that the data set would have to be very specific and not likely to be a common scenario. I have given my best estimated Big O running time analysis for the algorithms.

The algorithm runs fast because of the single item grid box test. First they iterate the grid and skip every grid box except for those who has a single item inside. If you expect few anomalies for large data set then this would run very fast because most grid boxes would be skipped for further examination. Thus the running time for anomaly search is closer to O(m) for A << n.

If you are working with dynamic data where positions changes, then the Grid algorithm will run faster because of the O(1) operations. With K-d tree you will have to rebuild the tree occasionally and delete/update takes O(log n).

Sample picture for n = 100
test result

Written by kunuk Nykjaer

January 13, 2013 at 8:14 am

Percent distribution of numbers with C#

leave a comment »

You have a list of n integers and you want to display the percentage distribution of the values.
The requirement:
You must round the numbers such the percent sum is 100 and the percent values must be integer values.
The percent values must be fair distributed according to the values.

How would you do it?
If you calculate the distribution and round the numbers the sum might not be equal to 100.

Here is one way to do it.

program.cs (algorithm)

 
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

class Program
{
    const string DrawFilePath = @"C:\temp\";

    static void Main(string[] args)
    {
        // Insert test data here
        var list = new List<int> { 30, 70, 10, 90 };

        var result = GetValuesMapped(list);
        GenerateJavascriptDrawFile(result);

        Console.WriteLine("Open canvas.html to watch the result\npress a key to exit ..");
        Console.ReadKey();
    }

    static List<Data> GetValuesMapped(List<int> list)
    {
        const int MAPTO = 100; // 100 %
        const int min = 0;
        const int max = 10000;

        var mapped = new List<MapData>();
        var noresult = new Data[list.Count].ToList();
        double sumList = list.Sum();

        // No value
        if (sumList <= 0)
        {
            return noresult;
        }

        // Sanitize data
        for (int i = 0; i < list.Count; i++)
        {
            if (list[i] < min) { list[i] = min; }
            if (list[i] > max) { list[i] = max; }
        }

        // Map data
        int id = 0;
        foreach (var i in list)
        {
            var percent = Map(i, 0, sumList, 0, MAPTO);
            mapped.Add(new MapData
            {
                Id = id++,
                Modulus = percent - Math.Truncate(percent),
                Divisor = (int)percent
            });
        }

        // Adjustment is needed
        // Iterate increment by 1 until sum is correct

        // sort by decimal values
        var sorted = mapped.OrderByDescending(i => i.Modulus).ToList(); 
        int sumFloor = mapped.Sum(i => i.Divisor);

        int addsNeeded = MAPTO - sumFloor;

        // Add need values until
        for (int i = 0; i < addsNeeded; i++)
        {
            sorted[i % sorted.Count].Divisor++;
        }

        // Sort back by id
        var ordered = sorted.OrderBy(i => i.Id).ToList();

        // Populate data
        var result = list.Select((t, i) => 
            new Data { Value = t, Percent = ordered[i].Divisor }).ToList();

        return result;
    }

    internal class MapData
    {
        public int Id { get; set; }
        public double Modulus { get; set; }
        public int Divisor { get; set; }
    }

    internal class Data
    {
        public int Value { get; set; }
        public int Percent { get; set; }
    }

    /// <summary>        
    /// Value x in range [a;b] is mapped to a new value in range [c;d]
    /// </summary>                
    static double Map(double x, double a, double b, double c, double d)
    {
        var r = (x - a) / (b - a) * (d - c) + c;
        return r;
    }

    internal static class FileUtil
    {
        public static void WriteFile(string data, FileInfo fileInfo)
        {
            try
            {
                using (StreamWriter streamWriter = File.CreateText(fileInfo.FullName))
                {
                    streamWriter.Write(data);
                }
            }
            catch
            {
                throw;
            }
        }
    }

    // Create canvas data in draw.js file
    static void GenerateJavascriptDrawFile(List<Data> list)
    {
        var sb = new StringBuilder("function drawData(ctx) {\n");

        const int xbeg = 30; // start x coord
        const int ybeg = 100;
        const int lenMultiply = 5; // percentage length display
        const int yline = 40; // next line offset
        const int txtX = 50; // text display offset
        const int txtY = 4;
        const int colorMin = 20; // min color range
        const int colorMax = 200;
        const int topY = -70;
        const string textCount = "count";
        const string textPercent = "%";

        if (list != null && list.Count > 0)
        {
            // draw top
            sb.Append("\t// top\n");
            sb.AppendFormat("\tctx.fillText('{0}{1}', {2}, {3});\n", 
                100, textPercent, xbeg, topY + ybeg - txtY);
            sb.AppendFormat("\tdrawLine({0}, {1}, 'rgb(0,0,0)', {2}, ctx);\n", 
                xbeg, ybeg + topY, (100 * lenMultiply) + 1);

            // draw lines
            var rand = new Random();
            sb.Append("\n\t// lines\n");
            for (int i = 0; i < list.Count(); i++)
            {
                var color = string.Format("'rgb({0},{1},{2})'", 
                    rand.Next(colorMin, colorMax), rand.Next(colorMin, colorMax), rand.Next(colorMin, colorMax));
                sb.AppendFormat("\tdrawLine({0}, {1}, {2}, {3}, ctx);\n", 
                    xbeg, (ybeg + i * yline), color, (list[i].Percent * lenMultiply) + 1);
            }

            // draw text
            sb.Append("\n\t// text\n");
            sb.Append("\tctx.fillStyle = 'rgb(0,0,0)';\n");
            for (int i = 0; i < list.Count(); i++)
            {
                sb.AppendFormat("\tctx.fillText('{0}{1}', {2}, {3});\n", 
                    list[i].Percent, textPercent, xbeg, i * yline + ybeg - txtY);
                sb.AppendFormat("\tctx.fillText('{0}: {1}', {2}, {3});\n", 
                    textCount, list[i].Value, xbeg + txtX, i * yline + ybeg - txtY);
            }
        }

        sb.Append("}");
        var path = new FileInfo(string.Concat(DrawFilePath, "draw.js"));
        FileUtil.WriteFile(sb.ToString(), path);
    }
}

Put both the html and javascript file in the c:\temp folder.
The C# program creates a new draw.js file in the c:\temp folder.
Open the html file with a modern browser that support canvas, like Firefox, Chrome or Internet Explorer 10+.

canvas.html (visualization)

 
<html>
<head>
    <title>Canvas</title>    
    <script type="text/javascript" src="draw.js?v=1"></script>    
    <script type="text/javascript">                        
        function drawLine(x, y, color, len, ctx) {
            ctx.lineWidth = 2;
            ctx.strokeStyle = color;
            ctx.strokeRect(x, y, len, 2);
        }

        window.onload = function draw() {
            var canvas = document.getElementById('canvas');
            if (canvas != null && canvas != undefined && canvas.getContext) {
                var ctx = canvas.getContext('2d');
                ctx.strokeStyle = "black";
                ctx.font = "10pt Arial";
                drawData(ctx);
            }
        }
    </script>
    <style type="text/css">
        body
        {
            margin-left: 10px;
            margin-top: 10px;
        }
        canvas
        {
            border: 1px solid red;
        }
    </style>
</head>
<body>    
    <canvas id="canvas" width="600" height="400">
        <p>
Your browser doesn't support canvas. 
Try Firefox, Chrome, Internet Explorer 10+ or an another modern browser.
       </p>
    </canvas>
</body>
</html>

The javascript file will be overwritten when you run the C# code.
draw.js (data)

 
function drawData(ctx) {
	// top
	ctx.fillText('100%', 30, 26);
	drawLine(30, 30, 'rgb(0,0,0)', 501, ctx);

	// lines
	drawLine(30, 100, 'rgb(101,78,132)', 76, ctx);
	drawLine(30, 140, 'rgb(32,101,168)', 176, ctx);
	drawLine(30, 180, 'rgb(139,151,71)', 26, ctx);
	drawLine(30, 220, 'rgb(163,73,143)', 226, ctx);

	// text
	ctx.fillStyle = 'rgb(0,0,0)';
	ctx.fillText('15%', 30, 96);
	ctx.fillText('count: 30', 80, 96);
	ctx.fillText('35%', 30, 136);
	ctx.fillText('count: 70', 80, 136);
	ctx.fillText('5%', 30, 176);
	ctx.fillText('count: 10', 80, 176);
	ctx.fillText('45%', 30, 216);
	ctx.fillText('count: 90', 80, 216);
}

For the list = 30, 70, 10, 90
gives this result:

Written by kunuk Nykjaer

December 19, 2012 at 9:04 pm