CGAL
PMP: Polyline Snapping
Summary of Changes
This introduces an internal non-documented function to snap a set of polylines under a user-specified tolerance. I also put a test and a plug-in for the demo.
Release Management
- Affected package(s): PMP
It's honestly no rush at all, so unless @sloriot (or you) can do a review and that the testsuite looks good soon enough for 4.12, it can easily be postponed to 4.13.
Warnings:
In file included from /Users/cgaltester/cgal_test/CGAL-4.12-Ic-200/cmake/platforms/x86-64_Darwin-13.0_Apple-clang-5.0_Release/test/Polyhedron_Demo/Plugins/PMP/Snap_polylines_plugin.cpp:7:
/Users/cgaltester/cgal_test/CGAL-4.12-Ic-200/include/CGAL/Polygon_mesh_processing/polyline_snapping.h:275:64: warning: unused typedef 'PointIterator' [-Wunused-local-typedef]
typedef typename boost::range_const_iterator<Polyline>::type PointIterator;
^
/Users/cgaltester/cgal_test/CGAL-4.12-Ic-200/include/CGAL/Polygon_mesh_processing/polyline_snapping.h:281:84: warning: unused typedef 'OutputType' [-Wunused-local-typedef]
typedef cpp11::tuple<std::size_t, std::size_t, std::size_t, std::size_t, FT, FT> OutputType;
^
/Users/cgaltester/cgal_test/CGAL-4.12-Ic-200/include/CGAL/Polygon_mesh_processing/polyline_snapping.h:273:69: warning: unused typedef 'PolylineIterator' [-Wunused-local-typedef]
typedef typename boost::range_const_iterator<PolylineRange>::type PolylineIterator;
^
3 warnings generated.
Maybe have a look at the other columns, because there might be other warnings: https://cgal.geometryfactory.com/CGAL/testsuite/results-4.12-Ic-200.shtml#Polyhedron_Demo
@lrineau I see you push it to the testsuite (there are warnings I'm going to take care of). Do you want this to be in 4.12? As I said, I don't mind waiting for 4.13 for this.
I have temporarily added the label "not yet approved", to avoid that I accidentally merge this PR, before the discussion between Sébastien and Simon is over.
After a discussion with @sgiraudot, we have decided to postpone the test of this PR for CGAL-4.13.
To be done:
- handle the case where the segments are colinear,
- even when segment are not colinear, handle the cases where the point of a segment s1 that is closest to a segment s2 is not the intersection of projections.
Maybe Simon you want to add things. I think we should in the end modify the first message of the discussion, with a summary of the to-do list.
@sgiraudot Have a look whether you want to refresh this PR and have it tested for CGAL-4.13.
I don't think I'll have time to do the work that has to be done (summed up in your message of March 22nd) before the release, so we should probably postpone it.
I honestly don't know. There's still quite a lot of work to do and it's quite low priority, so I don't see it improving anytime soon…
I rebased the branch and did some more work on it:
- the algorithm now takes a Graph as input and directly modifies it
- degenerate cases (collinear segments or coplanar segments) are well detected, and a first version of proximities detection is done
- so far, some cases are not handled, specifically cases were a segment is completely included in the tolerance cylinder of another coplanar segment
Actually, it is really difficult to figure out a way to deal with all possible cases. The problem seems ill-posed, as the same polyline set will give very different results depending on how densely it's sampled: it seems we should consider polylines as a linear distribution and not a set of segments, otherwise we are dependent on vertex densities/positions. But on the other hand, I don't see an easy way to do it without the points.
Handling collinear segments gives also a sort of instability: two segments almost collinear would snap at 1 point, but as soon as they become collinear, they should snap as a common segment?
Depending on how the handle proximities, we can also get quite different outputs, see this coplanar example:
There does not seem to be a right answer. If you start considering cases where N polylines might snap at the same location with a combination of degenerate cases, it quickly becomes a nightmare.
In all cases, we also have the problem that applying the algorithm several times would sequentially collapse the polylines onto each other, which is not the case with non-degenerate cases (that would remain stable).
I'm wondering if we should not just make it a precondition that no segments are collinear/coplanar (or use random perturbations to make sure of that), but that might be too restrictive.
Problems in license :
There are modifications in licenses (check if all modified/added headers files contain a valid SPDX tag compatible with the one in package_info/PKG/license and that no license text is present):
M Polygon_mesh_processing/package_info/Polygon_mesh_processing/license.txt