Exact Geometrical Predicate: Point in circle
logo

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3329
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
minus Automatic Testing Results by Insight-Journal Dashboard on Fri Dec 30 08:42:34 2011 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 4.5
yellow This project passed 3 out of 4 tests.
Click here for more details.

Go here to access the main testing dashboard.

Reviews
minus A meaningful contribution with implications for mesh filtering. by Davis Vigneault on 2015-06-09 11:10:14 for revision #1
starstarstarstarstar expertise: 2 sensitivity: 4.5
yellow
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:

NA

Evidence:

NA

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 :

NA

Interest:

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


Comment by Cbuycheap Holland: yellow


Comment by Cbuycheap Holland: yellow


Comment by Cbuycheap Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Hcritchfijohn Holland: yellow


Comment by Hcritchfijohn Holland: yellow


Comment by Hcritchfijohn Holland: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Tdvanlithrasha Holland: yellow


Comment by Tdvanlithrasha Holland: yellow


Comment by Tdvanlithrasha Holland: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow

Add a new review
Quick Comments


Resources
backyellow
Download All
Download Paper , View Paper
Download Source code
Github

Statistics more
backyellow
Global rating: starstarstarstarstar
Review rating: starstarstarstarstar [review]
Code rating: starstarstarstarstar
Paper Quality: plus minus

Information more
backyellow
Categories: Data Representation, Filtering, Geometric transforms, Mesh
Keywords: exact geometrical predicate, Mesh
Toolkits: ITK, CMake
Export citation:

Share
backyellow
Share

Linked Publications more
backyellow
Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy
by Vercauteren T., Pennec X., Perchant A., Ayache N.
A Label Geometry Image Filter for Multiple Object Measurement A Label Geometry Image Filter for Multiple Object Measurement
by Padfield D., Miller J.

View license
Loading license...

Send a message to the author
main_flat
Powered by Midas