stjärnform

Stjärnform är en geometrisk egenskap som beskriver hur en region i planet kan observeras från en punkt inom regionen. En mängd S är stjärnformig om det finns en punkt p i S sådan att varje x i S kan kopplas till p med en rät linje som helt ligger inom S. Denna punkt kallas ofta synpunkt och mängden av alla synpunkter bildar kärnan (kerneln) av S.

I fallet med polygoner uppstår kärnan genom att ta hänsyn till varje kant: för varje kant definieras en inåtvänd halvplan; kärnan är deras gemensamma skärning. Kärnan är alltid konvex. Om kärnan är icke-tom är polygonet stjärnformigt; om kärnan är tom är det inte stjärnformigt. Konvexa polygoner har alltid icke-tom kärna och är därmed stjärnformiga.

Beräkning av kärnan sker vanligtvis med halvplansklippning, där polygonet klipps med varje kantens inåtvända halvplan. Med vanliga klippningsalgoritmer kan kärnan beräknas effektivt, oftast i tidskomplexitet O(n) för enkla polygoner.

Användningar av stjärnform förekommer inom datorgrafik och robotik, där kärnan används för att analysera synlighet och observerbarhet inom en region samt för planering och formanalys i miljöer där det är viktigt att kunna observera hela formen från en viss plats. Termen används också inom geometri och datorstödd konstruktion som grundläggande begrepp för synlighet och områdesegenskaper.