Opened 6 years ago

Last modified 6 years ago

#4152 new defect

Delaunay triangulation creates overlapping triangles

Reported by: komzpa Owned by: pramsey
Priority: medium Milestone: PostGIS GEOS
Component: postgis Version: 2.4.x
Keywords: Cc:

Description

Feeding a multipoint into ST_DelaunayTriangles creates overlapping triangles: 

select ST_DelaunayTriangles('01040000004F0000000101000000244AD52CA286504058F4A4D3AB255140010100000062359967C8556240C56A32CF906B5E40010100000011DA2800CE1B60405A908C4AC1505D400101000000264AD52CA286504059F4A4D3AB255140010100000079E1CE20AB316540E21BBCE547446240010100000040496AF647A85F4031A081A090A36640010100000010DA2800CE9B52402C4846A560A8534001010000006040034121475E4060DBCA04DC2B634001010000009CBFFCBEDEB858409F2435FB23546740010100000079D2FDCC90544A4036F0ED5FDA964F40010100000079D2FDCC9054554035F0ED5FDA96554001010000003E533FDCB333604040102E99DBBC65400101000000EE19A0276FE15640602D7D25154B64400101000000D8F176DFB5276140AFE3EDBE6B0F5C400101000000C0B69509B8575740CF5F7E5F6FDC634001010000000000000000E065400000000000C06240010100000055E103C018095F40ADF001608C0467400101000000E4CAD299530D58403F98951A548557400101000000A3BFFCBEDEB858405EDBCA04DC2B63400101000000B8BB7C33D97E5D4051E8E48F47625B400101000000AF4E6833720C5D403AC4413D17115B4001010000008C4B663885294B406D4AF2FB35274F400101000000A6E153330BE33E4012504F75F3DC474001010000004EC3A76616C65A4048403DD5CD7359400101000000D86BB8A33572434090F27AC2234C4A40010100000062359967C8556240C36A32CF906B5E400101000000AA1EFC3FE7F65740530FFE9F737B634001010000008B4B663885294B406C4AF2FB35274F400101000000D8F176DFB5276140B0E3EDBE6B0F5C400101000000B04E6833F23064403AC4413D178E614001010000008559814798985640C0EFD16624C364400101000000A1DB5D6F204E5C40DE30542AEF6D57400101000000856E77BD817853407AC350A9BCB75240010100000000000000000049400000000000004E4001010000007AD2FDCC9054554036F0ED5FDA9655400101000000A6E153330BE3444025A09EEAE6B94B400101000000E492194E616A56409C92FC7ECD495440010100000042B7BBDE405C5940BD61A854DEDB5540010100000059E103C018095F40540FFE9F737B63400101000000E3CAD299538D65403E98951A54856240010100000045C3A76616C64F4021A09EEAE6B9514001010000007BD2FDCC90D4624036F0ED5FDA9660400101000000FBFFFFFFFF7F5B400000000000C06740010100000009F32F6C480F60409FD282DAEA34664001010000000000000000805640FEFFFFFFFF3F654001010000000AF32F6C480F6040622D7D25154B64400101000000EC78BBEFDA836340EC78BBEFDA636040010100000084598147989856403C102E99DBBC65400101000000A41EFC3FE7F65740AAF001608C0467400101000000846E77BD8178534079C350A9BCB752400101000000465693662F786140633834053B3F5F400101000000000000000040604000000000004065400101000000BF5AFA4A2A96594008F32F6C488F67400101000000A6E153330BE3444024A09EEAE6B94B400101000000EB19A0276FE156409BD282DAEA346640010100000057AFE18ED6C83B401DE5F58447984640010100000042496AF647A85F40D15F7E5F6FDC634001010000007EDFA3CD48865A403D533FDCB3B36740010100000076D2FDCC90544A4032F0ED5FDA964F4001010000000EDA2800CE9B52402B4846A560A85340010100000086DFA3CD48865A40C2ACC0234CCC6240010100000037A505B5D5695D400AF32F6C488F674001010000000000000000405F4000000000000059400101000000CA6BB8A33572434087F27AC2234C4A4001010000007AD2FDCC90544A4035F0ED5FDA964F4001010000003E533FDCB3336040C2EFD16624C3644001010000000000000000003440000000000000444001010000003DA505B5D5695D40F70CD093B7F062400101000000AF4E6833F23064403AC4413D178E614001010000004DC3A76616C64F4024A09EEAE6B9514001010000009B5CA9AE46F35F409B5CA9AE46B359400101000000E292194E616A56409B92FC7ECD4954400101000000C75AFA4A2A965940F60CD093B7F062400101000000BCB69509B85757402DA081A090A36640010100000078205C32B7795C403E533FDCB3B3674001010000005C40034121475E40A22435FB2354674001010000007E205C32B7795C40C2ACC0234CCC624001010000000200000000805B400000000000C06240010100000076BCDD77EDB1644076BCDD77ED916140');

Attachments (1)

Screenshot_20180816_164613.png​ (270.1 KB ) - added by komzpa 6 years ago.

Download all attachments as: .zip

Change History (5)

by komzpa, 6 years ago

Attachment: Screenshot_20180816_164613.png​ added

comment:1 by dbaston, 6 years ago

This can be reported to JTS: ​https://github.com/locationtech/jts/issues

comment:3 by komzpa, 6 years ago

Upstream says it's WONTFIX.

How about we change default tolerance from 0 to SQLMM_EPSILON = 1e-8 so that it works out of the box?

comment:4 by dbaston, 6 years ago

I wonder if it's possible to test for this situation somehow (without doing overlap tests) and then fail?

Note: See TracTickets for help on using tickets.