Computational geometry tools relative to lines and polygon intersection More...

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.

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.

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.

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.

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.

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.

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.

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`)

Functions/Subroutines

Detailed Description

Function/Subroutine Documentation

◆ cg2_brute_force_split_polygon_with_line()

◆ cg2_is_line_intersect_polygon()

◆ cg2_maxloc_line_point_signed_distance()

◆ cg2_minloc_line_point_signed_distance()

◆ cg2_optimized_split_polygon_with_line()

◆ cg2_split_polygon()

◆ cg2_split_polygon_with_line()