dormers
The detection of dormers and the construction of their events (DormerEvent) is done in the function skeletonize, before the event loop. In the event loop, an event handler in SLAV finally processes the dormer events and creates the Subtrees of the skeleton corresponding to these events.
Typically, dormers have four vertices with a sequence of right - left - left - right turns (RLLR ) in counterclockwise order and by angles of nearly 90°, as shown below.
This leads to a special effect during wave propagation, which is illustrated below. The vertices of the dormer move along their bisectors to the inside of the polygon (on the left, dotted lines with arrows), until they meet somewhere in the middle. The green lines merge into a single line that forms one of the edges of the skeleton. The orange lines merge into a single line that moves then upwards.
The blue edges in the image on the right are the correct edges of the skeleton. However, this is not what Felkel and Obdržálek's algorithm did. It continued one of the edges (shown by the red dotted line) upwards. Weird edges left the dormer and interacted with other edges and events in unpredictable ways, as shown in the following image. Therefore, we had to introduce the dormer event to handle these cases correctly.
The function detectDormers is used to detect dormers. The angles between consecutive egdes are measured by the cross-product of their unit-vectors. A string sequence of characters is generated. If the cross-product cp > 0.99, we have a left turn and the character 'L' is inserted in sequence. If cp < -0.99, a right turn produces a 'R', otherwise a '0' is inserted. The sequence RLLR is detected by string pattern matching with the pattern r"(?=(RLLR))", using positive lookahead to find overlapping patterns.
The matching pattern in sequence may overlap at the ends, such as LRLL000LL00RL, because the contour is circular. Therefore, the pattern matching is done in a string of two concatenated sequences. Now, the pattern matches somewhere in the middle, but still starts in the first half: LRLL000LL00RLLRLL000LL00RL.
Not all dormers are allowed to be processed. The first filter excludes dormers that share vertices (left image) or form the complete polygon (right image).
In addition, the following restrictions apply:
- The base width (edge between the 'L') of the dormer is limited to 10 meters.
- The square lengths of the edge d1 into and d2 out of the dormer must be approximately equal. This is achieved by limiting the contrast to abs(d1-d2)/(d1+d2) < 0.35.
- The edges on both sides of the dormer (the orange lines in the dormer wave image above, which will be merged later) must have a minimum length, depending on the direction of the rotation at their far ends. If they turn to the left ('L'), they must be at least 1.5 times the length of the base width, otherwise 0.125 of this length is sufficient. This is necessary to avoid conflicts with other skeleton edges.
If all these conditions are met, a dormer sequence is accepted and stored by the indices k to k+3 of its vertices and the base width w of the dormer, as shown below. A polygon may contain multiple dormers stored in the list dormers.
In the function skeletonize, after the detection of the dormers by detectDormers, all edge- and split-events are created by the next_event function of _LAVertex as initialEvents. Normally, the vertices of a dormer create split events for the vertices Vk and Vk+3 and an edge event for the vertex Vk+1. In the function processDormers, this is tested, and if it is the case, the intersection of the bisectors of the vertices Vk and Vk+3 is constructed as position of the dormer event, and its distance is determined to as w/2. A list of the events of the vertices Vk, Vk+3 and Vk+1 is prepared. The position, its distance and the list of these events is stored as an instance of DormerEvent in a list dormerEvents.
When it was possible to construct the dormer event, the four events from the vertices Vk to Vk+3 are removed from initialEvents.