I need some hints on this one:

A polygon P is star-shaped if there exists a point p in the interior of P such that any other point (vertex) on the boundary is visible to p.

Given a polygon P, how can i determine if P is a star shaped polygon?

Time complexity should be o(n) on average.

Ive been sitting on this for a while now, Any help will be appericiated.

CodePudding user response：

very weird definition of star according to that circle and pie are also stars ...

First simple and O(n) possibility I can think of is to render visibility map:

1. compute BBOX of the shape

   

2. create 2D map of the BBOX and clear it with zero

   so map 2D array (texture) to the BBOX of some resolution xs*ys

3. for each convex vertex increment visibility map

   simply by rendering "infinite" triangle/quad onto the map

   

   You can use winding rule to chose if vertex is convex or concave by simply checking the sign of z coordinate of the adjacent edges cross product against the winding rule of your shape.

4. scan the 2D map for cells containing number of convex vertexes

   all the cells/pixels containing number of convex vertexes are your possible Z so if any found your shape is a "star".

This is O(n*xs*ys) where n is number of (convex) vertexes and xs*ys is resolution of the visibility map. Note if your resolution is too low due to inaccuracies you might produce false negatives/positives ... if (max) resolution of the map is constant then the complexity will turn to O(n).

The rendering can be done simply for example with OpenGL and STENCIL buffer which directly has operation to increment STENCIL pixel however that one will limit the n to 255 as STENCIL is only 8 bit these days (after changes in OpenGL)... However you can workaround this by seting the BBOX to 1 and clear the exterior of the triangle/quad instead of incrementing its interrior. then the pixels holding 1 are your Z this might be used with any rendering engine no need for STENCIL