crashes python when using buggy geometry with 'p' flag

[songololo]

I've found that buggy geometry processed with the 'p' flag will crash Python. I've tested on two systems, both Mac.

This reproduces the behaviour for me. Note the repeated vertex at index 4:

from triangle import triangulate
geom = {
    'segments': [
        [0, 1],
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 0]
    ],
    'vertices': [
        [5, -5],
        [5, 0],
        [0, 0],
        [0, -2],
        [0, -2]
    ]
}
poly_triangulation = triangulate(geom, opts='p')

Would be nice if there were a way to throw an exception prior to Python itself crashing.

[drufat]

Can you provide a complete code sample that causes the crash?

[songololo]

Sure, I've updated the original post accordingly. I believe that I've tried all of the other flags and this is the only flag that causes the crash.

At one point, it threw this error, which appears to be from the underlying C triangles package:

Internal error in segmentintersection():  Attempt to find intersection of parallel segments.
  Please report this bug to jrs@cs.berkeley.edu
  Include the message above, your input data set, and the exact
    command line you used to run Triangle.

Here is the first part of the system's error report that I get when the crash occurs:

Process:               Python [70192]
Path:                  /opt/local/Library/Frameworks/Python.framework/Versions/3.4/Resources/Python.app/Contents/MacOS/Python
Identifier:            Python
Version:               3.4.3 (3.4.3)
Code Type:             X86-64 (Native)
Parent Process:        pycharm [69948]
Responsible:           pycharm [69948]
User ID:               505
Date/Time:             2015-04-12 22:19:47.790 +0100
OS Version:            Mac OS X 10.10.3 (14D130a)
Report Version:        11
Crashed Thread:        0  Dispatch queue: com.apple.main-thread
Exception Type:        EXC_BAD_ACCESS (SIGSEGV)
Exception Codes:       EXC_I386_GPFLT
Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   core.so                         0x0000000102fd1f71 insertsegment + 124
1   core.so                         0x0000000102fd23d1 formskeleton + 473
2   core.so                         0x0000000102fd6190 triangulate + 450
3   core.so                         0x0000000102fda8de __pyx_pw_8triangle_4core_3__triang + 506
4   core.so                         0x0000000102fdb27b __pyx_pw_8triangle_4core_1triang + 613
5   org.python.python               0x0000000100df54d5 PyEval_EvalFrameEx + 20989
6   org.python.python               0x0000000100df0121 PyEval_EvalCodeEx + 1622
7   org.python.python               0x0000000100df87a4 fast_function + 321
8   org.python.python               0x0000000100df5367 PyEval_EvalFrameEx + 20623
9   org.python.python               0x0000000100df0121 PyEval_EvalCodeEx + 1622
10  org.python.python               0x0000000100defac5 PyEval_EvalCode + 63
11  org.python.python               0x0000000100e13df1 run_mod + 58
12  org.python.python               0x0000000100e14090 PyRun_FileExFlags + 178
13  org.python.python               0x0000000100e1389d PyRun_SimpleFileExFlags + 902
14  org.python.python               0x0000000100e26c3b Py_Main + 3083
15  org.python.python               0x0000000100d4de27 0x100d4c000 + 7719
16  libdyld.dylib                   0x00007fff96c795c9 start + 1
Thread 0 crashed with X86 Thread State (64-bit):
  rax: 0x6400216400206400  rbx: 0x0000000101a05090  rcx: 0x0000000000000004  rdx: 0x0000000102ff14f0
  rdi: 0x00007fff5ee9ee98  rsi: 0x00007fff5ee9edf0  rbp: 0x00007fff5ee9ed40  rsp: 0x00007fff5ee9ecf0
   r8: 0x0000000000000000   r9: 0x0000000000000008  r10: 0x0000000102ff14f0  r11: 0x0000000000000002
  r12: 0x0000000101a05010  r13: 0x00007fff5ee9ee98  r14: 0x0000000000000000  r15: 0x00007fff5ee9edf0
  rip: 0x0000000102fd1f71  rfl: 0x0000000000010202  cr2: 0x0000000102fd1ef5

Logical CPU:     0
Error Code:      0x00000000
Trap Number:     13

[drufat]

I cannot duplicate this crash on Linux. In fact on my machine I get this output for poly_triangulation:

{'segment_markers': array([[1],
       [1],
       [1],
       [1]], dtype=int32),
 'segments': array([[1, 0],
       [2, 1],
       [3, 2],
       [0, 3]], dtype=int32),
 'triangles': array([[2, 3, 1],
       [0, 1, 3]], dtype=int32),
 'vertex_markers': array([[1],
       [1],
       [1],
       [1],
       [0]], dtype=int32),
 'vertices': array([[ 5., -5.],
       [ 5.,  0.],
       [ 0.,  0.],
       [ 0., -2.],
       [ 0., -2.]])}

This appears to be affecting MacOSX only.

[songololo]

OK, thanks for looking.

Really handy package by the way.

[songololo]

Somewhat related to the above post (where a duplicate vertex crashes python on a mac) I've also found that if an interior poly shares a point with an exterior point, then a crash likewise ensues. (Whereas it would be nice if it surfaced as an error instead of crashing python.) At the moment I am pre-processing the geometries to catch these duplicates, then the crashes can be avoided. Here is a sample:

from triangle import triangulate geom = { 'segments': [ [0, 1], [1, 2], [2, 3], [3, 0], [4, 5], [5, 6], [6, 7] ], 'vertices': [ [0, 0], [10, 0], [10, 10], [0, 10], [0, 10], [5, 1], [5, 9] ], 'holes': [[4, 8]] } poly_triangulation = triangulate(geom, opts='p')

[kxv]

This happens for me on linux, too.

[drmoose]

On my machine (Xenial, Python 2.7.12) this seems to only happen if I import multiprocessing after I import triangle. I'm not sure whether this is the same issue or a separate one. Using the data from the preceding comment as an example:

from triangle import triangulate
#import multiprocessing  # uncomment to cause crash
geom = {'segments': [ [0, 1], [1, 2], [2, 3], [3, 0], [4, 5], [5, 6], [6, 7] ], 
        'vertices': [ [0, 0], [10, 0], [10, 10], [0, 10], [0, 10], [5, 1], [5, 9] ],
        'holes': [[4, 8]]}
poly_triangulation = triangulate(geom, opts='pVVV') 

With the import multiprocessing line uncommented I get a segfault after this line of output:

  Connecting (0, 10) to (5, 1).

gdb's stack trace is:

#0  insertsegment (m=m@entry=0x7ffffffe9cc0, b=b@entry=0x7ffffffe9c10, endpoint1=endpoint1@entry=0xdb5e60, endpoint2=0xdb5e80, newmark=newmark@entry=0) at c/triangle.c:12278
#1  0x00007ffff35c908c in formskeleton (m=m@entry=0x7ffffffe9cc0, b=b@entry=0x7ffffffe9c10, segmentlist=0xa4f9a0, segmentmarkerlist=0x0, numberofsegments=<optimized out>) at c/triangle.c:12543
#2  0x00007ffff35cd437 in triangulate (triswitches=triswitches@entry=0x7ffff382c144 "Qzp", in=in@entry=0x7ffff38988e0, out=out@entry=0x7ffff3898998, vorout=vorout@entry=0x0) at c/triangle.c:15777
#3  0x00007ffff35d3495 in __pyx_pf_8triangle_4core_2__triang (__pyx_self=<optimized out>, __pyx_v_vorout=<optimized out>, __pyx_v_out_=0x7ffff3898988, __pyx_v_in_=0x7ffff38988d0, __pyx_v_switch=0x7ffff382c144 "Qzp")
    at triangle/core.c:6224

The only thing in the valgrind log that looks relevant is:

Conditional jump or move depends on uninitialised value(s)
   at 0xAB3AA89: insertsegment (triangle.c:12276)
   by 0xAB3B08B: formskeleton (triangle.c:12543)
   by 0xAB3F436: triangulate (triangle.c:15777)
   by 0xAB45494: __pyx_pf_8triangle_4core_2__triang (core.c:6224)
   by 0xAB45494: __pyx_pw_8triangle_4core_3__triang (core.c:6155)
   by 0xAB55651: __Pyx_PyObject_Call (core.c:21792)
   by 0xAB55651: __pyx_pf_8triangle_4core_triang (core.c:6032)
   by 0xAB55651: __pyx_pw_8triangle_4core_1triang (core.c:5940)
   by 0x4BC4A9: PyEval_EvalFrameEx (in /usr/bin/python2.7)
   by 0x4B9B65: PyEval_EvalCodeEx (in /usr/bin/python2.7)
   by 0x4C17C5: PyEval_EvalFrameEx (in /usr/bin/python2.7)
   by 0x4B9B65: PyEval_EvalCodeEx (in /usr/bin/python2.7)
   by 0x4EB69E: ??? (in /usr/bin/python2.7)
   by 0x4E58F1: PyRun_FileExFlags (in /usr/bin/python2.7)
   by 0x4E41A5: PyRun_SimpleFileExFlags (in /usr/bin/python2.7)
 Uninitialised value was created by a heap allocation
   at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
   by 0xAB25907: trimalloc (triangle.c:1431)
   by 0xAB26A1D: poolinit (triangle.c:3967)
   by 0xAB3D1F3: transfernodes (triangle.c:14119)
   by 0xAB3EF26: triangulate (triangle.c:15719)
   by 0xAB45494: __pyx_pf_8triangle_4core_2__triang (core.c:6224)
   by 0xAB45494: __pyx_pw_8triangle_4core_3__triang (core.c:6155)
   by 0xAB55651: __Pyx_PyObject_Call (core.c:21792)
   by 0xAB55651: __pyx_pf_8triangle_4core_triang (core.c:6032)
   by 0xAB55651: __pyx_pw_8triangle_4core_1triang (core.c:5940)
   by 0x4BC4A9: PyEval_EvalFrameEx (in /usr/bin/python2.7)
   by 0x4B9B65: PyEval_EvalCodeEx (in /usr/bin/python2.7)
   by 0x4C17C5: PyEval_EvalFrameEx (in /usr/bin/python2.7)
   by 0x4B9B65: PyEval_EvalCodeEx (in /usr/bin/python2.7)
   by 0x4EB69E: ??? (in /usr/bin/python2.7)

Trying to dump any variables that look potentially relevant at the time of the crash, and I get:

(gdb) p m->vertex2triindex
$1 = 3
(gdb) p searchtri1
$2 = {tri = 0x7ffff331b020, orient = 2}
(gdb) p encodedtri
$3 = (triangle) 0xa6b0006740400

But there's not anything noticeably different about the results with and without the import multiprocessing in there. I don't think I'm following the code well enough to really understand what the pointer math in the vertex2tri, encode and org macros does.

[drufat]

@drmoose Can you try with the last version in the repository, and see if this crash still happens?

[drmoose]

Still present as of 071b444d0e201ad42789603fc857f66261a4c72c

[addam]

Another example crash:

vertices = [(45.671, 124.433), (43.202, 123.208),
(44.86315146443515, 124.03218410041842),
(60, 95), (42, 131)]
edges = [(0, 1), (0, 2), (3, 4)]
triangulation = triangle.triangulate({"vertices": vertices, "segments": edges}, 'p')

Note that it is easy to avoid this crash by tweaking the coordinates in any slightest way. Catching the exception provides an easy workaround for this ugly computational geometry situation.

[FreakTheMighty]

I'm seeing a related issue. Its taken a while to track down a problematic polygon, but I've got one here that pretty reliably crashes. The weird thing is that it doesn't always crash. Running this directly on the command line ie. python small-test.py seems to reliably work. Running within a pytest unittest, fails nearly all the time, but not all the time. Running in the context of my larger application always crashes.

polygon.py

    from polygon import path
    results = triangulate(path, 'pzjqQn')

---

@addam what do you mean this is easy to avoid? I can't catch any errors, as the program fully segfaults. Also, what do you mean by change the coordinates? Is there a specific type of change you are making?

[addam]

The problem in my case is numerical precision. If it was possible to catch the error, I could just add 0.0001 to any of the coordinates and everything would go well. It is even enough to change the order of edges, such as edges = [(0, 1), (3, 4), (0, 2)]

[drufat]

I looked into the crashes a while back, and I think the problem may be in the underlying triangle library, and not in the wrapper code, unless I am violating some assumption when calling into the underlying library. I am not really familiar with the details of how the C library works, so I am afraid I will not be of much help if it is the former. If any of you can fix this crash feel free to submit a pull request.

[addam]

@drufat, you are right: the crashes that I found (and there are many besides the one I posted) can be reproduced in plain Triangle program. I don't expect anybody to fix the error.

What I'd like to see is a Python exception raised when the C code crashes. That way, it is possible to modify the input data or (at least) produce a meaningful error log.

[FreakTheMighty]

@drufat I would second @addam's point about exception handling. I'm not familiar with the wrapper, but avoiding the segfault would be a big win.

[drufat]

Since this is a memory error, I do not think there is a graceful way to recover from it in python.

Perhaps if we identify the pattern that causes it, we can create a guard in python that when the pattern is present raises an exception, and does not call the C code. That's the only workaround I can think of without touching the underlying C code.

Of course the best solution would be to fix the C code.

On May 31, 2020 5:57:21 PM PDT, Jesse Vander Does notifications@github.com wrote:

@drufat I would second @addam's point about exception handling. I'm not familiar with the wrapper, but avoiding the segfault would be a big win.

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/drufat/triangle/issues/4#issuecomment-636560200

[FreakTheMighty]

Gotcha, makes sense.

[brunohs1993]

I may be late for the party, but it may be relevant for future searches.

I was trying to make the triangulation automatic for my code so that it would get the lines, detect holes and concavities if there were any, and then triangulate using the 'p' option.

I spent some time trying to understand why sometimes the code would just stop, no error raised, no warning, nothing.

Then I realised that every time the simulation crashed, some of the points used to define holes were located outside the convex hull of the geometry. It wasn't definitive, though, since some of the times that it worked those points could also be there, even with convex geometries whitout any hole at all. But since I constrained the hole points to be inside the CH this problem didn't happen again.

Anywho, it would be good to keep this in mind for stability fixes.

Cheers!

[jni]

@drufat in my case, having repeated vertices in the input very often crashes the program, and based on my hopping around the internet this is indeed expected when vertices are repeated. (I apologise that I can't find the correct tab.) I've managed to correctly preprocess my data to remove repeated vertices, but as to what triangle could do (at the cost of performance) is:

if len(np.unique(tri['vertices'], axis=0)) < len(tri['vertices']) and 'p' in opts:
    raise ValueError('vertices cannot be repeated with option "p"')

If performance is a concern, one could use create a flag like strict='true' to the triangulate function.

If this is acceptable to you @drufat I'd be happy to submit a PR...

[jni]

(I apologise that I can't find the correct tab.)

Ah, it was the link in this comment in #70.

[bigsu]

Yes, I found that duplicating vertices causes the program to crash. It bothered me for a long time