cmerge Subroutine

private subroutine cmerge(n, a, i, m, h)

given the upper convex hulls of two consecutive sets of pairs (j,a(j)), compute the upper convex hull of their union

Arguments

Type IntentOptional Attributes Name
integer, intent(in) :: n

length of the vector a
real(kind=wp), intent(in) :: a(n)

vector defining the points (j,a(j))
integer, intent(in) :: i

abscissa of the common vertex of the two sets
integer, intent(in) :: m

the number of elements of each set is m+1
logical, intent(out) :: h(n)

vector defining the vertices of the convex hull, i.e., h(j) is .true. if (j,a(j)) is a vertex of the convex hull this vector is used also as output.

Calls

proc~~cmerge~~CallsGraph proc~cmerge cmerge proc~ctest ctest proc~cmerge->proc~ctest proc~left left proc~cmerge->proc~left proc~right right proc~cmerge->proc~right

Called by

proc~~cmerge~~CalledByGraph proc~cmerge cmerge proc~cnvex cnvex proc~cnvex->proc~cmerge proc~start start proc~start->proc~cnvex proc~polzeros polzeros proc~polzeros->proc~start

Source Code

    subroutine cmerge(n, a, i, m, h)

        !! given the upper convex hulls of two consecutive sets of pairs
        !! (j,a(j)), compute the upper convex hull of their union

        implicit none

        integer,intent(in) :: n !! length of the vector a
        real(wp),intent(in) :: a(n) !! vector defining the points (j,a(j))
        integer,intent(in) :: i !! abscissa of the common vertex of the two sets
        integer,intent(in) :: m !! the number of elements of each set is m+1
        logical,intent(out) :: h(n) !! vector defining the vertices of the convex hull, i.e.,
                                    !! h(j) is .true. if (j,a(j)) is a vertex of the convex hull
                                    !! this vector is used also as output.

        integer :: ir, il, irr, ill
        logical :: tstl, tstr

        ! at the left and the right of the common vertex (i,a(i)) determine
        ! the abscissae il,ir, of the closest vertices of the upper convex
        ! hull of the left and right sets, respectively
        call left(n, h, i, il)
        call right(n, h, i, ir)
        ! check the convexity of the angle formed by il,i,ir
        if (ctest(n, a, il, i, ir)) then
            return
        else
            ! continue the search of a pair of vertices in the left and right
            ! sets which yield the upper convex hull
            h(i) = .false.
            do
                if (il == (i - m)) then
                    tstl = .true.
                else
                    call left(n, h, il, ill)
                    tstl = ctest(n, a, ill, il, ir)
                end if
                if (ir == min(n, i + m)) then
                    tstr = .true.
                else
                    call right(n, h, ir, irr)
                    tstr = ctest(n, a, il, ir, irr)
                end if
                h(il) = tstl
                h(ir) = tstr
                if (tstl .and. tstr) return
                if (.not. tstl) il = ill
                if (.not. tstr) ir = irr
            end do
        end if

    end subroutine cmerge