How to randomly choose sample points that maximize space occupation?

Question

I would like to generate the sample points that can randomly fill/cover a space (like in the attached image). I think they have a method called "Quasi-random" that can generate such sample points. However, it's a little bit far from my knowledge. Can someone make suggestions or help me find a library that can be do this? Or suggest how to start writing such a program?

In the image, 256 sample points are applied on the given space, placed at random positions to cover the whole given space.

Update: I just try to use some code from Halton Quasi-random Sequence and compare with the result of pseudo-random which is post by friend below. The result of Halton's method is more better in my opinion. I would like to share some result as below;

The code which I wrote is

#include "halton.hpp"
#include "opencv2/opencv.hpp"
int main()
{
    int m_dim_num = 2;
    int m_n = 50;
    int m_seed[2], m_leap[2], m_base[2];
    double m_r[100];
    for (int i = 0; i < m_dim_num; i++)
    {
        m_seed[i] = 0;
        m_leap[i] = 1;
        m_base[i] = 2+i;
    }

    cv::Mat out(100, 100, CV_8UC1);
    i4_to_halton_sequence( m_dim_num, m_n, 0, m_seed, m_leap, m_base, m_r);

    int displaced = 100;
    for (int i = 0; i < 100; i=i+2)
    {
        cv::circle(out, cv::Point2d((m_r[i])*displaced, (m_r[i+1])*displaced), 1, cv::Scalar(0, 255, 0), 1, 8, 0);
    }
    cv::imshow("test", out);
    cv::waitKey(0);

    return 0;
}

As I little bit familiar with OpenCV, I wrote this code by plot on the matrix of OpenCV (Mat). The "i4_to_halton_sequence()" is the function from the library that I mentioned above.

The result is not better, but might be use in somehow for my work. Someone have another idea?

Answer 1

I am going to give an answer that will seem half-assed. However, this topic has been studied extensively in the literature, so I will just refer you to some summaries from Wikipedia and other places online.

What you want is also called low-discrepancy sequence (or quasi-random, as you pointed out). You can read more about it here: http://en.wikipedia.org/wiki/Low-discrepancy_sequence. It's useful for a number of things, which includes numerical integration and, more recently, simulating retinal ganglion mosaic.

There are many ways to generate low-discrepancy sequences (or pseudo quasi random sequences :p). Some of these are in ACM Collected Algorithms (http://www.netlib.org/toms/index.html).

The most common of which, I think, is called Sobol sequence (algorithm 659 from the ACM thing). You can get some details on this here: http://en.wikipedia.org/wiki/Sobol_sequence

For the most part, unless you are really into it, that stuff looks pretty scary. For quick result, I would use GNU's GSL (GNU Scientific Library): http://www.gnu.org/software/gsl/

This library includes code to generate quasi-random sequences (http://www.gnu.org/software/gsl/manual/html_node/Quasi_002dRandom-Sequences.html) including Sobol sequence (http://www.gnu.org/software/gsl/manual/html_node/Quasi_002drandom-number-generator-examples.html).

If you're still stuck, I can paste some code here, but you're better off digging into GSL.

Answer 2

Well here's another way to do quasi-random that covers the entire space.

Since you have 256 points to use, you can start by plotting those points as a 16x16 grid.

Then apply some function that give some random offset to each point (say 0 to ±2 to the points' x and y coordinates).