10 Полигони (многоъгълници) - Studizba

Многоъгълници (многоъгълници). Тестове за ориентация на точка спрямо многоъгълник

Концепцията за многоъгълник. Геометричен модел на плосък многоъгълник

Контурът на многоъгълник се определя от върхове, които са свързани с линейни сегменти. Във векторна форма многоъгълникът се дефинира чрез изброяване на неговите върхове: P = < p 1, p 2, …, pn, p 1 >.

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

Свойства на равнинни многоъгълници

Пресечната точка на права линия с многоъгълник. Една линия пресича многоъгълник, ако има поне една двойка върхове, разположени от противоположните му страни (това свойство предполага сравнение за всички налични двойки върхове, а не само за съседните).

Многоъгълна издутина. Изпъкнал многоъгълник има всички ъгли Ð pi -1 pi pi +1 с еднакъв знак. С други думи, при преминаване на изпъкнал многоъгълник по затворен контур в произволна посока, всеки връх pi +1 е разположен спрямо ръба pi -1 pi по един и същи начин за всички стойности на i: отляво за положителна посока на преминаване и отдясно за отрицателна.

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

Тестове за ориентация на точка спрямо многоъгълник

1. Конвексен тест. Определя позицията на точка спрямо многоъгълника (фиг. 10): външна точка, вътрешна точка, гранична точка (външното подпространство на многоъгълника се счита за положително, вътрешното– отрицателен, границата съответства на нула).

2. Измерителен тест. Определя гарантираната непринадлежност на точка q към произволен многоъгълник P чрез сравняване на координатите му с размерите на многоъгълника - минималната и максималната координата на върховете му. Размерният тест не решава напълно проблема с ориентацията, но поради своята простота той се използва в много алгоритми за бързо откриване на очевидно непресичащи се геометрични обекти (фиг. 11).

3. Ъглов тест. Въз основа на изчисляването и анализа на алгебричната сума на ъглите d i = Р ( Vi , Vi +1 ) между съседни вектори Vi = pi - q, свързващи точката q с върховете pi , докато обикалят произволен многоъгълник P по затворен контур в произволна посока.

Точката е вътрешна, ако сумата от ъглите е ∑ d i =2 π (фиг. 12). Една точка е външна, ако сумата от ъглите ∑ d i =0 (фиг. 13).

Точката е гранична точка (принадлежи към границата на многоъгълника):

● ако при изчисляване на векторите се получи нулев вектор ç Vi ç =0, тогава тестваната точка съвпада с върха pi ;

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

Има два вида ъглови тестове - радиан и октант.

Тест с лъч на ориентацията на точка q спрямо многоъгълник p се състои в заснемане от тази точка в произволна посока V a лъч p ( t )= q + Vt ( " t> 0) и преброяване на броя на пресичанията му с ръбове p. Анализът на двойки дава следните критерии за ориентацията на точка спрямо многоъгълник: точката е вътрешна, ако броят на двойките е нечетен ( ti> 0, 0 t i ; точка е външна, ако броят на двойките е четен, включително нула; точката лежи на границата p, ако има поне една двойка,за които ti =0 , 0 £ t i £ 1 .

Характеристики на теста на лъча (фиг. 14):

● несигурността на броя на пресичанията, когато лъчът преминава точно през върха pi при t i =1 или върха pi +1 при t i =0. Необходимо е тестът да се повтори отново с различна посока на лъча V;

● необходимо е да се изчислят параметрите на пресичането на лъча с всички ръбове на многоъгълника.

Изследват се параметрите на пресичането на лъча с отсечки pi +( pi +1 – pi ) t , " 0 £ t £ 1.

---