Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

New package: Frechet Distance #8284

Open
wants to merge 362 commits into
base: master
Choose a base branch
from
Open

New package: Frechet Distance #8284

wants to merge 362 commits into from
+112,376 −31

Conversation

lrineau
Copy link
Member

@lrineau lrineau commented Jun 12, 2024 •
edited by afabri
Loading

Summary of Changes

Add a new package computing the approximate Fréchet distance between two polylines in dD under Euclidean metric, or decides if the distance is smaller than a given value.

Release Management

  • Affected package(s): Frechet_distance
  • Feature/Small Feature (if any): link
  • Link to compiled documentation: link
  • License and copyright ownership: MPI, GeometryFactory, cnrs(?)

TODO:

afabri and others added 19 commits May 1, 2024 11:01
@afabri
Add Polyline_traits_3 and add comments where we have to fix things
7f57547
Fix compile errors.
45d4dee
@afabri
Back to 2D
348a9cb
@afabri
Change from where data are read to get ready for the testsuite; typed…
dc78a17 
…ef -> using
@afabri
Deal with examples (ha ha)
8a550b8
Remove stub of Polyline_d package.
dcf639f 
We don't want an explicit package for that for the Polyline_distance
package.
Make bichromaticFarthestDistance faster and high-dimensional.
d7f4f4d
Also use K::dimension everywhere in high_level_predicates.h
a7a23ef
@afabri
Remove it later. only needed to learn how to determine features
9b18db8
@afabri
RealType -> Lambda
210b447
@afabri
cleanup
08beeea
@afabri
Minimize traits class; parameterize with Curve
673efd5
@afabri
Add doxygen
a3662eb
@afabri
rename traits classes
9196109
@afabri
less #include
a4687d4
@afabri
Add dD (not working yet)
fcb4a1c
@afabri
Kernel: Add a BBox class with dimension as parameter
ec56c66
@afabri
fixes for clang
f519646
@afabri
Remove files that were accidentally added
8dc8330
@afabri afabri mentioned this pull request Jun 12, 2024
Open
@afabri afabri added this to the 6.1-beta milestone Jun 12, 2024
@afabri afabri linked an issue Jun 12, 2024 that may be closed by this pull request
Epick_d and Has_filtered_predicates_tag #8256
Open
lrineau
lrineau commented Jun 14, 2024
View reviewed changes
NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h Outdated
Comment on lines 66 to 71

// Added to be similar to CGAL::Filtered_kernel
typedef EK Exact_kernel;
enum { Has_filtered_predicates = true };
typedef Boolean_tag<Has_filtered_predicates> Has_filtered_predicates_tag;

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@mglisse please review

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As I said elsewhere, if that's really all that's needed (there is an example so I assume it compiles and runs, although I am rather surprised), ok.
(I would have mentioned in the comment the name of the package that needs it, but I guess this comment is good enough)

lrineau
lrineau commented Jun 14, 2024
View reviewed changes
NewKernel_d/test/NewKernel_d/Epick_d.cpp
Comment on lines +748 to +752

static_assert(Ker2::Has_filtered_predicates_tag::value);
static_assert(Ker3::Has_filtered_predicates_tag::value);
static_assert(Kerd::Has_filtered_predicates_tag::value);

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@mglisse please review

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ok, we can always modify this if we start testing non-filtered kernels.

@afabri
Copy link
Member

afabri commented Jun 14, 2024

/build:v0

@github-actions GitHub Actions
Copy link

There was an error while building the doc:

/home/runner/work/cgal/cgal/Documentation/doc/Documentation/packages.txt:341: warning: image file name pkg-small.png is ambiguous.
Possible candidates:
   /home/runner/work/cgal/cgal/Documentation/doc/Documentation/fig/pkg-small.png
   /home/runner/work/cgal/cgal/Polyline_distance/doc/Polyline_distance/fig/pkg-small.png
   /home/runner/work/cgal/cgal/Polygonal_surface_reconstruction/doc/Polygonal_surface_reconstruction/fig/pkg-small.png
   /home/runner/work/cgal/cgal/Weights/doc/Weights/fig/pkg-small.png
   /home/runner/work/cgal/cgal/Cone_spanners_2/doc/Cone_spanners_2/fig/pkg-small.png

https://github.com/CGAL/cgal/actions/runs/9516169288

afabri
afabri reviewed Dec 27, 2024
View reviewed changes
Frechet_distance/include/CGAL/Frechet_distance.h
template<class Dim> struct Epeck_d;

template < typename P, int D>
struct Ambient_dimension<P, Epick_d<Dimension_tag<D>>>
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should that go into Epick_d.h @sloriot ?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@mglisse ?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I guess we could add a template Ambient_dimension inside the class Kernel_d_interface that says everything has Base::Dimension as ambient dim, since that's what CGAL::Ambient_dimension looks for by default.

@afabri

This comment was marked as outdated.

Sign in to view
@github-actions GitHub Actions

This comment was marked as outdated.

Sign in to view
@afabri

This comment was marked as outdated.

Sign in to view
@github-actions GitHub Actions

This comment was marked as outdated.

Sign in to view
@afabri

This comment was marked as outdated.

Sign in to view
@github-actions GitHub Actions

This comment was marked as outdated.

Sign in to view
@sloriot

This comment was marked as outdated.

Sign in to view
@github-actions GitHub Actions
Copy link

github-actions bot commented Jan 3, 2025

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/8284/v0/Manual/index.html

@sloriot
Copy link
Member

sloriot commented Jan 7, 2025

Test failing in CGAL-6.1-Ic-57

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@mglisse mglisse mglisse left review comments

@albert-github albert-github albert-github left review comments

@afabri afabri afabri left review comments

@sloriot sloriot sloriot left review comments

Assignees
No one assigned
Labels
Feature Not yet approved The feature or pull-request has not yet been approved. Ready to be tested TODO (web)
Projects
None yet
Milestone
6.1-beta
Development

Successfully merging this pull request may close these issues.

Epick_d and Has_filtered_predicates_tag
6 participants
@lrineau @afabri @mglisse @sloriot @albert-github @MaelRL