Математические основы информатики: из неопубликованного

Продолжение. См. № 1–2/2008 и курс лекций
“Математические основы информатики” (№ 17–24/2007)

Компьютерная геометрия

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

Прежде всего заметим, что в компьютерной геометрии целесообразно различать два больших класса задач. К одному из них относятся задачи исследования геометрических объектов и конфигураций с помощью компьютера. К другому — задачи построения изображений на экране компьютера. Эти задачи нередко называют задачами визуализации, компьютерной графики и т.п. Имея в основе геометрическую подоплеку, они опираются на физические и физиологические законы восприятия изображений. Учет этих законов тоже, конечно, требует определенного математического аппарата, нередко весьма изощренного, но мы оставим эти вопросы в стороне. А вот геометрическая подоплека здесь та же, что и в задачах первого класса, — исследование геометрических объектов и конфигураций. Поэтому на этих задачах мы и сосредоточим свое внимание.

§ 10. Геометрия, к которой мы привыкли

Все знают, что геометрию, которую каждый из нас изучал в школе, называют евклидовой. Конечно, это в первую очередь дань тому, что именно Евклид систематически изложил известные к его времени геометрические сведения, причем сделал это, говоря современным языком, на основе аксиоматического метода и дедуктивного подхода к их обоснованию. Открытие неевклидовой геометрии, совершенное К.Гауссом, Н.Лобачевским и Я.Бойяи, вовсе не привело к исчезновению евклидовой геометрии из школьного курса. И это несмотря на то, что, как позже показал А.Эйнштейн, законы евклидовой геометрии справедливы только в абсолютно пустом пространстве, т.е. там, где нас с вами нет, не было и никогда не будет. Никого не смущает даже тот факт, что дословно “геометрия” означает “землемерие”, а то, что Земля — не плоскость, теперь знают и дети в детском саду.

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

Важным является еще одно обстоятельство, сопровождающее изучение геометрии “по Евклиду”. В сознании каждого ученика, а в силу всеобщности образования — каждого человека, закрепляются вполне конкретные геометрические образы: объекты и конфигурации. Отрезок, прямая, луч, треугольник, многоугольник, окружность и т.п., их взаимное расположение — вот тот геометрический мир, который осваивается нами в стенах общеобразовательной школы. И совершенно неважно, что в реальной жизни никто из нас никогда не будет доказывать равенство треугольников, пользуясь изученными тремя признаками, вряд ли кому-то из нас часто приходится вписывать окружность в треугольник, строя для этого точку пересечения биссектрис, и делать многое другое, что делают ученики на уроках геометрии (не говоря уже о том, что делают избранные из них на математических олимпиадах). Мы приучены к доисторическим инструментам — циркулю и линейке, и нетрудно понять, что вся школьная геометрия приспособлена именно к этим инструментам создания геометрических конфигураций ². Слепо следуя этим стереотипам, создавались и первые графические редакторы — все просто млели от того, что теперь на экране компьютера можно нарисовать отрезок прямой или окружность.

Первой альтернативной геометрией, реализованной в компьютерном варианте, стала графика Лого. Черепашка, создающая геометрический объект, допускает всего лишь два управляющих воздействия — перемещение на отрезок заданной длины и поворот на заданный угол. Фактически Черепашка рисует ломаную. Но попытайтесь с помощью Черепашки нарисовать треугольник, имеющий стороны заранее заданной длины, скажем, 2, 3 и 4. Вооружившись циркулем и линейкой, вы это сделаете в два счета: на раз проведете окружность радиуса 2 с центром в одном конце отрезка длины 4, на два — окружность радиуса 3 с центром в другом конце отрезка длины 4. Точка пересечения и есть третья вершина треугольника. А для Черепашки придется рассчитать, на какой угол повернуть в конце нарисованного ею отрезка длины 4, чтобы затем на этом направлении прочертить отрезок длины 3. Это значит, придется воспользоваться теоремой косинусов, а заодно научить Черепашку вычислять обратные тригонометрические функции ³. Да что треугольник! Попробуйте заставить Черепашку начертить отрезок, задав две точки — его концы. Проблем еще больше: надо и угол вычислить, на который должна повернуться Черепашка, и длину отрезка. А с помощью линейки никаких проблем.

Можно сказать, что на каждом шаге поведение Черепашки описывается длиной отрезка и его направлением, т.е. направленным отрезком. В свою очередь, для направленного отрезка есть общепринятое название — вектор ⁴. Евклидово изложение геометрии с векторами никак связано быть не могло — сам этот термин появился только в 1845 г. в работах ирландского ученого У.Гамильтона ⁵. В советском школьном образовании векторы появились благодаря реформе математического образования, затеянной академиком А.Н. Колмогоровым в начале 70-х годов прошлого столетия. Отношение к этой реформе было весьма неоднозначным, и далеко не все прогрессивное удалось отстоять ⁶, но векторная алгебра все же стала обязательным компонентом геометрической подготовки современных школьников. Правда, и сегодня она выглядит неким чужеродным фрагментом, поскольку с ее помощью содержательных геометрических утверждений в школьном курсе геометрии практически не доказывается и задач не решается.

Конечно, проблемы школьного математического образования должны решать математики — ученые и методисты. Им виднее, какой должна быть геометрическая подготовка учащихся. Но с точки зрения применения компьютера в решении геометрических задач в большинстве случаев оказывается, что векторный подход наиболее эффективен. Собственно, уже пример с Лого-черепашкой показывает, что векторы компьютеру “милее”, чем традиционная геометрия, к которой мы так привыкли. Впрочем, чем дальше мы будем вникать в компьютерную геометрию, тем сильнее это будет проявляться.

§ 11. Векторная алгебра как основа вычислительной геометрии

Каждый понимает, что каким бы умным и разносторонним ни казался компьютер, это всего лишь машина, быстро выполняющая вычисления. Значит, все чисто геометрические постановки задач должны быть переведены на язык вычислений. И не важно, идет ли речь о построении прямой, проходящей через заданную точку параллельно заданной прямой, или, наоборот, из этой точки надо опустить перпендикуляр на данную прямую, а может быть, надо построить касательную к данной окружности… Разнообразие геометрических задач огромно, а способ перевода нужен пригодный на все случаи жизни. По счастью, такой способ уже придуман Р.Декартом. Правда, он был максималистом (или оптимистом — что нередко оказывается одним и тем же), предлагая универсальный метод решения всех задач. Вот этот метод:

— любая задача сводится к математической задаче;

— любая математическая задача сводится к алгебраической задаче;

— любая алгебраическая задача сводится к системе уравнений;

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

К сожалению, оказалось, что ни одно из этих четырех утверждений не является верным. Но! Для евклидовой геометрии это оказалось верным.

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

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

Если точки плоскости выстраиваются в линию, то это означает, что между координатами имеется зависимость. Зависимость мы стараемся выразить с помощью равенства. Получается, что линия на плоскости задается некоторым уравнением, в котором переменными выступают координаты произвольной точки, принадлежащей линии. Оказалось, что прямые и окружности, составляющие основу всей школьной геометрии, задаются довольно простыми уравнениями: прямая — уравнением первой степени, а окружность — уравнением вида (x – a)² + (y – b)² = r². В последнем равенстве смысл параметров a, b и r очень прост: a и b — координаты центра окружности, а r — ее радиус.

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

Тем самым, получается следующий словарь перевода с геометрического языка (в случае плоскости) на алгебраический язык:

Конечно, этот “словарь” весьма не полон. Но мы почти не будем им пользоваться. И вот почему.

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

Нам даны координаты трех точек — А(m; n), B(p; q) и C(u; v). Ищем уравнение прямой, проходящей через точки А и В. Смотрим в строку № 3 в нашем словарике: нам требуется найти коэффициенты a, b и c в уравнении ax + by + c = 0. Откуда их искать? Смотрим строку № 5 в словаре: должны выполняться равенства am + bn + c = 0 и ap + bq + c = 0. Значит, надо решить систему этих двух уравнений с тремя неизвестными. Уже возникает ряд вопросов: всегда ли система имеет решение? если решений много, то можно ли взять одно из них, а остальными пренебречь? не может ли случиться так, что для одного решения системы окончательный ответ на вопрос задачи будет положительным, а для другого — отрицательным? Конечно, получить ответы на эти вопросы несложно, но возникает разбор случаев, связанный, в частности, с тем, имеются ли среди одноименных координат точек А и В равные. Кроме того, при нахождении коэффициентов a, b и c возникает деление на m – p или n – q, что при проведении вычислений, как известно, чревато неприятностями, если какая-либо из этих разностей мала.

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

Рис. 2

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

Оказывается, что для операций сложения и умножения на число справедливы все обычные законы, известные для этих операций над числами ⁷:

7) 1 · = — унитарность умножения.

Определив – = (–1), мы получаем возможность векторы не только складывать, но и вычитать: .

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

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

Теорема 1. (Признак коллинеарности.) Вектор коллинеарен ненулевому вектору тогда и только тогда, когда существует число, для которого .

Эта теорема сводит геометрический вопрос о параллельности прямых к простому алгебраическому вопросу — пропорциональны ли два вектора? А ведь сколько хлопот доставляют школьникам пресловутые признаки параллельности прямых!

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

Мы уже слишком много внимания уделили различным математическим фактам и фактикам из школьного курса векторной алгебры и метода координат. Но сейчас нам нужно соединить два этих метода (что на самом деле и проделал У.Гамильтон, кроме того, что придумал название “вектор”). Оказывается, что каждый вектор плоскости тоже можно описать парой чисел. Получается она так. Пусть вектор задается направленным отрезком, начало которого — это точка А(m; n), а конец — точка B(p; q). Тогда вектор однозначно определяется парой чисел (m – p; n – q). Эта пара чисел называется координатами вектора, и оказывается, что координаты вектора совершенно не зависят от того, какой направленный отрезок был выбран как представитель вектора . Факт совершенно чудесный. Но “чудеса” этим не ограничиваются. Вот еще одна теорема.

Теорема 2. Координаты суммы векторов равны суммам координат. Координаты произведения вектора на число равны произведениям координат на это число.

Из этой теоремы немедленно следует, что коллинеарность векторов — это пропорциональность их координат (число выступает коэффициентом пропорциональности). Возвращаясь к вопросу о том, лежат ли точки А(m; n), B(p; q) и C(u; v) на одной прямой, легко получаем ответ. Действительно, чтобы эти точки лежали на одной прямой, необходимо и достаточно, чтобы векторы, заданные направленными отрезками АВ и АС, были коллинеарны. Значит, для координат этих векторов должна выполняться пропорция:

Конечно, читатель в этом месте может поморщиться — условие принадлежности трех точек получилось легко, но ведь деления избежать не удалось. На самом деле правильно проверять, пропорциональны ли значения двух величин, школьников учат в 6-м классе (о чем к моменту изучения информатики они обычно забывают). Так называемое “основное свойство пропорции” гласит: пропорция выполняется, если произведение крайних ее членов равно произведению средних членов. Если не выражаться так пышно, то это просто значит, что должно иметь место равенство   (m – p) (n – v) = (m – u) (n – q). И все!

К пониманию, что такое геометрия, математики шли долго. Современное понимание связано с именем Ф.Клейна, который обосновал, что даже в рамках школьного курса на самом деле изучаются три разновидности геометрии. Те вопросы, которые мы рассматривали выше, — принадлежность точек одной прямой, параллельность прямых и другие подобные свойства, в которых не фигурирует измерение длин и углов, принято относить к так называемой “аффинной геометрии” ⁸. Но ясно, что в школьной геометрии изучаются понятие длины отрезка, измерение углов и площадей геометрических фигур. Все это относится к так называемой “метрической геометрии”. Чтобы с помощью векторов описать эти понятия, нам потребуется ввести еще две операции над векторами. Первая из них также изучается в школьном курсе математики и называется скалярным произведением. Напомним, что углом между ненулевыми векторами и называется наименьший угол между направленными отрезками этих векторов, отложенными от одной точки. Угол между векторами считается ориентированным: он положителен, если поворот от направленного отрезка вектора к направленному отрезку вектора совершается против часовой стрелки; в противном случае угол считается отрицательным. Скалярным произведением двух векторов называется произведение длин этих векторов на косинус угла между ними. Скалярное произведение векторов и будем обозначать .

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

1) — дистрибутивность скалярного произведения относительно сложения;

2) — “ассоциативность” умножения числа на скалярное произведение.

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

1) — дистрибутивность псевдоскалярного произведения относительно сложения;

2) — “ассоциативность” умножения числа на псевдоскалярное произведение.

Рис. 3

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

— ненулевые векторы и перпендикулярны тогда и только тогда, когда их скалярное произведение равно 0;

— скалярное произведение вектора на себя равно квадрату длины этого вектора.

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

Осталось, как и раньше, “увязать” эти операции с координатным способом задания векторов. Мы в очередной раз приведем готовые формулы, отсылая читателя к стандартным школьным учебникам (в случае скалярного произведения) и к упомянутой в сноске 9 книге Е.В. Андреевой (в случае псевдоскалярного произведения). Впрочем, в задании 3 мы предлагаем получить эти формулы самостоятельно.

Итак, пусть пара (х; у) — координаты вектора , пара (u; v) — координаты вектора . Тогда

Из определения псевдоскалярного произведения сразу следует, что оно равно нулю тогда и только тогда, когда перемножаемые векторы коллинеарны. Из этого утверждения уже совсем нетрудно еще раз получить условие принадлежности трех точек одной прямой: точки А(m; n), B(p; q) и C(u; v) лежат на одной прямой тогда и только тогда, когда (m – — p) (n – v) – (m – u) (n – q) = 0. Конечно, ничего нового мы не узнали, просто еще раз убедились в полезности псевдоскалярного произведения. Но основное внимание применению векторной алгебры к решению задач вычислительной геометрии будет уделено в следующем параграфе.

Вопросы и задания

1. Докажите равенство

2. а) Пусть на оси абсцисс выбран направленный отрезок единичной длины, совпадающий по направлению с осью. Обозначим соответствующий этому отрезку вектор через . Аналогичный вектор для оси ординат обозначим через . Докажите, что если вектор имеет координаты (х; у), то .

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

Таблица 1

Таблица 2

3. а) Используя свойства скалярного произведения и задание 2, докажите координатную формулу для скалярного произведения.

б) Используя свойства псевдоскалярного произведения и задание 2, докажите координатную формулу для псевдоскалярного произведения.

4. Пусть пара (х; у) — координаты вектора . Рассмотрим вектор ?, координаты которого (–у; х).

а) Проверьте, что векторы и ? перпендикулярны и имеют одинаковую длину.

б) Пункт а) показывает, что вектор ? получается из вектора поворотом на 90°. Выясните, по или против часовой стрелки осуществляется этот поворот.

в) Докажите, что . (Совет: используйте формулы приведения.)

г) Используя координатную формулу для скалярного произведения и пункт в), выведите координатную формулу для псевдоскалярного произведения.

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

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

а) (1,5; 2,5; 3,5) и (10,5; 7,5; 4,5);

б) (1 493 035,2; 4 356 618; 5 702 887) и (2 692 538; 3 524 578; 922 746,5).

§ 12. Задачи и их решения

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

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

Рис. 4

Задача 1. Найти расстояние от точки С до прямой АВ. Точки А, В и С заданы координатами.

Решение. Пусть А(m; n), B(p; q) и C(u; v). Рассмотрим векторы и заданные соответственно направленными отрезками АВ ¹² и АС. Тогда расстояние d от точки С до прямой АВ — это высота параллелограмма, построенного на отрезках АВ и АС (см. рис. 4).

Следовательно, .

Задача 2. Найти основание перпендикуляра, опущенного из точки С на прямую АВ. Точки А, В и С заданы координатами.

Решение. Пусть А(m; n), B(p; q) и C(u; v). Рассмотрим векторы и , заданные соответственно направленными отрезками АВ и АС. Пусть D — основание перпендикуляра, опущенного из точки С на АВ. Рассмотрим вектор , заданный направленным отрезком AD. С одной стороны, из теоремы 1 . С другой стороны, вектор , определенный направленным отрезком CD, перпендикулярен вектору. Тем самым, . Следовательно,
, откуда . Тем самым, . Вычисление координат вектора теперь не составляет труда. Пусть они равны (s; t). Тогда координаты точки D — это пара (m + s; n + t).

Задача 3. Найти площадь треугольника с вершинами в точках А, В и С. Точки А, В и С заданы координатами.

Решение. Пусть А(m; n), B(p; q) и C(u; v). Рассмотрим векторы и , заданные соответственно направленными отрезками АВ и АС. Площадь АВС — это половина площади параллелограмма, построенного на отрезках АВ и АС. Следовательно, искомая площадь равна .

Задача 4. Найти угол между прямыми АВ и СD. Точки А, В, С и D заданы координатами.

Решение. Пусть А(m; n), B(p; q), C(u; v) и D(s; t). Рассмотрим векторы  и , заданные соответственно направленными отрезками АВ и СD. Обозначим через угол между прямыми АВ и СD. Тогда

Угол теперь найти легко.

Обсудим использование данного решения. Функция Arctg является встроенной практически в любой язык программирования, чего никак нельзя сказать о функциях Arccos и Arcsin. Тем не менее сразу вычислять вряд ли полезно. Лучше сначала вычислить и убедиться, что оно не равно 0. В противном случае прямые перпендикулярны, и ничего больше находить не требуется (тем более, что на 0 лучше не делить). Затем полезно вычислить . Если это произведение равно 0, то наши прямые либо параллельны, либо совпадают. И только если оба произведения отличны от нуля, можно и тангенс подсчитать.

Задача 5. Найти точку пересечения прямых АВ и СD или установить, что прямые параллельны или совпадают. Точки А, В, С и D заданы координатами.

Решение. Пусть А(m; n), B(p; q), C(u; v) и D(s; t). Рассмотрим векторы  и , заданные соответственно направленными отрезками АВ и СD. Если = 0, то прямые параллельны или совпадают. Чтобы выяснить, какой из этих случаев на самом деле имеет место, достаточно выяснить, лежит ли на прямой АВ точка С — как это сделать, мы обсуждали выше. Пусть 0. Пусть K — точка пересечения данных прямых. Обозначим через вектор, заданный направленным отрезком АС. Рассмотрим АСK. Определение суммы векторов и теорема 1 показывают, что для подходящих выполняется равенство (см. рис. 5). Но тогда выполняются равенства и . Пользуясь свойствами псевдоскалярного произведения, получаем и .

Рис. 5

Следовательно, . Впрочем, для получения ответа достаточно знать . Действительно, пусть координаты точки K — это х и у. Тогда

Задача 6. Определить, лежат ли точки С и D по одну сторону от прямой АВ. Точки А, В, С и D заданы координатами.

Решение. Пусть А(m; n), B(p; q), C(u; v) и D(s; t). Рассмотрим векторы , заданные соответственно направленными отрезками АВ, АС и АD. Из определения псевдоскалярного произведения немедленно следует, что точки С и D лежат по одну сторону от прямой АВ тогда и только тогда, когда и одного знака. Иными словами, произведение ( ) ( ) > 0.

Задача 7. Определить, лежит ли точка С на луче АВ, где А — вершина луча. Точки А, В и С заданы координатами.

Решение. Пусть А(m; n), B(p; q) и C(u; v). Рассмотрим векторы и , заданные соответственно направленными отрезками АВ и АС. Если  0,
то точка С не лежит даже на прямой АВ. Если же  = 0, то для точки, лежащей на луче, косинус угла между векторами должен быть равен 1 (в противном случае он равен –1), так что достаточно проверить, что > 0.

Задача 8. Определить, лежит ли точка С на отрезке АВ. Точки А, В и С заданы координатами.

Решение. Пусть А(m; n), B(p; q) и C(u; v). Фактически задача сводится к предыдущей, поскольку точка лежит на данном отрезке в том и только том случае, когда она одновременно лежит на лучах АВ и ВА. Запишите возникающие необходимые и достаточные условия самостоятельно.

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

Вопросы и задания

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

Формат ввода. В первой строке вводится n. В каждой из последующих n строк вводится по два числа, являющихся координатами точки с соответствующим номером ¹³.

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

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

Формат ввода такой же, как в задании 1. Вывести номера точек, являющихся вершинами искомого треугольника. Если треугольников оказалось несколько, вывести все такие тройки.

3. Даны n точек на плоскости. Кроме них, заданы две точки А и В. Составьте программу, которая позволит выбрать из n заданных точек ту, которая наиболее удалена от прямой АВ.

Формат ввода. В первой строке два числа, являющиеся координатами точки А, во второй — два числа, являющиеся координатами точки В, в третьей строке вводится n. В каждой из последующих n строк вводится по два числа, являющихся координатами точки с соответствующим номером.

Вывести номер искомой точки. Если точек оказалось несколько, вывести номера всех таких точек.

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

Формат ввода. В первой строке вводится n. В каждой из последующих n строк вводится по два числа, являющихся координатами точки с соответствующим номером.

Вывести номера точек, являющихся вершинами трапеции. Если четверок оказалось несколько, вывести все такие четверки.

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

Формат ввода такой же, как в задании 4. Вывести одно число.

6. Даны n точек на плоскости. Составьте программу, которая указывает, каково наименьшее число прямых, на которых лежат все заданные точки.

Формат ввода такой же, как в задании 4. Вывести одно число ¹⁴.

---

¹ Это принципиально важное положение является одним из краеугольных камней информатики. Академик А.П. Ершов, которому школьная информатика обязана своим существованием, писал (см. О предмете информатики // Вестник АН СССР, 1984, № 2): “Как самостоятельная наука информатика вступает в права тогда, когда в рамках соответствующей частной науки строится информационная модель того или иного фрагмента действительности... В информатике рассматриваются методологические принципы построения таких моделей и манипулирования с ними”. Понимание, что решение человеком любой жизненной задачи опирается на построение соответствующей модели и что каждая модель имеет ограниченную область адекватности, — вот то, что закладывает информатика в мировоззрение человека. И в отличие от философии делает это спокойно и конструктивно, без споров до хрипоты, познаваем наш мир или нет, можно ли войти в реку только один раз или вообще ни разу.

² Геометрические образы, впитанные нами со школьной скамьи, доминируют в нашем сознании всю жизнь. Они диктуют стандарты промышленных образцов. Мы строим прямоугольные дома и изготовляем цилиндрическую посуду, хотя в природе сочленение поверхностей под углом встречается разве лишь в результате природных катаклизмов — обвалов горной породы, оползней и т.п. А если мы и проектируем сопряжение линий (например, поворот трамвайных путей), то пользуемся для этого дугой окружности (см. рис. 1). Что же в этом случае происходит с пассажиром? Пока трамвай движется по прямолинейному участку, на пассажира в худшем случае (при торможении и разгоне) действует сила, направленная вдоль движения. Но вот трамвай стал поворачивать по окружности. Радиус кривизны из бесконечного мгновенно стал весьма конечным, и также мгновенно на пассажира стала действовать центробежная сила. Он получает мгновенный удар поперек движения. Но никому и в голову не придет принести школьные стереотипы в жертву комфорту пассажира.

Рис. 1

³ Этот простой пример ясно показывает, почему Лого-черепашку нельзя “приспособить” для изучения школьного курса геометрии.

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

⁵ Он образовал этот термин от латинского слова vector, означающего “несущий”.

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

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

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

⁹ Термин “псевдоскалярное” употреблен в “Математической энциклопедии”, т. 1, ст. 635 (М.: Советская энциклопедия, 1977).
В книге Е.В. Андреевой и др. “Математические основы информатики” (М.: Бином, 2005) отдано предпочтение термину “косое произведение”. Г.Грассман в работе 1844 г. рассматривал его под названием “внешнее произведение”, правда, обычное скалярное произведение он называл “внутренним”. Используемое нами обозначение этой операции восходит к так называемым “грассмановым алгебрам”, хотя сам Г.Грассман таким обозначением не пользовался.

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

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

¹² Здесь и в дальнейшем, обозначая направленный отрезок двумя буквами, мы всегда на первом месте будем писать обозначение его начала, а на втором месте — обозначение конца.

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

¹⁴ При обсуждении с учащимися задачи 6 полезно у них поинтересоваться, нельзя ли для ее решения использовать решение задачи 5, реализуя так называемый “жадный” алгоритм: сначала выберем прямую, на которой лежит наибольшее число точек, затем эти точки уберем и для оставшихся снова выберем прямую с максимальным числом расположившихся на ней точек и т.д. (Впрочем, совсем не исключено, что такое “решение” будет предложено кем-либо из учащихся.) Нетрудно построить пример (из 12 точек), демонстрирующий неправильность этого подхода к решению задачи.