Практика

В этом разделе даны задания для самостоятельного выполнения. Сначала будут разобраны необходимые для решения этих задач примитивы, после чего будет дан общий алгоритм решения.

За каждое задание ставится по две оценки, за защиту три.

Таблица уроков:

Название	Коммит	Кол-во уроков
ReadMe	ReadMe	2
Примитивы	Primitives	2
Добавление мышью	Mouse add ready	2
Панель добавления	Manual add panel	2
Случайные точки	Random	2
Работа с файлами	Files	2
Решение задачи	Solve	2
Help	Help panel	2
Отчёт	Report	1
Презентация	Presentation	1
Защита	-	2

Задачи

В этом разделе предложены задачи для самостоятельного решения.

Чтобы определиться, какую задачу нужно решать, найдите в таблице ваш номер в группе. Таблицы находятся в этом файле.

Задачи составлены Ушаковым Денисом Михайловичем.

1. На плоскости задано множество точек. Найти среди них такие две пары, что точка пересечения прямых, проведенных через эти пары точек, находится ближе всего к началу координат. То есть, если рассмотреть все возможные прямые, которые могут быть построены по парам указанных точек, и все возможные точки пересечения этих прямых между собой, то нужно найти такую точку пересечения этих прямых, которая находится ближе всего к началу координат. Ответом должна быть: эта точка пересечения, те две прямые, которые в этой точке пересекаются, а также отрезок, проведенный из начала координат до точки пересечения.

2. На плоскости задано множество точек, и "параллельный" прямоугольник. Множество точек образует все возможные прямые, которые могут быть построены парами точек множества. Найти такую прямую (и такие две точки, через которые она проходит), что эта прямая пересекает указанный прямоугольник, и при этом длина отрезка прямой, находящейся внутри прямоугольника, максимальна. В качестве ответа: выделить найденные две точки, нарисовать прямую, которая через них проходит, а также выделить на этой прямой отрезок между двумя найденными точками пересечения.

3. На плоскости задано множество точек, и прямоугольник. Множество точек образует все возможные прямые, которые могут быть построены парами точек множества. Найти такую прямую (и такие две точки, через которые она проходит), что эта прямая пересекает указанный прямоугольник, и при этом длина отрезка прямой, находящейся внутри прямоугольника, максимальна. В качестве ответа: выделить найденные две точки, нарисовать прямую, которая через них проходит, а также выделить на этой прямой отрезок между двумя найденными точками пересечения.

4. На плоскости задано множество точек, и множество окружностей. Множество точек образует все возможные прямые, которые могут быть построены парами точек множества. Найти такую прямую (и такие две точки, через которые она проходит) и такую окружность, что эта прямая пересекает указанную окружность, и при этом длина отрезка прямой, находящейся внутри окружности, максимальна. В качестве ответа: выделить найденные две точки, выделить найденную окружность, нарисовать прямую, которая через них проходит, а также выделить на этой прямой отрезок между двумя найденными точками пересечения.

5. На плоскости задано множество окружностей. Найти такую пару пересекающихся окружностей, что длина отрезка, проведенного от одной точки пересечения этих двух окружностей до другой, максимальна. В качестве ответа: выделить эту пару окружностей, нарисовать отрезок между найденными точками пересечения.

6. На плоскости задан треугольник и еще множество точек. Необходимо найти такие две точки множества, что прямая, проходящая через эти две точки, пересекает треугольник, и при этом отрезок этой прямой, оказавшейся внутри треугольника, оказывается наибольшей длины. В качестве ответа хотелось бы видеть выделенные эти две точки, прямую, через них проходящую, и этот отрезок.

7. Множество точек на плоскости назовем дваждытреугольным, если каждая точка этого множества является вершиной хотя бы двух правильных треугольников, построенных по точкам множества. Определить, удовлетворяет ли заданное множество точек этому свойству.

8. Дано множество точек на плоскости. Определить среди них множество точек наибольшего размера такое, что каждая точка этого множества является вершиной равностороннего треугольника, вершины которого принадлежат этому множеству. В качестве ответа хотелось бы видеть все эти равносторонние треугольники.

9. Дано множество точек на плоскости. Определить среди них подмножество точек наибольшего размера такое, что каждая точка этого множества является вершиной хотя бы двух равносторонних треугольников, вершины которого принадлежат этому подмножеству. В качестве ответа хотелось бы видеть все эти равносторонние треугольники.

10. Дано множество точек на плоскости. Выберем из этого множества две точки и проведем через них прямую. Назовем дистанцией такую величину, что на расстоянии от прямой не меньше, чем дистанция лежит хотя бы половина оставшихся точек множества (кроме этих двух). Найти такую пару точек, у которой дистанция будет минимальна. В качестве ответа: выделить эти две точки, нарисовать проходящую через них прямую, выделить точки, лежащие на дистанции, нарисовать дистанцию (отрезок от одной из самых удаленных точек до прямой), а также "коридор" (две прямые, параллельные найденной прямой, находящиеся на найденной дистанции).

11. На плоскости задано множество прямоугольников. Найти такую пару пересекающихся прямоугольников, что длина отрезка, проведенного от одной точки пересечения этих двух прямоугольников до другой, максимальна. Если прямоугольники имеют более двух точек пересечения, выбирать среди них такую пару, расстояние между которыми максимально. В качестве ответа: выделить эту пару прямоугольников, нарисовать отрезок между найденными точками пересечения.

12. На плоскости задано множество "острых углов". Найти такие два "острых угла", что фигура, находящаяся "внутри" обоих "острых углов" замкнута и имеет максимальную площадь. Опция: искать только такие фигуры, все точки которых находятся внутри отображаемой на экране системы координат. В этом случае крайне желательно "залить цветом пространство фигуры". В качестве ответа: выделить найденные два "острых угла", выделить контур фигуры, которая ограничивает точки "внутри" обоих "острых углов", желательно выделить внутреннее пространство фигуры ("залить цветом").

13. На плоскости задано множество треугольников. Найти такие два треугольника, что площадь фигуры, находящейся внутри обоих треугольников, будет максимальна. В качестве ответа: выделить найденные два треугольника, выделить контур фигуры, находящейся внутри обоих треугольников, желательно "залить цветом" внутреннее пространство этой фигуры.

14. На плоскости задано множество прямоугольников. Найти такую пару пересекающихся прямоугольников, что площадь фигуры, находящейся внутри обоих прямоугольников, будет максимальна. В качестве ответа: выделить эту пару прямоугольников, выделить контур фигуры, находящейся внутри обоих треугольников, желательно "залить цветом" внутреннее пространство этой фигуры.

15. На плоскости задано множество окружностей и множество "острых углов". Найти такую пару "окружность - угол", что площадь фигуры, находящейся внутри найденной окружности и "острого угла" будет максимальной. В качестве ответа: выделить эту пару "окружность - угол", выделить контур фигуры, находящейся внутри окружности и "острого угла",

16. На плоскости задано множество прямоугольников и множество "острых углов". Найти такую пару "прямоугольник - угол", что площадь фигуры, находящейся внутри найденного прямоугольника и "острого угла" будет максимальной. В качестве ответа: выделить эту пару "прямоугольник - угол", выделить контур фигуры, находящейся внутри прямоугольника и "острого угла",

17. На плоскости задано множество треугольников и множество "острых углов". Найти такую пару "треугольник - угол", что площадь фигуры, находящейся внутри найденного треугольника и "острого угла" будет максимальной. В качестве ответа: выделить эту пару "треугольник - угол", выделить контур фигуры, находящейся внутри треугольника и "острого угла",

18. На плоскости задано множество "широких лучей". Найти такие два "широких луча", что фигура, находящаяся внутри этих двух "широких лучей" замкнута и имеет наибольшую площадь. В качестве ответа: выделить найденные два "широких луча", выделить контур фигуры, которая ограничивает точки внутри обоих "широких лучей", желательно выделить внутреннее пространство фигуры ("залить цветом").

19. На плоскости задано множество "широких лучей" и множество треугольников. Найти такую пару "широкий луч"-треугольник, что фигура, находящаяся внутри "широкого луча" и треугольника, имеет максимальную площадь. В качестве ответа: выделить найденные "широкий луч" и треугольник, выделить контур фигуры, которая ограничивает точки внутри найденного "широкого луча" и треугольника, желательно выделить внутреннее пространство фигуры ("залить цветом").

20. На плоскости задано множество "широких лучей" и множество окружностей. Найти такую пару "широкий луч"-окружность, что фигура, находящаяся внутри "широкого луча" и окружности, имеет максимальную площадь. В качестве ответа: выделить найденные "широкий луч" и окружность, выделить контур фигуры, которая ограничивает точки внутри найденного "широкого луча" и окружности, желательно выделить внутреннее пространство фигуры ("залить цветом").

21. На плоскости задано множество прямоугольников и множество окружностей. Найти такую пару прямоугольник-окружность, что фигура, находящаяся внутри прямоугольника и окружности, имеет максимальную площадь. В качестве ответа: выделить найденные прямоугольник и окружность, выделить контур фигуры, которая ограничивает точки внутри найденного прямоугольника и окружности, желательно выделить внутреннее пространство фигуры ("залить цветом").

22. На плоскости задано множество точек. Найти окружность, содержащую внутри себя хотя бы две точки множества, имеющую наибольшую плотность точек внутри себя (количество точек на единицу площади). В качестве ответа нарисовать найденную окружность и выделить все точки, находящиеся внутри нее.

23. На плоскости задано множество точек. Найти окружность наименьшей площади, внутри которой находятся все точки множества. Если таких окружностей несколько, найти любую. В качестве ответа нарисовать найденную окружность.

24. На плоскости задано два множества "параллельных" прямоугольников. Найти "разность" множеств. То есть, все такие точки плоскости, которые лежат внутри хотя бы одного прямоугольника первого множества, и не лежат ни в одном прямоугольнике второго множества. Отобразить найденное множество (желательно, "заливкой").

25. На плоскости задано два множества "параллельных" прямоугольников. Найти "пересечение" множеств. То есть, все такие точки плоскости, которые лежат внутри хотя бы одного прямоугольника первого множества, и внутри хотя бы одного прямоугольника второго множества. Отобразить найденное множество (желательно, "заливкой").

26. На плоскости задано множество точек. Найти такие две окружности, что их центры находятся в точках заданного множества, внутри этих окружностей находятся все точки заданного множества, и больший из двух радиусов минимален.

27. На плоскости задано множество точек. Найти такие две окружности, что их центры находятся в точках заданного множества, внутри этих окружностей находятся хотя бы половина из всех точек заданного множества, и меньший из двух радиусов минимален.

28. На плоскости задано множество точек. Найти такие две окружности, что их центры находятся в точках заданного множества, внутри каждой из этих окружностей находятся хотя бы половина из всех точек заданного множества, и меньший из двух радиусов минимален.

29. На плоскости имеется прямая. Также имеется еще некоторое множество точек. По каждой паре точек этого множества строим прямые. Найти такие две пары точек, что построенные по ним две прямые пересекаются с первой прямой на минимальном расстоянии друг от друга. Выделить найденные точки, нарисовать прямые, построенные по ним. Выделить точки пересечения этих прямых с первой прямой. Выделить отрезок между этими точками пересечения. Дополнительная опция: искомые две пары точек не должны иметь общих точек.

30. На плоскости имеется окружность. Также имеется еще некоторое множество точек. По каждой паре точек этого множества строим прямые. Найти такие две пары точек, что построенные по ним две прямые пересекаются с окружностью на минимальном расстоянии друг от друга. Выделить найденные точки, нарисовать прямые, построенные по ним. Выделить точки пересечения этих прямых с окружностью. Выделить дугу между этими точками пересечения. Дополнительная опция: искомые две пары точек не должны иметь общих точек.

31. На плоскости задано множество точек. Найти из них такие 4 точки, что построенный по ним четырёхугольник не является самопересекающимся и имеет при этом максимальную площадь.

32. На плоскости задано множество точек. Найти из них такие 4 точки, что построенный по ним четырёххугольник не является самопересекающимся и содержит в себе максимальное количество точек множества.

Примитивы

Для тестов примитивов напишем новую программу. Оставим в ней только рисование, удалив все панели:

Обратите внимание:

Этот блок - демонстрационный, выполнять его не нужно.

Исходники этого приложения можно скачать здесь

Все команды для демонстрации примитивов пишутся внутри метода RenderTask():

// рисование задачи на невидимом окне во всё окно приложения
void RenderTask() {
    // задаём левый верхний край невидимого окна
    ImGui::SetNextWindowPos(ImVec2(0, 0));
    // задаём правый нижний край невидимого окна
    ImGui::SetNextWindowSize(ImVec2(WINDOW_SIZE_X, WINDOW_SIZE_Y));
    // создаём невидимое окно
    ImGui::Begin("Overlay", nullptr,
                 ImGuiWindowFlags_NoTitleBar | ImGuiWindowFlags_NoResize | ImGuiWindowFlags_NoMove |
                 ImGuiWindowFlags_NoScrollbar | ImGuiWindowFlags_NoInputs | ImGuiWindowFlags_NoBackground);
    // получаем список примитивов, которые будут нарисованы
    auto pDrawList = ImGui::GetWindowDrawList();


    // рисуем точку
    pDrawList->AddCircleFilled(
            sf::Vector2i(400, 400),
            3,
            ImColor(100, 200, 150),
            20
    );

    // заканчиваем рисование окна
    ImGui::End();
}

Точка

Точка Задается своими координатами $x$ и $y$. Чтобы нарисовать точку, используйте команду рисования закрашенного круга

    // рисуем точку
    pDrawList->AddCircleFilled(
            sf::Vector2i(400, 400),
            3,
            ImColor(100, 200, 150),
            20
    );

Сама команда рисования - это pDrawList->AddCircleFilled(), она принимает в качестве аргумента положение центра круга, его радиус, цвет и количество сегментов круга.

Прямая

Прямая задается двумя точками, через которые проходит.

    // рисуем линию
    pDrawList->AddLine(
            sf::Vector2i(450, 550),
            sf::Vector2i(550, 450),
            ImColor(200, 100, 150),
            0.5f
    );

Нарисуется отрезок:

У движка нет готового метода рисования линий, потому что линия - бесконечный объект, но у него есть метод рисования отрезка pDrawList->AddLine(). В качестве аргументов он принимает сначала координаты первой точки, потом второй, потом цвет, потом вещественное значение толщины отрезка.

Чтобы нарисовать именно прямую, нам нужно продлить данный нам отрезок в обе стороны так, чтобы оба его конца выходили за границы экрана. Тогда линия точно нарисуется во весь экран.

Для этого просто найдём вектор, который ведёт из точки A в точку B, умножим его на длину диагонали экрана. Тогда, чтобы получить первую опорную точку, нам нужно прибавить этот вектор к точке A, а чтобы вторую - вычесть.

    // опорные точки линии
    sf::Vector2i pointA = {450, 550};
    sf::Vector2i pointB = {550, 450};

    // получаем максимальную длину отрезка на экране, как длину диагонали экрана
    double maxDistance = std::sqrt(WINDOW_SIZE_X * WINDOW_SIZE_X + WINDOW_SIZE_Y * WINDOW_SIZE_Y);

    // получаем новые точки для рисования, которые гарантируют, что линия
    // будет нарисована до границ экрана
    sf::Vector2i renderPointA = sf::Vector2i(
            pointA.x + (int) ((pointA.x - pointB.x) * maxDistance),
            pointA.y + (int) ((pointA.y - pointB.y) * maxDistance)
    );
    sf::Vector2i renderPointB = sf::Vector2i(
            pointA.x - (int) ((pointA.x - pointB.x) * maxDistance),
            pointA.y - (int) ((pointA.y - pointB.y) * maxDistance)
    );

    // рисуем линию
    pDrawList->AddLine(
            renderPointA,
            renderPointB,
            ImColor(200, 150, 100),
            0.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointA,
            pointB,
            ImColor(200, 100, 150),
            1.5f
    );

Треугольник

Треугольник задается тремя точками-вершинами, точки попарно не совпадают.

Встроенный инструмент рисования треугольника в imGui довольно неудачный.

Например, код

    // опорные точки треугольника
    sf::Vector2i pointA = {430, 530};
    sf::Vector2i pointB = {530, 400};
    sf::Vector2i pointC = {450, 450};

    // рисуем треугольник
    pDrawList->AddTriangle(
            pointA,
            pointB,
            pointC,
            ImColor(200, 150, 150),
            10.0f
    );

Нарисует такой треугольник:

Поэтому треугольник линиями следует рисовать с помощью трёх отрезков-сторон

Чтобы нарисовать треугольник, нужно просто нарисовать три отрезка

    // опорные точки треугольника
    sf::Vector2i pointA = {430, 530};
    sf::Vector2i pointB = {530, 400};
    sf::Vector2i pointC = {450, 450};

    // рисуем отрезок
    pDrawList->AddLine(
            pointA,
            pointB,
            ImColor(200, 150, 150),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointB,
            pointC,
            ImColor(200, 150, 150),
            1.5f
    );
    // рисуем отрезок
    pDrawList->AddLine(
            pointC,
            pointA,
            ImColor(200, 150, 150),
            1.5f
    );

Зато заполненный треугольник рисуется вполне корректно:

    // опорные точки треугольника
    sf::Vector2i pointA = {430, 300};
    sf::Vector2i pointB = {530, 310};
    sf::Vector2i pointC = {350, 250};

    // рисуем треугольник
    pDrawList->AddTriangleFilled(
            pointA,
            pointB,
            pointC,
            ImColor(150,200, 150)
    );

Окружность

Окружность задается точкой центра и точкой на окружности, точки не совпадают.

Чтобы нарисовать окружность(контур круга), нужно использовать команду pDrawList->AddCircle():

    // опорная точка окружности
    sf::Vector2i pointA = {230, 300};
    
    // рисуем окружность
    pDrawList->AddCircle(
            pointA,
            30,
            ImColor(150, 200, 150)
    );

Здесь используется укороченная форма, также можно добавить два параметра: число сегментов и толщину линий.

Чтобы нарисовать круг, нужна команда pDrawList->AddCircleFilled()

    // опорная точка круга
    sf::Vector2i pointA = {230, 450};

    // рисуем окружность
    pDrawList->AddCircleFilled(
            pointA,
            30,
            ImColor(150, 150, 200)
    );

Параллельный прямоугольник

Параллельный прямоугольник задается точками двумя противоположными вершинами. Все стороны параллельны осям координат, координаты вершин не совпадают по каждой из координат.

Чтобы нарисовать параллельный прямоугольник, нам достаточно просто нарисовать четыре линии:

    // опорные точки параллельного четырёхугольника
    sf::Vector2i pointA = {50, 50};
    sf::Vector2i pointC = {200, 150};

    // вспомогательные точки параллельного четырёхугольника
    sf::Vector2i pointB = {pointA.x, pointC.y};
    sf::Vector2i pointD = {pointC.x, pointA.y};

    // рисуем отрезок
    pDrawList->AddLine(
            pointA,
            pointB,
            ImColor(200, 150, 100),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointB,
            pointC,
            ImColor(200, 150, 100),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointC,
            pointD,
            ImColor(200, 150, 100),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointD,
            pointA,
            ImColor(200, 150, 100),
            1.5f
    );

Прямоугольник

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

Нам необходимо прописать функцию расстояния от точки до прямой, а также поворот вектора на угол.

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

Для удобства пропишем преобразования вещественного вектора в целочисленный и наоборот:

// преобразование целочисленного вектора в вещественный
static sf::Vector2f toFloat(sf::Vector2i v) {
    return {(float)v.x, (float)v.y};
}

// преобразование вещественного вектора в целочисленный
static sf::Vector2i toInt(sf::Vector2f v) {
    return {(int) v.x, (int) v.y};
}

Для двумерного вектора $(x_0,~y_0)$ поворот на угол $a$ вычисляется по следующей формуле:

$$x_r = x_0 \cos(a)-y_0 \sin(a)\\ y_r = x_0 \sin(a)+y_0 \cos(a)$$

где $[x_r, y_r]$ - координаты повёрнутого вектора

// поворот вектора на угол
static sf::Vector2f rotated(sf::Vector2f v, float a) {
    return {
            v.x * std::cos(a) - v.y * std::sin(a),
            v.x * std::sin(a) + v.y * std::cos(a)
    };
}

Также нам понадобится метод нормализации вектора. Нормализованный вектор - это вектор, сонаправленный с исходным, но имеющий единичную длину. Чтобы получить нормализованный вектор, нужно просто каждую из его координат разделить на длину.

Напишем функции длины и нормирования вектора:

// длина вектора
static float length(sf::Vector2f f) {
    return std::sqrt(f.x * f.x + f.y * f.y);
}

// нормирование вектора
static sf::Vector2f norm(sf::Vector2f v) {
    float ln = length(v);
    return {v.x / ln, v.y / ln};
}

Ещё нам понадобится метод, возвращающий векторное произведение векторов. Строго говоря, для двумерного вектора оно не определено. Т.к. результат векторного умножения - это вектор, перпендикулярный плоскости, образованный исходными векторами.

Но для двумерного вектора придумана хитрость: мы создаём на основе исходных двумерных векторов трёхмерные, у которых координата $z$ равна нулю, тогда результатом их векторного умножения будет вектор, сонаправленный с осью $z$. Т.е. длина этого вектора равна модулю $z$ координаты. Эта координата равна результату векторного умножения двумерных векторов.

Обозначим результат векторного умножения за $v$, а перемножаемые вектора за $a$ и $b$, тогда умножение вычисляется по следующей формуле:

$$v = a\times b = a.x*b.y - a.y*b.x$$

Векторное умножение обозначается $\times$

Теперь напишем метод векторного умножения

// векторное умножение двумерных векторов
static float cross(sf::Vector2f a, sf::Vector2f b) {
    return a.x * b.y - a.y * b.x;
}

Он нам нужен для определения того, в какую сторону направить смещение.

Знак векторного произведения также определяет знак синуса угла между векторами. Нас интересует, куда следует повернуть вектор: по часовой стрелке или против часовой. Повороту по часовой стрелке соответствуют отрицательные углы, а против часовой - положительные.

Знак угла нам нужне, чтобы понять, куда направить вектор смещения $E$. Вектор смещения - это вектор, прибавив который к координатам вершины $A$ мы получим координаты вершины $D$, а к координатам $C$ - координаты вершины $D$.

На диапазоне значений $[-\pi,\pi]$ знак синуса, т.е. знак векторного произведения совпадает со знаком угла. Получается, чтобы определить направление поворота вектора смещения, нам нужно просто определить знак угла между $\vec{AB}$ и $\vec{AP}$.

Если этот угол положительный, то и угол между известной стороной и вектором смещения тоже будет положительным, а если угол отрицательный, то отрицательный.

Угол между вектором смещения и известной стороной можно найти по следующей формуле

$$e = sign(p)\frac{\pi}{2}=sign(\vec{AB}\times\vec{AD})\frac{\pi}{2}$$

$sign()$ - функция знака, возвращает $-1$, если её аргумент отрицательный, $0$ - если он равен нулю и $1$ если положительный.

Если прямая определяется двумя точками $A(x_a, y_a)$ и $B(x_b, y_b)$, то коэффициенты её канонического уравнения

$$ax + by + c = 0$$

Можно найти по формулам:

$$a = y_a - y_b \\ b = x_a - x_b \\ c = x_a y_b - x_b y_a$$

Расстояние от точки $P(x_0,y_0)$ до прямой $ax+by+c=0$ находится по формуле:

$$d = \frac{|ax_0+by0+c|}{\sqrt{a^2+b^2}}$$

Напишем функцию, находящую расстояние от прямой, образованной первыми двумя точками, до третьей.

// расстояние от прямой, образованной первыми двумя точками, до третьей
static float distance(sf::Vector2f pointA, sf::Vector2f pointB, sf::Vector2f pointC){
    float a = pointA.y - pointB.y;
    float b = pointB.x - pointA.x;
    float c = pointA.x * pointB.y - pointB.x * pointA.y;

    return std::abs(a * pointC.x + b * pointC.y + c) / std::sqrt(a * a + b * b);
}

Также напишем функции суммы и разности векторов и умножения вектора на число:

// сумма векторов
static sf::Vector2f sum(sf::Vector2f a, sf::Vector2f b) {
    return {a.x + b.x, a.y + b.y};
}

// разность векторов
static sf::Vector2f subtract(sf::Vector2f a, sf::Vector2f b) {
    return {a.x - b.x, a.y - b.y};
}

// сумма векторов
static sf::Vector2i sum(sf::Vector2i a, sf::Vector2i b) {
    return {a.x + b.x, a.y + b.y};
}

// разность векторов
static sf::Vector2i subtract(sf::Vector2i a, sf::Vector2i b) {
    return {a.x - b.x, a.y - b.y};
}

// умножение вектора на число
static sf::Vector2f mul(sf::Vector2f a, float b) {
    return {a.x * b, a.y * b};
}

Также нам понадобится функция sign:

// знак переменной
static float sign(float a) {
    if (a > 0)
        return -1;
    else if (a < 0)
        return 1;
    else
        return 0;
}

Теперь добавим само рисование прямоугольника:

    // рисуем прямоугольник

    // первая вершина
    sf::Vector2i pointA = {300, 100};
    // вторая вершина
    sf::Vector2i pointB = {500, 200};
    // точка на противоположной стороне
    sf::Vector2i pointP = {300, 50};

    // рассчитываем векторы для векторного умножения
    sf::Vector2i AB = subtract(pointB, pointA);
    sf::Vector2i AP = subtract(pointP, pointA);

    // определяем направление смещения(добавляем минус, т.к. ось y СК экрана смотрит вниз.
    float direction = -sign(cross(toFloat(AB), toFloat(AP)));

    // рассчитываем расстояние от прямой до точки
    float dist = distance(toFloat(pointA), toFloat(pointB), toFloat(pointP));

    // получаем единичный вектор направления смещения
    sf::Vector2f n = norm(rotated(toFloat(AB), ((float) M_PI / 2.f * direction)));

    // получаем вектор смещения
    sf::Vector2i offset = toInt(mul(n, dist));

    // находим координаты вторых двух вершин прямоугольника
    pointC = sum(pointB, offset);
    pointD = sum(pointA, offset);

    // рисуем отрезок
    pDrawList->AddLine(
            pointA,
            pointB,
            ImColor(100, 150, 200),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointB,
            pointC,
            ImColor(100, 150, 200),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointC,
            pointD,
            ImColor(100, 150, 200),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointD,
            pointA,
            ImColor(100, 150, 200),
            1.5f
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointA,
            3,
            ImColor(200, 100, 150)
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointB,
            3,
            ImColor(200, 100, 150)
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointP,
            3,
            ImColor(200, 100, 150)
    );

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

Параллелограмм

Задается тремя точками вершинами. Четвертая вершина определяется через три другие.

Пусть нам даны три вершины параллелограмма $A$, $B$ и $C$. Тогда координаты точки $D$ можно определить как $C+\vec{AB}$.

Запишем это в коде:

    // рисуем параллелограмм

    // первая вершина
    sf::Vector2i pointA = {650, 150};
    // вторая вершина
    sf::Vector2i pointB = {600, 50};
    // третья вершина
    sf::Vector2i pointC = {700, 100};

    // определяем вектор смещения
    sf::Vector2i AB = subtract(pointA, pointB);
    sf::Vector2i pointD = sum(pointC, AB);

    // рисуем отрезок
    pDrawList->AddLine(
            pointA,
            pointB,
            ImColor(150, 100, 200),
            1.5f
    );
    // рисуем отрезок
    pDrawList->AddLine(
            pointB,
            pointC,
            ImColor(150, 100, 200),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointC,
            pointD,
            ImColor(150, 100, 200),
            1.5f
    );

    // рисуем отрезок
    pDrawList->AddLine(
            pointD,
            pointA,
            ImColor(150, 100, 200),
            1.5f
    );


    // рисуем опорные точки

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointA,
            3,
            ImColor(200, 100, 150)
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointB,
            3,
            ImColor(200, 100, 150)
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointC,
            3,
            ImColor(200, 100, 150)
    );

Получим рисование параллелограмма

Угол

Угол задается точкой-вершиной и двумя точками, через которые проходят его лучи, выходящие из вершины. Угол между лучами меньше 180 градусов.

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

    // рисуем угол

    // вершина угла
    sf::Vector2i pointA = {150, 400};
    // опорные точки
    sf::Vector2i pointB = {50, 300};
    sf::Vector2i pointC = {80, 500};

    // определяем вектор смещения
    sf::Vector2i AB = subtract(pointB, pointA);
    sf::Vector2i AC = subtract(pointC, pointA);


    // получаем максимальную длину отрезка на экране, как длину диагонали экрана
    maxDistance = std::sqrt(WINDOW_SIZE_X * WINDOW_SIZE_X + WINDOW_SIZE_Y * WINDOW_SIZE_Y);

    // получаем новые точки для рисования, которые гарантируют, что линия
    // будет нарисована до границ экрана
    sf::Vector2i renderPointB = sum(pointA, toInt(mul(toFloat(AB), maxDistance)));
    sf::Vector2i renderPointC = sum(pointA, toInt(mul(toFloat(AC), maxDistance)));


    // рисуем линию
    pDrawList->AddLine(
            pointA,
            renderPointB,
            ImColor(200, 150, 100),
            0.5f
    );


    // рисуем линию
    pDrawList->AddLine(
            pointA,
            renderPointC,
            ImColor(200, 150, 100),
            0.5f
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointA,
            3,
            ImColor(200, 100, 150)
    );
    // рисуем точку
    pDrawList->AddCircleFilled(
            pointB,
            3,
            ImColor(200, 100, 150)
    );
    // рисуем точку
    pDrawList->AddCircleFilled(
            pointC,
            3,
            ImColor(200, 100, 150)
    );

Получим рисование угла

Полоса

Полоса - это широкая линия с заданной толщиной. Она задается прямой с помощью двух опорных точек, лежащей на ней и толщиной.

Для неё нам нужно определить сначала вектор направления по двум точкам, взять от него перпендикуляр и сместиться вдоль него на половину толщины полосы в обе стороны.

Так мы получим опорные точки, отложив от которых вектор направления, умноженный на длину диагонали экрана мы уже получим точки для рисования линии, как в соответствующем пункте.

    // рисуем широкий луч

    // первая точка
    sf::Vector2i pointA = {400, 700};
    // вторая точка
    sf::Vector2i pointB = {700, 500};
    // отрезок AB
    sf::Vector2i AB = subtract(pointB, pointA);
    // толщина линии
    float width = 40.f;

    // вектор направления для откладывания ширины
    sf::Vector2f wd = norm(rotated(toFloat(AB), M_PI / 2));
    sf::Vector2i widthDirection = toInt(mul(wd, width / 2));


    // получаем максимальную длину отрезка на экране, как длину диагонали экрана
    maxDistance = std::sqrt(WINDOW_SIZE_X * WINDOW_SIZE_X + WINDOW_SIZE_Y * WINDOW_SIZE_Y);

    sf::Vector2i lineDirection = toInt(mul(norm(toFloat(AB)), maxDistance));

    // получаем опорные точки для откладывания направления
    sf::Vector2i basePointA = sum(pointA, widthDirection);
    sf::Vector2i basePointB = subtract(pointA, widthDirection);

    // получаем точки рисования
    sf::Vector2i renderPointA = sum(basePointA, lineDirection);
    sf::Vector2i renderPointB = sum(basePointB, lineDirection);
    sf::Vector2i renderPointC = subtract(basePointB, lineDirection);
    sf::Vector2i renderPointD = subtract(basePointA, lineDirection);

    // рисуем линию
    pDrawList->AddLine(
            renderPointB,
            renderPointC,
            ImColor(150, 200, 100),
            0.5f
    );

    // рисуем линию
    pDrawList->AddLine(
            renderPointD,
            renderPointA,
            ImColor(150, 200, 100),
            0.5f
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointA,
            3,
            ImColor(200, 100, 150)
    );
    // рисуем точку
    pDrawList->AddCircleFilled(
            pointB,
            3,
            ImColor(200, 100, 150)
    );
    // рисуем точку
    pDrawList->AddCircleFilled(
            basePointA,
            3,
            ImColor(200, 100, 150)
    );
    // рисуем точку
    pDrawList->AddCircleFilled(
            basePointB,
            3,
            ImColor(200, 100, 150)
    );

Проверим рисование полосы

Широкий луч

Широкий луч - это прямоугольник с одной из сторон, находящейся в бесконечности.

Он задается двумя точками, являющимися вершинами одной из сторон прямоугольника. Направление "луча" получается поворотом на $\frac{\pi}{2}$ вектора, проведенного из первой точки во вторую.

Этот примитив рисуется очень похожим способом, как полоса, но точки за экраном нужно создать только в одном направлении. Вместо построения в противоположную сторону условно бесконечных отрезков мы просто нарисуем отрезок, соединяющий две опорные точки.

    // первая точка
    sf::Vector2i pointA = {100, 600};
    // опорные точки
    sf::Vector2i pointB = {150, 650};
    // отрезок AB
    sf::Vector2i AB = subtract(pointB, pointA);


    // получаем максимальную длину отрезка на экране, как длину диагонали экрана
    double maxDistance = std::sqrt(WINDOW_SIZE_X * WINDOW_SIZE_X + WINDOW_SIZE_Y * WINDOW_SIZE_Y);

    // создаём вектор направления для рисования условно бесконечной полосы
    sf::Vector2i lineDirection = toInt(mul(norm(rotated(toFloat(AB), M_PI / 2)), maxDistance));

    // получаем точки рисования
    sf::Vector2i renderPointC = sum(pointA, lineDirection);
    sf::Vector2i renderPointD = sum(pointB, lineDirection);

    // рисуем линию
    pDrawList->AddLine(
            pointA,
            pointB,
            ImColor(150, 200, 100),
            0.5f
    );

    // рисуем линию
    pDrawList->AddLine(
            pointA,
            renderPointC,
            ImColor(150, 200, 100),
            0.5f
    );

    // рисуем линию
    pDrawList->AddLine(
            pointB,
            renderPointD,
            ImColor(150, 200, 100),
            0.5f
    );

    // рисуем точку
    pDrawList->AddCircleFilled(
            pointA,
            3,
            ImColor(200, 100, 150)
    );
    // рисуем точку
    pDrawList->AddCircleFilled(
            pointB,
            3,
            ImColor(200, 100, 150)
    );

Получим рисование широкого луча

Многоугольник

Чтобы нарисовать многоугольник, нужно перечислить его вершины в массиве и вызвать метод рисования с одним из аргументов, равным этому массиву.

    // получаем список примитивов, которые будут нарисованы
    auto pDrawList = ImGui::GetWindowDrawList();

    // список вершин
    ImVec2 lst[5] = {
            ImVec2(200, 550),
            ImVec2(250, 550),
            ImVec2(290, 600),
            ImVec2(190, 700),
            ImVec2(160, 700),
    };

    // рисуем закрашенный многоугольник
    pDrawList->AddConvexPolyFilled(
            lst,
            5,
            ImColor(150, 150, 200)
    );

    // рисуем многоугольник линиями
    pDrawList->AddPolyline(
            lst,
            5,
            ImColor(200, 200, 200),
            ImDrawListFlags_AntiAliasedLines,
            2.5
    );

    // рисуем опорные точки
    for (ImVec2 pos: lst) {
        // рисуем точку
        pDrawList->AddCircleFilled(
                pos,
                3,
                ImColor(200, 100, 150)
        );
    }

Метод Монте-Карло

В части задач нужно находить площадь пересечения. Лучше всего с этим справляется метод Монте-Карло.

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

Поэтому если принять площадь экрана за исходную $S$, тогда площадь любой фигуры $S_f$ будет равна

$$S_f = S\frac{C_f}{C},$$

где $C$ - общее число случайных точек, $C_f$ - кол-во точек внутри фигуры

Задание

Здесь описаны основные этапы выполнения проекта, также обозначены даты их дедлайнов для учащихся 239.

Каждый законченный этап должен быть сохранён в коммите с указанным названием. Между такими коммитами вы можете добавлять сколько угодно своих, но этапы будут оцениваться именно по последнему коммиту с требуемым названием. Если такого коммита нет, этап считается невыполненным.

Ссылку на репозиторий с проектом необходимо прислать в соответствующий тест mdl.

Ссылка на контест

Без readme задания не проверяются

Для каждого этапа обязателен оформленный в соответствии с требованиями readme файл. Без него проверка исходного кода не выполняется

ReadMe

Вам необходимо создать репозиторий и поместить в него readme файл. Он должен быть устроен следующим образом:

Сначала должен идти заголовок "Геометрический проект по информатике"

После него в первом абзаце необходимо указать: класс, фамилию и имя

Во втором абзаце необходимо привести условие задачи

Также должна быть добавлена картинка, иллюстрирующая задачу.

Название коммита: ReadMe

Примитивы

Необходимо заполнить добавить окно управления. В нём должна быть всего одна панель, управляющая цветом фона.

Также необходимо написать структуры под каждый примитив, создать соответствующие списки. По этим спискам требуется запрограммировать рисование примитивов на экране, списки должны заполняться вручную при старте приложения.

Название коммита: Primitives

Добавление мышью

Необходимо с помощью кнопок мыши добавлять все примитивы. Если примитив состоит из $n$ точек, то примитив должен добавляться каждые $n$ кликов соответствующей кнопкой мыши.

Название коммита: Mouse add ready

Панель добавления

Необходимо добавить в приложение панель ручного добавления примитивов.

Название коммита: Manual add panel

Случайные точки

Необходимо добавить в приложение панель случайного добавления примитивов.

Название коммита: Random

Работа с файлами

Необходимо добавить в приложение панель работы с файлами.

Название коммита: Files

Решение задачи

Необходимо добавить в приложение панель решения задачи.

Также необходимо прописать отображение ответа как на панели информации, так и на панели рисования.

Название коммита: Solve

Help

Необходимо добавить в приложение панель помощи

Название коммита: Help panel

Отчёт

В отчёте необходимо описать, что было выполнено, какие алгоритмы были разработаны. Pdf пример готового отчёта можно скачать здесь, а Word здесь.

Готовый отчёт нужно положить в папку report в корне вашего проекта. Предварительно необходимо создать эту папку. Отчёт должен быть сохранён в двух форматах: 'pdf' и 'word' и называться ГОД_ВЫПУСКА_ПАРАЛЛЕЛЬ_ФАМИЛИЯ_ИМЯ_отчёт.

Например, для учащегося 10-8 в 2022 году Иванова Александра отчёт должен называться 2023_8_Иванов_Александр.pdf и 2023_8_Иванов_Александр.docx

Название коммита: Report

Презентация

Для защиты проекта вам необходимо подготовить презентацию. Пример презентации можно скачать здесь.

Готовую презентацию надо также, как и отчёт, положить в папку report. Название файла определяется так же как и название отчёта. Презентация Иванова Александра должен была бы называться 2023_8_Иванов_Александр.pptx.

Название коммита: Presentation

---

Защита

Защита проекта происходит на уроке. Учащийся должен будет выступить с презентацией и рассказать о том, как работает его программа. Защищать проект можно на любом из уроков, как только учащийся посчитает себя подготовленным к этому.

Оценка за защиту ставится с коэффициентом 2, оценивается само выступление, законченность приложения и качество презентации