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% [?]
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% [?]
SaGA – Spatial and Geometric Analysis Toolbox
Here is a directory to a useful toolbox from:
Kirill K. Pankratov
SaGA is a collection of MATLAB programs dealing with various aspects of geometrical modeling and spatial data analysis.
Before proceeding further you are invited to a short tour of the gallery of pictures easily produced with SaGA routines.
By the way here is the m-file sagawcm.m which produces the above header picture.
This is is the Readme file with brief information describing the SaGA package.
Here you can get straight to the SAGA directory where all the programs are stored.
To see a list of functions contained in the SaGA Toolbox go to the Contents file.
One can transfer the archives containing most of the SaGA toolbox from SAGA_Z directory.
The structure and function interdependence of the SaGA toolbox is detailed in the Flowchart.
See License file for registration information.
The Whatsnew file will contains information about updates and further development of the SaGA Toolbox.
And here one can find answers to some Frequently Asked Questions about SaGA.
pkirill@mit.eduPopularity: 2% [?]
In Polygon Test For Convex Polygon
Translator
By N2H Follow Us
Video Posts
-
