Calling Java, R, C, Perl, & System Commands

May 8, 2010 by Admin · 1 Comment
Filed under: C, Java, Utility 
VN:F [1.8.8_1072]
Rating: +2 (from 2 votes)
VN:F [1.8.8_1072]
Rating: 10.0/10 (2 votes cast)

By Matt Dunham

Matlab is an extremely powerful programming environment, not least because of its support for the execution of code written in other languages, java in particular.

Contents

Useful Functions

  • system, eval
  • import, char, double, cell, struct, javaArray, methods, methodsView
  • javaAddPath, setenv, getenv,
  • actxserver, openR, closeR, evalR, getRdata, putRdata
  • mex, emlmex, assert, eml.extrinsic
  • perl

System Commands

You can execute system commands from Matlab using the system() function or, equivalently, the ! operator.

system('mspaint');                     % launch mspaint.exe, same as ! mspaint
system('echo hello world > tmp.txt');  % low level pipe to a file
system('type tmp.txt');                % low level display of a file
system('del tmp.txt');                 % delete the file
hello world

Eval

Often we do not know precisely which system commands to execute until run time. The eval() function can be very useful in these cases. Eval executes a string specified command as if it were typed at the command prompt or executed in a script or function.

While extremely powerful, it should only be used when other options have been exhausted as it can result in code that is very difficult to debug. If you want to dynamically determine which function to execute as your program runs, it is much better to pass around function handles than string names. See the section on functions for more information.

eval('a = 1+1')
a =
     2

Create 5 files tmp1.txt through tmp5.txt using low level system commands

for i=1:5
   eval(['! echo filenum: ',num2str(i),' > tmp',num2str(i),'.txt']);
end

Calling Java

To create an object of a java class, you simply need to call the constructor. You must use the fully qualified name, even for classes under java.lang, unless you first import the name space with the import() function. While you could theoretically write java code to a file, dynamically from Matlab, and call the java compiler using the ! command to create a new class, it is much more straight forward to write your classes first and simply use objects of that class within Matlab.

import java.lang.*;       % import the java.lang namespace
imports = import          % view all of the imports
%clear import             % clear all imports
S = String('hello')       % Create a java String object
A = S.substring(0,2)      % Call a method from the java.lang.String class
imports =
    'java.lang.*'
S =
hello
A =
he

Recall, that java indexes from 0, not 1 as in Matlab

I = Integer(3);            % Create a java.lang.Integer object

When the type returned by a java method is either of type java.lang.Object or a java primitive type, such as int, double, char, boolean, etc, Matlab automatically converts to a Matlab type for you. Similarly, you can pass Matlab data directly to java methods or constructors and Matlab will usually convert the data in a ‘reasonable’ way as we saw above. If you want to explicitly convert from a java type to a Matlab type, use the char() , double() , cell() , or struct() functions. To use char() , the java class must have an obj.toChar() method and to use double() ,it must have an obj.toDouble() method.

B = char(A)               % convert to a Matlab char array
C = double(I)             % convert to a Matlab double
B =
he
C =
     3

Java objects can be stored in arrays, cell arrays and structs. When you concatenate two java objects, the type of the resulting matrix is the lowest common superclass.

D = [A,I]
D =
java.lang.Object[]:
    'he'
    [ 3]

You can of course, pass java objects to the methods of other java objects.

H = java.util.HashMap();
H.put(S,I);
H.get(S)
ans =
     3

Use the javaArray() function to create a java array. Suppose we wanted a 2D array of Strings as would be created by the java code, String[][] myArray = new String[4][5];

JA = javaArray('java.lang.String',4,5)      % Create a java array of Strings
JA =
java.lang.String[][]:
 
     []     []     []     []     []
     []     []     []     []     []
     []     []     []     []     []
     []     []     []     []     []

You must specify the fully qualified name here, even if you have imported the name space.

While Java indexes from 0, when using Matlab syntax as in the following command, Matlab automatically converts for you and indexing is once again from 1.

JA(3,2) = String('hello')
K = char(JA(3,2))
JA =
java.lang.String[][]:
 
     []         []     []     []     []
     []         []     []     []     []
     []    'hello'     []     []     []
     []         []     []     []     []
 
K =
hello

Static methods can be used as well

Math.random()
ans =
    0.9604

To create objects of java classes, the classes must be on the Matlab java class path. Matlab uses both a static and dynamic path. The static path is loaded when Matlab is started and is defined in the classpath.txt file. To include classes you have written to the static path, edit this file, add the directory name containing your .class files at the bottom, and restart Matlab. They will then be available every time you load Matlab. Classes added to the dynamic path are available right away without having to restart Matlab, but are cleared when Matlab is closed. Also, using classes loaded dynamically is slightly less efficient. To add a directory to the dynamic path use the javaaddpath() function.

javaaddpath('C:\Users\matt\Desktop\javaTest');          % add a directory to the dynamic path
clear java;                                             % clear the dynamic path

The methods() and methodsview() functions can be useful for viewing the public methods of a java object’s class.

Java Example

In this example, we create simple java table

import java.lang.* javax.swing.* java.awt.*
colNames = javaArray('java.lang.String',3);              % create String array
colNames(1) = String('X');                               % add data
colNames(2) = String('Y');                               % add data
colNames(3) = String('Z');                               % add data
data = javaArray('java.lang.String',100,3);              % create String array
data(:) = String('1');                                   % add data
table = JTable(data,colNames);                           % create a new JTable
scrollPane = JScrollPane(table);                         % create a JScrollPane and add the table
frame = JFrame('Table Example');                         % create a JFrame
frame.getContentPane().add(scrollPane);                  % add the JScrollPane
frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); % Important to avoid memory leaks
frame.pack();                                            % pack the components
frame.setVisible(true);                                  % set visible
clear all; clear java;

Calling R

R is a programming environment and language similar to Matlab but containing somewhat different functionality. It can sometimes be useful to execute R code from Matlab, rather than work entirely in R or rewrite the code. Here we describe how to call R functions and obtain the results from within Matlab.

There are three approaches we can take to interface with R.

  1. Since we can execute system commands from Matlab and easily write to files, we could take a file based approach to calling R.
  2. We can bring up an R command prompt in Matlab by typing ! R –no-save at the command prompt – q() to quit – but we cannot transfer data this way.
  3. A better approach, in Windows at least, is to use the DCOM interface. Some initial configuration is required.

DCOM CONFIGURATION

  1. Install R version 2.62 or later from http://www.r-project.org/
  2. Add R.exe to the windows path.
  3. Install the RCom Server available at http://lib.stat.cmu.edu/R/CRAN/contrib/extra/dcom/RSrv250.exe
  4. Add the m-files from the link below to your Matlab path, (e.g. using pathtool), http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=5051&objectType=FILE#
  5. Reboot Matlab

You can add the R directory to your windows path for the duration of the Matlab session with the command below: alter the 2.6.2 accordingly. To add it permanently, add the directory to Control Panel -> System -> (Advanced System Settings) -> Environment Variables -> Path, or similar, depending on the version of Windows.

setenv('PATH',[getenv('PATH') ';C:\Program Files\R\R-2.6.2\bin']);

The m-files from above, openR, closeR, evalR, getRdata, putRdata, make interfacing with R easier, however, you can perform the same commands yourself as follows:

Rcon = actxserver('StatConnectorSrv.StatConnector')  % setup connection
Rcon.Init('R');                                      % open R
Rcon.Evaluate('A <- 3');                             % execute an R command, (in R memory space)
A = Rcon.GetSymbol('A')                              % import R data into Matlab
B = [1,2,3];                                         % some Matlab data
Rcon.SetSymbol('B',B);                               % export Matlab data to R
C = Rcon.Evaluate('B <- B +1')                       % execute an R command, get returned data
Rcon.Close;                                          % close connection (remember to do this!)
Rcon =
	COM.StatConnectorSrv_StatConnector
A =
     3
C =
     2     3     4

The interface can be finicky and will return highly cryptic error messages when anything goes wrong. When exporting Matlab matrices to R for example, it is sometimes necessary to create the variable in R first, assigning it a dummy scalar value.

R Example

Here we demonstrate how to use the openR, closeR, evalR, getRdata, and putRdata files. We attempt to classify data using R’s randomForest function. The R randomForest package must first be installed in R by going to packages -> install Packages -> (choose a server) -> randomForest

rand('twister',1);                       % seed rand num generator
load fisherIris                          % builtin dataset
[j,j,species] = unique(species);         % convert to numeric class labels instead of strings
ntrain  = 120;                           % number of training cases to use
ntest   = 30;                            % number of test cases to use
perm   = randperm(size(meas,1)        ); % randomly divide data into training and test sets
Xtrain = meas    (perm(1:ntrain    ),:);
Xtest  = meas    (perm(ntrain+1:end),:);
ytrain = species (perm(1:ntrain    ),:);
ytest  = species (perm(ntrain+1:end),:);
openR;                                % open the R connection
evalR('library(randomForest)');       % load the already installed randomForest package
putRdata('Xtrain',Xtrain);            % export the Matlab data to R
evalR('Xtrain <- data.frame(Xtrain)') % randomForest expects an R data frame, create it.
putRdata('ytrain',ytrain);            % export to R
evalR('ytrain <- data.frame(ytrain)');% build frame
putRdata('Xtest',Xtest);              % export to R
evalR('Xtest <- data.frame(Xtest)');  % build frame

Here we call the actual randomForest function in R and ask the constructed forest to predict the class labels given the training data.

evalR('rf <- randomForest(Xtrain[1:120,],ytrain[1:120,])');
evalR('yhat <- predict(rf,Xtest[1:30,])');
yhat = getRdata('yhat');                     % import the predictions into Matlab
closeR;                                      % close the R connection
numWrong = sum(round(yhat') ~= ytest)        % How many, out of 30, did it get wrong?
numWrong =
     1

Note, the R random forest function performed regression here not classification so we round the results to approximate the class labels.

Calling C, C++, Fortran

Matlab can be extremely fast if you are able to vectorize the code, but when you are faced with loops, executing many many times, Matlab code can be prohibitively slow. It is sometimes necessary, for the sake of speed, to write certain time intensive parts of a Matlab application in a low level language like C. Unfortunately, the process of interfacing with C, C++ and Fortran can be somewhat complicated. We explain here, how to write a simple C function and make it work in Matlab. For more detailed information consult the online documentation at http://www.mathworks.com/access/helpdesk/help/techdoc/matlab.html

We use the mex() function to compile C code for use in Matlab but we must first add the required components to the C source file itself. We import the mex library, which gives us access to various error checking and matrix creation utilities in C.

  1. type mex – setup and follow the simple instructions to setup the compiler.
  2. start writing your C function and include the line #include “mex.h”
  3. add a Matlab mex gateway function with the definition given below. This function will be called when you execute the function from within Matlab.
  4. perform any error checking in the gateway function, setup the output parameters using say the mxCreateDoubleMatrix function available from mex.h. and call out to whatever function does the real work.
  5. save the C file and make sure its on the Matlab path
  6. type mex filename.C at the Matlab command prompt to compile the function, creating, (in windows at least) a file called filename.mexw32. The extension differs in different operating systems.
  7. call the function as you would any other Matlab function.

To see an example, check out C:\Program Files\MATLAB\R2008a\extern\examples\mex\yprime.c (replace 2008a with your version of Matlab)

The gateway function must have the following definition:

void mexFunction(int nlhs, mxArray *plhs[],int nrhs, const mxArray*prhs[])

  • nlhs is the number of output arguments
  • nrhs is the number of input arguments
  • plhs is a pointer array to mxArrays created using the mxCreateDoubleMatrix function
  • prhs is a pointer array of mxArrays passed from Matlab

For information on mxCreateDoubleMatrix and other related functions go to help -> contents -> Matlab -> C and Fortran API Reference

Using emlmex for Increased Speed

In a certain restricted set of cases, we can compile Matlab m-code to C, for use within Matlab, improving speed. The compiler function is emlmex() and as above, it creates a mexw32 file. As long as this file is on the path, it shadows the original m-code function and is called in its place. The compiler is designed to produce embedded code and compiles functions that do not require any dynamic memory. Such code is extremely fast but requires that the type and size of all of the variables be pre-declared at compile time. This is quite a strong precondition; when it cannot be met, consider the previous approach, or try compiling in ‘real time’ as described below. The mex compiler must be first setup by following step one of the previous section.

Note that emlmex() is only available if you have either the simulink or fixed-point toolboxes installed.

emlmex() does not support, cell arrays, objects, sparse matrices, try/catch blocks, nested functions, matrix element deletion, variables that change size or type, and java.

Matlab is usually able to automatically infer the type and size of variables used. Sometimes, however, the assert() function must be used.

m = ones(3,3);                      % suppose this data is passed to the function.
assert(isa(m,'double'));            % declare the type
assert(all (size(m) == [3 3]));     % declare the size

Alternatively, the size and type of the input variables can be specified at compile time using the -eg switch. Here we compile LassoShootingFast(X,y,lambda,w0) available here:

LassoShootingFast.m

  • X is 1000-by-16,
  • y is 1000-by-1,
  • lambda is 1-by-1,
  • w0 is 16-by-1.
emlmex('LassoShootingFast','-eg','{zeros(1000,16),zeros(1000,1),0,zeros(16,1)}');

We could also parameterize the dimensions as follows:

n = 1000; d = 16;
emlmex('LassoShootingFast','-eg',[' {zeros(',num2str(n),',',num2str(d),'),zeros(',num2str(n),',1),0,zeros(',num2str(d),',1)}']);

We can call the compiler using the above syntax within another parent function and have it determine the size of the inputs as it runs, before it compiles the subfunction. This gives us the flexibility of determining the input sizes at run time but the speed of a compiled subfunction. However, compilation can take a few seconds and so you must be sure that the gain obtained from compilation outweighs the overhead. Use the tic() and toc() functions to time your code both ways and compare.

Moreover, compilation is only likely to speed up a function if it contains loops and executes a sufficiently large, (i.e. time consuming) chunk of code. It will not reduce the asymptotic running time of your algorithm and writing emlmex complaint code can be a tedious process; be sure its both possible and worth the effort before you begin. In the case of LassoShootingFast, however, compiling the function did result in code that was about 10 to 100 times faster.

If the m-file to be compiled calls additional functions, emlmex() tries to compile these as well unless they are first declared extrinsic with the command

eml.extrinsic('myFunction');

A final note, include the following comment as the first line below the function header: %#eml. This tells affects the warning messages displayed in the editor.

Calling Perl

Perl scripts can be run using the perl() function.

fid = fopen('hello.pl','w');
fprintf(fid,'$input = $ARGV[0];\nprint "Hello $input.";');
fclose(fid);
perl('hello.pl','World')
ans =
Hello World.

Exporting Matlab Code

Matlab code can be exported as a stand-alone application or as a shared library for use in Excel, java, C, C++, or .NET applications using the deployment graphical interface – launched by typing deploytool at the command prompt. Such code depends on the freely available Matlab Compiler Runtime, (MCR), which can be optionally included when using deploytool. Thus, code that you write in Matlab can be distributed and used by users who do not have Matlab installed, or used inside of larger applications. Furthermore, deployed code is encrypted and thus protected should you not wish to make it open-source.

VN:F [1.8.8_1072]
Rating: 10.0/10 (2 votes cast)
VN:F [1.8.8_1072]
Rating: +2 (from 2 votes)

Popularity: 1% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

The fastest way to sort N numbers: sortN library

March 22, 2010 by Luigi Giaccari · Leave a Comment
Filed under: Algorithms, C, Code Optimization 
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)
VN:F [1.8.8_1072]
Rating: 10.0/10 (1 vote cast)

 

Have you ever thought about the fastest way to sort N numbers?

Last week I wrote a post about the fastest way to sort 3 numbers, this week I show you a tricky way to optimize the sort of N numbers.

The problem of sorting an array of numbers is probably the most studied in computer science. The efficiency of a sort algorithm depends essentially on the number of comparisons and swaps it needs to reach the solution. This post  contains an optimized sort algorithm for small buckets (to my knowledge the fastest).

Currently most of sorting algorithms uses quick sort for large buckets and insertion sort for smaller ones. Both these algorithms uses an optimized way to swaps and compare numbers. The sortN library is a further optimization of this operations. It does first all the needed comparisons and then, only in the end, it swaps values to reach the sorted solution only in the end. It is in practice an enhanced Insertion sort algorithm.

The sortN library

The library is written in C++, but it can be written in any code, and supports arrays up to 7 elements. It can be applied , in theory, to array of any size but we will see this can not be realized in practice, only small arrays can be sorted.

The sortN libary can be considered enhanced insertion sort algorithm.

It contains a list of optimized function to sort 3,4,5,6,7 values. Each function is optimized to sort an N number of values.

Here is the approach to the solution:

N numbers can be disposed in Nc combinations where Nc is N!.

We may think to write a recursive code that reach the sorted solution in the way algorithms for permutations does.

The permutations represents all the possible solutions, depending on the value of each comparison (between 2 values of the array) a permutation is chosen or refused.

This allows, depending on the results of the comparisons, to build a decisionary tree that unequivocally leads to the permutation that represents the solution. Once we know the solution we can optimize swaps to reach it.

Notice that no swaps must be done done before we know the exact solution. This can be considered an enhanced insertion sort algorithm.

The number of comparisons possible are great even for a relative small array, we can not think about writing by hand the code, we need some function to do job for us. That’s what the sort library does, it prints the enhanced insertion sort algorithm.

There is a small disadvantage: the problem has size N!. It becomes huge for relative small buckets like 8 numbers. The sort8 function requires a 10MB file, I waited10 minutes for the compiler to build it, but no success, then I give up and decide to use the library till sort7 function.

The sortN function

You probably got confused, so here it is the code that I hope will clarify the concept.

The sort N function is a MATLAB script that prints the enhanced insertionsort algorithm for N values.

It recursively finds all the solutions and it prints optimized swaps.

function PrintSortNFunction(fid,N)
%Prints a c++ sort N function.
%fid is the file identifier where the function will be written.
%N is the number of points the function will sort, for example:
%
%PrintSortNFunction(fid,4);%print the sort4 function
 
%function definition
fprintf(fid,'void sort%1.0f(double* a){\n',N);
fprintf(fid,'double temp;\n');
x=1:N;
PrintIS(x,1,2,fid);
fprintf(fid,'}\n');
 
%The normal insertion sort:
 
% void insertionSort(double* x,int length)
% {
%
%
%
%   double key;
%       int i;
%
%   for(int j=1;j<length;j++)
%  {
%      key=x[j];
%      i=j-1;
%      while(x[i]>key && i>=0)
%      {
%                x[i+1]=x[i];
%          i--;
%      }
%      x[i+1]=key;
%   }
% }
end
 
%print the isertion sort operations, takes in input the i an j paramater
% (see code above). The x vector goes from 1 to N as matlab notation, the
% prints instead goes from 0:N-1 as C++ notation
function PrintIS(x,i,j,fid)
 
N=length(x);
 
%fprintf('%1.0f  %1.0f\n',i,j);    
 
% we reached the end of the array
if j>N%print solution
 fprintf(fid,'//');
 for i=1:length(x)
 fprintf(fid,'%1.0f',x(i)-1);
 end
 fprintf(fid,'\n');
 
 PrintSwaps(x,fid);%print swaps 
 
 return
end
 
%if (x[i]>key)
 
key=x(j);
x0=x;%make a copy
if i>=1 %if we are in the middle of the array
ii=x(i);jj=x(j);
fprintf(fid,'if (a[%1.0f]<a[%1.0f]){\n',ii-1,jj-1);    
 
%modify the solution
x(i+2:j)=x(i+1:j-1);
x(i+1)=key;
 
%go forward
PrintIS(x,j,j+1,fid);
fprintf(fid,'}\n');
fprintf(fid,'else{\n');
PrintIS(x0,i-1,j,fid);
 
fprintf(fid,'}\n') ;
else
%we have reached the beginning of the array 
 
%modify the solution
x(2:j)=x(1:j-1);
x(1)=key;
 
%go forward
PrintIS(x,j,j+1,fid)  ;  
 
end
 
end
 
%prints swaps combination to go from the base array 1:N to the
% sorted solution (permutation)
 
function PrintSwaps(Perm,fid)
 
N=length(Perm);
 
%We first have to store a temp value
 
%Perm=N:-1:1];test for debugging
Base=1:N;%to record the change due to swaps
 
swaps=zeros(N*3,2);
c=1;
for n=1:N       
 
 i=Base(n);
 j=Perm(n);
 
 if j==i %do nothing already in place
 continue;
 end
 
 %we have to make Base(n) equal to Perm(n);
 
 i=find(Base==j);
 
 temp=Base(i);%phisically swap (i and n)
 Base(i)=Base(n);
 Base(n)=temp;
 
 %print swap
 %-1 stays for temp value
 swaps(c,1)=-1;swaps(c,2)=n;
 swaps(c+1,1)=n;swaps(c+1,2)=i;
 swaps(c+2,1)=i;swaps(c+2,2)=-1;
 c=c+3;
 
end
 
%detecting duplicate values in swaps (they do not need to be copied in
%temp)
swaps(c:end,:)=[];%remove unused values
 
ind=false(c-1,1);
 
for i=2:c-2%loop trough candidate swaps
 
 if swaps(i,1)==swaps(i+1,2) && swaps(i,2)==swaps(i+1,1)
 ind(i)=true;ind(i+1)=true;
 end
end
 
%remove duplicate values from swaps
swaps(ind,:)=[];
 
for k=1:size(swaps,1)
 
 i=swaps(k,1);j=swaps(k,2);
 if i==-1
 fprintf(fid,'temp=a[%1.0f];\n',j-1);%store the temp value
 elseif j==-1
 fprintf(fid,'a[%1.0f]=temp;\n',i-1);%copy the temp value
 else
 fprintf(fid,'a[%1.0f]=a[%1.0f];\n',i-1,j-1);%keep copying
 end
end  
 
end

Perfomances

I have compared the sortN functions with insertion sort and stl sort here are some results:

Program Started

This program shows the perfomaces of the sortN library against
stl sort and insertions sort
Enter the number of buckets
10000000

BUCKET SIZE=3
STL sort of 3 points required 260.3610 ms
insertionSort of 3 points required 240.9796 ms
SortN sort of 3 points required 172.1386 ms
IS vs stl= 7.44406 %
SortN vs stl= 33.8846 %
SortN vs IS= 28.5671 %

BUCKET SIZE=4
STL sort of 4 points required 434.7305 ms
insertionSort of 4 points required 353.5941 ms
SortN sort of 4 points required 287.3990 ms
IS vs stl= 18.6636 %
SortN vs stl= 33.8903 %
SortN vs IS= 18.7206 %

BUCKET SIZE=5
STL sort of 5 points required 594.5557 ms
insertionSort of 5 points required 563.9854 ms
SortN sort of 5 points required 401.6870 ms
IS vs stl= 5.1417 %
SortN vs stl= 32.4391 %
SortN vs IS= 28.777 %

BUCKET SIZE=6
STL sort of 6 points required 883.9322 ms
insertionSort of 6 points required 735.4656 ms
SortN sort of 6 points required 517.2404 ms
IS vs stl= 16.7962 %
SortN vs stl= 41.4842 %
SortN vs IS= 29.6717 %

BUCKET SIZE=7
STL sort of 7 points required 1162.6356 ms
insertionSort of 7 points required 930.5345 ms
SortN sort of 7 points required 992.6320 ms
IS vs stl= 19.9634 %
SortN vs stl= 14.6223 %
SortN vs IS= -6.67331 %

You can run your own test by downloading the code below. As you can see for 7 numbers it becomes unadvantageous (dunno Why).

Downloads

The whole library can be build by downloading this:

Download Now

You can download the library (up to sort7 here):

Download SortN library

The quickest sort algorithm?

I don’t know, if you find something faster let me know.

What I known is that the sortN library can be further optimized. For example it can be made recursive (avoiding to write thousands lines of code), or it it can be  sped up in the swaps: for each solution find the minimum number of swaps to allows to pass from the original vector to the sorted one (currently I can only avoid to copy values in “temp” twice).

VN:F [1.8.8_1072]
Rating: 10.0/10 (1 vote cast)
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)

Popularity: 1% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

Quick Delaunay Triangulation

March 16, 2010 by Luigi Giaccari · 8 Comments
Filed under: Algorithms, C, Computational Geometry, FEM, Geometry 
VN:F [1.8.8_1072]
Rating: +1 (from 1 vote)
VN:F [1.8.8_1072]
Rating: 10.0/10 (4 votes cast)

Contents

QuickDel

It has always been a dream of mine to code a Delaunay triangulator. Last week I had 3 free days and I did it. I actually thought it was more complicated, as it often happens, when you are outside the problem it seems bigger than it really is.

In this post you will  find a Delaunay triangulation algorithm. My idea is to start a project which purpose is to create a robust an efficient triangulation/meshing tool.

The first release will be Delaunay triangulation function QuickDelMex

Below a comparison with DelaunayTri  from the computational geometry toolbox.

Number of points      QuickDel      Built-in Matlab    speed-up
10            0.0002 s         0.0142          98.69% s
100            0.0002 s         0.0094          97.61% s
1000            0.0016 s         0.0099          84.13% s
10000            0.0149 s         0.0707          78.96% s
100000            0.1856 s         1.2044          84.59% s
1000000            2.5094 s        14.1102          82.22% s

t=QuickDelMex(p) (version 0.3)
returns the Delaunay triangulation of the 2D point set p;

INPUT:

  • * p: double array of size 2xN. The list of unique points [x1 y1,x2 y2];

OUTPUT:

  • * t: double array of size ntx3. It contains the triangles of the Delaunay triangulation. Each rows contains 3 indexes of the points forming the triangle. Indexes are sorted counterclockwise; first points is flagged as one.


NOTES:

  • * -This function is a prototype so don’t trust too much, please check the results and in case send bug report.
  • * -This function is optimized for uniform random dataset, sparse datasets may slow down the algorithm.
  • * -This function may not return the whole convex hull. Thin boundary triangles may be discarded.
  • *- v0.3 is alittle slower but much more robust than v0.2.

Author: Luigi Giaccari (giaccariluigi@msn.com)

see also DelaunayTri delaunay delaunayn

Downloads

Matlab

You can download MEX Files of QuickDel here (win32 and linux):

Download QuickDelMex Version 0.3

A test to evaluate performances is also available on Matlab file exchange (Download Now)

C++

A Win32 executable is available here (v0.2):

Download QuickDel.exe Version 0.2

it asks for the number of points to be triangulated. Once the triangulation has been done it prints a text file (a matlab m-file) which allows to visualize the triangulations inside Matlab.

I can also build a win32 .dll, but I was too lazy to do it, if you want it please contact me.

Acknowledgements

Contacts

Please send bug reports/suggestions at: giaccariluigi@msn.com

This utility can be greatly enlarged, please compile the following survey.

What would you like too see on the next version of QuickDel?









VN:F [1.8.8_1072]
Rating: 10.0/10 (4 votes cast)
VN:F [1.8.8_1072]
Rating: +1 (from 1 vote)

Popularity: 2% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

Next Page »