Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона



Скачать 32.87 Kb.
Дата26.07.2014
Размер32.87 Kb.
ТипТесты

Лекция

Многоугольники (полигоны). Тесты ориентации точки относительно полигона

Понятие полигона. Геометрическая модель плоского полигона


Контур полигона определяется вершинами, которые соединены отрезками прямых. В векторной форме полигон задается перечислением своих вершин: P={p1, p2, …, pn, p1}.

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


Свойства плоских многоугольников


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

Выпуклость полигона. У выпуклого полигона все углы
pi-1 pi pi+1 одного знака. Другими словами, при обходе выпуклого полигона по замкнутому контуру в произвольном направлении каждая вершина pi+1 расположена относительно ребра pi-1 pi одинаково для всех значений i: слева при положительном направлении обхода и справа при отрицательном.

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

Тесты ориентации точки относительно полигона


1. Выпуклый тест. Определяет положение точки относительно полигона (рис. 10): внешняя точка, внутренняя точка, граничная точка (внешнее подпространство полигона считается положительным, внутреннее – отрицательным, граница соответствует нулю).



2. Габаритный тест. Определяет гарантированную непринадлежность точки q произвольному полигону P путем сравнения ее координат с габаритами полигона – минимальными и максимальными координатами его вершин. Полностью задачу ориентации габаритный тест не решает, тем не менее, благодаря своей простоте, применяется во многих алгоритмах для быстрого обнаружения заведомо непересекающихся геометрических объектов (рис. 11).




3. Угловой тест.

Основан на вычислении и анализе алгебраической суммы углов i=(Vi, Vi+1) между смежными векторами Vi=pi-q, соединяющими точку q с вершинами pi, при обходе произвольного полигона P по замкнутому контуру в произвольном направлении.

Т
очка является внутренней, если сумма углов ∑i=2 π (рис. 12). Точка является внешней, если сумма углов ∑i=0 (рис. 13).

Точка является граничной (принадлежит границе полигона):

● если при расчете векторов получен нулевой вектор Vi=0, то тестируемая точка совпадает с вершиной pi;

● если при расчете углов i получен развернутый угол с модулем | i | = π, то тестируемая точка лежит на ребре pi pi+1.

Существуют две разновидности углового теста – радианный и октантный.




Лучевой тест ориентации точки q относительно полигона p заключается в выпускании из этой точки в произвольном направлении V луча p(t)=q+Vt ( t > 0) и подсчете числа его пересечений с ребрами p. Анализ пар дает следующие критерии ориентации точки относительно полигона: точка является внутренней, если число пар нечетно (ti>0, 0<i<1); точка является внешней, если число пар четно, в том числе равно нулю; точка лежит на границе p, если найдется хотя бы одна пара, для которой ti=0, 0i1.

Особенности лучевого теста (рис. 14):


 неопределенность числа пересечений при прохождении луча точно через вершину pi при i=1 или вершину pi+1 при i=0. Необходимо повторить тест заново с другим направлением луча V;

● требуется расчет параметров пересечения луча со всеми ребрами полигона.



Исследуются параметры пересечения луча с отрезками pi+(pi+1pi), 01.

Похожие:

Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconТесты для учеников 12 2 Тесты для студентов по теме «Правильные многоугольники» 14
Анализ содержания учебных пособий и методические особенности преподавания темы «Правильные многоугольники» 4
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconМногоугольники Выпуклые и невыпуклые многоугольники
Аn называется фигура, состоящая из отрезков А1А2, А2А3, Аn–1An, которые называются её звеньями. Ломаная называется замкнутой, если...
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconЛекция 3 теорема об изменении кинетического момента
Выберем произвольный центр о (Рис. 1). Кинетическим моментом точки mj относительно центра о называется вектор момента ее количества...
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона icon«Конструирование и исследование многоугольников (работа в тетради для исследований)»
Исследование №2 «Многоугольники». Конструируем многоугольники из тико-деталей, считаем количество углов и сторон, называем многоугольники...
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconПравила сложения сил. Теорема о трех пересекающихся силах. Вычисление момент силы относительно точки. Условия равенства нулю момента силы относительно точки
Определение закона движения, траектории, переход от закона движения к уравнению траектории
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconТесты по геометрии для 9-го класса по теме «Многоугольники»
А1А2А3 … Аn называется фигура, которая состоит из точек А1, А2, А3, …, Аn и соединяющих их отрезков А1А2, А2А3,… Аn-1Аn
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconРезультаты исследования пробы фильтрата полигона токсичных отходов «Красный Бор»
Проба была отобрана 26 апреля 2010 г из дренажной канавы вокруг полигона, впадающей в р. Большую Ижорку (приток р. Ижоры)
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconМногоугольники Симметрия
По просьбам трудящихся не только многоугольники, а ещё и листья, снежинки, бабочки…
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconТест «Осевая симметрия»
Две точки симметричны относительно некоторой прямой, если отрезок, соединяющий эти точки, перпендикулярен данной прямой
Лекция Многоугольники (полигоны). Тесты ориентации точки относительно полигона iconЛаборатория профессиональной ориентации и социально-психологического сопровождения
Артюхова И. С. Воспитательная работа с подростками: занятия, игры, тесты. – М.: Первое сентября, 2003
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org