Improve isValid

[mhugo]

The isValid algorithm seems very slow.

Identified points to improve so far:

• the self intersection test is in O(n^2). Is there something better to do here ?
• replace explicit x() / y() / z() accessors by predicates when possible

[vmora]

• O(n^2) is fast when n is small... :) of course we can index everything with bboxes.
• the x() y() z() are IMO necessary to detected if the polygon is "roughly" plane:
  • I don't know is CGAL provides such "approximate notion"
  • Epic kernel could be used there, maybe also for most of the validation
  • I'm not sure it's a necessary condition to guaranty the good behaviour of algos, because we reproject or triangulate 3D polygons to use CGAL, Since polygon comes from double: they are not plane.

Maybe SFS validity and pre-condition validity should be uncoupled (especially usefull for conversion of polygons SFS-Valid <-> CGAL-Valid)

[mborne]

@vmora It's possible to do approximate computation with Epeck kernel :

See this example from Sébastien : https://github.com/Oslandia/SFCGAL/blob/sprint/doc/devnotes/cgal-approximate.md

(should be "just" twice slower than pure double operations)

[mhugo]

approx() takes the centre of the interval boxes, which is here enough to compute a distance, right ?

[mhugo]

"Maybe SFS validity and pre-condition validity should be uncoupled (especially usefull for conversion of polygons SFS-Valid <-> CGAL-Valid)" I like this idea. But are you able to explicit those CGAL preconditions ?

[mhugo]

hmmm : just the list of assertions in CGAL ?

[vmora]

are you able to explicit those CGAL preconditions

the only ones I know about is the polygon hole-touching ring case and the "plane polygon" required by SFS

just the list of assertions in CGAL

maybe an idea... if not complete to ensure robustness -> upstream the problem ;)

[danielcu888]

Validation caching can make great improvements to the performance of this algorithm. In summary, once a geometry has been validated, the result need not be recalculated if it has not been mutated, yet this is repeatedly done, and is very expensive, in particular for Polygons. Included in the list of mutations that dispose of any cached validation result is the access to non-const geometry components of a given Geometry, which may, via the non-const reference, be mutated. Of course there is no certainty that the client would mutate through use of these accessors, but there is no way to tell. A solution is to offer const& accessors to ensure preservation of the Geometry and hence avoid clearing any cached validation state. Its expected that speedups as a result of this are of order 1000.

In addition, minor improvements include:

• Caching the Plane_3 of a given Polygon
• Caching the Triangulated surface derived from a given PolyhedralSurface

Its expected that such caching provides significant speedups where applicable.