Elementary computational geometry
Материал из PTHSWiki
Версия от 17:55, 9 декабря 2020; Gusarev (обсуждение | вклад)
Почитать
Сдать тренировочные задачи
Cейчас на сервере есть возможность сдавать задачи на Python 3, C++ 17 и Java 8.
| Условия задач | Ссылка для входа | Тесты для самостоятельного тестирования |
|---|---|---|
| Разные задачи на геометрические примитивы | Вход в тестирующую систему (контест 341) | Все задачи |
Материалы некоторых занятий
Начало — классы Point, Vector (16 сентября 2020 г.)
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return "({0}, {1})".format(self.x, self.y)
class Vector:
# конструктор
def __init__(self, a, b):
if type(a) == Point and type(b) == Point:
self.x = b.x - a.x
self.y = b.y - a.y
elif type(a) == int and type(b) == int:
self.x = a
self.y = b
else:
raise Exception("Неверно указан тип параметра при создании вектора!")
def __str__(self):
return "({0}, {1})".format(self.x, self.y)
def __add__(self, other):
return Vector(self.x + other.x, self.y + other.y)
def scalar(self, other):
return self.x * other.x + self.y * other.y
P = Vector(3, 4)
Q = Vector(1, 2)
print(P, Q, P + Q)
A = Point(3, 4)
B = Point(1, 2)
v = Vector(1, 3)
u = Vector(-1273548172564, 1)
print(v.scalar(u))
Скалярное и векторное (косое) произведение векторов, неправильная реализация метода Vector.polar() (23 сентября 2020 г.)
from math import atan, pi
class Point:
# конструктор
def __init__(self, *args):
if len(args) == 1 and type(args[0]) == str:
self.x, self.y = map(int, args[0].split())
elif len(args) == 2 and type(args[0]) == int and type(args[1]) == int:
self.x = int(args[0])
self.y = int(args[1])
else:
raise Exception("Неверно указан тип параметров при создании точки!")
def __str__(self):
return "({0}, {1})".format(self.x, self.y)
class Vector:
# конструктор
def __init__(self, a, b):
if type(a) == Point and type(b) == Point:
self.x = b.x - a.x
self.y = b.y - a.y
elif type(a) == int and type(b) == int:
self.x = a
self.y = b
else:
raise Exception("Неверно указан тип параметра при создании вектора!")
def __str__(self):
return "({0}, {1})".format(self.x, self.y)
def __add__(self, other):
return Vector(self.x + other.x, self.y + other.y)
def scalar(self, other):
return self.x * other.x + self.y * other.y
def cross(self, other):
return self.x * other.y - self.y * other.x
def polar(self):
one = Vector(1, 0)
return one.cross(self) / one.scalar(self)
def dist(A, B):
return ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ** 0.5
A = Vector(*map(int, input().split()))
print(A.polar())
Разбор задачи про вычисление полярного угла точки (30 сентября 2020 г.)
Фото с доски: использование знаков скалярного и косого произведений
Разбор задач про принадлежность точки лучу и расстояние от точки до луча (07 октября 2020 г.)
Фото с доски: принадлежность точки лучу
Фото с доски: расстояние от точки до луча
from math import atan, pi
class Point:
# конструктор
def __init__(self, *args):
if len(args) == 1 and type(args[0]) == str:
self.x, self.y = map(int, args[0].split())
elif len(args) == 2 and type(args[0]) == int and type(args[1]) == int:
self.x = int(args[0])
self.y = int(args[1])
else:
raise Exception("Неверно указан тип параметров при создании точки!")
def __str__(self):
return "({0}, {1})".format(self.x, self.y)
class Vector:
# конструктор
def __init__(self, a, b):
if type(a) == Point and type(b) == Point:
self.x = b.x - a.x
self.y = b.y - a.y
elif type(a) == int and type(b) == int:
self.x = a
self.y = b
else:
raise Exception("Неверно указан тип параметра при создании вектора!")
def __str__(self):
return "({0}, {1})".format(self.x, self.y)
def __add__(self, other):
return Vector(self.x + other.x, self.y + other.y)
def scalar(self, other):
return self.x * other.x + self.y * other.y
def cross(self, other):
return self.x * other.y - self.y * other.x
def polar(self):
one = Vector(1, 0)
sc = one.scalar(self)
cr = one.cross(self)
add = 0
if cr < 0:
add = pi
if sc == 0:
return pi / 2 + add
if cr == 0:
if sc > 0:
return 0
else:
return pi
if sc > 0 and cr > 0:
return atan(cr / sc)
if sc > 0 and cr < 0:
return atan(cr / sc) + 2 * pi
if sc < 0:
return atan(cr / sc) + pi
def angle(self, other):
ans = abs(self.polar() - other.polar())
return ans if ans < pi else 2 * pi - ans
class Ray:
# конструктор позволяет задавать луч двумя точками: первая это начало луча, вторая — произвольная точка на его продолжении
def __init__(self, A, B):
self.start = A
self.direction = Vector(A, B)
def pt_in(self, A):
# реализуйте сами, мы её обсудили на занятии
pass
def dist(A, B):
return ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ** 0.5
# проверка того, что три точки лежат на одной прямой
def pts_same_line(A, B, C):
return Vector(A, B).cross(Vector(A, C)) == 0
A = Point(*map(int, input().split()))
B = Point(*map(int, input().split()))
C = Point(*map(int, input().split()))
r = Ray(B, C)
if r.pt_in(A):
print('YES')
else:
print('NO')
Проверка того, что точка находится внутри угла; пересечение лучей (14 октября 2020 г.)
На дом: сдать задачу L (пересечение двух лучей).
Код будет чуть позже.
Поворот точки против часовой стрелки на угол /alpha относительно начала координат (11 ноября 2020 г.)
Создание элементарного прототипа с классами Point и Triangle с вращением последнего. Пока в плоскости. (18 ноября 2020 г.)
Java: рекомендованная библиотека для GUI
Пример элементарного GUI на Python с использованием библиотеки TKinter:
from tkinter import *
root = Tk()
WIDTH, HEIGHT = 800, 800
w = Canvas(root, width=WIDTH, height=HEIGHT)
w.create_polygon(100, 100, 400, 700, 400, 500, fill = '#ff0000')
w.configure(background='#113311')
w.pack()
mainloop()
Шаблон для классов Point и Triangle (Python):
from math import sin, cos, pi, sqrt
class Point:
def __init__(self, x = 0, y = 0):
pass
def multVector(self, b):
pass
def multScalar(self, p):
pass
def multVectorMatrix(self, matrice):
pass
def rotate(self, alpha):
pass
def length(self):
pass
def __str__(self):
return f'orig: ({self.x}, {self.y})'
class Triangle:
def __init__(self, A, B, C):
pass
def __str__(self):
ret = []
for p in self.pts:
ret.append(f'({p.x}, {p.y})'
return ' '.join(ret)
def rotate(self, alpha):
pass
A = Point(3, 4)
B = Point(1, -4)
C = Point(-7, 4)
T = Triangle(A, B, C)
T.rotate(pi / 4)
Вращение (Python и Kotlin by Дмитрий Ляпин) (25 ноября 2020 г.)
Вращение треугольника в плоскости (полностью работающий пример на Python):
from math import sin, cos, pi, sqrt
from tkinter import *
class Point:
def __init__(self, *args):
if len(args) == 1 and type(args[0]) == str:
self.x, self.y = map(int, args[0].split())
elif len(args) == 2 and type(args[0]) == int and type(args[1]) == int:
self.x = int(args[0])
self.y = int(args[1])
else:
raise Exception("Неверно указан тип параметров при создании точки!")
def rotate(self, alpha):
self.x, self.y = self.x * cos(alpha) - self.y * sin(alpha), \
self.x * sin(alpha) + self.y * cos(alpha)
def __str__(self):
return f'orig: ({self.x}, {self.y})'
class Triangle:
def __init__(self, A, B, C):
self.pts = [A, B, C]
def __str__(self):
ret = []
for p in self.pts:
ret.append(f'({p.x}, {p.y})')
return ' '.join(ret)
def rotate(self, alpha):
for pt in self.pts:
pt.rotate(alpha)
def show_triangle(w, t, orig, width, fill_color):
for k in range(len(t.pts) - 1):
w.create_line(t.pts[k].x + orig.x, t.pts[k].y + orig.y, t.pts[k + 1].x + orig.x, t.pts[k + 1].y + orig.y,
width=width, fill=fill_color)
w.create_line(t.pts[0].x + orig.x, t.pts[0].y + orig.y, t.pts[-1].x + orig.x, t.pts[-1].y + orig.y,
width=width, fill=fill_color)
def move():
w.delete(ALL)
t.rotate(pi / 400)
show_triangle(w, t, ORIG, LINE_WIDTH, 'yellow')
master.after(10, move)
master = Tk()
WIDTH = 800
HEIGHT = 800
LINE_WIDTH = 5
BG_COLOR = '#000000'
ORIG = Point(WIDTH // 2, HEIGHT // 2)
w = Canvas(master, width = WIDTH, height = HEIGHT, bg = BG_COLOR)
t = Triangle(Point(-300, 100), Point(100, 300), Point(50, -300))
move()
w.pack()
mainloop()
Пример на Kotlin и комментарии, автор Дмитрий Ляпин.
Добавление третьего измерения, вращение точки вокруг осей (2 декабря 2020 г.)
# метод, реализующий вращение точки вокруг трёх осей
# bimask — анализируем младшие три бита для того, чтобы определить крутить или нет относителдьно соответствующей оси
def rotate(self, alphax, alphay, alphaz, bitmask):
rotationMatrix = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
if bitmask & 4 != 0: # rotate with alphax
self.rotate_x = (self.rotate_x + alphax) % 360
ax = self.rotate_x * pi / 180
rotationMatrix = [[1, 0, 0], [0, cos(ax), -sin(ax)], [0, sin(ax), cos(ax)]]
if bitmask & 2 != 0:
self.rotate_y = (self.rotate_y + alphay) % 360
ay = self.rotate_y * pi / 180
My = [[cos(ay), 0, -sin(ay)], [0, 1, 0], [sin(ay), 0, cos(ay)]]
rotationMatrix = multMatrixMatrix(rotationMatrix, My)
if bitmask & 1 != 0:
self.rotate_z = (self.rotate_z + alphaz) % 360
az = self.rotate_z * pi / 180
Mz = [[cos(az), -sin(az), 0], [sin(az), cos(az), 0], [0, 0, 1]]
rotationMatrix = multMatrixMatrix(rotationMatrix, Mz)
self.multVectorMatrix(rotationMatrix)
Необходимые критерии для получения зачёта
- Работающая программа, которая вращает в трёхмерном пространстве многоугольник, одна из сторон которого считается лицевой и показывается, а другая — не показывается.
- Программу вы будете запускать с демонстрацией своего экрана.
- До 23:59:59 выслать на мою почту (gusarer на gmail com) или в телеграм (@rgusarev) архив с работаюшей программой.
- Код программы должен быть разумно прокомментирован.
По коду я буду задавать вопросы и оценивать адекваьность ответов. Если не вы писали код программы, лучше на защиту не "приходить".
