Материал: 12562633_1109924Ispol_zo

2. ТЕСТИРОВАНИЕ ПРОГРАММ

Основное внимание в следующих работах необходимо уделить тестированию программ и разработке квалифицированных тестов.

Лабораторная работа 2

Пересекаются ли отрезки?

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

Требования

Четыре часа на выполнение, язык реализации – С или С++.

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

Первый этап – алгоритмизация задачи

Задача, естественно, планиметрическая, оба отрезка принадлежат одной плоскости. Пусть первый отрезок соединяет точку P1 = (x1, y1) с точкой P2 = (x2, y2), а второй отрезок – точку P3 = (x3, y3) с точкой

P4 = (x4, y4).

Будем также пока считать, что никакие три точки из них не лежат на одной прямой (для упрощения).

x1 y1 1

Знак определителя det(P1, P2, P3) x2 y2 1 устанавливает, x3 y3 1

какая полуплоскость линии L1, образованной продолжением отрезка P1-P2, содержит точку P3. Отрезок P3-P4 будет пересекать L1 в том случае, если точки P3 и P4 находятся по разные стороны от L1, при этом

det(P1, P2, P3) det(P1, P2, P4) 0 .

Для того чтобы точка пересечения принадлежала отрезку P1-P2, также необходимо, чтобы

det(P3, P4, P1) det(P3, P4, P2) 0 .

6

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

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

Вычислим определители третьего порядка:

(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) = det(P1,P2,P3) (x2-x1)*(y4-y1)-(x4-x1)*(y2-y1) = det(P1,P2,P4)

(x3-x1)*(y4-y1)-(x4-x1)*(y3-y1) = det(P3,P4,P1)

det(P1,P2,P3)-det(P1,P2,P4)+det(P3,P4,P1) = det(P3,P4,P2)

Теперь сравним знаки определителей – и задача решена! (Так ли?)

Второй этап – написание программы

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

Точка, Отрезок, Определитель,

Функция проверки отрезков на пересечение. Должна включать также и вырожденные случаи, такие, например, как отрезки нулевой длины, принадлежность точки P3 отрезку P1-P2 и т.д.

Напишем часть программы, выполняющую ввод информации.

Третий этап – реализация

Для реализации используйте язык С или С++. Существенно важно, чтобы в реализации не использовались платформенно-зависимые функции и заголовочные файлы, например, stdio.h, stdafx.h.

Это необходимо для осуществления пятого этапа (смотри далее лаб. работу 5) с возможностью переноса приложения в другие операционные системы.

Четвертый этап – тестирование

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

Пятый этап– графический пользовательский интерфейс

Выполнение этого этапа представляет отдельную лабораторную работу, которую предстоит сделать после ознакомления с методами создания графического пользовательского интерфейса (GUI).

7

Лабораторная работа 3

Находится ли точка внутри многоугольника?

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

Работа выполняется в несколько этапов.

Требования

Четыре часа на выполнение, язык реализации – С или С++.

Особое внимание необходимо обратить на реализацию функции, которая должна обрабатывать все возможные особые случаи.

Первый этап – алгоритмизация задачи

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

Второй этап – написание программы

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

Точка, Отрезок,

Функция проверки отрезков на пересечение, из предыдущей работы. Вот, где пригодится хорошо работающая функция!

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

Третий этап – реализация

Для реализации используйте язык С или С++. Существенно важно, чтобы в реализации не использовались платформенно-зависимые функции и заголовочные файлы, например, stdio.h, stdafx.h.

Это необходимо для осуществления пятого этапа (смотри далее лаб. работу 6) с возможностью переноса приложения в другие операционные системы.

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

8

Четвертый этап – тестирование

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

Пятый этап – графический пользовательский интерфейс

Выполнение этого этапа представляет отдельную лабораторную работу, выполнение которой предстоит выполнить после ознакомления с методами создания GUI (лаб. работа 6).

9

3. СОЗДАНИЕ ГРАФИЧЕСКОГО ПОЛЬЗОВАТЕЛЬСКОГО ИНТЕРФЕЙСА

Основы FLTK

Этот раздел посвящен основам компилирования и использования FLTK. Почему FLTK? Прежде всего из-за небольших размеров, доступности исходного кода, простоты и понятности классов используемых методов. Нельзя сбрасывать со счетов и мобильность. Вы можете разрабатывать приложение под Linux, а затем перенести его в Windows и наоборот.

Написание простой программы с использованием FLTK

Все программы должны подключать заголовочный файл <FL/Fl.H>. Кроме того, программы обязаны подключать заголовочные файлы для каждого используемого класса FLTK. На листинге 1 показана простая программа "Hello, World!" для отображения окна при помощи FLTK.

Листинг 1 – "hello.cxx"

#include <FL/Fl.H>

#include <FL/Fl_Window.H>

#include <FL/Fl_Box.H>

int main(int argc, char **argv) {

Fl_Window *window = new Fl_Window(300,180); Fl_Box *box = new

Fl_Box(20,40,260,100,"Hello, World!"); box->box(FL_UP_BOX); box->labelsize(36); box->labelfont(FL_BOLD+FL_ITALIC); box->labeltype(FL_SHADOW_LABEL); window->end();

window->show(argc, argv); return Fl::run();

}

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

Fl_Window *window = new Fl_Window(300,180);

и прямоугольник со строкой "Hello, World!" в нем:

Fl_Box *box = new

Fl_Box(20,40,260,100,"Hello, World!");

10