Computational geometry tools relative to lines and line segments intersection More...

Functions/Subroutines
logical pure function	mod_cg2_line_segment::cg2_does_segments_intersect (p0, p1, q0, q1)
	Check if two line segments intersect [`p0`, `p1`] ∩ [`q0`, `q1`].

logical pure function	mod_cg2_line_segment::cg2_does_line_intersect_segment (l0, l1, s0, s1)
	Check if a line intersect a line segment (l0, l1) ∩ [s0, s1].

double precision pure function	mod_cg2_line_segment::cg2_line_point_distance (l0, l1, p)
	Return the distance of the point `p` to the line (`l0`, `l1`).

double precision pure function	mod_cg2_line_segment::cg2_line_point_signed_distance (l0, l1, p, pref)
	Return the signed distance of point `p` to the line (`l0`, `l1`) relatively to the point `pref`.

pure subroutine	mod_cg2_line_segment::cg2_point_line_segment_closest_point (s0, s1, p, point)
	Return the closest point of point `p` to the line segment [`s0`, `s1`].

pure subroutine	mod_cg2_line_segment::cg2_line_segment_intersection (l0, l1, s0, s1, is_intersection, intersection_point)
	Return the intersection point of a line and a segment (`l0`, `l1`) ∩ [`s0`, `s1`].

pure subroutine	mod_cg2_line_segment::cg2_line_segment_intersection2 (origin, v, s0, s1, is_intersection, intersection_point)
	Return the intersection point of a line and a segment {`origin`, `v}` ∩ [`s0`, `s1`].

pure subroutine	mod_cg2_line_segment::cg2_line_segment_inclusive_intersection (l0, l1, s0, s1, is_intersection, intersection_point)
	Return the intersection point of a line and a segment (`l0`, `l1`) ∩ [`s0`, `s1`] including end points.

pure subroutine	mod_cg2_line_segment::cg2_segments_intersection (p0, p1, q0, q1, is_intersection, intersection_point)
	Return the intersection point of two line segments [`p0`, `p1`] ∩ [`q0`, `q1`].

pure subroutine	mod_cg2_line_segment::cg2_segment_ray_intersection (p0, p1, o, d, is_intersection, distance, intersection_point)
	Return the intersection point a line segment [`p0`, `p1`] and a ray.

pure subroutine	mod_cg2_line_segment::cg2_segments_overlap (p0, p1, q0, q1, s0, s1, are_overlapping)
	Check and compute the overlapping of two line segments.

subroutine	mod_cg2_line_segment::cg2_line_write_vtk_file (s0, s1, filename)
	Print a line segment into a VTK file for debug purpose.

Detailed Description

Computational geometry tools relative to lines and line segments intersection

This module defines various functions and subroutines to detect and/or compute the intersection of two lines or line segments.

Attention: Modify these functions at your own risk. Many algorithms depend on the specific behaviour of these functions. They are designed to not generate false negative results. Note that false positive results may occur due to the finite representation of real numbers. Take that into consideration when writing new algorithms.

Function/Subroutine Documentation

◆ cg2_does_line_intersect_segment()

logical pure function mod_cg2_line_segment::cg2_does_line_intersect_segment	(	double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		double precision, dimension(2), intent(in)	s0,
		double precision, dimension(2), intent(in)	s1 )

Check if a line intersect a line segment (l0, l1) ∩ [s0, s1].

Parameters

[in]	l0,l1	Two points of the line (`l0`, `l1`)
[in]	s0,s1	The two extreme points of the line segment [`s0`, `s1`]

◆ cg2_does_segments_intersect()

logical pure function mod_cg2_line_segment::cg2_does_segments_intersect	(	double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		double precision, dimension(2), intent(in)	q0,
		double precision, dimension(2), intent(in)	q1 )

Check if two line segments intersect [p0, p1] ∩ [q0, q1].

Parameters

[in]	p0,p1	The two extreme points of the line segment [`p0`, `p1`]
[in]	q0,q1	The two extreme points of the line segment [`q0`, `q1`]

◆ cg2_line_point_distance()

double precision pure function mod_cg2_line_segment::cg2_line_point_distance	(	double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		double precision, dimension(2), intent(in)	p )

Return the distance of the point p to the line (l0, l1).

Parameters

[in]	l0,l1	Two points of the line (`l0`, `l1`)
[in]	p	Any point

◆ cg2_line_point_signed_distance()

double precision pure function mod_cg2_line_segment::cg2_line_point_signed_distance	(	double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		double precision, dimension(2), intent(in)	p,
		double precision, dimension(2), intent(in)	pref )

Return the signed distance of point p to the line (l0, l1) relatively to the point pref.

If pref lies on the same side as p, the sign is positive, otherwise it is negative. If you are interested in the distance of a point to a line, see mod_cg2_line_segment::cg2_line_point_distance.

Parameters

[in]	l0,l1	Two points of the line (`l0`, `l1`)
[in]	p	Any point
[in]	pref	Reference point to determinate the sign

◆ cg2_line_segment_inclusive_intersection()

pure subroutine mod_cg2_line_segment::cg2_line_segment_inclusive_intersection	(	double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		double precision, dimension(2), intent(in)	s0,
		double precision, dimension(2), intent(in)	s1,
		logical, intent(out)	is_intersection,
		double precision, dimension(2), intent(out)	intersection_point )

Return the intersection point of a line and a segment (l0, l1) ∩ [s0, s1] including end points.

Parameters

[in]	l0,l1	Two points of the line (`l0`, `l1`)
[in]	s0,s1	The two extreme points of the line segment [`s0`, `s1`]
[out]	is_intersection	.true. if an intersection is found
[out]	intersection_point	contains the intersection point if it exists, otherwise it contains the null vector

◆ cg2_line_segment_intersection()

pure subroutine mod_cg2_line_segment::cg2_line_segment_intersection	(	double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		double precision, dimension(2), intent(in)	s0,
		double precision, dimension(2), intent(in)	s1,
		logical, intent(out)	is_intersection,
		double precision, dimension(2), intent(out)	intersection_point )

Return the intersection point of a line and a segment (l0, l1) ∩ [s0, s1].

Attention: This function is designed to generate false positive intersection instead of false negative results.

Parameters

[in]	l0,l1	Two points of the line (`l0`, `l1`)
[in]	s0,s1	The two extreme points of the line segment [`s0`, `s1`]
[out]	is_intersection	.true. if an intersection is found
[out]	intersection_point	contains the intersection point if it exists, otherwise it contains the null vector

◆ cg2_line_segment_intersection2()

pure subroutine mod_cg2_line_segment::cg2_line_segment_intersection2	(	double precision, dimension(2), intent(in)	origin,
		double precision, dimension(2), intent(in)	v,
		double precision, dimension(2), intent(in)	s0,
		double precision, dimension(2), intent(in)	s1,
		logical, intent(out)	is_intersection,
		double precision, dimension(2), intent(out)	intersection_point )

Return the intersection point of a line and a segment {origin, v} ∩ [s0, s1].

Attention: This function is designed to generate false positive intersection instead of false negative results.

Parameters

[in]	origin	origin point of the line
[in]	v	direction vector of the line
[in]	s0,s1	The two extreme points of the line segment [`s0`, `s1`]
[out]	is_intersection	.true. if an intersection is found
[out]	intersection_point	contains the intersection point if it exists, otherwise it contains the null vector

◆ cg2_line_write_vtk_file()

subroutine mod_cg2_line_segment::cg2_line_write_vtk_file	(	double precision, dimension(2)	s0,
		double precision, dimension(2)	s1,
		character(len=*), intent(in)	filename )

Print a line segment into a VTK file for debug purpose.

Parameters

[in]	s0,s1	The two extreme points of the line segment [`s0`, `s1`]
[in]	filename	File name of the VTK file

◆ cg2_point_line_segment_closest_point()

pure subroutine mod_cg2_line_segment::cg2_point_line_segment_closest_point	(	double precision, dimension(2), intent(in)	s0,
		double precision, dimension(2), intent(in)	s1,
		double precision, dimension(2), intent(in)	p,
		double precision, dimension(2), intent(out)	point )

Return the closest point of point p to the line segment [s0, s1].

Parameters

[in]	s0,s1	The two extreme points of the line segment [`s0`, `s1`]
[in]	p	Any point
[out]	point	Closest point of point @ p to the line segment [`s0`, `s1`].

◆ cg2_segment_ray_intersection()

pure subroutine mod_cg2_line_segment::cg2_segment_ray_intersection	(	double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		double precision, dimension(2), intent(in)	o,
		double precision, dimension(2), intent(in)	d,
		logical, intent(out)	is_intersection,
		double precision, intent(out)	distance,
		double precision, dimension(2), intent(out)	intersection_point )

Return the intersection point a line segment [p0, p1] and a ray.

Parameters

[in]	p0,p1	The two extreme points of the line segment [`p0`, `p1`]
[in]	o	Origin of the ray
[in]	d	Direction of the ray
[out]	is_intersection	.true. if an intersection is found
[out]	distance	distance from the origin to the intersection. Contains zero if no intersection is found
[out]	intersection_point	contains the intersection point if it exists, otherwise it contains the null vector

◆ cg2_segments_intersection()

pure subroutine mod_cg2_line_segment::cg2_segments_intersection	(	double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		double precision, dimension(2), intent(in)	q0,
		double precision, dimension(2), intent(in)	q1,
		logical, intent(out)	is_intersection,
		double precision, dimension(2), intent(out)	intersection_point )

Return the intersection point of two line segments [p0, p1] ∩ [q0, q1].

Attention: This function is designed to generate false positive intersection instead of false negative results.

Parameters

[in]	p0,p1	The two extreme points of the line segment [`p0`, `p1`]
[in]	q0,q1	The two extreme points of the line segment [`q0`, `q1`]
[out]	is_intersection	.true. if an intersection is found
[out]	intersection_point	contains the intersection point if it exists, otherwise it contains the null vector

◆ cg2_segments_overlap()

pure subroutine mod_cg2_line_segment::cg2_segments_overlap	(	double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		double precision, dimension(2), intent(in)	q0,
		double precision, dimension(2), intent(in)	q1,
		double precision, dimension(2), intent(out)	s0,
		double precision, dimension(2), intent(out)	s1,
		logical, intent(out)	are_overlapping )

Check and compute the overlapping of two line segments.

  !!  + p1
  !!  |        + q1       + s1
  !!  |        |          |
  !!  |        ^      ->  ^
  !!  ^        |          |
  !!  |        + q0       + s0
  !!  + p0
  !!

If both line segments are parallel and have the same orientation [s0, s1] will have the same orientation as [p0, p1].

Parameters

[in]	p0,p1	The two extreme points of the line segment [`p0`, `p1`]
[in]	q0,q1	The two extreme points of the line segment [`q0`, `q1`]
[out]	s0,s1	The two extreme points of the resulting line segment [`s0`, `s1`]
[out]	are_overlapping	.true. if an overlapping is found

Functions/Subroutines

Detailed Description

Function/Subroutine Documentation

◆ cg2_does_line_intersect_segment()

◆ cg2_does_segments_intersect()

◆ cg2_line_point_distance()

◆ cg2_line_point_signed_distance()

◆ cg2_line_segment_inclusive_intersection()

◆ cg2_line_segment_intersection()

◆ cg2_line_segment_intersection2()

◆ cg2_line_write_vtk_file()

◆ cg2_point_line_segment_closest_point()

◆ cg2_segment_ray_intersection()

◆ cg2_segments_intersection()

◆ cg2_segments_overlap()