Elementary computational geometry

(Различия между версиями)
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
! Тесты для самостоятельного тестирования
 
! Тесты для самостоятельного тестирования
 
|-
 
|-
|[http://wiki.school.ioffe.ru/images/5/5e/Class-geometry.pdf Разные задачи на геометрические примитивы] || [https://207.154.240.40/cgi-bin/new-client?contest_id=341 Вход в тестирующую систему (контест 341)] || [https://prog.school.ioffe.ru/upload/problems.zip Все задачи]
+
|[http://wiki.school.ioffe.ru/images/5/5e/Class-geometry.pdf Разные задачи на геометрические примитивы] || [http://prog.school.ioffe.ru//cgi-bin/new-client?contest_id=341 Вход в тестирующую систему (контест 341)] || [https://prog.school.ioffe.ru/upload/problems.zip Все задачи]
 
|}
 
|}
  

Версия 14:51, 18 ноября 2020

Содержание

Почитать

Материалы по вычислительной геометрии ЛКШ, 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 г.)

Фото с доски: поворот точки

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