Comments (21)
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')
from triangle.
This happens for me on linux, too.
from triangle.
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.
from triangle.
from triangle.
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.
from triangle.
@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.
from triangle.
Yes, I found that duplicating vertices causes the program to crash. It bothered me for a long time
from triangle.
Can you provide a complete code sample that causes the crash?
from triangle.
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 [email protected]
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
from triangle.
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.
from triangle.
OK, thanks for looking.
Really handy package by the way.
from triangle.
@drmoose Can you try with the last version in the repository, and see if this crash still happens?
from triangle.
Still present as of 071b444
from triangle.
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.
from triangle.
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.
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?
from triangle.
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)]
from triangle.
@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.
from triangle.
Gotcha, makes sense.
from triangle.
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!
from triangle.
@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...
from triangle.
(I apologise that I can't find the correct tab.)
Ah, it was the link in this comment in #70.
from triangle.
Related Issues (20)
- Issue with License / conda forge submission HOT 1
- Wheels for Python 3.9 / 3.10 on PyPI HOT 7
- triangle/core.c:19390:5: error: lvalue required as increment operand HOT 1
- i cannot establish a restrictive triangulation network HOT 2
- "a" option for maximum area ignored if smaller than 0.00001 HOT 1
- i can't install triangle in mac M1 HOT 2
- pip install fails with python 3.10 HOT 1
- Build wheel for Python 3.10 and Apple M1 HOT 5
- Pip install of latest version fails for intel mac with python 3.9 HOT 2
- 0xC0000005 error HOT 4
- [Feature Request] Make a new release HOT 5
- Segmentation fault while doing multiple loop in ubuntu. HOT 2
- access segments including attribute HOT 1
- Could not build wheels for triangle HOT 1
- Broken intall for python 3.11 HOT 2
- "c1: fatal error C1083: Cannot open source file: 'c/triangle.c': No such file or directory" error while building from source HOT 2
- Error: Ran out of precision at HOT 1
- Refine mesh HOT 1
- Add docs here? HOT 1
- No Response when Triangulating Section
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from triangle.