A New Fully Projective O(lg N) Line Convex Polygon Intersection Algorithm

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F25%3A43976558" target="_blank" >RIV/49777513:23520/25:43976558 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/article/10.1007/s00371-024-03413-3" target="_blank" >https://link.springer.com/article/10.1007/s00371-024-03413-3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00371-024-03413-3" target="_blank" >10.1007/s00371-024-03413-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A New Fully Projective O(lg N) Line Convex Polygon Intersection Algorithm

Popis výsledku v původním jazyce

Intersecting algorithms, especially line clipping in E2 and E3 in computer graphics, have been studied for a long time. Many different algorithms have been developed. The simplest case is a line clipping by a convex polygon in E2 with O(N) computational complexity and with known polygon edges orientation. This contribution presents a new algorithm for a line clipping by a convex polygon in E2 with O(lg N) complexity, which is based on the point-in-half plane test. The proposed algorithm does not require prior knowledge of the polygon edge orientation. The vertices of the convex polygon and the clipped line can be given in projective space using homogeneous coordinates. The algorithm uses vector–vector operations for efficient implementation with SSE or AVX vector–vector instructions or on GPUs.

Název v anglickém jazyce

A New Fully Projective O(lg N) Line Convex Polygon Intersection Algorithm

Popis výsledku anglicky

Intersecting algorithms, especially line clipping in E2 and E3 in computer graphics, have been studied for a long time. Many different algorithms have been developed. The simplest case is a line clipping by a convex polygon in E2 with O(N) computational complexity and with known polygon edges orientation. This contribution presents a new algorithm for a line clipping by a convex polygon in E2 with O(lg N) complexity, which is based on the point-in-half plane test. The proposed algorithm does not require prior knowledge of the polygon edge orientation. The vertices of the convex polygon and the clipped line can be given in projective space using homogeneous coordinates. The algorithm uses vector–vector operations for efficient implementation with SSE or AVX vector–vector instructions or on GPUs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

VISUAL COMPUTER

ISSN

0178-2789

e-ISSN

1432-2315

Svazek periodika

41

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

9

Strana od-do

1241-1249

Kód UT WoS článku

001242202400002

EID výsledku v databázi Scopus

—