CODEWITHSUNDEEP
pythonalgorithmgeometrycurve-fittingransac
Kiran Ramachandra
Kiran Ramachandra

Reputation: 29

Fit more than one line to a set of data points in python

I have a set of sensor data points and I am trying to fit 4 lines to form a quadrilateral in the below figure. My intention is to obtain vertices of the quadrilateral.

Illustration of the problem

RANSAC would help to determine lines, but multiple lines on this point cloud is challenging.

I'm struggling to use RANSAC to fit multiple lines. Does anyone has an idea or an approach?

Is there any good method to get multiple lines in this scenario other than RANSAC?

Other method would be to fit a quadrilateral to these points.

PS: I know its only 4 line segments which is required.

Upvotes: 1

Views: 1303

Answers (1)

0009laH
0009laH

Reputation: 2000

You should look at the PIP (Perceptually Important Points) algorithm. I've used it to implement an algorithm which recognizes abnormal patterns in a huge sensor dataset coming from daily nuclear plants reports. The PIP algorithm works on time series in a 2D context but I think it is easy to adapt the code to a 3D graph like yours.

Unfortunately I don't find free and complete documentation on Google, so to make it simple :

  • You draw a line between the two most distant points (point A and point B)
  • For all points in your graph, you calculate the distance between the line and that point
  • Consider the point with the maximum calculated distance (point C)
  • If that distance exceeds a threshold (that you can define yourself), you have to "cut" AB into 2 lines : AC and CB. In the other case, do nothing.

Then reiterate the operation using AC and CB sub-lines. You can perfectly customize the algorithm defining a maximum number of sub-lines.

The algorithm complexity is in O(n.ln(n)) in a standard case and O(n^2) in the worst case (noisy graph).

There is an illustration below, hope it will help you :)

PIP application example

Upvotes: 1

Related Questions