I have a 3D object which I have segmented and represented as a 3D binary array. I need to find the longest line which fits inside of the object in three dimensional space. What would be an efficient method I could use to approach this problem.

The following is an example of what I am trying to do but in 2 dimensions. The black part of the image is the background and the white is a segmented object. The red line is the longest line which can be drawn inside the object. I would like to find the length of this line.

enter image description here

I could do this by calculating the distance between each pair of two points on the surface of the object and taking the longest distance as my result, but this seems horribly inefficient particularity when solving the problem in 3 dimensions.

Is there a better way to solve this problem.


  • 1
    $\begingroup$ Welcome to DSP SE. We always appreciate more details as it is increasing your chances for getting better answer. $\endgroup$
    – jojeck
    Commented Jun 19, 2014 at 18:51
  • $\begingroup$ Interesting problem! Did this paper help? $\endgroup$
    – Emre
    Commented Jun 19, 2014 at 21:03
  • $\begingroup$ I don't think that paper addresses the question I am trying to solve. I am adding an image that I think will help explain what I am trying to do. $\endgroup$
    – James
    Commented Jun 19, 2014 at 21:36
  • $\begingroup$ What if you found the diameter of the convex relaxation? Or do you need to exclude lines that would protrude from the hull? $\endgroup$
    – Emre
    Commented Jun 19, 2014 at 22:34
  • $\begingroup$ Do you want to find the distance or like to have access to the line itself? $\endgroup$ Commented Mar 31, 2019 at 11:38

1 Answer 1


These are very computationally expensive problems and it also depends if your polygons are convex. Also in your case you don't have any extra constraints and it can be any line within. I think that the best read for you is the following publication:

Hall-Holt O., et al. - Finding large sticks and potatoes in polygons

You will definitely find few algorithms among ones they described (computational complexities are given). Here is some brief presentation concerning their work: click

  • $\begingroup$ Is there a technical name for such a largest line or for the length of such a line? $\endgroup$
    – Kvothe
    Commented Apr 8, 2021 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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