Invalid triangulated output generated when using Delaunay triangulation algorithm with QJ qhull option.

[naresh07ec065]

Delaunay triangulation library has been used using a set of numpy ndarry points, when the points are fed to Delaunay triangulation , invalid / distorted triangles are formed. This output is creating issues and its not usable.
request you to suggest if something is wrong with the implementation.

Reproducing Code Example

scipy/scipy#19551

Error message
There is no error message, but triangulated output is invalid.

SciPy/NumPy/Python version and system information
SciPy version: 1.10.1
NumPy version : 1.24.2
Python version 3.8

[someshsomesh]

Hi,
Can someone please check this issue and please help us with resolution? Thanks!

[cbbarber]

Qhull is behaving correctly. Your code is using the 'QJ' option.

Option 'QJ' perturbs the input sites to enforce general position and triangulated output. This option is called "joggled input" in the Qhull documentation. The Delaunay Triangulation is correct for the perturbed points (i.e., extreme vertices of the corresponding convex hull).
http://www.qhull.org/html/qh-optq.htm#QJn
http://www.qhull.org/html/qh-impre.htm
http://www.qhull.org/html/qh-optf.htm#Fx

If option 'QJ' is not used, Qhull merges coplanar facets and other geometric degeneracies. These facets are non-simplicial. They can be triangulated with option 'Qt'.
http://www.qhull.org/html/qh-optq.htm#Qt

Instead of using Qhull's floating point arithmetic, other codes use exact arithmetic. They perform symbolic perturbations as needed. Their output is simplicial.
http://www.qhull.org/html/qh-impre.htm#exact

[naresh07ec065]

@cbbarber : Thanks for sharing the details !!.
Is it expected that scaling factor also has to be included within the QJ setting to get the valid triangulation output?
For example: "QJ0.0001" is working fine for given data points but "QJ" doesn't .
input.csv