GeezerVison is showing github.com — Python/other/graham_scan.py at master · https-github-com-nzysoft/Python

Expand file tree

graham_scan.py

Copy path

More file actions

Latest commit

History

173 lines (142 loc) · 5.33 KB

graham_scan.py

Copy path

File metadata and controls

173 lines (142 loc) · 5.33 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

"""

This is a pure Python implementation of the merge-insertion sort algorithm

Source: https://en.wikipedia.org/wiki/Graham_scan

For doctests run following command:

python3 -m doctest -v graham_scan.py

"""

from __future__ import annotations

from collections import deque

from enum import Enum

from math import atan2, degrees

from sys import maxsize

# traversal from the lowest and the most left point in anti-clockwise direction

# if direction gets right, the previous point is not the convex hull.

class Direction(Enum):

left = 1

straight = 2

right = 3

def __repr__(self):

return f"{self.__class__.__name__}.{self.name}"

def angle_comparer(point: tuple[int, int], minx: int, miny: int) -> float:

"""Return the angle toward to point from (minx, miny)

:param point: The target point

minx: The starting point's x

miny: The starting point's y

:return: the angle

Examples:

>>> angle_comparer((1,1), 0, 0)

45.0

>>> angle_comparer((100,1), 10, 10)

-5.710593137499642

>>> angle_comparer((5,5), 2, 3)

33.690067525979785

"""

# sort the points accorgind to the angle from the lowest and the most left point

x, y = point

return degrees(atan2(y - miny, x - minx))

def check_direction(

starting: tuple[int, int], via: tuple[int, int], target: tuple[int, int]

) -> Direction:

"""Return the direction toward to the line from via to target from starting

:param starting: The starting point

via: The via point

target: The target point

:return: the Direction

Examples:

>>> check_direction((1,1), (2,2), (3,3))

Direction.straight

>>> check_direction((60,1), (-50,199), (30,2))

Direction.left

>>> check_direction((0,0), (5,5), (10,0))

Direction.right

"""

x0, y0 = starting

x1, y1 = via

x2, y2 = target

via_angle = degrees(atan2(y1 - y0, x1 - x0))

via_angle %= 360

target_angle = degrees(atan2(y2 - y0, x2 - x0))

target_angle %= 360

# t-

# \ \

# \ v

# \|

# s

# via_angle is always lower than target_angle, if direction is left.

# If they are same, it means they are on a same line of convex hull.

if target_angle > via_angle:

return Direction.left

elif target_angle == via_angle:

return Direction.straight

else:

return Direction.right

def graham_scan(points: list[tuple[int, int]]) -> list[tuple[int, int]]:

"""Pure implementation of graham scan algorithm in Python

:param points: The unique points on coordinates.

:return: The points on convex hell.

Examples:

>>> graham_scan([(9, 6), (3, 1), (0, 0), (5, 5), (5, 2), (7, 0), (3, 3), (1, 4)])

[(0, 0), (7, 0), (9, 6), (5, 5), (1, 4)]

>>> graham_scan([(0, 0), (1, 0), (1, 1), (0, 1)])

[(0, 0), (1, 0), (1, 1), (0, 1)]

>>> graham_scan([(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)])

[(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)]

>>> graham_scan([(-100, 20), (99, 3), (1, 10000001), (5133186, -25), (-66, -4)])

[(5133186, -25), (1, 10000001), (-100, 20), (-66, -4)]

"""

if len(points) <= 2:

# There is no convex hull

raise ValueError("graham_scan: argument must contain more than 3 points.")

if len(points) == 3:

return points

# find the lowest and the most left point

minidx = 0

miny, minx = maxsize, maxsize

for i, point in enumerate(points):

x = point[0]

y = point[1]

if y < miny:

miny = y

minx = x

minidx = i

if y == miny:

if x < minx:

minx = x

minidx = i

# remove the lowest and the most left point from points for preparing for sort

points.pop(minidx)

sorted_points = sorted(points, key=lambda point: angle_comparer(point, minx, miny))

# This insert actually costs complexity,

# and you should instead add (minx, miny) into stack later.

# I'm using insert just for easy understanding.

sorted_points.insert(0, (minx, miny))

stack: deque[tuple[int, int]] = deque()

stack.append(sorted_points[0])

stack.append(sorted_points[1])

stack.append(sorted_points[2])

# In any ways, the first 3 points line are towards left.

# Because we sort them the angle from minx, miny.

current_direction = Direction.left

for i in range(3, len(sorted_points)):

while True:

starting = stack[-2]

via = stack[-1]

target = sorted_points[i]

next_direction = check_direction(starting, via, target)

if next_direction == Direction.left:

current_direction = Direction.left

break

if next_direction == Direction.straight:

if current_direction == Direction.left:

# We keep current_direction as left.

# Because if the straight line keeps as straight,

# we want to know if this straight line is towards left.

break

elif current_direction == Direction.right:

# If the straight line is towards right,

# every previous points on those straigh line is not convex hull.

stack.pop()

if next_direction == Direction.right:

stack.pop()

stack.append(sorted_points[i])

return list(stack)