JetCracker

Life-time learner's blog

Tag Archives: Programming

Constrained Cubic Spline Interpolation in Java

Representation of numeric data is a very common problem. On PC we usually use different data visualisation software from Microsoft Excel or OpenOffice Calc to more advanced utilities for charting, such as QtPlot or Origin. These apps are designed for processing of data and you can easily draw a printable scatter plot or a pie chart. But what if you need to draw a plot in your own application?

Example of charts in CardioMood

There are plenty of libraries that can draw different kinds of charts. To draw charts in the web, you might use Google Charts API, or jQuery Flot for example. In my Android app, I use GraphView and ShinobiCharts.

Spline overshoot example

Line charts look nice when they are smooth. The most popular way to make your chart look smooth is to apply a cubic spline interpolation. This type of interpolation is very common and you have it already implemented in many open source mathematic libraries. However a simple cubic spline has a few flaws.

The result function is smooth (it is actually very smooth – twice continuously differentiable), but it tends to overshoot, especially in places where you don’t expect. This is illustrated in the picture above. When we draw a line chart, we usually have some knowledge about the process we are trying to visualise. For instance, the resulting function must be monotonic, or the function value should never be negative. If this information is critical, we must use more advanced interpolation algorithms.

If the function is monotonic, in Android you can just use MonotoneCubicSpline:

import android.util.Spline;

float x[] = ...
float y[[] = ...
Spline f = Spline.createMonotoneCubicSpline(x, y);

// this will evaluate y0 = f(x0)
float y0 = f.interpolate(x0);

If we want to avoid overshoot for an arbitrary function, we should find some other interpolation algorithm. One of the methods is called Constrained Cubic Spline Interpolation. It was proposed by CJC Kruger in his article: http://www.korf.co.uk/spline.pdf

The algorithms is based on a classic cubic spline algorithm. The key step in it is the calculation of the slope (first derivative) at each point. Intuitively, the slope will be between the slopes of the adjacent straight lines (can be a mean value of the two slopes), but it also should approach zero if the slope of either line approaches zero.

Unfortunately, I couldn’t find an implementation of the algorithm in Java. That’s why I decided to implement Constrained Spline for my project.

I use Apache Commons Math library. To make the interpolation compatible with my project, I’ve overridden UnivariateInterpolator class. Here is a full code of my implementation.

import org.apache.commons.math3.analysis.interpolation.UnivariateInterpolator;
import org.apache.commons.math3.analysis.polynomials.PolynomialFunction;
import org.apache.commons.math3.analysis.polynomials.PolynomialSplineFunction;
import org.apache.commons.math3.exception.DimensionMismatchException;
import org.apache.commons.math3.exception.NonMonotonicSequenceException;
import org.apache.commons.math3.exception.NumberIsTooSmallException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
import org.apache.commons.math3.util.MathArrays;

/**
 * Constrained Spline Interpolation algorithm (CJC Kruger).
 * Source: http://www.korf.co.uk/spline.pdf
 *
 * Created by Anton Danshin on 24/12/14.
 */
public class ConstrainedSplineInterpolator implements UnivariateInterpolator {

    @Override
    public PolynomialSplineFunction interpolate(double x[], double y[])
            throws DimensionMismatchException, NumberIsTooSmallException, NonMonotonicSequenceException
    {
        if (x.length != y.length) {
            throw new DimensionMismatchException(x.length, y.length);
        }

        if (x.length < 3) {
            throw new NumberIsTooSmallException(LocalizedFormats.NUMBER_OF_POINTS,
                    x.length, 3, true);
        }

        // Number of intervals.  The number of data points is n + 1.
        final int n = x.length - 1;

        MathArrays.checkOrder(x);

        // Differences between knot points
        final double dx[] = new double[n];
        final double dy[] = new double[n];
        for (int i = 0; i < n; i++) {
            dx[i] = x[i + 1] - x[i];
            dy[i] = y[i + 1] - y[i];
        }

        final double f1[] = new double[n+1]; // F'(x[i])
        for (int i=1; i<n; i++) {
            double slope = dy[i-1]*dy[i];
            if (slope > 0d) {
                // doesn't change sign
                f1[i] = 2d / (dx[i]/dy[i] + dx[i-1]/dy[i-1]);
            } else if (slope <= 0d) {
                // changes sign
                f1[i] = 0d;
            }
        }
        f1[0] = 3d * dy[0] / (2d * (dx[0])) - f1[1]/2d;
        f1[n] = 3d * dy[n-1] / (2d * (dx[n-1])) - f1[n-1]/2d;

        // cubic spline coefficients -- a contains constants, b is linear, c quadratic, d is cubic
        final double a[] = new double[n+1];
        final double b[] = new double[n+1];
        final double c[] = new double[n+1];
        final double d[] = new double[n+1];

        for (int i = 1; i <= n; i++) {
            final double f2a = - 2d * (f1[i] + 2 * f1[i-1]) / dx[i-1] + 6d * dy[i-1] / (dx[i-1]*dx[i-1]);
            final double f2b = 2d * (2d * f1[i] + f1[i-1]) / dx[i-1] - 6d * dy[i-1] / (dx[i-1]*dx[i-1]);
            d[i] = (f2b - f2a) / (6d * dx[i-1]);
            c[i] = (x[i] * f2a - x[i-1] * f2b) / (2d * dx[i-1]);
            b[i] = (dy[i-1] -
                    c[i] * (x[i]*x[i] - x[i-1]*x[i-1]) -
                    d[i] * (x[i]*x[i]*x[i] - x[i-1]*x[i-1]*x[i-1])
            ) / dx[i-1];
            a[i] = y[i-1] - b[i]*x[i-1] - c[i]*x[i-1]*x[i-1] - d[i]*x[i-1]*x[i-1]*x[i-1];
        }

        final PolynomialFunction polynomials[] = new PolynomialFunction[n];
        final double coefficients[] = new double[4];
        for (int i = 1; i <= n; i++) {
            coefficients[0] = a[i];
            coefficients[1] = b[i];
            coefficients[2] = c[i];
            coefficients[3] = d[i];
            final double x0 = x[i-1];
            polynomials[i-1] = new PolynomialFunction(coefficients) {
                @Override
                public double value(double x) {
                    // bypass the standard Apache Commons behavior
                    return super.value(x + x0);
                }
            };
        }

        return new PolynomialSplineFunction(x, polynomials);
    }

} 

Feel free to use this in your own code! 🙂

Speedometer Gauge with Needle for Android

I am working very hard on my CardioMood app for Android.

As described in one of my previous posts, CardioMood is a health monitoring social service with a stress monitor app. It measures your stress level according to heart rate variability. It also shows a bunch of other parameters, which are represented as different kinds of charts.

Stress Index is a quantitative characteristic of your stress. Normally, the value of Stress Index varies from 50 to 150. The SI value outside of the range could be caused by a number of factors, such as physical or emotional stress, diseases (including heart diseases), and low quality of data obtained from heart rate sensor.

In CardioMood Stress Monitor app, we need to visually represent a calculated value of Stress Index – and that is another problem. I decided to use a speedometer-like gauge.

A simple way: WebView

In our measurement report screen used WebView to visually represent the result.

Android WebView supports almost all HTML and javascript features, which enables developers to render anything and use various javascript libraries already available on the net.

So, WebView gives you an easiest way to add Speedometer gauge to your android app. In our case we used a solution from Geek’s Retreat.

Their implementation is purely javascript. It has a certain number of limitations. For example, you have to specify the exact width and height of the canvas before rendering.

We had hard time with sizing and layouting components in WebView. Soon, we realized that WebView is not reliable – it’s better to use native controls than spend days on fixing issues and supporting diverse screen densities and sizes in HTML.

Hard way: Implementing Android custom view

I decided to take a bull by the horns and convinced our team to stop using WebView. After two days of working, I finally created SpeedometerView – a simple speedometer with needle gauge for Android. It looks similar to it’s javascript brother and has the same features.

CardioMood SpeedometerView in action

Supported features:

  • Major and minor tick marks
  • Custom labels
  • Colored value ranges
  • Animation of arrow (requires Android API level 11+)

Download

Check out a GitHub repo to see source code, release binary and usage example.

UPD: The component was moved to AndroidWidgets library.

GitHub: https://github.com/ntoskrnl/AndroidWidgets

Screenshot of CardioMood with SpeedometerView

Feel free to comment, request features or report bugs.

[Java] [Glassfish 3] Wrong character encoding in multipart servlet request

Hello!

It’s been a long time since I posted here, but I’m currently very busy with my study, work and projects.
Recently we had a problem with processing multipart HTTP requests in Java servlet. We are using Glassfish 3.1.1 as application server. The thing is despite of the fact that HTTP request had UTF-8 encoding, all string data actually were in ISO-8859-1 (a.k.a. ISO-LATIN-1).

I tried several different approaches to set encoding to UTF-8… until I came across the following: http://java.net/jira/browse/GLASSFISH-18516. As I understood, It says that there is a known issue in Glassfish 3.1.2 with incorrect interpretation of character encoding of multipart HTTP request parameters. Instead of UTF-8 it applies ISO-8859-1 ignoring settings in configuration files (web.xml, glassfish-web.xml) and in HTTP request. Turns out, this issue also affects Glassfish 3.1.1, which is used in our project.

Read more of this post

[MPI] Calculating integral in parallel

Problem: write a programme to calculate the integral with MPI:

Actually, the programme must be able to calculate any integral. But before writing a parallel programme, we should write a serial one to make sure it works and the algorithm is correct.

There are plenty of algorithms for calculating integrals. One of the most advanced (efficient), among non-parallel, is the method of local stack. Read more of this post

[MPI] Solving the advection equation in parallel

In chemistry, engineering and earth sciences, advection is a transport mechanism of a substance or conserved property by a fluid due to the fluid’s bulk motion.

Mathematics describes the process of advection with the advection equation:

\frac{\partial\psi}{\partial t}+\nabla\cdot\left(\psi{\bold u}\right)=0

In my course on Parallel programming, I had to implement a solution to a particular advection equation, with  the initial and boundary conditions defined. Read more of this post

The Magic of 42

Hi there!

It’s been quite a long time since I posted here (more than one month). Honestly, I was really busy and there were some problems with the Internet in my dorm.

The month was full of events!

Firstly, I got a position of software engineer (intern) in NetCracker in department Solution Delivery. Secondly, we almost finished with the first release of Reshaka.Ru which is currently being tested. In addition, we moved to another room at the dormitory. I changed my roommates – now they all programmers and my friends too. Some time I will tell you more about all these events. But now let’s get down to business!

Read more of this post

PHP: Syntax highlighting with GeSHi

One day I needed to add some source code examples to the web-site. But there was no features for highlighting syntax. I decided to create my own tool for highlighting source code. Here I will show you how to do it using PHP with GeSHi. Read more of this post

MPI: Calculating sum 1/n! in parallel

Hello.
I’ve spend several hours to understand how to programme in MPI and how to calculate the sum of 1/n! in parallel (it’s my task from university). (By the way, why do I have study this shit? I don’t think I will be working in the field of parallel/distributed computing.)

But finally I wrote a decent programme, which showed not bad results. And I am very excited to share with you! Read more of this post

[My old trash] Resizing images in Delphi.

Hello!

A hundred years ago I was working on a PHP web site. I needed to place there a lot of images but all of them have different resolutions and sizes. For example, pictures from photo camera were very heavy (~ 5 Mb) and maximum file size that was allowed on the hosting was 3 Mb. So, before placing those photos to my hosting I needed to scale them down so that they met the limits.

You might have suggested using a PhotoShop or anything like that to get this job done. But I didn’t have the money to use this software (actually, I still don’t have). There were also a lot of free photo editors, which provided the function to scale images in bulk, but they were too overloaded and not so handy. Besides, I was very curious about how to make such a tool that would solve my problem.

Here I’m going to show you how to create a tool in Delphi that will automatically scale all images (only jpeg) in the directory that you specify. Why Delphi? Simply because it was the only programming language I was good enough at. Read more of this post

Learn programming to solve real problems!

Cute Hacker Girl

Don’t learn to program.  Learn to program the sexy way.

View original post