Main Page   Compound List   File List   Compound Members   File Members   Related Pages  

Segment Incidences Detector

© 2002-2003 Ondrej Pavlata

Segment Incidences Detector, or SegIncid shortly, is an application of the R-tree library which detects singular incidences between elements of a given set of line segments.

Four basic types of singularities are considered:

While the first 3 types belong to the one to one relation category, the 4th type is different. A free (or uncovered) end is a missing one to one relation, so belonging to the "one to the whole" relation category.

SegIncid reads a given segment set from a text file into an in-memory container model (a list with its elements grouped into arrays), then builds an R-tree for that model and, using the search capabilities of the R-tree, it performs a 2-level search for incidences: For every segment s of the model, an R-tree range search is made (with the range of s) so that all range-incident segments are traversed, each being checked for its type of proper incidence with s (which may appear to be a non-incidence). If a pair with singular incidence is encountered, a record is made (but care is taken not to count each pair twice). Simultaneously, during the traversal for s, a check for end coverage is made, so after the traversal the collected end coverage is evaluated and if not complete, is recorded too.
After the 2-level search is completed, the collected result is reported.

Note that singularities in segment incidences are not expressed in terms of planar partition induced by the given line segment set. For instance, an edge (of induced partition) with 4 duplicit underlying segments is reported 6 times (as 6 pairs of duplicit segments).

To make the example more illustrating, segments are equipped with a color attribute. A text file SegList0.txt, located in testdata directory, contains demonstration data with green, red, yellow, violet and gray segments. The data set comes from Czech cadastre. Red segments are supposed to cause inner crossings, yellow segments are supposed to have duplicities, violet segments are supposed to have partial coalescence. Gray segments are removed from the R-tree (for purely test purposes in a hope not to influence the possible practical use of the application), thus missing of them causes free ends potentionally.

Having 2 segments with a range incidence, the proper incidence check is based on two tests: 1. A "halfspace orientation" test: For a given base abscissa line and a point (which originates from an end of an secondary abscissa) determine the sign of the halfspace with the line as its boundary which has the point in its interior. Value of -1/1 means the point is below/above the line (or right/left for the case of a vertical line), value of 0 means the point lies on the line. This test is also known as the 2d-orientation test or the ccw-test. 2. A "lexicographical order" tests evaluates lexicographical order for each pair of ends between two abscissae, so that incidences of "abscissae intervals" are classified.

The halfspace orientation evaluates a 2-degree predicate: For given planar vectors u, v the values u.x*v.y and u.y*v.x are compared. To gain correct results, 32-bit integer coordinates are assumed and the __int64 type is used for exact multiplication.


Generated on Mon Mar 24 22:59:19 2003 for Mg R-tree Library by doxygen1.2.16