Skip to content

squared_distance(Segment_3, Ray_3) is wrong when the segment and the ray are parallel to the z-axis #9858

Open

Description

@Ishaan400

Issue Details

CGAL::squared_distance() between a Segment_3 and a Ray_3 gives a wrong (too large) value when the two are parallel to the z-axis and point in opposite directions. I ran into it while comparing the distance functions against brute force on small integer inputs.

In the example below the ray runs alongside the whole segment, so the squared distance is 5 (e.g. between (2 2 1) and (0 1 1)), but 6 is returned, which is the squared distance between the ray's source and the segment's target. If I just swap the endpoints of the segment I get 5.

I think the cause is in squared_distance_parallel() in Distance_3/include/CGAL/Distance_3/Segment_3_Ray_3.h. It decides whether the segment and the ray have the same direction by comparing the sign of hx() or of hy(), whichever is larger for the segment. When both directions are along z, hx() and hy() are 0 for both, the signs are equal, and opposite directions are taken to be the same. So it only goes wrong along the z-axis; along x or y the result is fine. There is already a same_direction() in Distance_3/internal/squared_distance_utils_3.h that also looks at z (Ray_3_Ray_3.h uses it), so that could be used here as well.

The only Segment_3 - Ray_3 case in test_distance_3.cpp is a non-parallel one, so this path isn't tested at the moment.

I have a fix with a test and can open a PR for it.

Source Code

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <iostream>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_3 P;
typedef K::Segment_3 S;
typedef K::Ray_3 R;

int main()
{
  // both parallel to the z-axis, pointing in opposite directions
  S s(P(2, 2, 2), P(2, 2, 1));
  R r(P(0, 1, 0), P(0, 1, 1));

  std::cout << CGAL::squared_distance(s, r) << "\n";            // expected 5
  std::cout << CGAL::squared_distance(s.opposite(), r) << "\n"; // 5
}

This prints 6 and 5. I get the same with Epick and Simple_cartesian.

Environment

  • Operating system (Windows/Mac/Linux, 32/64 bits): Linux (Ubuntu 24.04), 64 bits
  • Compiler: GCC 13.3
  • Release or debug mode: both
  • Specific flags used (if any): -std=c++17
  • CGAL version: main (92a95da) and 6.1.x-branch (c49dd7c)
  • Boost version: 1.83
  • Other libraries versions if used (Eigen, TBB, etc.): GMP 6.3.0, MPFR 4.2.1

Activity

  1. victrvondoom commented on Nov 19, 2026

    @victrvondoom

    I checked Distance_3/include/CGAL/Distance_3/Segment_3_Ray_3.h: the parallel branch compares only hx()/hy(), so when both directions are along z it compares sign(0) and treats opposite directions as matching. That is consistent with the reported 6-versus-5 result; same_direction() in squared_distance_utils_3.h looks like the natural shared helper.

    A focused regression in Distance_3/test/Distance_3/test_distance_3.cpp could assert the reported result for both segment endpoint orders, then cover same-direction z and the reversed Ray_3/Segment_3 overload. Since you already have a fix in mind, could you assign me to add the test/follow-up if you are not already preparing that change?

  2. Ishaan400 commented on Nov 20, 2026

    @Ishaan400
    ContributorAuthor

    Thanks for looking into it @victrvondoom The fix is already up in #9859. It switches the parallel case to same_direction(), and the test in test_distance_3.cpp covers both endpoint orders of the segment and rays pointing both ways along each of the three axes. check_squared_distance also checks the Ray_3/Segment_3 order, so that’s covered too. If you have time, a review or a test run of #9859 would be very welcome.

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions