загрузка...
загрузка...
На головну

Відсікання неопуклого многоугольником без самоперетинів


Мал. 5. Отсечение неопуклого многоугольником.

На Рис. 5 результатом відсікання відрізка AB є відрізки C1D1 и C2D2

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


Створимо список точок перетину Ax c многоугольником:

Для кожного ребра можливі 4 випадки:

 а) обидві його вершини лежать вище або нижче Ax (наприклад, на Рис. 5 3-4): нічого не заносимо в наш список  
 б) його вершини лежать по різні боки від Ax (наприклад, на Рис. 5 1-2): заносимо в список точку перетину  
 в) ребро лежить на Ax нічого не заносимо в наш список
 г) вершина лежить на Ax г 1) якщо інші вершини суміжних ребер лежать по одну сторону від Ax: нічого не заносимо в список
 г 2) якщо інші вершини суміжних ребер лежать по різні боки від Ax: заносимо цю вершину в список,

Далі, список точок перетину повинен бути відсортований по зростанню (їх кількість повинна бути парним, т. К. Для кожного "входу" в багатокутник повинен існувати і "вихід"):

x1  і т. д., тоді шуканий відрізок - це:

[0, l] C ([x1, x2] E [x3, x4] E [x5, x6] ...)(Т. К. Непарна точка - завжди точка "входу", а парна - точка "виходу")

2.3. Комбінований алгоритм Кузьміна. [Kuzmin, 1995]

Алгоритм Кузьміна є модифікацією алгоритму Брезенхема, що дозволяє відразу вирішувати завдання і відсікання по прямокутнику, і малювання відрізка. Нижче наводяться основні ідеї алгоритму. Точний опис можна знайти в [Kuzmin, 1995]


Мал. 6. Визначення точки входу.

Насамперед перевіримо, чи потрібно малювати що-небудь взагалі (наприклад, за допомогою ідеї алгоритму Сазерленда-Кохена).

Якщо потрібно малювати, то перейдемо до канонічної системі координат Axy, Тоді наш відтинає прямокутник можна задати координатами своїх лівого нижнього C (x1, y1) і правого верхнього D (x2, y2)кутів. Тоді в залежності від знака векторного твори [AB 'AC] (т. е.a * y1-b * x1)відрізок ABперетинає:

1) горизонтальну кордон (випадок на Рис. 6)

[AB 'AC]> 0

2) вертикальну кордон

[AB 'AC] <0


Знайдемо для двох випадків початкові значення x, y и e0 , Далі будемо діяти за алгоритмом Брезенхема. Заради целочисленности алгоритму всі змінні, пов'язані з e, Як і раніше домножимо на 2a.

1) Горизонтальний випадок (Рис. 7).

Мал. 7. Горизонтальний випадок.  В цьому випадку y = y1; а ось x треба знайти. Для цього будемо слідувати алгоритму Брезенхема, як якщо б ми малювали без відсікання, тоді перша точка з координатою y1 буде намальована тоді, коли для якогось x = xв буде виконано наступне: xR I (xв , xв+1], Де R - точка перетину нашого відрізка з прямою y = y1- 0.5 xв=* (Y1 -) + 1 = (a * (2 * y1-1)) / (2 * b) +1 (Поділ целочисленное (т. Е. Повертає цілу частину приватного) !!) De = (yP0- yP1) * 2a = (y1 -* xв) * 2a = = 2 * (a * y1- B * xв) e0= 2b - a - De = 2b - a- 2 * a * y1+ 2 * b * xв= = 2b * (xв+1) - A * (2 * y1+1)

2) Вертикальний випадок (Рис. 8).

Мал. 8. Вертикальний випадок.  У цьому випадку x = x1; а ось yнадо знайти виходячи з значення e0нехай yв= x1* (B / a) = (x1* B) / a (Поділ целочисленное (т. Е. Повертає цілу частину приватного) !!) e0= (* x1-yв-) * 2a = 2b * x1-a * (2 * yв+1) Тоді можливі 2 варіанти: 1) e0 <0 тоді перша точка - P1 (X = x1 , Y = yв) І e0= e0 + 2 * b 2) e0 ?0 тоді перша точка - P2 (X = x1 , Y = yв+1) І e0= e0 + 2 * b-2 * a

Умовою виходу з алгоритму є:

(Т. Е. Досягнення краю прямокутника або кінця відрізка)

Відсікання опуклим багатокутником. «-- попередня | наступна --» I. Зображення кіл.
загрузка...
© om.net.ua