lav
After initialization, the attribute self.head of the class _LAV holds a circular double-linked list of active vertices (LAV) of one contour of the polygon to be processed (its perimeter or one of the holes). The nodes of this linked list are instances of the class _LAVertex, which uses its attributes self.prev and self.next as forward and backward links of the list. The list is circular, so LAV needs only one anchor, self.head. Its attribute self.lav of the nodes is a back pointer to the instance of _LAV.
The contents of LAV are the vertices of the currently active contour and are subject to change during the process, hence the name. A LAV can be initialized either by a list of edges (class Edge2) or by the linked list of another LAV, two class methods are provided for this. A method unify provides the possibility to cut out a part of the list between two vertices and glue these to one vertex.
Instances of _LAVertex form the nodes of the list of active vertices in a _LAV instance. In addition, it holds self.point (its position), and references to the previous and next edges (plus their unit vectors, which are called creator vectors). Finally, it provides properties, like the bisector between its edges (an instance of Ray2) and the boolean is_reflex. The latter is true, if the inner angle of the contour is greater than 180°.
The most important method of _LAVertex is next_event. This method analyzes the vertex and its edges and yields an edge event (_EdgeEvent), if the vertex is not reflex, or, possibly, a split event (_SplitEvent), if the vertex is reflex.
The method creates always one or two edge events, as shown in the image below. If the vertex is reflex, an additional test may produce a split event. The method finally returns the event with the shortest distance (defined below).
For each vertex Vi compute the intersections i_prev and i_next of its bisector bi (red dotted line) with the bisectors bi-1 and bi+1, starting at the adjacent vertices Vi-1 and Vi+1. Store each intersection point together with its distance to the corresponding edge line and its endpoints as an edge event (_EdgeEvent) and add it to the result list of next_event.
If the vertex V is reflex, sometimes an additional event can be created. The first step is to find a candidate vertex point B and a corresponding opposite edge, as shown below.
All line segments edge of the original polygon are traversed and tested if they can be an opposite line segment of the vertex V. The egde selfedge, adjacent to V, which is less parallel to edge is selected, to avoid parallel lines. The intersection (green circle) of this edge line (red dotted line) with the potential edge line e is calculated. The candidate B for the split event is then the intersection of the bisector at V and the bisector of this green intersection point, if it exists.
As shown above, a test, whether the candidate point B lies in the area bounded by the currently tested edge and by the bisectors leading from the vertices at both ends of this line segment (red gradient), decides whether B is a split event. If it passes this test, store the point B together with its distance to the opposite edge line and the vertex V as split event (_SplitEvent) and add it to the result list of next_event.
Finally, the method next_event returns the event from it result list, that has the smallest distance between the event position and the vertex position.