CODEWITHSUNDEEP
geometry
Nyaruko
Nyaruko

Reputation: 4459

How to measure whether a set of line segments is more "curve" than the other?

Is there any fast algorithm that produces a "curve score" for a set of interconnected line segments?

For example in the following picture:

enter image description here

line-segments (a) shall be less "curved" compared to (b).

Upvotes: 0

Views: 28

Answers (1)

Adrien Kaczmarek
Adrien Kaczmarek

Reputation: 550

Here is a solution I found.
I wrote the algorithm in Python, ask any question you would like.

I am not sure it works all the time.

I am calculating the angle between each segment and sum their absolute value.
Here the complete code:

import matplotlib.pyplot as plt
import numpy as np 


lineA_x = [3, 1, 2, 4]
lineA_y = [6, 4, 2, 1]

lineB_x = [10, 8, 9, 8]
lineB_y = [6, 4, 2, 1]

plt.plot(lineA_x, lineA_y)
plt.plot(lineB_x, lineB_y)
plt.savefig("my_fig.png")

theta_A = 0
for i in range(1, len(lineA_x) - 1):
    a = np.array([lineA_x[i] - lineA_x[i - 1], lineA_y[i] - lineA_y[i - 1]])
    b = np.array([lineA_x[i + 1] - lineA_x[i], lineA_y[i + 1] - lineA_y[i]])


    # np.sum(a * b ): produit scalaire
    theta_A += np.abs(np.arccos(np.sum(a * b) / (np.linalg.norm(a) * np.linalg.norm(b))))

theta_B = 0
for i in range(1, len(lineB_x) - 1):
    a = np.array([lineB_x[i] - lineB_x[i - 1], lineB_y[i] - lineB_y[i - 1]])
    b = np.array([lineB_x[i + 1] - lineB_x[i], lineB_y[i + 1] - lineB_y[i]])


    # np.sum(a * b ): produit scalaire
    theta_B += np.abs(np.arccos(np.sum(a * b) / (np.linalg.norm(a) * np.linalg.norm(b))))

print("Theta A:", theta_A)
print("theta_B:", theta_B)

if (theta_A > theta_B):
    print("A > B")
elif (theta_B > theta_A):
    print("B > A")
else:
    print("A = B")

The important part is only this one (repeated two times, forgive me...)

theta_A = 0
for i in range(1, len(lineA_x) - 1):
    a = np.array([lineA_x[i] - lineA_x[i - 1], lineA_y[i] - lineA_y[i - 1]])
    b = np.array([lineA_x[i + 1] - lineA_x[i], lineA_y[i + 1] - lineA_y[i]])


    # np.sum(a * b ): produit scalaire
    theta_A += np.abs(np.arccos(np.sum(a * b) / (np.linalg.norm(a) * np.linalg.norm(b))))

Here is the output of the program:

Theta A: 1.8925468811915391
theta_B: 2.498091544796509
B > A

The lines used were (as describe by the two arrays): Lines use for the example

So it outputs B more curved than A.

I encoded each segments in two arrays, one for the x and one for the y, just to make the work a little bit easier.
The system of coordinates you use has no importance (it just has to be orthogonal).

I do not think my solution is optimal, if you have any new insight I will be happy to hear you.

Upvotes: 1

Related Questions