Insight Journal (ISSN 2327-770X) - Exact Geometrical Predicate: Point in circle

Exact Geometrical Predicate: Point in circle

Singapore Immunology Network, Agency for Science, Technology and Research (A*STAR), Biopolis, Singapore

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3329

Published in The Insight Journal - 2011 July-December.

Submitted by Alexandre Gouaillard on 11-28-2011.

This document describes the implementation in ITK of the "point in circle" geometrical predicate.
Based on Jonathan Shewchuk's work which implements an exact version of the predicate using standard
floating point types and arithmetic, the implementation consist of an ITK wrapper around the
public domain C routines made available by the author of the precedent paper.
Wrapper using itk::PointSet, itk:CellInterface and itk:Mesh / itk:QuadEdgeMesh APIs are provided
along with corresponding examples which should provide enough details for users to directly
copy paste code in their application.

The application in mind for us is an exact and robust implementation of a delaunay triangulation /
voronoi tesselation in ITK, and will be presented in a separate paper.

Code

Automatic Testing Results by Insight-Journal Dashboard on Fri Dec 30 08:42:34 2011 for revision #1

expertise: 5 sensitivity: 4.5

This project passed 3 out of 4 tests.
Click here for more details.

Go here to access the main testing dashboard.

Reviews

A meaningful contribution with implications for mesh filtering. by Davis Vigneault on 2015-06-09 11:10:14 for revision #1

expertise: 2 sensitivity: 4.5

Summary:

The authors provide an implementation of the Straight Walk method for efficiently determining which cell in a mesh contains a specified point. This has particular application in reversing a mesh parameterization, among other tasks.

Hypothesis:

Evidence:

Open Science:

One function, OrientTest(), appeared to be missing. Other than that, all code was provided. This builds off a public domain code base for exact floating point calculations, cited in the article.

Reproducibility:

I downloaded, compiled, and ran the code, with some difficulty. Here are the steps I needed to take to get it working:

1. It appears that the submodule is not linked correctly in github. I needed to remove the .gitmodules file and add the submodule manually. Here is my StackOverflow question [3] which solved the problem.

2. I had to change WalkInTriangulation/CMakeLists.txt:6:

include( ${USE_ITK_FILE}) ==> include( ${ITK_USE_FILE})

3. At this point, CMake runs without errors; but when building I'm told that OrientationTest is missing. I assumed that OrientationTest is a wrapper for orient2d, and added the following function to itkWalkInTriangulationFunction.h:

template< typename TPoint >

double

OrientationTest( TPoint a, TPoint b, TPoint c )

{

double pa[2];

double pb[2];

double pc[2];

pa[0] = a[0];

pa[1] = a[1];

pb[0] = b[0];

pb[1] = b[1];

pc[0] = c[0];

pc[1] = c[1];

return orient2d(pa, pb, pc);

}

With those changes, the example seems to work correctly, though I haven't done thorough testing yet.

Use of Open Source Software:

This takes advantage of software currently in the public domain:

http://www.cs.cmu.edu/~quake/robust.html

Open source Contributions:

With some modification, this could be integrated into the toolkit. Integrating the provided floating point calculation software could be useful independent of this application.

Code Quality :

I have only compiled and run on Ubuntu. However, the library used is in C, and therefore is expected to be portable.

Quality of the data :

Interest:

This submission has implications for mesh processing, as noted in the authors' later work.

Comment by Ekabyesheri Holland:

Comment by Lschelneli Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Hyherscherwesle Vigorda:

Comment by Itezziodiss Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Rnseremmi Vigorda:

Comment by Lschelneli Vigorda:

Comment by Corelickcolt Vigorda:

Comment by Ekabyesheri Holland:

Comment by Mwangmajor Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Ohnatowgabr Ken:

Comment by Ekjamerkend Ken:

Comment by Lithrailesmered Olivier:

Comment by Lheeralalkris Olivier:

Comment by Rnseremmi Vigorda:

Comment by Aaccajohn Holland:

Comment by Elissierdeon Olivier:

Comment by Corelickcolt Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Rthierrymeag Vigorda:

Comment by Itezziodiss Holland:

Comment by Rankeurensuan Ken:

Comment by Tyamatriley Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Ekabyesheri Holland:

Comment by Corelickcolt Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Pshopgolf Olivier:

Comment by Lschelneli Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Ohnatowgabr Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Defeldanni Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Lithrailesmered Olivier:

Comment by Defeldanni Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Elissierdeon Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Rankeurensuan Ken:

Comment by Umcglaufllind Olivier:

Comment by Lithrailesmered Olivier:

Comment by Mwangmajor Holland:

Comment by Elissierdeon Olivier:

Comment by Nhuskinsaran Ken:

Comment by Bridesmaidbride Ken:

Comment by Elissierdeon Olivier:

Comment by Umcglaufllind Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Tyamatriley Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Pshopgolf Olivier:

Comment by Mwangmajor Holland:

Comment by Corelickcolt Vigorda:

Comment by Aaccajohn Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Elissierdeon Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Defeldanni Vigorda:

Comment by Rthierrymeag Vigorda:

Comment by Ohnatowgabr Ken:

Comment by Umcglaufllind Olivier:

Comment by Nhuskinsaran Ken:

Comment by Rankeurensuan Ken:

Comment by Milbluemelsherr Ken:

Comment by Ntlnoel Holland:

Comment by Lithrailesmered Olivier:

Comment by Rankeurensuan Ken:

Comment by Ekjamerkend Ken:

Comment by Pshopgolf Olivier:

Comment by Ohnatowgabr Ken:

Comment by Rankeurensuan Ken:

Comment by Rthierrymeag Vigorda:

Comment by Ekabyesheri Holland:

Comment by Nhuskinsaran Ken:

Comment by Itezziodiss Holland:

Comment by Tyamatriley Vigorda:

Comment by Rankeurensuan Ken:

Comment by Lheeralalkris Olivier:

Comment by Elissierdeon Olivier:

Comment by Nhuskinsaran Ken:

Comment by Lschelneli Vigorda:

Comment by Mwangmajor Holland:

Comment by Pshopgolf Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Elissierdeon Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Tyamatriley Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Elissierdeon Olivier:

Comment by Lheeralalkris Olivier:

Comment by Lithrailesmered Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Pshopgolf Olivier:

Comment by Lheeralalkris Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Rsalbarrantravi Olivier:

Comment by Lheeralalkris Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Defeldanni Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Lheeralalkris Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Defeldanni Vigorda:

Comment by Rankeurensuan Ken:

Comment by Elissierdeon Olivier:

Comment by Aaccajohn Holland:

Comment by Rthierrymeag Vigorda:

Comment by Defeldanni Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Bridesmaidbride Ken:

Comment by Lheeralalkris Olivier:

Comment by Lithrailesmered Olivier:

Comment by Elissierdeon Olivier:

Comment by Itezziodiss Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Aaccajohn Holland:

Comment by Lheeralalkris Olivier:

Comment by Nhuskinsaran Ken:

Comment by Ntlnoel Holland:

Comment by Aaccajohn Holland:

Comment by Rsalbarrantravi Olivier:

Comment by Corelickcolt Vigorda:

Comment by Eusriddlebthadd Vigorda:

Comment by Nhuskinsaran Ken:

Comment by Rnseremmi Vigorda:

Comment by Ekabyesheri Holland:

Comment by Ekjamerkend Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Ohnatowgabr Ken:

Comment by Ekjamerkend Ken:

Comment by Lithrailesmered Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Mwangmajor Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Tyamatriley Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Pshopgolf Olivier:

Comment by Ekjamerkend Ken:

Comment by Ntlnoel Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Rsalbarrantravi Olivier:

Comment by Ekjamerkend Ken:

Comment by Pshopgolf Olivier:

Comment by Rsalbarrantravi Olivier:

Comment by Nhuskinsaran Ken:

Comment by Rsalbarrantravi Olivier:

Comment by Rnseremmi Vigorda:

Comment by Defeldanni Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Elissierdeon Olivier:

Comment by Lheeralalkris Olivier:

Comment by Rnseremmi Vigorda:

Comment by Rsalbarrantravi Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Pshopgolf Olivier:

Comment by Bridesmaidbride Ken:

Comment by Defeldanni Vigorda:

Comment by Ohnatowgabr Ken:

Comment by Nhuskinsaran Ken:

Comment by Defeldanni Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Elissierdeon Olivier:

Comment by Lithrailesmered Olivier:

Comment by Elissierdeon Olivier:

Comment by Defeldanni Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Itezziodiss Holland:

Comment by Kssicktyso Holland:

Comment by Mwangmajor Holland:

Comment by Elissierdeon Olivier:

Comment by Tsmccathedema Ken:

Comment by Bridesmaidbride Ken:

Comment by Obalmorval Ken:

Comment by Rnseremmi Vigorda:

Comment by Defeldanni Vigorda:

Comment by Elissierdeon Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Defeldanni Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Mwangmajor Holland:

Comment by Ohnatowgabr Ken:

Comment by Nhuskinsaran Ken:

Comment by Milbluemelsherr Ken:

Comment by Tnboydstunmerly Ken:

Comment by Rsalbarrantravi Olivier:

Comment by Elissierdeon Olivier:

Comment by Ntlnoel Holland:

Comment by Itezziodiss Holland:

Comment by Elissierdeon Olivier:

Comment by Pshopgolf Olivier:

Comment by Rsalbarrantravi Olivier:

Comment by Ltermilleldo Olivier:

Comment by Nhuskinsaran Ken:

Comment by Lheeralalkris Olivier:

Comment by Defeldanni Vigorda:

Comment by Rnseremmi Vigorda:

Comment by Mwangmajor Holland:

Comment by Itezziodiss Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Pshopgolf Olivier:

Comment by Tnorthfor Olivier:

Comment by Rsalbarrantravi Olivier:

Comment by Defeldanni Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Itezziodiss Holland:

Comment by Ntlnoel Holland:

Comment by Lheeralalkris Olivier:

Comment by Itezziodiss Holland:

Comment by Rsalbarrantravi Olivier:

Comment by Mwangmajor Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Pshopgolf Olivier:

Comment by Nhuskinsaran Ken:

Comment by Ekjamerkend Ken:

Comment by Defeldanni Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Mwangmajor Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Defeldanni Vigorda:

Comment by Ekjamerkend Ken:

Comment by Rferrerirola Holland:

Comment by Redbergaaro Ken:

Comment by Aupaul Ken:

Comment by Elissierdeon Olivier:

Comment by Cbuycheap Holland:

Comment by Itezziodiss Holland:

Comment by Pshopgolf Olivier:

Comment by Lheeralalkris Olivier:

Comment by Umcglaufllind Olivier:

Comment by Lheeralalkris Olivier:

Comment by Itezziodiss Holland:

Comment by Pshopgolf Olivier:

Comment by Defeldanni Vigorda:

Comment by Hcritchfijohn Holland:

Comment by Lithrailesmered Olivier:

Comment by Lheeralalkris Olivier:

Comment by Elissierdeon Olivier:

Comment by Defeldanni Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Umcglaufllind Olivier:

Comment by Tyamatriley Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Itezziodiss Holland:

Comment by Lheeralalkris Olivier:

Comment by Tyamatriley Vigorda:

Comment by Defeldanni Vigorda:

Comment by Itezziodiss Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Defeldanni Vigorda:

Comment by Itezziodiss Holland:

Comment by Ohnatowgabr Ken:

Comment by Ntlnoel Holland:

Comment by Itezziodiss Holland:

Comment by Mwangmajor Holland:

Comment by Bridesmaidbride Ken:

Comment by Tsmccathedema Ken:

Comment by Rsalbarrantravi Olivier:

Comment by Lithrailesmered Olivier:

Comment by Itezziodiss Holland:

Comment by Lheeralalkris Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Defeldanni Vigorda:

Comment by Ntlnoel Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Rsalbarrantravi Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Tsmccathedema Ken:

Comment by Pshopgolf Olivier:

Comment by Bridesmaidbride Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Ntlnoel Holland:

Comment by Itezziodiss Holland:

Comment by Mwangmajor Holland:

Comment by Ntlnoel Holland:

Comment by Pshopgolf Olivier:

Comment by Tdvanlithrasha Holland:

Comment by Lithrailesmered Olivier:

Comment by Mwangmajor Holland:

Comment by Pshopgolf Olivier:

Comment by Tyamatriley Vigorda:

Comment by Elissierdeon Olivier:

Comment by Tyamatriley Vigorda:

Comment by Pshopgolf Olivier:

Comment by :

Comment by Tyamatriley Vigorda:

Comment by Milbluemelsherr Ken:

Comment by :

Add a new review

Quick Comments

Resources


Download All
Download Paper , View Paper
Download Source code
Github

Statistics more


Global rating:
Review rating:	[review]
Code rating:
Views:	3788
Downloads:	4517
Paper Quality:

Information more


Paper Id:	843
Categories:	Data Representation, Filtering, Geometric transforms, Mesh
Keywords:	exact geometrical predicate, Mesh
Toolkits:	ITK, CMake
Revision:
Export citation:
Status:	Open for public review

Share

Linked Publications more


Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy by Vercauteren T., Pennec X., Perchant A., Ayache N.
Importing Contours from DICOM-RT Structure Sets by Dowling J., Malaterre M., Greer P.B., Salvado O.
A Label Geometry Image Filter for Multiple Object Measurement by Padfield D., Miller J.
Scalable Simple Linear Iterative Clustering (SSLIC) Using a Generic and Parallel Approach by Lowekamp B., Chen D., Yaniv Z., Yoo T.
Computing Bone Morphometric Feature Maps from 3-Dimensional Images by Vimort J., McCormick M., Paniagua B.
A Skull-Stripping Filter for ITK by Bauer S., Fejes T., Reyes M.
Walk In A Triangulation : Straight Walk by Rigaud S., Gouaillard A.
InsightToolkit Kinetic Analysis (itk::ka) Library by Dowson N., Baker C., Raffelt D., Smith J., Thomas P., Salvado O., Rose S.
Anisotropic Fast Marching in ITK by Mirebeau J.
Anomalous Diffusion Paradigm for Image Denoising Process by Senra Filho A.C., Murta Junior L.O.

View license

Loading license...

Send a message to the author