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

Теперь идея исходит из использования кросс-произведения двух векторов в алгоритмах для нахождения выпуклого множества множества точек, например. Graham Scan . Скажем, мы имеем две точки p1 и p2, которые определяют точечные векторы p1 и p2 , начиная с начала (0,0) до (x1, y1) и (x2, y2) соответственно. Перекрестное произведение p1 x p2 дает третий вектор p3 , который перпендикулярен как p1 , так и p2 и имеет величину, заданную площадью параллелограмма, ограниченного векторами.

Очень полезный результат состоит в том, что определитель матрицы

/ x1, x2 \ \ y1, y2 /

Который является x1 * y2 - x2 * y1, дает величину вектора p3 , а знак указывает, является ли p3 "выходящим" из плоскости или "входить" в него. Ключевым моментом здесь является то, что если эта величина положительная, то p2 находится "слева" от p1 , а если она отрицательная, то p2 вправо " p1 .

Надеюсь, этот пример искусства ascii поможет:

P2(4, 5) / / / /_ _ _ _ _. p1(5, 0)

x1 * y2 - x2 * y1 = 5 * 4 - 0 * 5 = 20, и поэтому p2 находится "слева" от p1

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

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

poly = [(1, 1), (4, 2), (5, 5), (3, 8), (0, 4)]

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

points = set(["(3, 0), (10, -2), (3,3), ...])

Основной бит самого кода на самом деле довольно компактен для того, как долго мне приходилось писать о том, как он работает. to_right принимает два кортежа, представляющих векторы, и возвращает True , если v2 лежит справа от v1 . Затем петли проходят через все края многоугольника и удаляют точки из рабочего набора, если они находятся справа от любого из ребер.

Def to_right(v1, v2): return (v1*v2 - v1*v2) < 0 for i in range(len(poly)): v1 = poly v2 = poly[i] for p in points: if(to_right(v2-v1, p-v1)): points.remove(p)

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

В любом случае, надеюсь, что я прав по этому поводу, и это может помочь кому-то, даже если не OP. Асимптотическая сложность этого алгоритма равна O (mn), где n - количество точек в графе, а m - количество вершин многоугольника, так как в худшем случае все точки лежат внутри многоугольника, и мы должны проверять каждую точку для каждого ребра, при этом никто не удаляется.

Графическое отображение точки на комплексном чертеже

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

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

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

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

Построение проекций точки по ее координатам

Пусть заданы координаты какой-либо точки А (x, y, z ). Тогда ее проекции строят следующим образом: сначала откладывают абсциссу по оси ОХ ; затем проводят вертикальную линию; далее на ней откладывают ординату по оси OY и аппликату по оси OZ (вверх, либо вниз от оси ОХ в зависимости от знака координат y, z ). По оси OY получают горизонтальную проекцию А 1 , по оси OZ - фронтальную А 2 . Профильную проекцию А 3 строят по А 1 и А 2 (либо по координатам). Например, построим проекции точки А (10, 20, 30), заданной конкретными координатами. Построения показаны на рис. 1.4.

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

Рис. 1.4. Взаимосвязь координат точки и ее проекций:

а) вид в аксонометрии; б) комплексный чертеж.

Исходя из тех же положений, решается обратная задача – определение координат точки по ее проекциям. Если на комплексном чертеже изображены проекции точки, тогда, измерив соответствующие расстояния, определяем ее координаты (см. рис. 1.4, б). Причем для определения всех трех координат достаточно двух проекций, т.к. любая пара проекций однозначно задается тремя координатами.

Удаленность точки от плоскостей проекций

Расстояние точки от какой-либо плоскости проекций определяет положение соответствующих проекций, а именно: расстояние до П 1 характеризует положение фронтальной проекции, расстояние до П 2 – горизонтальной проекции, расстояние до П 3 – и горизонтальной и фронтальной проекций. Так, если известно, что точка А удалена от П 1 на 30 мм, тогда ее фронтальная проекция А 2 удалена от оси ОХ на 30 мм; если задано, что точка А удалена от П 3 на 10 мм, тогда А 1 и А 2 удалены от осей OZ и OY соответственно на это расстояние (рис. 1.5).

Задание 1. (7 баллов)

Числитель и знаменатель дроби - положительные числа. Числитель увеличили на 1, а знаменатель - на 100. Может ли полученная дробь оказаться больше исходной?

Ответ: да.

Решение. Например, . Есть и много других примеров.

Критерии. Любой правильный пример: 7 баллов.

Ответ без примера или неправильный ответ: 0 баллов.

Задание 2. (7 баллов)

Ребятам дали задания перевести скорость черепахи из сантиметров в секунду в метры в минуту. Маша получила ответ 25 м/мин, но при этом считала, что в метре 60 см, а в минуте 100 секунд. Помогите Маше найти правильный ответ.

Ответ: 9 м/мин.

Решение. Черепаха за одну Машину «минуту» преодолевает расстояние в 25 Машиных «метров», то есть за 100 секунд проползает 25 · 60 сантиметров. Тогда скорость черепахи равна (25· 60)/100 = 15 см/сек. Значит, за 60 секунд черепаха проползет 15 · 60 сантиметров, то есть (15· 60)/100 = 9 метров.

Критерии.

Правильно найдена скорость в сантиметрах в секунду, а последующая часть не сделана или сделана с ошибкой: 3 балла.

Задание 3. (7 баллов)

В некоторый момент времени Аня измерила угол между часовой и минутной стрелками своих часов. Ровно через один час она снова измерила угол между стрелками. Угол оказался таким же. Каким мог быть этот угол?

(Разберите все случаи.)

Ответ: 15° либо 165°.

Решение. Через 1 час минутная стрелка остается на своем месте. При этом часовая стрелка повернулась на 30°. Раз угол не изменился, то минутная стрелка делит пополам один из углов между положениями часовой стрелки (либо тот, который 30°, либо дополнительный угол в 330°).

Значит, либо часовая стрелка была на 15° раньше, либо на 165° позже.

Критерии. Любое правильное решение: 7 баллов.

Даны оба правильных ответа без обоснования или с неверным обоснованием: 3 балла.

Дан один из правильных ответов: 1 балл.

Задание 4. (7 баллов)

Два пешехода вышли на рассвете. Каждый шёл с постоянной скоростью. Один шёл из A в B , другой - из B в A . Они встретились в полдень (т. е. ровно в 12 часов) и, не прекращая движения, пришли: один - в B в 4 часа вечера, а другой – в A в 9 часов вечера. В котором часу в тот день был рассвет?

Ответ: в 6 утра.

Решение. Точку встречи обозначим за C . Пусть от рассвета до полудня прошло x часов.

Скорость первого пешехода на участке AC равна AC/x , на участке BC равна BC/ 4. Его скорость постоянна, и значит AC/x = BC/ 4 , что можно переписать в виде AC/BC = x/ 4 .

Аналогично для второго пешехода: равенство скоростей на участках BC , AC выльется в соотношение BC/x = AC/9 , которое мы перепишем в форме AC/ BC = 9x .

Получаем, что x/ 4 = 9/x , и по свойству пропорции x 2 = 36, x = 6 . Рассвет был на 6 часов раньше полудня, т. е. в 6 утра.

Критерии. Любое правильное решение: 7 баллов.

Правильно найден промежуток времени от рассвета до встречи, но время рассвета не найдено или найдено с ошибкой: 5 баллов.

Только ответ без решения: 1 балл.

Задание 5. (7 баллов)

Определите, в каком количестве точек пересекаются 10 прямых, если среди них есть только две параллельные и ровно три из этих прямых пересекаются в одной точке.

Ответ : 42.

Решение. Пронумеруем прямые так, чтобы именно прямые 1, 2 и 3 пересекались в одной точке (эту точку обозначим за X ). Выпишем всевозможные пары прямых (1 и 2, 1 и 3, 1 и 4, . . . , 8 и 9, 8 и 10, 9 и 10) и их точки пересечения. Всего пар прямых 45 (пар вида 1 и ` ровно 9, пар вида 2 и ` ровно 8 и так далее; 9+8+7+6+5+4+3+2+1 = 45). По условию ровно две прямые параллельны. Значит, всего будет выписано 44 точки пересечения. При этом все точки пересечения прямых кроме X будут выписаны ровно по одному разу, а точка X появится трижды: для пар прямых 1 и 2, 1 и 3, 2 и 3. Сотрем из списка точек пересечения две лишние буквы X . Останутся ровно 42 точки, и на этот раз все точки пересечения будут посчитаны ровно по одному разу.

Критерии. Любое правильное решение: 7 баллов.

Правильно посчитано число пар прямых и при этом дан правильный ответ: 2 балла.

Рассмотрены лишь частные случаи или приведен правильный ответ без объяснения: 1 балл.

Для решения задачи разделим ее на следующие этапы:

1. Рассмотрение задачи со стороны многомерного пространства.
2. Рассмотрение задачи со стороны двухмерного пространства.
3. Расчет количества точек пересечения.

Рассмотрение задачи со стороны многомерного пространства

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

Рассмотрение задачи со стороны двухмерного пространства

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

Расчет количества точек пересечения

При добавлении на плоскость новой не параллельной прямой будут добавляться точки пересечения с теми прямыми, которые уже нанесены на плоскости. Следовательно, две прямые дают 1 точку пересечения. Добавляя третью прямую, мы получаем еще 2 точки пересечения с уже нанесенными двумя прямыми; добавляя четвертую прямую получаем еще 3 точки пересечения; пятую - еще 4 точки пересечения. Таким образом, всего получаем:

1 + 2 + 3 + 4 = 10 точек пересечения

Ответ: 1) многомерное пространство - 0 точек пересечения; 2) двухмерное пространство - 10 точек пересечения.

Две прямые имеют одну точку пересечения. Добавив к ним ещё одну прямую, мы получим ещё 2 точки пересечения с каждой из этих двух прямых. Добавив ещё одну прямую, она даст дополнительно столько точек пересечения, сколько уже было прямых, т.е. ещё 3. И так далее. Каждая n-ая прямая даёт дополнительно (n-1) точек пересечения с (n-1) прямыми.

1 + 2 + 3 + 4 = 10

Всё вышесказанное справедливо в случае если ни одна из любых 3 прямых не имеет 1 общую точку пересечения.

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

Ответ: 10 точек пересечения будет образовано 5 не параллельными прямыми, когда более 2 прямых не пересекается в одной точке. Или же 5 точек пересечения если более двух прямых может пересекаться в одной точке.

Рассмотрим следующий рисунок.

На нем изображен график функции y = x^3 – 3*x^2. Рассмотрим некоторый интервал содержащий точку х = 0, например от -1 до 1. Такой интервал еще называют окрестностью точки х = 0. Как видно на графике, в этой окрестности функция y = x^3 – 3*x^2 принимает наибольшее значение именно в точке х = 0.

Максимум и минимум функции

В таком случае, точку х = 0 называют точкой максимума функции. По аналогии с этим, точку х = 2 называют точкой минимума функции y = x^3 – 3*x^2. Потому что существует такая окрестность этой точки, в которой значение в этой точке будет минимальным среди всех других значений из этой окрестности.

Точкой максимума функции f(x) называется точка x0, при условии, что существует окрестность точки х0 такая, что для всех х не равных х0 из этой окрестности, выполняется неравенство f(x) < f(x0).

Точкой минимума функции f(x) называется точка x0, при условии, что существует окрестность точки х0 такая, что для всех х не равных х0 из этой окрестности, выполняется неравенство f(x) > f(x0).

В точках максимума и минимума функций значение производной функции равно нулю. Но это не достаточное условие для существования в точке максимума или минимума функции.

Например, функция y = x^3 в точке х = 0 имеет производную равную нулю. Но точка х = 0 не является точкой минимума или максимума функции. Как известно функция y = x^3 возрастает на всей числовой оси.

Таким образом, точки минимума и максимума всегда будут находиться среди корне уравнения f’(x) = 0. Но не все корни этого уравнения будут являться точками максимума или минимума.

Стационарные и критические точки

Точки, в которых значение производной функции равно нулю, называются стационарными точками. Точки максимума или минимума могут иметься и вточках, в которых производной у функции вообще не существует. Например, у = |x| в точке х = 0 имеет минимум, но производной в этой точке не существует. Эта точка будет являться критической точкой функции.

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

Пусть f(x) некоторая дифференцируемая на интервале (a;b) функция. Точка х0 принадлежит этому интервалу и f’(x0) = 0. Тогда:

1. если при переходе через стационарную точку х0 функция f(x) и её производная меняет знак, с «плюса» на «минус», тогда точка х0 является точкой максимума функции.

2. если при переходе через стационарную точку х0 функция f(x) и её производная меняет знак, с «минуса» на «плюс», тогда точка х0 является точкой минимума функции.