Line/line segment intersection

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

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 )

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 )

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 )

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 )

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 )

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 )

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 )

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 )

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 )

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 )

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 )

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 )

   !!  + 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