OVERVIEW
The kernel of polygon P is the set of points in P that can see every vertex.
This program allows you to plot a simple polygon and calculate it's kernel.


ALGORITHM AND RUNNING TIME
The algorithm calculates the kernel of a simple polygon P as the intersection of its reflex edge visibilities RE+(P), where RE+(P) is the reflex edge visibility inside the polygon. This kernel calculation is bound by the number of reflex edges in P. As a result, the kernel is calculable in O(n).


WHAT IS DISPLAYED
Black - The original polygon
Blue - The point or reflex edge visibility
Green - The current vertex or edge that is being calculated
Red - The kernel


KNOWN ISSUES TO BE RESOLVED:
1.) The points of the polygon must be entered in counter-clockwise order.
2.) Rounding and precision thresholds are are used in many calculations which causes a small degree of error.


THEORY:
Lemma 1: If point q sees every vertex of a polygon P then q sees all of P. (This is for simple polygons, it is not true in polygons with holes)


Proof: If point q can see both end points of an edge, then q can see the whole edge. If point q sees every vertex of P then q sees all points on the boundary of P. Using the fact that q can completely see all edges of P, take any point p in P. Take the ray qp→ and note it's intersections with the boundary of P, say r. There will be exactly 1 such intersection, as otherwise q wouldn't see the farther points. q sees r, so the line segment qr is in P. Since the segment qp is a subset of qr it must also lie in P. Therefore, q sees p.


Lemma 2: The kernel of a polygon P is the intersection of N half-planes.


Proof: From Question 1, a point q sees all of P if and only if it sees every vertex of P. To find the kernel, we want to find all points that see all vertices of P. To see each vertex, the point q must see each edge completely. To see each edge completely, q must lie on the inside of the half-plane defined by the edge. Therefore, a point q sees all of P if and only if it is contained in the half-plane defined by each of the N edges. That is, a point q is in the kernel if and only if it is in the intersection of N half-planes.