Статья Автор: Лебедев Дмитрий Алексеевич

КЧ на Python - Выпуклые оболочки

Из точки A вектором b надо нарисовать правильный N-угольник и подсчитать количество точек с целочисленными координатами внутри него.
Задачу разобьем на два этапа:

Построим список вершин
Переберем точки в описанном прямоугольнике и подсчитаем количество подходящих

Для выполнения 1-го этапа надо:

определить угол поворота = 360/N (только в радианах)
можно нарисовать Черепашкой

Выполнять задание будем в комплексных числах, поэтому потребуется библиотека cmath

import cmath as cm # импорт библиотеки КЧ
import turtle as tr # импорт Черепашки
A = -30-40j #рисовать начинаем из точки с координатами 
rb,ub = 50, cm.pi/180*30 # длина вектора и начальный угол
N = 9 # число сторон многоугольника
u = 2*cm.pi/N # базовый угол поворота многоугольника
P = [A] # список для вершин многоугольника
for i in range(N-1): # добавление вершин
  P.append(P[-1]+cm.rect(rb,u*i+ ub)) 
P.append(P[0]) # зацикливание
print(P) # отладочнай печать координат вершин 
m =3 # Масштаб для рисования
tr.dot(5); tr.width(3); tr.speed(10) # начальная настройка Черепашки
tr.up(); tr.goto(m*(P[0].real), m*(P[0].imag)); tr.down() # перемещение в точку старта
for d in P : #отрисовка многоугольника
  tr.goto(m*(d.real), m*(d.imag))
tr.done()

Задача могла быть представлена в формате экзамена (КЕГЭ-6. Черепашка)
Исполнителю Черепашка задан алгоритм

Поднять перо; Назад 40; Направо 90; Назад 30
Налево 30; Опусти перо
Повтори 9 раз [Вперед 50 Налево 40]

Вопросы к задаче могли быть заданы следующие:

Сколько точек с целочисленными координатами находятся строго внутри многоугольника (точки на границе не учитываются)
Сколько точек с целочисленными координатами разного знака, находятся строго внутри многоугольника (Число нуль знака не имеет)
Сколько точек с чётной суммой целочисленных координат находятся строго внутри многоугольника (Учитываем только точки с целочисленнми координатами)
и т.п.

Для ответа на эти вопросы надо уметь

проверять положение точки относительно многоугольника
описать многоугольник прямоугольником (для перебора всех точек прямоугольника и отбора нужных)

def fin(dot, Poly):
  z0 = cm.phase((dot - Poly[-1]).conjugate()*(Poly[-1]-Poly[-2]))
  for i in range(len(Poly)-1):
    z = cm.phase((dot - Poly[i]).conjugate()*(Poly[i+1]-Poly[i]))
    if z * z0 <= 0 : 
      return False
  return True  
  
    
import cmath as cm # импорт библиотеки КЧ
import turtle as tr # импорт Черепашки
from math import gcd
A = -30-40j #рисовать начинаем из точки с координатами 
rb,ub = 50, cm.pi/180*45 # длина вектора и начальный угол
N =4 # число сторон многоугольника
u = 2*cm.pi/N # базовый угол поворота многоугольника
P = [A] # список для вершин многоугольника
for i in range(N-1): # добавление вершин
  P.append(P[-1]+cm.rect(rb,u*i+ ub)) 
P.append(P[0]) # зацикливание
#print(P) # отладочнай печать координат вершин 
m =5 # Масштаб для рисования
#tr.dot(5);
tr.width(3); tr.speed(0) # начальная настройка Черепашки
tr.up(); tr.goto(m*(P[0].real), m*(P[0].imag)); tr.down() # перемещение в точку старта
for d in P : #отрисовка многоугольника
  tr.goto(m*(d.real), m*(d.imag))
tr.done()
tr.up()
ans = 0
for x in range(-150,151):
  for y in range (-160,161):
    if gcd(x , y)% 13 == 1 : continue
    z = complex(x,y)
    fl = fin(z, P) 
    if fl == False : continue
    tr.goto(m*x,m*y); tr.dot(2,'red')
    ans += 1
print(f'{ans=}')    
tr.done()

Используем библиотеку cmath для работы с комплексными числами
Библиотека cmath во многом аналогична библиотеке math, но работает с комллексными числами и возвращает комплексное значение (там, где это возможно и нужно)
Можно увидеть различие при вызове метода sqrt:
cmath.sqrt(-1) вернет 1j. а math.sqrt(-1) вызовет ошибку (что иногда полезнее, чем значение)
Из наиболее полезных (для геометрии) методов - это получение полярных координат.

import cmath as cm # импорт библиотеки КЧ
import turtle as tr # импорт Черепашки
A = -30-40j #рисовать начинаем из точки с координатами 
rb,ub = 50, cm.pi/180*30 # длина вектора и начальный угол
N = 9 # число сторон многоугольника
u = 2*cm.pi/N # базовый угол поворота многоугольника
P = [A] # список для вершин многоугольника
for i in range(N-1): # добавление вершин
  P.append(P[-1]+cm.rect(rb,u*i+ ub)) 
P.append(P[0]) # зацикливание
print(P) # отладочнай печать координат вершин 
m =3 # Масштаб для рисования
tr.dot(5); tr.width(3); tr.speed(10) # начальная настройка Черепашки
tr.up(); tr.goto(m*(P[0].real), m*(P[0].imag)); tr.down() # перемещение в точку старта
for d in P : #отрисовка многоугольника
  tr.goto(m*(d.real), m*(d.imag))
tr.done()

Печать