Defining a polygon with the specified property

Question

I am creating a graphic project in which I must at some point find that if there is a point in the polygon x, so if I attach this point to all the vertices of this polygon, then all the segments connect the vertices, and this point xlies completely inside the polygon.

I wonder if there is any known algorithm, or if any of you can describe an algorithm for this.

I am looking for a linear time algorithm.

Answer 1

You ask how to calculate the core of a star-shaped polygon. This problem was solved in 1979 by Lee and Prepata in an article entitled Optimal Polygon Core Search Algorithm . From their theses:

The core of a K(P)simple polygon Pwith vertices nis the locus of the point, the inner k P, from which all vertices are visible PEquivalently, K(P)is the intersection of the corresponding half-planes defined by the edges of the polygon. Although it is known that it ntakes time to find half-planes to intersect O(n log n), we show that one can use the half-plane ordering of the corresponding sequence of polygon edges to obtain a kernel search algorithm that works in time O(n)and, therefore, is optimal.