Star-shaped polygon
In
Formally, a polygon P is star-shaped if there exists a point z such that for each point p of P the segment lies entirely within P.[1] The set of all points z with this property (that is, the set of points from which all of P is visible) is called the kernel of P.
If a star-shaped polygon is convex, the link distance between any two of its points (the minimum number of sequential line segments sufficient to connect those points) is 1, and so the polygon's link diameter (the maximum link distance over all pairs of points) is 1. If a star-shaped polygon is not convex, the link distance between a point in the kernel and any other point in the polygon is 1, while the link distance between any two points that are in the polygon but outside the kernel is either 1 or 2; in this case the maximum link distance is 2.
Examples
Convex polygons are star shaped, and a convex polygon coincides with its own kernel.
Regular star polygons are star-shaped, with their center always in the kernel.
Antiparallelograms and self-intersecting Lemoine hexagons are star-shaped, with the kernel consisting of a single point.
Visibility polygons are star-shaped as every point within them must be visible to the center by definition.
Algorithms
Testing whether a polygon is star-shaped, and finding a single point in the kernel, may be solved in
Each edge of a polygon defines an interior
See also
References
- ^ ISBN 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988.
- S2CID 6156190, archived from the originalon September 24, 2017