Construct lines from multiple 2D points and measure the distance between those lines

user_1900892 0
Viewed 251

Multiple points on a 2D plane are given. They represent a window frame of mostly rectangular form with some possible variations. The points which are part of each side are not guaranteed to form a perfect line. Each side of the window should be measured.

A rotating electronic device attached to a window measures the distance in all directions providing a 360 degree measurements. By using the rotation angle and the distance, a set of points are plotted on a 2D coordinate system. So far so good.

Points in a 2D plane


Now comes the harder part. The measured window frame could have some variations. The points should be converted to straight lines and the length of each line should be measured.

I imagine that the following steps are required:

  1. Group the different points into straights lines. This means approximating each line “between” the points that form it.
  2. Drawing those lines, getting rid of the separate points used to construct the lines.
  3. Find the points where each two lines intersect.
  4. Measure the distance between those points. However not all distances between all points are interesting. For example diagonals within a frame are irrelevant.

Any Java libraries dealing with geometry that could solve the problem are acceptable. I will write the solution in Kotlin/Java, but any algorithmic insights or code examples and ideas in any other languages or pseudo code are welcome.

Thank you in advance!

New Image enter image description here

measure line distance measurement algorithm
1 Answers

I would solve this in 2 stages:

  • Data cleaning: round the location (X, Y) of each point to its nearest multiple of N (vary N for varying degrees of precision)
  • Apply the gift-wrapping algorithm (also known as Jarvis March)
  • You now have only those points that are not co-linear, and the lines between them, and the order in which they need to be traversed to form the perimeter.
  • Iterate over the points in order, take point Px and P(x+1), and calculate the distance between them.
user_60743760
Related