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

В общем случае плоскости проекций разделяют все пространство на 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

Определить взаимное расположении точки и прямой: лежит выше прямой, на прямой, под прямой.

Решение
Понятно, что если прямая задана своим уравнением ax + by + c = 0, то тут и решать нечего. Достаточно подставить координаты точки в уравнение прямой и проверить чему оно равно. Если больше нуля, то точка находится в верхней полуплоскости, если равна нулю, то точка находится на прямой и если меньше нуля, то точка находится в нижней полуплоскости. Интереснее случай, когда прямая задана, задана координатами двух точек назовем их P 1 (x 1 , y 1), P 2 (x 2 , y 2). В этом случае можно спокойно найти коэффициенты a, b и c и применить предыдущее рассуждение. Но надо сначала подумать, оно нам надо? Конечно, нет! Как я говорил косое произведения - это просто жемчужина вычислительной геометрии. Давайте применим его. Известно, что косое произведение двух векторов положительно, если поворот от первого вектора ко второму идет против часовой стрелки, равно нулю, если векторы коллинеарны и отрицательно, если поворот идет по часовой стрелки. Поэтому нам достаточно посчитать косое произведение векторов P 1 P 2 и P 1 M и по его знаку сделать вывод.

Задача №2

Определить принадлежит ли точка лучу.

Решение
Давайте вспомним, что такое луч: луч - это прямая, ограниченная точкой с одной стороны, а с другой стороны бесконечная. То есть луч задается некоторой начальной точкой и любой точкой лежащей на нем. Пусть точка P 1 (x 1 , y 1) - начало луча, а P 2 (x 2 , y 2) - любая точка принадлежащая лучу. Понятно, что если точка принадлежит лучу, то она принадлежит и прямой проходящей через эти точки, но не наоборот. Поэтому принадлежность прямой является необходимым, но не достаточным условием для принадлежности лучу. Поэтому от проверки косового произведения нам никуда не деться. Для достаточного условия нужно вычислить еще и скалярное произведение тех же векторов. Если оно меньше нуля, то точка не принадлежит лучу, если же оно не отрицательно, то точка лежит на луче. Почему так? Давайте посмотрим на рисунок.

Итак, для того чтобы точка M(x, y) лежала на луче с начальной точкой P 1 (x 1 , y 1), где P 2 (x 2 , y 2) лежит на луче необходимо и достаточно выполнения двух условий:

2. (P 1 P 2 , P 1 M) ≥ 0 – скалярное произведение (точка лежит на луче)

Задача №3

Определить принадлежит ли точка отрезку.

Решение
Пусть точки P 1 (x 1 , y 1), P 2 (x 2 , y 2) концы заданного отрезка. Опять-таки необходимым условием принадлежности точки отрезку является ее принадлежность прямой проходящей через P 1 , P 2 . Далее нам нужно определить лежит ли точка между точками P 1 и P 2 , для этого нам на помощь приходит скалярное произведение векторов только на этот раз других: (MP 1 , MP 2). Если оно меньше либо равно нуля, то точка лежит на отрезке, иначе вне отрезка. Почему так? Посмотрим на рисунок.

Итак, для того чтобы точка M(x, y) лежала на отрезке с концами P 1 (x 1 , y 1), P 2 (x 2 , y 2) необходимо и достаточно выполнения условий:
1. = 0 – косое произведение (точка лежит на прямой)
2. (MP 1 ,MP 2) ≤ 0 – скалярное произведение (точка лежит между P 1 и P 2)

Задача №4

Взаимное расположение двух точек относительно прямой.

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

Если точки находятся по разные стороны относительно прямой, то косые произведения имеют разные знаки, а значит их произведение отрицательно. Если же точки лежат по одну сторону относительно прямой, то знаки косых произведений совпадают, значит, их произведение положительно.
Итак:
1. * < 0 – точки лежат по разные стороны.
2. * > 0 – точки лежат по одну сторону.
3. * = 0 – одна (или две) из точек лежит на прямой.

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

Задача №5

Определить пересекаются ли две прямые.

Решение
Будем считать, что прямые не совпадают. Понятно, что прямые не пересекаются, только если они параллельны. Поэтому, найдя условие параллельности, мы можем, определить пересекаются ли прямые.
Допустим прямые заданы своими уравнениями a 1 x + b 1 y + c 1 = 0 и a 2 x + b 2 y + c 2 = 0. Тогда условие параллельности прямых заключается в том, что a 1 b 2 - a 2 b 1 = 0.
Если же прямые заданы точками P 1 (x 1 , y 1), P 2 (x 2 , y 2), M 1 (x 3 , y 3), M 2 (x 4 , y 4), то условие их параллельности заключается в проверки косого произведения векторов P 1 P 2 и M 1 M 2: если оно равно нулю, то прямые параллельны.

В общем, то когда прямые заданы своими уравнениями мы тоже проверяем косое произведение векторов (-b 1 , a 1), (-b 2 , a 2) которые называются направляющими векторами.

Задача №6

Определить пересекаются ли два отрезка.

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

Итак, нам нужно проверить, чтобы концы каждого из отрезков лежали по разные стороны относительного концов другого отрезка. Пользуемся косым произведением векторов. Посмотрите на первый рисунок: > 0, < 0 => * < 0. Аналогично
* < 0. Вы наверно думаете, почему не меньше либо равно. А потому, что возможен следующий случай, при котором векторное произведение как раз и равно нулю, но отрезки не пересекаются:

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

Итак, для того чтобы отрезки имели общие точки необходимо и достаточно:
1. Концы отрезков лежат по разные стороны относительно другого отрезка.
2. Хотя бы один из концов одного отрезка принадлежит другому отрезку.

Задача №7

Расстояние от точки до прямой.

Решение
Пусть прямая задана двумя точками P 1 (x 1 , y 1) и P 2 (x 2 , y 2).

В предыдущей статье мы говорили о том, что геометрически косое произведение - это ориентированная площадь параллелограмма, поэтому S P 1 P 2 M = 0,5*. С другой стороны каждому школьнику известна формула для нахождения площади треугольника: половина основание на высоту.
S P 1 P 2 M = 0,5*h*P 1 P 2 .
Приравнивая эти площади, находим

По модулю взяли потому, что первая площадь ориентированная.

Если же прямая задана уравнением ax + by + c = 0, то уравнение прямой проходящей через точку M перпендикулярной заданной прямой есть: a(y - y 0) – b(x - x 0) = 0. Теперь спокойно можно решить систему из полученных уравнений, найти их точку пересечения и вычислить расстояние от исходной точки до найденной: оно будет ровно ρ = (ax 0 + by 0 + c)/√(a 2 + b 2).

Задача №8

Расстояние от точки до луча.

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

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

Как же определить падает ли перпендикуляр на луч или нет? Если перпендикуляр не падает на луч, то угол MP 1 P 2 – тупой иначе острый (прямой). Поэтому по знаку скалярного произведения векторов мы можем определить попадает ли перпендикуляр на луч или нет:
1. (P 1 M, P 1 P 2) < 0 перпендикуляр не попадает на луч
2. (P 1 M, P 1 P 2) ≥ 0 перпендикуляр попадает на луч

Задача №9

Расстояние от точки до отрезка.

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

Чтобы определить попадает ли перпендикуляр на отрезок нужно по аналогии с предыдущей задачей использовать скалярное произведение векторов. Если перпендикуляр не падает на отрезок, то либо угол MP 1 P 2 либо угол MP 2 P 1 будут тупыми. Поэтому по знаку скалярных произведений мы можем определить попадает ли перпендикуляр на отрезок или нет:
Если (P 1 M, P 1 P 2) < 0 или (P 2 M, P 2 P 1) < 0 то перпендикуляр не падает на отрезок.

Задача №10

Определить количество точек прямой и окружности.

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

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

Задача №11

Взаимное расположение двух окружностей.

Решение
Возможные случаи расположения окружностей: пересекаются, касаются, не пересекаются.

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

Вспомним теперь, что такое сектор и сегмент.

Пересечение кругов состоит из двух сегментов O 1 AB и O 2 AB.

Казалось бы необходимо сложить площади этих сегментов и все. Однако, все не так просто. Необходимо еще определить всегда ли эти формулы верны. Оказывается, нет!

Рассмотрим случай, когда центр второго круга O 2 совпадает с точкой C. В этом случае d 2 = 0 и за значение α примем α = π. В этом случае имеем полукруг с площадью 1/2 πR 2 2 .

Теперь рассмотрим случай, когда центр второго круга O 2 находится между точками O 1 и C. В этом случае получим отрицательное значение величины d 2 . Использование отрицательного значения d 2 приводит к отрицательному значению α. В этом случае необходимо для правильного ответа прибавить к α 2π.

Заключение

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

Надеюсь, Вам понравилось.

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

Навигация по странице.

Точка пересечения двух прямых – определение.

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

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

Рассмотрим решение примера.

Пример.

Найдите точку пересечения двух прямых, определенных в прямоугольной системе координат на плоскости уравнениями x-9y+14=0 и 5x-2y-16=0 .

Решение.

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

Найденное решение системы уравнений дает нам искомые координаты точки пересечения двух прямых.

Ответ:

M 0 (4, 2) x-9y+14=0 и 5x-2y-16=0 .

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

Пример.

и .

Решение.

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

Теперь проведем необходимые действия с каноническим уравнением прямой :

Таким образом, искомые координаты точки пересечения прямых являются решением системы уравнений вида . Используем для ее решения :

Ответ:

M 0 (-5, 1)

Существует еще один способ нахождения координат точки пересечения двух прямых на плоскости. Его удобно применять, когда одна из прямых задана параметрическими уравнениями вида , а другая – уравнением прямой иного вида. В этом случае в другое уравнение вместо переменных x и y можно подставить выражения и , откуда можно будет получить значение , которое соответствует точке пересечения заданных прямых. При этом точка пересечения прямых имеет координаты .

Найдем координаты точки пересечения прямых из предыдущего примера этим способом.

Пример.

Определите координаты точки пересечения прямых и .

Решение.

Подставим в уравнение прямой выражения :

Решив полученное уравнение, получаем . Это значение соответствует общей точке прямых и . Вычисляем координаты точки пересечения, подставив в параметрические уравнения прямой:
.

Ответ:

M 0 (-5, 1) .

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

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

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

Рассмотрим примеры, подходящие под эти ситуации.

Пример.

Выясните, пересекаются ли прямые и , и если пересекаются, то найдите координаты точки пересечения.

Решение.

Заданным уравнениям прямых соответствуют уравнения и . Решим систему, составленную из этих уравнений .

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

Ответ:

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

Пример.

Найдите координаты точки пересечения прямых и , если это возможно.

Решение.

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

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

Второй способ решения.

Давайте выясним, пересекаются ли заданные прямые.

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

Ответ:

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

Пример.

Найдите координаты точки пересечения прямых 2x-1=0 и , если они пересекаются.

Решение.

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

Для нахождения координат точки пересечения прямых нам нужно решить систему:

Полученное решение дает нам координаты точки пересечения прямых, то есть, 2x-1=0 и .

Ответ:

Нахождение координат точки пересечения двух прямых в пространстве.

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

Рассмотрим решения примеров.

Пример.

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

Решение.

Составим систему уравнений из уравнений заданных прямых: . Решение этой системы даст нам искомые координаты точки пересечения прямых в пространстве. Найдем решение записанной системы уравнений.

Основная матрица системы имеет вид , а расширенная - .

Определим А и ранг матрицы T . Используем

Я боюсь, что не знаком с библиотеками, которые вы используете, но я думаю, что у меня есть разумная идея для алгоритма, который вы могли бы использовать, и я просто займусь тем, как я буду реализовывать это с помощью 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 - количество вершин многоугольника, так как в худшем случае все точки лежат внутри многоугольника, и мы должны проверять каждую точку для каждого ребра, при этом никто не удаляется.