Elementary computational geometry

Версия 17:43, 18 ноября 2020

Почитать

Сдать тренировочные задачи

Cейчас на сервере есть возможность сдавать задачи на Python 3, C++ 17 и Java 8.

Материалы некоторых занятий

Начало — классы 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 г.)

Python: руководство по графической библиотеке TKinter (неофициальный сайт, много работающих примеров)

Java: рекомендованная библиотека для GUI

Kotlin: UI разработка

Пример элементарного 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)