Convex hull: Difference between revisions
→{{header|Fortran}}
Line 956:
public :: find_convex_hull
contains
Line 1,021 ⟶ 1,020:
end do
end subroutine sort_points
subroutine delete_neighbor_duplicates (n, pt)
integer, intent(inout) :: n
complex, intent(inout) :: pt(0:*)
call delete_trailing_duplicates
call delete_nontrailing_duplicates
contains
subroutine delete_trailing_duplicates
integer :: i
logical :: done
i = n - 1
done = .false.
do while (.not. done)
done = .true.
else if (pt(i - 1) /= pt(i)) then
n = i + 1
done = .true.
else
i = i - 1
end if
end do
end subroutine delete_trailing_duplicates
subroutine delete_nontrailing_duplicates
integer :: i, j, num_deleted
logical :: done
i = 0
do while (i < n - 1)
j = i + 1
done = .false.
do while (.not. done)
if (j == n) then
done = .true.
else if (pt(j) /= pt(i)) then
done = .true.
else
j = j + 1
end if
end do
if (j /= i + 1) then
num_deleted = j - i - 1
do while (j /= n)
pt(j - num_deleted) = pt(j)
j = j + 1
end do
n = n - num_deleted
end if
i = i + 1
end do
end subroutine delete_nontrailing_duplicates
end subroutine delete_neighbor_duplicates
subroutine construct_lower_hull (n, pt, hull_size, hull)
Line 1,124 ⟶ 1,182:
complex :: pt(0 : n - 1)
integer :: ipoints0, ihull0, numpt
ipoints0 = lbound (points, 1)
ihull0 = lbound (hull, 1)
numpt = n
call delete_neighbor_duplicates (numpt, pt)
if (numpt == 0) then
hull_size = 0
else if (
hull_size =
hull(:ihull0 + numpt - 1) =
▲ else if (n == 2) then
▲ hull_size = 2
else
▲ call sort_points (n, pt)
end if
end subroutine find_convex_hull
| |||