Finding the Center of Many Intersecting Lines

Question

I have the following matrix of linear equations which gives rise to the following plot. (All of my examples and code use R.)

A <- matrix(c(-1, -1, -3, -5, -2, 3, -2, 3, -3, -3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), ncol = 2)
b <- c(1, 2, -5, -3, 0, 1, 0, 1, -5, -5, 4)
Ab <- cbind(A, b)
> Ab
   A_Column_1 A_Column_2  b
1          -1          1  1
2          -1          1  2
3          -3          1 -5
4          -5          1 -3
5          -2          1  0
6           3          1  1
7          -2          1  0
8           3          1  1
9          -3          1 -5
10         -3          1 -5
11          2          1  4

In the figure, coincident lines are colored differently as described in the legend.

As you can see, most of the lines behave nicely and intersect at a point; there are a couple that are parallel, and there are a few others that are coincidental.

I'm trying to determine, for all the points of intersection, what the centroid is. This calculation is straightforward for the lines that intersect at a point and for the lines that are parallel. For parallel lines, there are no points of intersection, I can just omit them from the calculation. It gets tricky when there are coincident lines, and I'm suggesting to handle them in the following way. I'll describe the steps I've come up with so far and would love to get input from folks who know more about math than me.

First, break up this large matrix into smaller matrices for each possible combination of 2 lines.

Second, delete any of these smaller matrices that correspond to parallel lines.

Third, calculate all of the intersections for the lines that behave nicely and intersect at exactly one point.

Fourth, calculate the centroid of these points of intersection. If n lines intersect at one point, that point is counted n * (n - 1) / 2 times in the centroid calculation - in other words, it's counted once for each pair of lines it is the intersection of.

Fifth, determine if there are any coincident lines, and how many there are that overlap for each slope and intercept.

> Coincidental_Lines
  A_Column_1 A_Column_2  b Number_of_Overlapping_Lines
1         -3          1 -5                           3
2         -5          1 -3                           1
3         -2          1  0                           2
4         -1          1  1                           1
5          3          1  1                           2
6         -1          1  2                           1
7          2          1  4                           1

Sixth, for coincident lines, find the coincident line that represents the fewest number of overlapping lines, and project the centroid onto that line to generate a new centroid. If there are more than one coincident lines that contain an equal number of overlapping lines like there are in this example, the new centroid will be the centroid of these projected points. (In the plots, the dashed lines may not appear perfectly perpendicular, and it's because the vertical and horizontal axis scales are a little off.)

Seventh, if there are coincident lines that contain more overlapping lines than there were in step six, project the centroid from step six onto these coincident lines which represent more overlapping lines to generate a new centroid. Continue projecting these new centroids onto coincident lines that represent more and more overlapping lines.

Eighth, if there is a tie - in other words, if there are multiple independent, separate lines that are duplicates - project the centroid onto all of them (as long as they are of the same magnitude - as long as they all contain the same number of overlapping lines), and then take the centroid of all of these projections. (I showed how to do this process in step six above.)

I've followed these steps with my example data, and the plots interspersed in the text above show each step. Here's the final centroid, which happens to be the projection of the second-order centroid onto the only third-order coincidental line.

Is this process valid? Are there better ways to go about solving this problem? I'm describing a general method, but I'm using it in conjunction with the Hough transform to determine lines of best fit when there are possibly multiple distinct lines in a plot of data.

Answer 1

Your method based on points of intersection has an issue of stability, at least when you have few lines. For example, if you slightly move 2 lines having similar slopes, their point of intersection can move far away, therefore oblige you to take different cases.

As you are asking for alternatives, I propose you to explore a completely different track by using median/medial (broken) lines ("MLL lines" as in my recent answer here) which could be considered as belonging to the category of regression lines, with a good stability due to median (compared to mean). How can this be done ? By building the "West-East" $MLL_{yx}$ line for the "regression" of $y$ with respect to $x$ ; then the "North-South" $MLL_{xy}$ line for the "regression" of $x$ with respect to $y$ ; the intersection of these lines provides another "center" for the family of lines. This center shouldn't be too sensible to slight changes in the lines' position, avoiding in this way to have to consider different cases.

Remark 1: the idea behind this point of intersection is the same as for "true" regression lines $y \ vs. \ x$ and $x \ vs. \ y$ whose intersection is the center of gravity of the set of points.

Remark 2: in the case of an even number 2n of lines, one can define 2 median lines ranked $n$ and $n+1$, do the same thing in the other direction, giving rise to an intersection which, instead of being a point, is a small quadrilateral, and finally take "a" center of this quadrilateral.

Remark 3: I have been working a lot with Hough Transform ; but, here, your question is mainly connected to statistics, which is not the domain in which H.T. could be well used.