event_handlers
The main task of the function skeletonize is to process the events to construct the wavefront during the shrinking process. The order of the events to be processed is given by a priority queue, an instance of _EventQueue. The distance, stored in each event, is used as a priority value; the smaller the distance, the higher the priority of the entry in the queue. Besides the usual methods of a priority queue, _EventQueue has a method getAllEqualDistance, that returns all events at the top of the queue, that have almost equal distance values.
The event queue is filled with the events from the list of initial eventsinitialEvents.
As long as the event queue is not empty and as long as there are active vertices in SLAV, the function getAllEqualDistance of the event queue returns a list of one or more events. After a validity test, each of these events is processed by a corresponding event handler of SLAV. There are three such handlers, one for the edge event, one for the split event, and one for the dormer event. Each of these handlers returns as part of the skeleton a list of one or more Subtrees with the vertex as the source, and a list of none to several next events. The list of Subtrees is appended to the ouput list containing the final skeleton, while the new events are added to the event queue.
At an edge event, an edge shrinks to zero, making its neighboring edges adjacent. This is the task of the edge event handler in SLAV, shown in the figure below.
The content of _EdgeEvent is its intersection_point, the adjacent vertices vertex_a and vertex_b and the distance from the adjacent edge and a reference to its instance of the list of active vertices lav. First, this double-linked list is redirected. This is done by the method unify of _LAV. It creates a new vertex at the event position intersection_point and redirects the links in the list so that the adjacency to the old edges is resolved. vertex_aand vertex_b are invalidated. A call to the method next_event of LAV for this newly created vertex may create a new next event.
The handler then creates a Subtree with the event position intersection_point as source, the positions of vertex_a and vertex_b as sinks and the event distance as height.
The next event, if any, is packed into a list and returned together with the Subtree as result.
The split event holds the vertex V as vertex (and its position as vertex.point), the intersection_point (the famous B), a reference opposite_edge to the opposite edge and the distance from B to that egde. An example of this setup is shown in the left image below.
The process of the split event handler is demontrated in the right image above. The first step is to find a pair of vertices (X,Y) in all LAV's, that correspond to the endpoints of the opposite edge. If such a pair is found, the test for the point B is repeated, as described for the method next_event of _LAV. The point B must lie in the area bounded by the opposite edge and the bisectors leading from the vertices X and Y at both ends of this edge. This test is not drawn here. If no such pair is found, the split event failed and an equivalent edge event is expected to follow. The handler will return an empty result.
Now, create two new vertices V1 and V2 with the same coordinates as the intersection point B (these are plotted slightly separated in the drawing for visualization. Vertex V1 is connected between the predecessor M of V and the vertex X. V2 is connected between the successor N of V and the vertex Y, which is a starting point of the opposite line segment (see all red connections).
The lav of the split event is then removed from SLAV and new lavs (new_lavs) are created. It is possible, that the opposite edge belongs to a different lav than vertex V of the split event. In this case two lavs are merged, so the new_lavs becomes a list containing only the lav connected to V1. Otherwise, new_lavs consist of one lav connected to V1 and the other lav connected to V2. Finally, any lav that is longer than 2 vertices is appended to SLAV, otherwise the position of the vertex, that is not the first in the lav is added to the sinks list and the vertex is invalidated. For all Vi that survived this procedure, their next_event function is called. If it returns an event, it is appended to the event list. The vertex of the split event is invalidated, a Subtree is constructed with its position and distance and the sinks. This tree is returned as a result, along with the event list.
The four vertices of the dormer must be removed and the list of active vertices (lav) to be updated accordingly. The picture below illustrates this process, using the names from the code for better understanding.
These vertices are invalidated at the end of the handler. Before that, two Subtrees (green and blue in the image below) are constructed from the edge and split events. The intersection point p of the bisectors of the split events v_prev and v_next is the source of the blue Subtree, while the positions of these events are its sinks.
The green Subtree is almost already given by the edge event, which is stored as an attribute in the dormer event. Its source is the intersection point of this event, its sinks are its vertices vertex_a and vertex_b and the newly computed point p.
Both Subtrees are returned as result, but the dormer event handler does not return a next event.