是否可以对重合线进行分组以评估线“密度"? [英] Is there a possibility to group coincident lines to evaluate line "density"?

问题描述

从具有许多重叠线条的线条汤开始.对这些重合的行进行分组并求和.将此总和除以装配中的最高和，即可得到相对数量.使用此相对量作为线密度的度量.

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.

我想到的一种可能性是创建一个线"类(或使用整齐的LineString)来计算线对之间的距离.在巧合的情况下，line_i的P_1和P_2在line_j上.对于该应用，将需要对重合的小的公差. 在这种蛮力方法中，必须完成许多循环，这可能会导致较大的程序集出现性能问题(我想).目标行数范围是50.000-150.000.

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.

当前，缺少一种聪明的方法来执行此任务，或者

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.

下面有一个过程片段的示例.我有一个由多条线表示的近似多边形.我只想获得最重要"的多边形，以便从中重建最重要的"多边形.在图中，可以看到16和17仅存在一次，因此18/12是首选.

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.

推荐答案

使用rho-theta方程表示线.

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)  

填充2D表，其中包含一些离散的角度和rho，例如霍夫变换累加器.

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

例如，使角度步长为1°，因此360行和几百列以获得合理的rho范围.对于A[theta][rho]的每行增量值，使用四舍五入到最接近的整数索引.

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.

请注意，此方法比Hough变换要快得多，因为它适用于即用型线，它与线数成线性关系，并且像元数取决于所需的精度，而Hough可处理点并填充其中的整个轨迹每个点的rho-theta空间.

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.

这篇关于是否可以对重合线进行分组以评估线“密度"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！