GeographicLib: GeographicLib::Intersect Class Reference (original) (raw)

Geodesic intersections More...

#include <[GeographicLib/Intersect.hpp](Intersect%5F8hpp%5Fsource.html)>

Geodesic intersections

Find the intersections of two geodesics X and Y. Four calling sequences are supported.

• The geodesics are defined by a position (latitude and longitude) and an azimuth. In this case the closest intersection is found.
• The geodesics are defined by two endpoints. The intersection of the two segments is found. If they don't intersect, then the closest intersection is returned.
• The geodesics are defined as an intersection point, a single position and two azimuths. In this case, the next closest intersection is found.
• The geodesics are defined as in the first case and all intersection within a specified distance are returned.

In all cases the position of the intersection is given by the signed displacements x and y along the geodesics from the starting point (the first point in the case of a geodesic segment). The closest itersection is defined as the one that minimizes the L1 distance, Intersect::Dist([x, y) = |x| + |y|.

The routines also optionally return a coincidence indicator c. This is typically 0. However if the geodesics lie on top of one another at the point of intersection, then c is set to +1, if they are parallel, and −1, if they are antiparallel.

Example of use:

#include

#include

using namespace std;

try {

Geodesic geod(Constants::WGS84_a(), Constants::WGS84_f());

GeodesicLine lineX(geod, 0, 0, 45, Intersect::LineCaps);

GeodesicLine lineY(geod, 45, 10, 135, Intersect::LineCaps);

Intersect::Point point = intersect.Closest(lineX, lineY);

double latx, lonx, laty, lony;

lineX.Position(point.first, latx, lonx);

lineY.Position(point.second, laty, lony);

cout << "X intersection displacement + position "

<< point.first << " " << latx << " " << lonx << "\n";

cout << "Y intersection displacement + position "

<< point.second << " " << laty << " " << lony << "\n";

}

catch (const exception& e) {

cerr << "Caught exception: " << e.what() << "\n";

return 1;

}

}

int main(int argc, const char *const argv[])

Header for GeographicLib::Constants class.

Header for GeographicLib::Intersect class.

std::pair< Math::real, Math::real > Point

Namespace for GeographicLib.

IntersectTool is a command-line utility providing access to the functionality of this class.

This solution for intersections is described in

• C. F. F. Karney,
  Geodesic intersections, J. Surveying Eng. 150(3), 04024005:1–9 (2024); preprint arxiv:2308.00495.

It is based on the work of

• S. Baseldga and J. C. Martinez-Llario, Intersection and point-to-line solutions for geodesics on the ellipsoid, Stud. Geophys. Geod. 62, 353–363 (2018); DOI: 10.1007/s11200-017-1020-z.

Definition at line 71 of file Intersect.hpp.

◆ Point

The type used to hold the two displacement along the geodesics. This is just a std::pair with x = first and y = second.

Definition at line 79 of file Intersect.hpp.

Constructor for an ellipsoid with

Parameters

Exceptions

Note

This class has been validated for -1/4 ≤ f ≤ 1/5. It may give satisfactory results slightly outside this range; however sufficient far outside the range, some internal checks will fail and an exception thrown.

If |f| > 1/50, then the Geodesic object should be constructed with exact = true.

Definition at line 20 of file Intersect.cpp.

References GeographicLib::Geodesic::Inverse(), GeographicLib::Math::pi(), and std::swap().

◆ Closest() [1/2]

Find the closest intersection point, with each geodesic specified by position and azimuth.

Parameters

Returns

p the intersection point closest to p0.

The returned intersection minimizes Intersect::Dist(p, p0).

Definition at line 55 of file Intersect.cpp.

References Closest(), GeographicLib::Geodesic::Line(), and LineCaps.

Referenced by Closest(), and main().

◆ Closest() [2/2]

Find the closest intersection point, with each geodesic given as a GeodesicLine.

Parameters

Returns

p the intersection point closest to p0.

The returned intersection minimizes Intersect::Dist(p, p0).

Note

lineX and lineY should be created with minimum capabilities Intersect::LineCaps. The methods for creating a GeodesicLine include all these capabilities by default.

Definition at line 64 of file Intersect.cpp.

◆ Segment() [1/2]

Find the intersection of two geodesic segments defined by their endpoints.

Parameters

Returns

p the intersection point if the segments intersect, otherwise the intersection point closest to the midpoints of the two segments.

Warning

The results are only well defined if there's a unique shortest geodesic between the endpoints of the two segments.

segmode codes up information about the closest intersection in the case where the segments intersect. Let _x_12 be the length of the segment X and x = p.first, the position of the intersection on segment X. Define

• kx = −1, if x < 0,
• kx = 0, if 0 ≤ x ≤ _x_12,
• kx = 1, if _x_12 < x.

and similarly for segment Y. Then segmode = 3 kx + ky.

Definition at line 72 of file Intersect.cpp.

References GeographicLib::Geodesic::InverseLine(), LineCaps, and Segment().

Referenced by main(), and Segment().

◆ Segment() [2/2]

Find the intersection of two geodesic segments each defined by a GeodesicLine.

Parameters

Returns

p the intersection point if the segments intersect, otherwise the intersection point closest to the midpoints of the two segments.

Warning

lineX and lineY must represent shortest geodesics, e.g., they can be created by Geodesic::InverseLine. The results are only well defined if there's a unique shortest geodesic between the endpoints of the two segments.

Note

lineX and lineY should be created with minimum capabilities Intersect::LineCaps. The methods for creating a GeodesicLine include all these capabilities by default.

See previous definition of Intersect::Segment for more information on segmode.

Definition at line 83 of file Intersect.cpp.

◆ Next() [1/2]

Find the next closest intersection point to a given intersection, specified by position and two azimuths.

Parameters

Returns

p the next closest intersection point.

The returned intersection minimizes Intersect::Dist(p) (excluding p = [0,0]).

Note

Equidistant closest intersections are surprisingly common. If this may be a problem, use Intersect::All with a sufficiently large maxdist to capture close intersections.

Definition at line 91 of file Intersect.cpp.

References GeographicLib::Geodesic::Line(), LineCaps, and Next().

Referenced by main(), and Next().

◆ Next() [2/2]

Find the next closest intersection point to a given intersection, with each geodesic specified a GeodesicLine.

Parameters

Returns

p the next closest intersection point.

Warning

lineX and lineY must both have the same starting point, i.e., the distance between [lineX.Latitude(), lineX.Longitude()] and [lineY.Latitude(), lineY.Longitude()] must be zero.

Note

lineX and lineY should be created with minimum capabilities Intersect::LineCaps. The methods for creating a GeodesicLine include all these capabilities by default.

Equidistant closest intersections are surprisingly common. If this may be a problem, use Intersect::All with a sufficiently large maxdist to capture close intersections.

Definition at line 98 of file Intersect.cpp.

◆ All() [1/4]

Find all intersections within a certain distance, with each geodesic specified by position and azimuth.

Parameters

Returns

plist a vector for the intersections closest to p0.

Each intersection point satisfies Intersect::Dist(p, p0) ≤ maxdist. The vector of returned intersections is sorted on the distance from p0.

Definition at line 115 of file Intersect.cpp.

References All(), GeographicLib::Geodesic::Line(), and LineCaps.

Referenced by All(), All(), and main().

◆ All() [2/4]

Find all intersections within a certain distance, with each geodesic specified by position and azimuth. Don't return vector of coincidences.

Parameters

Returns

plist a vector for the intersections closest to p0.

Each intersection point satisfies Intersect::Dist(p, p0) ≤ maxdist. The vector of returned intersections is sorted on the distance from p0.

Definition at line 106 of file Intersect.cpp.

References All(), GeographicLib::Geodesic::Line(), and LineCaps.

◆ All() [3/4]

Find all intersections within a certain distance, with each geodesic specified by a GeodesicLine.

Parameters

Returns

plist a vector for the intersections closest to p0.

Each intersection point satisfies Intersect::Dist(p, p0) ≤ maxdist. The vector of returned intersections is sorted on the distance from p0.

Note

lineX and lineY should be created with minimum capabilities Intersect::LineCaps. The methods for creating a GeodesicLine include all these capabilities by default.

Definition at line 132 of file Intersect.cpp.

◆ All() [4/4]

Find all intersections within a certain distance, with each geodesic specified by a GeodesicLine. Don't return vector or coincidences.

Parameters

Returns

plist a vector for the intersections closest to p0.

Each intersection point satisfies Intersect::Dist(p, p0) ≤ maxdist. The vector of returned intersections is sorted on the distance from p0.

Note

lineX and lineY should be created with minimum capabilities Intersect::LineCaps. The methods for creating a GeodesicLine include all these capabilities by default.

Definition at line 125 of file Intersect.cpp.

◆ NumInverse()

Returns

the cumulative number of invocations of h.

This is a count of the number of times the spherical triangle needs to be solved. Each involves a call to Geodesic::Inverse and this is a good metric for the overall cost. This counter is set to zero by the constructor.

Warning

The counter is a mutable variable and so is not thread safe.

Definition at line 504 of file Intersect.hpp.

◆ NumBasic()

Returns

the cumulative number of invocations of b.

This is a count of the number of invocations of the basic algorithm, which is used by all the intersection methods. This counter is set to zero by the constructor.

Warning

The counter is a mutable variable and so is not thread safe.

Definition at line 514 of file Intersect.hpp.

◆ NumChange()

Returns

the number of times intersection point was changed in Intersect::Closest and Intersect::Next.

If this counter is incremented by just 1 in Intersect::Closest, then the initial result of the basic algorithm was eventually accepted. This counter is set to zero by the constructor.

Note

This counter is also incremented by Intersect::Segment, which calls Intersect::Closest.

Warning

The counter is a mutable variable and so is not thread safe.

Definition at line 528 of file Intersect.hpp.

◆ NumCorner()

Returns

the number of times a corner point is checked in Intersect::Segment.

This counter is set to zero by the constructor.

Warning

The counter is a mutable variable and so is not thread safe.

Definition at line 537 of file Intersect.hpp.

◆ NumOverride()

Returns

the number of times a corner point is returned by Intersect::Segment.

This counter is set to zero by the constructor.

Note

A conjecture is that a corner point never results in an intersection that overrides the intersection closest to the midpoints of the segments; i.e., NumCorner() always returns 0.

Warning

The counter is a mutable variable and so is not thread safe.

Definition at line 550 of file Intersect.hpp.

◆ GeodesicObject()

◆ Dist()

The L1 distance.

Parameters

Returns

the L1 distance of p from p0, i.e., |p x − p0 x| + |p y − p0 y|.

Definition at line 576 of file Intersect.hpp.

Referenced by main().

◆ LineCaps

The documentation for this class was generated from the following files:

• Intersect.hpp
• Intersect.cpp