1
$\begingroup$

Given a set S of line segments and an additional segment L, I'm looking for a procedure that determines which of the line segments in S is nearest to L. My first thought was to compute the distance between the points of L and the points of each line segment in S, however it can be tricky as illustrated in the following figure:

enter image description here

Let's say that L is the blue line, I want my method to point out that the green one is the nearest, but computing the distance between the points in such example may not provide the intended result.

Therefore my question is: which is the simplest (and correct) way to address this problem.

Thank you so much for your help.

edit: note that the lines are not always parallel, horizontal nor straight

$\endgroup$
  • $\begingroup$ To make the question complete, are the line segments always horizontal? Parallel? $\endgroup$ – NoChance Nov 13 '18 at 18:47
  • $\begingroup$ unfortunately not always $\endgroup$ – João Matos Nov 13 '18 at 18:48
  • $\begingroup$ they can be curve as well $\endgroup$ – João Matos Nov 13 '18 at 18:49
  • $\begingroup$ I have an approach that could work but it is not detailed to the equation level. Its a general algorithm I came up with. I am not sure it would work in all cases since I just made it up. If I publish it here the question will show as if it has an answer and this may prevent others from looking at it. If you don't get replies and want to see my idea let me know. My idea is not trivial to implement as a program but it is not too difficult either. $\endgroup$ – NoChance Nov 13 '18 at 20:47
  • $\begingroup$ Thank you for your effort. I think you should post it as an answer as it may help others in the future. As for not working in all cases or any sort of limitations in your algorithm, you can point them out in your answer, e.g. specify the scenarios in which your algorithm works well and which ones it does not. This way the readers can determine if it is an appropriate solution for their problem at hand $\endgroup$ – João Matos Nov 14 '18 at 8:59
0
$\begingroup$

I ended up figuring out an answer (maybe not the best one) sooner than I expected, but thanks for your attention anyway.

My idea requires that we add a point to the beginning and end of each line, which is acceptable to my problem at hand. Then we can take each pair (L,s_i), s_i = s1,s2,..sn in S and for each one connect each point to form a polygon. Then we can simply compute its perimeter or area and return the lowest one found.

e.g.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.