Geometric Primitives and Geomtric Operations with Matlab
Matlab does not come by default with a geometric primitives library. About for some simple function like the “sphere” command, using some geometric entities may be an issue. Fortunately on Matlab file exchange are available these two packages, from David Legland ,that help us to develop geometric projects.
- Geom2D Download Now
- Geom3D Download Now
The packages include functions for computations on planar and spatial geometrical shapes (points, lines, circles, polygons…)
The goal is to provide a low-level library for manipulating geometrical primitives, making easier the development of more complex geometric algorithms.
The library proposes functions to:
- create various shapes (points, circles, lines, ellipses, polylines, polygons) using an intuitive syntax. Ex: createCircle(p1, p2, p3) to create a circle through 3 points.
- derive new shapes: intersection between 2 lines, between a line and a circle, parallel and perpendicular lines
Functions to compute intersections - work on polylines and polygons: compute centroid and area, expand, clip with half-plane…
- measure distances (between points, a point and a line, a point and a group of points), angle (of a line, between 3 points), or test geometry (point on a line, on a circle).
- manipulate planar transformation. Ex: P2 = transformPoint(P1, createRotation(CENTER, THETA));
- draw shapes easily. Ex: drawCircle([50 50], 25), drawLine([X0 Y0 DX DY]). Some clipping is performed for infinite shapes such as lines or rays.
- functions for 3D polygons and polyhedra. Polyhedra use classical vertex-faces arrays (face array contain indices of vertices), and support faces with any number of vertices. Some basic models are provided (createOctaedron, createCubeoctaedron…), as well as some computation (like faceNormal or centroid)
- direct drawing of shapes with specialized functions. Clipping is performed automatically for unbounded shapes such as lines or rays. Ex:
drawPoint3d([50 50 25; 20 70 10], ‘ro’); % draw some points
drawLine3d([X0 Y0 Z0 DX DY DZ]); % clip and draw straight line
Popularity: 3% [?]
MatlabBGL: a graph library for Matlab
Filed under: Computational Geometry, Mathematics, Numerical Analysis
The most complete graph library for Matlab offered by David Gleich.
The MatlabBGL library fills a hole in Matlab’s suite of algorithms. Namely, it provides a rich set of algorithms to work with graphs, as in graph theory graphs. The MatlabBGL package uses Matlab’s native sparse matrix type as a graph and provides algorithms that work
The algorithms included are
- Searching: breadth first search,depth first search, and astar (A*) search
- Shortest Path Algorithms: Dijkstra’s algorithm, the Bellman-Ford algorithm, Johnson’s algorithm, and the Floyd-Warshall algorithm.
- Minimum Spanning Trees: Prim’s algorithm and Kruskal’s algorithm.
- Components: strongly connected components and biconnected components (and articulation points).
- Flow Algorithms: Goldberg’s push-relabel maximum-flow minimum-cut algorithm.
- Statistics: Betweenness Centrality, Clustering Coefficients, and Edge Centrality
- Graph Creation: Erdos Reyni (Gnp) Graph, Cycle Graph, Wheel Graph, Star Graph
- Planar Graphs: Boyer-Myrvold planarity testing, Chrobak-Payne straight line drawing
- Graph Layout: force directed layout, spring based layout, topology filling layout
Additional informations can be found on the MatlabBGL official website, here is a directory:
MatlabBGL
Popularity: 4% [?]
GLTree Pro Version: a fast nearest neighbour library for Matlab and C++
Filed under: Algorithms, Computational Geometry, Geometry, Graphics
Contents
Introduction
The nearest neighbor search problem arises in numerous fields of application, including:
- Pattern recognition – in particular for optical character recognition
- Statistical classification- see k-nearest neighbor algorithm
- Computer vision
- Databases – e.g. content-based image retrieval
- Coding theory – see maximum likelihood decoding
- Data compression – see MPEG-2 standard
- Recommendation systems
- Internet marketing - see contextual advertising and behavioral targeting
- DNA sequencing
- Spell checking - suggesting correct spelling
- Plagiarism detection
- Contact searching algorithms in FEA
- Similarity scores for predicting career paths of professional athletes.
- Cluster analysis – assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense, usually based on Euclidean distance
The algorithm
The reason that pushed me to develop this algorithm was the need of more speed in nearest neighbors search. The first implementation of GLTree was coded in the September 2008, and a first, rough, but very fast version was uploaded on Matlab File Exchange as C++ code to compile into MEX file in November. These version are still available and open-source:
After using this library for about a year I released the potential and I decided to make a step further. In this page a faster and low memory version is proposed. Many more functions have been developed like: a nearest neighbour filter radius search and a cuboid search and many more can be developed.
Perfomances
This are the timings for a NNGraph in 2D and 3D on my 2.4Ghz laptop. Test is run on uniform randomly points in 0-1 range. Given a set of N random points, for each one finds his nearest neighbour.
START NNGraph Test: 2D NNGraph of 10 points took: 0.0001 s NNGraph of 100 points took: 0.0001 s NNGraph of 1000 points took: 0.0004 s NNGraph of 10000 points took: 0.0039 s NNGraph of 100000 points took: 0.0629 s NNGraph of 1000000 points took: 1.1897 s 3D NNGraph of 10 points took: 0.0014 s NNGraph of 100 points took: 0.0001 s NNGraph of 1000 points took: 0.0007 s NNGraph of 10000 points took: 0.0075 s NNGraph of 100000 points took: 0.1219 s NNGraph of 1000000 points took: 2.4760 s TEST SUCCESFULLY COMPLETED !!!
You can run this test by downloading the demo version (linux and win32):
Download GLTreePro Demo
For very sparse data, like logspace data, GLTree becomes slower. It may be convenient using others algorithm. For more see this post:
A comparison of GLTree with Kd-Tree and Bd-Tree
Release
- 15/02/2010 GLTreePro_v1.0
Matlab
This release includes the following MEX files:
- 2D
- K-Nearest Neighbor Search
- K-Nearest Neighbour Graph
- Nearest Neighbour Filter
- Radius Search
- Cuboid Search
- BuildTree
- DeleteTree
- 3D
- K-Nearest Neighbor Search
- K-Nearest Neigbour Graph
- Nearest Neighbour Filter
- Radius Search
- Cuboid Search
- BuildTree
- DeleteTree
We support Win32 and Linux platform. Source code is currently not supported. The package includes all the MEX files plus .m files for the help command.
| Version | Minimum Support amount |
| 2D | 10 euro |
| 3D | 10 euro |
| 2D&3D | 15 euro |
or on the following bank account:
| Name | Luigi Giaccari |
| IBAN | IT 07 E05550 77710 000000483947 |
Please e-mail at: giaccariluigi@msn.com after the donation. You will soon receive the latest version of the GLTree library and all following updates.
C++
Under Construction. You need it? tell me and I may speed up the development.
Examples
See the examples for 2D:
Popularity: 2% [?]
GLTree Matlab Example: Nearest Neighbor Filter Function
Filed under: Algorithms, Computational Geometry, Optimization
KNNSearch2D query a GL-tree for k nearest neighbor(kNN)
SYNTAX
[cutdist,ndel,idel]=KNNFilter2D(p,ptrtree,’r',r);% radius mode
[cutdist,ndel,idel]=KNNFilter2D(p,ptrtree,’f',f);% consolidator mode
INPUT PARAMETERS
- p: [2xN] double array coordinates of reference points
- ptrtree: a pointer to the previously constructed GLtree.Warning if the pointer is incorrect it will cause a crash, there is no way to check this in the mex routine, you have to check it in your script.
- ‘r’ or ‘f’: string. Specify the RADIUS mode or the CONSOLIDATOR mode.
- r or f: double parameter for the mode.
OUTPUT PARAMETERS
- cutdist: in the dataset no couple of points will be closer than cutdist. In the radius mode cutdist==radius.
- ndel: number of points removed from the tree
- iddel: ids of points removed from the tree
GENERAL INFORMATIONS
- -RADIUS mode: if 2 points are closer than r only one will survive.
- -CONSOLIDATOR mode: the nearest neighbour graph is computed and the mean distance between points is evaluated. The cutdistance is set to meandist/f.
- -points removed form the tree are not physically deleted (memory deaollocated), they are just skipped during search.
For question, suggestion, bug reports
giaccariluigi@msn.com
Author: Luigi Giaccari
N=300;%reference points Cuboid=[.2 ,.5 ,.2 ,.5 ]'; p=rand(N,2);%reference points fprintf('RANDOM POINTS GENERATED\n\n') fprintf('BUILDING THE DATA STRUCTURE:\n') tic ptrtree=BuildGLTree2D(p'); fprintf('\tGLTree built in %4.4f s\n\treturned pointer %4.0f:\n\n',toc,ptrtree); fprintf('START FILTER:\n') tic [idc]=CuboidSearch2D(p',Cuboid,ptrtree); fprintf('\t %4.0f Points found in range\n\n',length(idc)); fprintf('DELETING THE TREE\n\n') DeleteGLTree2D(ptrtree); fprintf('TEST SUCCESFULLY COMPLETED !!!\n\n') %plot the NNG figure(1) title('Cuboid Search','fontsize',14); axis equal hold on x=[Cuboid(1),Cuboid(1),Cuboid(2),Cuboid(2),Cuboid(1)]; y=[Cuboid(3),Cuboid(4),Cuboid(4),Cuboid(3),Cuboid(3)]; h1=plot(p(:,1),p(:,2),'g.'); h2=plot(x,y,'b-'); h3=plot(p(idc,1),p(idc,2),'r.'); legend([h1,h2,h3],'Reference points','Cuboid','Inside points');
RESULTS
Points inside the cut radius are found
And deleted..
Go to main post
Popularity: 2% [?]
GLTree Matlab Example: Radius Search Function
Filed under: Computational Geometry, Optimization
RSearch2D query a GL-Tree for Radius search
SYNTAX
idc=RSearch3D(p,qp,ptrtree,r);
INPUT PARAMETERS
- p: [2xN] double array coordinates of reference points
- qp: [2x1] double array coordinates of query points. NOTE: differently from NNsearch this function does not support multiple query points.
- ptrtree: a pointer to the previously constructed GLtree.Warning if the pointer is uncorrect it will cause a crash, there is no way to check this in the mex routine, you have to check it in your script.
- r: double value, radius to perform the search.
OUTPUT PARAMETERS
- idc: [?x1] column vector, each rows contains an index of a point found in the range described by the radius.
GENERAL INFORMATIONS
-Conditions for a point to be found in the radius is <=, so
points with distance from the query=r will be returned.
For question, suggestion, bug reports
giaccariluigi@msn.com
Author: Luigi Giaccari
EXAMPLE
function test() N=200;%reference points k=3;%k neigh p=rand(N,2);%reference points qp=rand(1,2);%query point r=.1;%radius for search fprintf('RANDOM POINTS GENERATED\n\n') fprintf('BUILDING THE DATA STRUCTURE:\n') tic ptrtree=BuildGLTree2D(p'); fprintf('\tGLTree built in %4.4f s\n\treturned pointer %4.0f:\n\n',toc,ptrtree); fprintf('START RADIUS SEARCH:\n') tic [idc]=RSearch2D(p',qp',ptrtree,r); fprintf('\t %4.0f Points found in range\n\n',length(idc)); fprintf('DELETING THE TREE\n\n') DeleteGLTree2D(ptrtree); fprintf('TEST SUCCESFULLY COMPLETED !!!\n\n') %plot the NNG figure(1) title([num2str(k),' Neighbours'],'fontsize',14); axis equal hold on h1=plot(p(:,1),p(:,2),'g.'); h2=plot(qp(:,1),qp(:,2),'b+'); h2=circle(qp,r,30,'-b'); h3=plot(p(idc,1),p(idc,2),'r.'); legend([h1,h2,h3],'Reference points','Circle','Inside points'); end function H=circle(center,radius,NOP,style) %--------------------------------------------------------------------------------------------- % H=CIRCLE(CENTER,RADIUS,NOP,STYLE) % This routine draws a circle with center defined as % a vector CENTER, radius as a scaler RADIS. NOP is % the number of points on the circle. As to STYLE, % use it the same way as you use the rountine PLOT. % Since the handle of the object is returned, you % use routine SET to get the best result. % % Usage Examples, % % circle([1,3],3,1000,':'); % circle([2,4],2,1000,'--'); % % Zhenhai Wang <zhenhai@ieee.org> % Version 1.00 % December, 2002 %--------------------------------------------------------------------------------------------- if (nargin <3), error('Please see help for INPUT DATA.'); elseif (nargin==3) style='b-'; end; THETA=linspace(0,2*pi,NOP); RHO=ones(1,NOP)*radius; [X,Y] = pol2cart(THETA,RHO); X=X+center(1); Y=Y+center(2); H=plot(X,Y,style); axis square; end
Popularity: 2% [?]
Translator
By N2H Follow Us
Video Posts
-
