alt text

$%\frac{x-4}{8-4}=\frac{y-4}{12-4}⇒\frac{x-4}{4} = \frac{y-4}{8}⇒8(x-4)=4(y-4)$%

$%8x-32=4y-16⇒2x-8=y-4⇒2x-y-8+4=0$%

$%2x-y-4=0$%

$%10 \cdot 2-6-4≥0$%

И у меня вот ещё какой вопрос - оптимизация. Мне, в месте с Вашей помощью, показали пример, который вроде тоже самое, но я не могу не как его понять. Там вот как - $%(E_y-A_y) \cdot (B_x-A_x) - (E_x-A_x) \cdot (B_y-A_y)$% Помогите мне его пожалуйста интерпретировать, сам пол дня думаю, пытаюсь его натянуть на уравнение плоскости через две точки, но не могу, а осознавать, что пользуешься тем, чего не понимаешь, не хочется. И хотел хотел спросить о том, что относится ли это к данной теме, но мне кажется что да.

задан 21 Янв '14 1:46

изменен 24 Янв '14 23:32

@shatal: нет, это просто первые попавшиеся буквы, которыми я обозначил коэффициенты уравнения прямой, проходящей через точки $%A_i$% и $%A_{i+1}$%. Обратите внимание, что у меня в ответе об этом сказано в явной форме. Задача составления уравнения прямой по двум точкам с известными координатами -- вещь очень простая.

(21 Янв '14 16:47) falcao

Прямая AB имеет уравнение x=2. Это видно сразу, так как она идёт вертикально. Точка E находится справа от этой прямой, так как у неё абсцисса равна 3, то есть больше двух. Это не очень удачный пример для иллюстрации. Желательно брать точки в общем положении, чтобы прямая шла наклонно.

Точку E, кстати, Вы подставили неправильно. Прямая имеет уравнение $%1\cdot x+0\cdot y-2=0$%. Если подставить (3;2), то будет 3+0-2=1, что больше нуля.

(24 Янв '14 20:22) falcao

@falcao: Спасибо! Переделал пример и задал ещё маленький вопросик.

(24 Янв '14 23:30) shatal

@shatal: то векторное выражение, которое Вы написали, может иметь разные знаки, и оно в принципе описывает то же самое, то есть принадлежность точки $%E$% одной из полуплоскостей с границей $%AB$%. В аналитической геометрии одно и то же можно описывать многими эквивалентными способами. Я бы рекомендовал придерживаться чего-то простого, происхождение чего Вы хорошо понимаете. Использовать два равноценных метода вместо одного, вообще говоря, нежелательно.

(25 Янв '14 0:48) falcao
10|600 символов нужно символов осталось
0

Такой способ есть, и он состоит в проверке неравенств. На программном уровне это реализуется довольно легко. Независимо от того, какой вариант имеет место (проверить попадание точки хотя бы в один из многоугольников, во все сразу, или как-то ещё), всё сводится к проверке попадания точки в заданный n-угольник. (В вопросе, видимо, имеется опечатка, потому что сначала говорится о многоугольниках вообще, а потом о прямоугольниках).

Для простоты будем считать, что многоугольники выпуклые. Пусть имеется такой n-угольник с вершинами $%A_1...A_n$%. Координаты каждой из точек нам известны. Поэтому для каждой из n пар соседних точек $%A_i$%, $%A_{i+1}$% (здесь $%A_{n+1}$% совпадает с $%A_1$%) можно составить уравнение прямой, проходящей через эти две точки. Прямая имеет уравнение $%p_ix+q_iy=r_i$%, где все коэффициенты нам известны. Она делит плоскость на две полуплоскости, в одной из которых находится наш многоугольник. Сам он является пересечением n таких полуплоскостей. Поэтому принадлежность заданной точки многоугольнику означает её принадлежность каждой из таких полуплоскостей. Последнее условие представляет собой систему неравенств вида $%p_ix+q_iy\ge r_i$% или $%p_ix+q_iy\le r_i$%, и остаётся лишь конкретизировать выбор знака, чтобы он указывал на ту именно полуплоскость, которая нам нужна. То есть на ту, в которой наш многоугольник находится.

Поскольку программа не работает с "картинкой", она всё это должна отслеживать арифметически. Сделать это просто. А именно, в выражение $%p_ix+q_iy-r_i$% можно в качестве $%x$% и $%y$% подставить координаты любой из вершин кроме тех двух, через которые мы проводили прямую. Выражение при этом окажется либо положительным, либо отрицательным. Из этого мы сразу же делаем вывод, какое из двух неравенств задаёт нужную нам полуплоскость: $%p_ix+q_iy-r_i\ge0$% или $%p_ix+q_iy-r_i\le0$%.

ссылка

отвечен 21 Янв '14 2:15

@shatal: можете для начала посмотреть это всё на примере треугольника. Основная идея здесь простая: выпуклый многоугольник есть пересечение плоскостей; принадлежность полуплоскости выражается на языке линейных неравенств.

(21 Янв '14 13:37) falcao

Модно говорить о точках плоскости, или об упорядоченных парах чисел (x;y), или о векторах -- это одно и то же. Разница только в названиях. Картинка с углом меня наводит только на одну мысль: возможен способ проверки принадлежности точки углу, основанный на разложении вектора AP по векторам AB и AC. Для этого надо решить систему линейных уравнений и проверить, что обе координаты (L и M) неотрицательны. Условие L+M<=1 означает, что P принадлежит треугольнику. Этот способ отличается от описанного мной только тем, что работает примерно в два раза дольше. Но его при желании тоже можно применять.

(21 Янв '14 15:18) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×99
×86

задан
21 Янв '14 1:46

показан
2783 раза

обновлен
25 Янв '14 0:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru