Polygon/polygon intersection

Computational geometry tools relative to polygon intersection More...

Functions/Subroutines
pure subroutine	mod_cg2_polygon_polygon::cg2_convex_polygon_intersection (polygon1, polygon2, polygon_intersection, intersection_found)
	Intersection of two convex polygons whose points are defined in counterclockwise order.
pure subroutine	mod_cg2_polygon_polygon::cg2_polygon_boundary_intersection (polygon1, polygon2, s0, s1, i, j, intersection_found)
	Check if two polygons have a common boundary and compute the intersection.

Detailed Description

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

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

pure subroutine mod_cg2_polygon_polygon::cg2_convex_polygon_intersection	(	type(t_polygon), intent(in)	polygon1,
		type(t_polygon), intent(in)	polygon2,
		type(t_polygon), intent(out)	polygon_intersection,
		logical, intent(out)	intersection_found )

This algorithm is an adaptation of the O'Rourke's algorithm to non-integer coordinates.

References:

• O'Rourke, J., Chien, C. B., Olson, T., & Naddor, D. (1982). A new linear algorithm for intersecting convex polygons. Computer Graphics and Image Processing, 19(4), 384-391. doi:10.1016/0146-664X(82)90023-5

Parameters

[in]	polygon1,polygon2	Convex polygons to intersect
[out]	polygon_intersection	Convex polygon resulting in the intersection of polygon1 and polygon2
[out]	intersection_found	.true. if an intersection is found

cg2_polygon_boundary_intersection()

pure subroutine mod_cg2_polygon_polygon::cg2_polygon_boundary_intersection	(	type(t_polygon), intent(in)	polygon1,
		type(t_polygon), intent(in)	polygon2,
		double precision, dimension(2), intent(out)	s0,
		double precision, dimension(2), intent(out)	s1,
		integer, intent(out)	i,
		integer, intent(out)	j,
		logical, intent(out)	intersection_found )

Parameters

[in]	polygon1,polygon2	Polygons to check for boundary intersection
[out]	s0,s1	The two extreme points of the resulting line segment
[out]	i,j	Indices of the polygon edges [i, i+1] and [j, j+1].
[out]	intersection_found	.true. if the boundaries overlap