[GEOS] #976: Voronoi polygons robustness issue

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[GEOS] #976: Voronoi polygons robustness issue

geos-2
#976: Voronoi polygons robustness issue
------------------------+--------------------------
 Reporter:  komzpa      |      Owner:  geos-devel@…
     Type:  defect      |     Status:  new
 Priority:  major       |  Milestone:
Component:  Default     |    Version:  3.6.2
 Severity:  Unassigned  |   Keywords:
------------------------+--------------------------
 https://trac.osgeo.org/postgis/ticket/4335

 {{{
 SELECT ST_VoronoiPolygons(ST_GeomFromWKB(
 E'\\001\\354\\003\\000\\000\\027\\000\\000\\000\\001\\351\\003\\000\\000\\354Q\\270\\036\\021\\242\\007A\\354Q\\270\\036\\205\\245\\034A\\\\\\217\\302\\365(\\3345@\\001\\351\\003\\000\\000\\037\\205\\353Q\\024\\242\\007A\\\\\\217\\302\\365\\205\\245\\034A{\\024\\256G\\341\\2725@\\001\\351\\003\\000\\000\\205\\353Q\\270\\030\\242\\007A\\250\\306K7\\206\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\000\\000\\000\\000\\033\\242\\007A\\376\\324x\\351\\204\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\205\\353Q\\270\\030\\242\\007A\\376\\324x\\351\\204\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\012\\327\\243p\\026\\242\\007A\\376\\324x\\351\\204\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\000\\000\\000\\000\\033\\242\\007AT\\343\\245\\233\\203\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\205\\353Q\\270\\030\\242\\007AT\\343\\245\\233\\203\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\012\\327\\243p\\026\\242\\007AT\\343\\245\\233\\203\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\000\\000\\000\\000\\033\\242\\007A\\252\\361\\322M\\202\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\205\\353Q\\270\\030\\242\\007A\\252\\361\\322M\\202\\245\\034A>\\012\\327\\243p\\2355@\\001\\351\\003\\000\\000\\366(\\\\\\217\\022\\242\\007A\\354Q\\270\\036\\210\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000""""\\020\\242\\007AR\\270\\036\\305\\206\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000O\\033\\350\\264\\015\\242\\007AR\\270\\036\\305\\206\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000{\\024\\256G\\013\\242\\007AR\\270\\036\\305\\206\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000""""\\020\\242\\007A\\270\\036\\205k\\205\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000O\\033\\350\\264\\015\\242\\007A\\270\\036\\205k\\205\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000{\\024\\256G\\013\\242\\007A\\270\\036\\205k\\205\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000\\247\\015t\\332\\010\\242\\007A\\270\\036\\205k\\205\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000\\324\\006:m\\006\\242\\007A\\270\\036\\205k\\205\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000{\\024\\256G\\013\\242\\007A\\037\\205\\353\\021\\204\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000\\247\\015t\\332\\010\\242\\007A\\037\\205\\353\\021\\204\\245\\034AA`\\345\\320"\\3335@\\001\\351\\003\\000\\000\\324\\006:m\\006\\242\\007A\\037\\205\\353\\021\\204\\245\\034AA`\\345\\320"\\3335@'
 ))
 }}}

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Can you post plain 'ol WKB?

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:1>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by komzpa):

 {{{0104000080170000000101000080EC51B81E11A20741EC51B81E85A51C415C8FC2F528DC354001010000801F85EB5114A207415C8FC2F585A51C417B14AE47E1BA3540010100008085EB51B818A20741A8C64B3786A51C413E0AD7A3709D35400101000080000000001BA20741FED478E984A51C413E0AD7A3709D3540010100008085EB51B818A20741FED478E984A51C413E0AD7A3709D354001010000800AD7A37016A20741FED478E984A51C413E0AD7A3709D35400101000080000000001BA2074154E3A59B83A51C413E0AD7A3709D3540010100008085EB51B818A2074154E3A59B83A51C413E0AD7A3709D354001010000800AD7A37016A2074154E3A59B83A51C413E0AD7A3709D35400101000080000000001BA20741AAF1D24D82A51C413E0AD7A3709D3540010100008085EB51B818A20741AAF1D24D82A51C413E0AD7A3709D35400101000080F6285C8F12A20741EC51B81E88A51C414160E5D022DB354001010000802222222210A2074152B81EC586A51C414160E5D022DB354001010000804F1BE8B40DA2074152B81EC586A51C414160E5D022DB354001010000807B14AE470BA2074152B81EC586A51C414160E5D022DB354001010000802222222210A20741B81E856B85A51C414160E5D022DB354001010000804F1BE8B40DA20741B81E856B85A51C414160E5D022DB354001010000807B14AE470BA20741B81E856B85A51C414160E5D022DB35400101000080A70D74DA08A20741B81E856B85A51C414160E5D022DB35400101000080D4063A6D06A20741B81E856B85A51C414160E5D022DB354001010000807B14AE470BA207411F85EB1184A51C414160E5D022DB35400101000080A70D74DA08A207411F85EB1184A51C414160E5D022DB35400101000080D4063A6D06A207411F85EB1184A51C414160E5D022DB3540}}}

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:2>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Thanks!

 This is a robustness issue in the current JTS overlay algorithm.  Might be
 able to be fixed with a smarter implementation of Voronoi polygons... but
 more likely will be fixed with the coming smarter implementation of
 overlay.  I will log this as a JTS issue, to surface it at source.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:3>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 This is due to a couple of the generated Voronoi polygons being
 topologically invalid, and because of that failing during the intersection
 computation (when clipping the raw Voronoi polygons to a surrounding
 rectangle).

 The reason the polygons are invalid is that they contain two points which
 are almost identical, one of which happens to lie on another edge of the
 polygon, thus creating a self-intersection.

 The reason the very close points are present is because the input points
 (Voronoi sites) generating them lie on a regular grid pattern.  This
 produces two Delaunay triangles with *almost* identical circumcentres.
 They are not 100% identical because of round-off error. The DT
 circumcentres form the vertices of the Voronoi polygons, and so polygons
 are created with almost-but-not-identical points in them.

 See attached diagrams for images.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:4>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by mdavis):

 * Attachment "sites-and-delaunay.png" added.

 Shows some input site vertices lying on a regular grid, and the Delaunay
 triangles containing them which have identical circumcentres

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by mdavis):

 * Attachment "invalid-voronoi-polygons.png" added.

 Shows one of the invalid Voronoi polygons, containing a self-intersection

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by mdavis):

 * Attachment "invalid-polygon-detail.png" added.

 Detail of an invalid polygon, showing very close vertices causing self-
 intersection

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 At the moment I'm not sure what an appropriate fix would be.  Some sort of
 slight snapping, probably, but not sure where or how to determine an
 appropriate tolerance.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:5>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Perhaps another way of fixing this is to detect pairs of triangles which
 should have identical circumcentres and force this to be the case.  I'm
 not sure it's possible to do this in full generality, but for points
 falling exactly on a square (or diamond) it is possible to robustly detect
 that the circumcentres should be the same.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:6>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by komzpa):

 Can longer arithmetics solve that? There's a patch of mine in master that
 promotes double to long double - is it reproducing on master?

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:7>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Reported upstream in JTS: https://github.com/locationtech/jts/issues/447

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:8>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Extra precision might fix the problem.  Have to try it and see.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:9>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 This is the place to see if extra precision can provide a more stable
 circumcentre result:

 https://github.com/libgeos/geos/blob/master/src/triangulate/quadedge/QuadEdgeSubdivision.cpp#L424

 The circumcentre call could be replaced with one that uses higher
 precision arithmetic.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:10>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Here's a simple test case to reproduce the problem. It's two of the
 Delaunay triangles.
 {{{
 GEOMETRYCOLLECTION (POLYGON ((193600.80333333334 469345.355,
 193600.80333333334 469345.0175, 193601.10666666666 469345.0175,
 193600.80333333334 469345.355)),
   POLYGON ((193600.80333333334 469345.355, 193601.10666666666 469345.0175,
 193601.10666666666 469345.355, 193600.80333333334 469345.355)))
 }}}

 Computing the circumcentres produces slightly different points:
 {{{
 GEOMETRYCOLLECTION (POINT (193600.95500000002 469345.18625),
                     POINT (193600.95500000002 469345.18624999997) )
 }}}

 This can be tried with extended-precision to see if it produces identical
 points.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:11>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Good news... I implemented Triangle.circumcentreDD in JTS, using the JTS
 extended precision floating point provided by DD.  The test case above now
 works, and so does the original Voronoi calculation.

 I'll be committing this to JTS very shortly.

 Based on the thread from Dec 2018 about DoubleDouble vs long double [1],
 it seems like perhaps DoubleDouble is the way to go for this in GEOS?

 [1] http://osgeo-org.1560.x6.nabble.com/double-double-td5388315.html

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:12>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 It also looks like just about any set of points on a grid will trigger
 this issue, and is handled by the fix in the works. So this is definitely
 worthwhile to implement.

 DD arithmetic is slower than double precision, of course, but this code is
 only used when generating Voronoi diagrams, and the slowdown is likely a
 small percentage of the runtime.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:13>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Fixed in JTS by https://github.com/locationtech/jts/pull/448

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:14>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by komzpa):

 > Based on the thread from Dec 2018 about DoubleDouble? vs long double
 [1], it seems like perhaps DoubleDouble? is the way to go for this in
 GEOS?

 going to long double is just a matter of adding "long" all over the
 function, and has almost no performance penalty. Worth trying that first?

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:15>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #976: Voronoi polygons robustness issue

geos-2
In reply to this post by geos-2
#976: Voronoi polygons robustness issue
------------------------+---------------------------
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Replying to [comment:15 komzpa]:
 > going to long double is just a matter of adding "long" all over the
 function, and has almost no performance penalty. Worth trying that first?

 My reading suggests that compilers can choose how to implement long
 double, and some may choose to implement it as plain double (including
 clang and MSVC?).  So that would not make it useful for GEOS in general-
 although we can try it to see if it works in some cases.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/976#comment:16>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
12