Q: Bug with small areas in python bindings

[icemtel]

I have found a problem with python binding of Triangle, and I suspect this is related to the C code. I describe the issue here: https://github.com/drufat/triangle/issues/26 If I run triangulate with 'a' argument and value smaller than 10^-4, then the program will totally ignore this argument. Was this problem already discussed or fixed for the original version of Triangle?

[wo80]

Which version of triangle does the python code use? I cannot reproduce the problem with the latest code from this repository:

double boundary_points[] = { -1, -1, 1, -1, 1, 1, -1, 1 };

triangleio in;
statistics s;

triangleio_reset(&in);

in.numberofpoints = 4;
in.pointlist = boundary_points;

int n = 5;
double areas[] = { pow(10.0, -5), 9.0 * pow(10.0, -5), pow(10.0, -4), 1.1 * pow(10.0, -4), pow(10.0, -2) };
char* options[] = { "a0.00001", "a0.00009", "a0.0001", "a0.00011", "a0.01", };

printf("Max area   Num of triangles\n");

for (int i = 0; i < n; i++)
{
    context *c = triangle_context_create();

    triangle_context_options(c, options[i]);
    triangle_mesh_create(c, &in);
    triangle_mesh_statistics(c, &s);

    printf("%.2e   %i\n", areas[i], s.triangles);

    triangle_context_destroy(c);
}

Output:

Max area   Num of triangles
1.00e-05   622268
9.00e-05   69408
1.00e-04   62223
1.10e-04   56758
1.00e-02   628

[wo80]

Ok, so the Python code uses Triangle version 1.6, which is the version this repository is based on. Since there haven't been any changes to the algorithms, I suspect the problem is on the Python side.

[wo80]

Just tested with the original C program. Works fine:

Input: test.node

4  2  0  0
   1   -1 -1
   2    1 -1
   3    1  1
   4   -1  1

Output:

> Triangle -a0.00001 test.node

Opening test.node.
Constructing Delaunay triangulation by divide-and-conquer method.
Adding Steiner points to enforce quality.

Writing test.1.node.
Writing test.1.ele.

Statistics:

  Input vertices: 4

  Mesh vertices: 311789
  Mesh triangles: 622268
  Mesh edges: 934056
  Mesh exterior boundary edges: 1308

[icemtel]

Thank you for clarifying this. Then I will try to take a look what could cause this in Python library

[icemtel]

The python project is quite dead, but I found something strange in output and maybe you could tell me where I should look next.

Triangle output for 'a0.01':

Constructing Delaunay triangulation by divide-and-conquer method.
Adding Steiner points to enforce quality.

Writing vertices.
Writing triangles.

Statistics:

  Input vertices: 4

  Mesh vertices: 334
  Mesh triangles: 628
  Mesh edges: 961
  Mesh exterior boundary edges: 38

Triangle output for 'a0.00001':

Constructing Delaunay triangulation by divide-and-conquer method.
Adding Steiner points to enforce quality.

Writing vertices.
Writing triangles.
Writing edges.

Statistics:

  Input vertices: 4

  Mesh vertices: 5
  Mesh triangles: 4
  Mesh edges: 8
  Mesh exterior boundary edges: 4

The second example produces extra line "Writing edges". Do you know what could be the reason why it happens, and could it be connected to the problem?

[wo80]

I never encountered this. Such unexpected behavior might indicate a buffer overflow or other memory alignment problems.

How did you compile the sources, which compiler flags, which platform?

I compared the source code of triangle.c and found that (in the Python project) all occurances of unsigned long were replaced with size_t. This might lead to problems on x64 platforms.

[wo80]

Regarding the Writing edges. output. This is usally done by applying the -e option. You should check if your arguments string gets parsed correctly by debugging the triangulate function. Step over the parsecommandline call and inspect the behavior variable b.

b.edgesout should be 0 if the -e switch isn't used.

[icemtel]

Thanks again.
I use windows x64, all the C code is handled by python library Cython, it compiles '.c' files to '.pyd', but I couldn't find info what exact compiler and parameters does it use.

I also noticed that size_t is used in Python library, but I don't know the reason why. Maybe I can change it back, I will need to see if I will have to change something in Python code too.

[wo80]

One last idea: writing something like

char* options = "a0.01";

in C will actually result in a null-terminated char-array. Don't know how this is in Python. Maybe you could just add the \0 manually and see if it makes a difference.

[wo80]

I also noticed that size_t is used in Python library, but I don't know the reason why. Maybe I can change it back, I will need to see if I will have to change something in Python code too.

The reason is to support x64. The problem with size_t is, that it is guaranteed to represent an unsigned integer, but not to be 8 bytes long (this may vary for compilers).

EDIT: see https://github.com/wo80/Triangle/commit/6a87bb006c3a0de22615c041b89ed7a1f8013bfb

[icemtel]

in C will actually result in a null-terminated char-array. Don't know how this is in Python

It is not in Python, but you made me think.. and I found the problem in my code. I didn't specify how Python should transform number to string, so below 10 ** -4 any number was written to string in exponential form, e.g. 'a1e-5' thereby it parsed 'a' and '1' together and 'e' to write edges

Thanks for your input again, the problem is completely on my side.