CODEWITHSUNDEEP
pythonmathgeometry
BennyS
BennyS

Reputation: 165

Is there a possibility to group coincident lines to evaluate line "density"?

Objective

Starting from a line soup with many overlying lines. Group these coincident lines and sum the number of lines. Divide this sum to the highest sum in the assembly to get the relative amount. Use this relative amount as a measurement for the line density.

State of work

One possibility that comes to my mind is to create a "Line" Class (or use shapely LineString) to calculate the distance between line pairs. In a coincident case, P_1 and P_2 of line_i are on line_j. For the application, a small tolerance for the coincidence would be required. In this brute force approach, many many loops have to be done which can cause performance issues (I guess) for larger assemblies. Target number range of lines is 50.000 - 150.000.

Line Coincidence

Problem

Currently, a smart approach is missing to do this task, either to

The resulting reduced set of lines shall be used for constructing polygons.

Unfortunately, I do not have an exemplary data set since I am already theoretically struggling. As soon as I have built an exemplary data set, I will put it online here.

Below, there is an example of a segment of the process. I have an approximated polygon represented by multiple lines. I only want to get the most "important" ones to rebuild the "most important" polygon from it. In the figure, one can see that l6 and l7 are there only once, so l8/l2 are preferred.

Line segments

Upvotes: 0

Views: 243

Answers (1)

MBo
MBo

Reputation: 80232

Represent lines using rho-theta equation.

dx = x2 - x1  
dy = y2 - y1
L = Sqrt(dx*dx+dy*dy)
Dis = dx*y1 - dy*x1
SD = Sign(Dis)
rho = SD * Dis / L   // always poitive
theta = atan2(-SD*dx, SD*dy)

Fill 2D table containing some discrete set of angles and rho's like Hough Transform accumulator.

For example, make angle step 1°, so 360 rows and some hundred columns for reasonable rho range. For every line increment value of A[theta][rho] using rounding to the closest integer indices.

Then check what cell has the largest amount of votes - in describes a set of close lines.

Note that this method is much faster than Hough transform because it works with ready-to-use lines, it is linear against number of lines and cell count depends on needed precision, while Hough works with points and fills the whole trajectory in rho-theta space for every point.

Upvotes: 4

Related Questions