Type | Intent | Optional | Attributes | Name | ||
---|---|---|---|---|---|---|
integer | :: | nsides | ||||
type(Vector_2d) | :: | polygon(nsides) | ||||
type(Vector_2d) | :: | point |
Nodes of different colours represent the following:
Solid arrows point from a procedure to one which it calls. Dashed arrows point from an interface to procedures which implement that interface. This could include the module procedures in a generic interface or the implementation in a submodule of an interface in a parent module. Where possible, edges connecting nodes are given different colours to make them easier to distinguish in large graphs.
function polygon_contains_point_2d ( nsides, polygon, point) result(inside)
! Function information:
! Author Linda Lawrie
! Date written October 2005
! Modified na
! Re-engineered na
! Purpose of this function:
! Determine if a point is inside a simple 2d polygon. For a simple polygon (one whose
! boundary never crosses itself). The polygon does not need to be convex.
! Methodology employed:
! <Description>
! References:
! M Shimrat, Position of Point Relative to Polygon, ACM Algorithm 112,
! Communications of the ACM, Volume 5, Number 8, page 434, August 1962.
! Use statements:
! na
Implicit none ! Enforce explicit typing of all variables in this routine
! Function argument definitions:
integer :: nsides ! number of sides (vertices)
type(Vector_2d) :: polygon(nsides) ! points of polygon
type(Vector_2d) :: point ! point to be tested
logical :: inside ! return value, true=inside, false = not inside
! Function parameter definitions:
real(r64), parameter :: point_tolerance=.00001d0
! Interface block specifications:
! na
! Derived type definitions:
! na
! Function local variable declarations:
integer i
integer ip1
inside = .false.
do i = 1, nsides
if ( i < nsides ) then
ip1 = i + 1
else
ip1 = 1
end if
if ( ( polygon(i)%y < point%y .and. point%y <= polygon(ip1)%y ) .or. &
( point%y <= polygon(i)%y .and. polygon(ip1)%y < point%y ) ) then
if ( ( point%x - polygon(i)%x ) - ( point%y - polygon(i)%y ) &
* ( polygon(ip1)%x - polygon(i)%x ) / ( polygon(ip1)%y - polygon(i)%y ) < 0 ) then
inside = .not. inside
end if
end if
end do
return
end function polygon_contains_point_2d