Elementary computational geometry

Материал из PTHSWiki
Перейти к: навигация, поиск

Содержание

Почитать

Материалы по вычислительной геометрии ЛКШ, 2010 г., параллель B' (там же глоссарий англ. терминов)
Подробные лекции по вычислительной геометрии на плоскости, Е.В. Андреева, Ю.Е. Егоров
Короткий справочник по скалярному и косому произведениям


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

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 г.)

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)

Вращение (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()


Добавление третьего измерения, вращение точки вокруг осей (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)

Необходимые критерии для получения зачёта

  1. Работающая программа, которая вращает в трёхмерном пространстве многоугольник, одна из сторон которого считается лицевой и показывается, а другая — не показывается.
  2. Программу вы будете запускать с демонстрацией своего экрана.
  3. До 23:59:59 выслать на мою почту (gusarer на gmail com) или в телеграм (@rgusarev) архив с работаюшей программой.
  4. Код программы должен быть разумно прокомментирован.

По коду я буду задавать вопросы и оценивать адекватность ответов. Если не вы писали код программы, лучше на защиту не "приходить".

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты