convex created by croese - https://repl.it/@croese/convex

Convex hull algorithm - python

import random
import math

class RandomPointGenerator:
  
  def generate(self, num_points, max_x, max_y, min_allowable_distance):
    r = self.random_points(max_x, max_y)
    found_points = set()
    for i in range(num_points):
      cx, cy = next(r)
      
      if len(found_points) == 0:
        found_points.add((cx,cy))
        continue
      
      distances = (math.sqrt( (cx - fx) ** 2 + (cy - fy) ** 2 ) for (fx, fy) in found_points)
      min_distance = min(distances)
      if min_distance >= min_allowable_distance:
        found_points.add((cx,cy))
    
    return list(found_points)

  def random_points(self, max_x, max_y):
    while True:
      yield (random.randrange(0,max_x), random.randrange(0, max_y))
  
rpg = RandomPointGenerator()
points = rpg.generate(100, 200, 200, 10)
print(points)

class ConvexHullGenerator:
  
  LEFT_TURN = 1
  RIGHT_TURN = -1
  COLLINEAR = 0

  def generate(self, points):
    if len(points) < 3:
      return []
    
    sorted_points = sorted(points)
    hull_upper = [sorted_points[0], sorted_points[1]]
    
    for index in range(2, len(points)):
      hull_upper.append(sorted_points[index])
      while len(hull_upper) > 2:
        p1, p2, p3 = hull_upper[len(hull_upper)-3:]
        turn = self.cross_product_sign(p1,p2,p3)
        if turn == self.RIGHT_TURN:
          break
        
        hull_upper.pop(-2)
    
    hull_lower = [sorted_points[-1], sorted_points[-2]]
    for index in range(len(sorted_points)-3, -1, -1):
      hull_lower.append(sorted_points[index])
      while len(hull_lower) > 2:
        p1, p2, p3 = hull_lower[len(hull_lower)-3:]
        turn = self.cross_product_sign(p1,p2,p3)
        if turn == self.RIGHT_TURN:
          break
        
        hull_lower.pop(-2)
      
    return hull_upper + hull_lower[1:-1]
    
  
  def cross_product_sign(self, p1, p2, p3):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    cross_product = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
    
    if cross_product < 0:
      return self.RIGHT_TURN
    elif cross_product > 0:
      return self.LEFT_TURN
    else:
      return self.COLLINEAR


chg = ConvexHullGenerator()
hull_points = chg.generate(points)
print(hull_points)

print('<svg width="300" height="300">')
for (cx,cy) in points:
  print('<circle cx="{}" cy="{}" r="5" />'.format(cx+50, cy+50))
  
for ((x1, y1), (x2, y2)) in zip(hull_points, hull_points[1:]):
  print('<line x1="{}" x2="{}" y1="{}" y2="{}" stroke="black"/>'.format(x1+50, x2+50, y1+50, y2+50))

p_first, p_last = hull_points[0], hull_points[-1]
print('<line x1="{}" x2="{}" y1="{}" y2="{}" stroke="black"/>'.format(p_first[0]+50, p_last[0]+50, p_first[1]+50, p_last[1]+50))
print('</svg>')