Line/polygon intersection

Functions/Subroutines
logical pure function	mod_cg2_line_polygon::cg2_is_line_intersect_polygon (polygon, l0, l1)
	Return true if a line [l0, l1] intersect a convex polygon. More...
pure subroutine	mod_cg2_line_polygon::cg2_split_polygon (polygon, p0, p1, i0, i1, polygon_left, polygon_right)
	Split a convex polygon {p(1),...,p(n)} in two polygons. More...
pure subroutine	mod_cg2_line_polygon::cg2_split_polygon_with_line (polygon, l0, l1, is_intersection, polygon_left, polygon_right)
	Split a convex polygon with a line. More...
pure subroutine	mod_cg2_line_polygon::cg2_brute_force_split_polygon_with_line (polygon, l0, l1, is_intersection, polygon_left, polygon_right)
	Split a polygon with a line using a brute force method. More...
pure subroutine	mod_cg2_line_polygon::cg2_optimized_split_polygon_with_line (polygon, l0, l1, is_intersection, polygon_left, polygon_right)
	Split a polygon with a line using an optimized algorithm. More...
pure subroutine	mod_cg2_line_polygon::cg2_minloc_line_point_signed_distance (polygon, p0, p1, pref, minimum_distance, minloc_distance)
	Locate the minimum location of the signed distance using Fibonacci search of periodic bimodal function. More...
pure subroutine	mod_cg2_line_polygon::cg2_maxloc_line_point_signed_distance (polygon, p0, p1, pref, maximum_distance, maxloc_distance)
	Locate the maximum location of the signed distance using Fibonacci search of periodic bimodal function. More...

Detailed Description

This module defines various functions and subroutines to detect and/or compute the intersection of a line and a polygon.

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_brute_force_split_polygon_with_line()

pure subroutine mod_cg2_line_polygon::cg2_brute_force_split_polygon_with_line	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		logical, intent(out)	is_intersection,
		type(t_polygon), intent(out)	polygon_left,
		type(t_polygon), intent(out)	polygon_right
	)

Parameters

[in]	polygon	Any convex polygon whose points are defined in counterclockwise order
[in]	l0,l1	Two points defining a line
[out]	is_intersection	.true. if an intersection is found
[out]	polygon_left	The polygon that lies on the left side of the line (l0, l1)
[out]	polygon_right	The polygon that lies on the right side of the line (l0, l1)

cg2_is_line_intersect_polygon()

logical pure function mod_cg2_line_polygon::cg2_is_line_intersect_polygon	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1
	)

This function uses the Fibonacci search to speed up the detection for convex polygons with large number of points.

See also

mod_cg2_line_polygon::cg2_minloc_line_point_signed_distance

Parameters

[in]	polygon	Any convex polygon
[in]	l0,l1	Two points defining a line

cg2_maxloc_line_point_signed_distance()

pure subroutine mod_cg2_line_polygon::cg2_maxloc_line_point_signed_distance	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		double precision, dimension(2), intent(in)	pref,
		double precision, intent(out)	maximum_distance,
		integer, intent(out)	maxloc_distance
	)

Comments A0,...,A5 are reference to the Veroy's publication.

References:

• Chazelle, B., & Dobkin, D. P. (1987). Intersection of convex objects in two and three dimensions. Journal of the ACM (JACM), 34(1), 1-27. doi:10.1145/7531.24036
• Veroy, B. S. (1986). An optimal algorithm for search of extrema of a bimodal function. Journal of Complexity, 2(4), 323-332. doi:10.1016/0885-064X(86)90010-5

Parameters

[in]	polygon	Any convex polygon whose points are defined in counterclockwise order
[in]	p0,p1	Two points of the line (p0, p1)
[in]	pref	Any reference point
[out]	maximum_distance	Maximal signed distance between the polygon and a line
[out]	maxloc_distance	Location of maximal signed distance between the polygon and a line

cg2_minloc_line_point_signed_distance()

pure subroutine mod_cg2_line_polygon::cg2_minloc_line_point_signed_distance	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		double precision, dimension(2), intent(in)	pref,
		double precision, intent(out)	minimum_distance,
		integer, intent(out)	minloc_distance
	)

Comments A0,...,A5 are reference to the Veroy's publication.

References:

• Chazelle, B., & Dobkin, D. P. (1987). Intersection of convex objects in two and three dimensions. Journal of the ACM (JACM), 34(1), 1-27. doi:10.1145/7531.24036
• Veroy, B. S. (1986). An optimal algorithm for search of extrema of a bimodal function. Journal of Complexity, 2(4), 323-332. doi:10.1016/0885-064X(86)90010-5

Parameters

[in]	polygon	Any convex polygon whose points are defined in counterclockwise order
[in]	p0,p1	Two points of the line (p0, p1)
[in]	pref	Any reference point
[out]	minimum_distance	Minimal signed distance between the polygon and a line
[out]	minloc_distance	Location of the minimal signed distance between the polygon and a line

cg2_optimized_split_polygon_with_line()

pure subroutine mod_cg2_line_polygon::cg2_optimized_split_polygon_with_line	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		logical, intent(out)	is_intersection,
		type(t_polygon), intent(out)	polygon_left,
		type(t_polygon), intent(out)	polygon_right
	)

References:

• Chazelle, B., & Dobkin, D. P. (1987). Intersection of convex objects in two and three dimensions. Journal of the ACM (JACM), 34(1), 1-27. doi:10.1145/7531.24036

Parameters

[in]	polygon	Any convex polygon whose points are defined in counterclockwise order
[in]	l0,l1	Two points defining a line
[out]	is_intersection	.true. if an intersection is found
[out]	polygon_left	The polygon that lies on the left side of the line (l0, l1)
[out]	polygon_right	The polygon that lies on the right side of the line (l0, l1)

cg2_split_polygon()

pure subroutine mod_cg2_line_polygon::cg2_split_polygon	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	p0,
		double precision, dimension(2), intent(in)	p1,
		integer, intent(in)	i0,
		integer, intent(in)	i1,
		type(t_polygon), intent(out)	polygon_left,
		type(t_polygon), intent(out)	polygon_right
	)

The output consists in two polygons defined as:

• left polygon {p0, p(i0+1), ..., p(i1), p1}
• right polygon {p1, p(i1+1), ..., p(i0), p0}

where:

• p0 is a point which belongs to the segment [p(i0 ), p(i0 +1)] of the input polygon
• p1 is a point which belongs to the segment [p(i1 ), p(i1 +1)] of the input polygon

Parameters

[in]	polygon	Any convex polygon whose points are defined in counterclockwise order
[in]	p0	Any point that belongs to the segment [p(i0), p(i0+1)]
[in]	p1	Any point that belongs to the segment [p(i1), p(i1+1)]
[in]	i0,i1	Indices of the point such that p0 ∈ [p(i0), p(i0+1)] and p1 ∈ [p(i1), p(i1+1)]
[out]	polygon_left	The polygon that lies on the left side of the line (p0, p1)
[out]	polygon_right	The polygon that lies on the right side of the line (p0, p1)

cg2_split_polygon_with_line()

pure subroutine mod_cg2_line_polygon::cg2_split_polygon_with_line	(	type(t_polygon), intent(in)	polygon,
		double precision, dimension(2), intent(in)	l0,
		double precision, dimension(2), intent(in)	l1,
		logical, intent(out)	is_intersection,
		type(t_polygon), intent(out)	polygon_left,
		type(t_polygon), intent(out)	polygon_right
	)

Two algorithms are available:

• a brute force algorithm: mod_cg2_line_polygon::cg2_brute_force_split_polygon_with_line
• an optimized algorithm: mod_cg2_line_polygon::cg2_optimized_split_polygon_with_line

This routine selects the fastest algorithm depending on the number of points.

Parameters

[in]	polygon	Any convex polygon whose points are defined in counterclockwise order
[in]	l0,l1	Two points defining a line
[out]	is_intersection	.true. if an intersection is found
[out]	polygon_left	The polygon that lies on the left side of the line (l0, l1)
[out]	polygon_right	The polygon that lies on the right side of the line (l0, l1)