9
$\begingroup$

My shape is a slightly concave polygon, and I'd like to know the maximal diameter. I imagine a straight line between two points on the surface of the polygon, such that the line does not pass outside the polygon.

Is there a general algorithm for this?

In my case I am interested in 2D. My shapes are tumors in medical images. So we can also assume: 1 the centroid is always inside the polygon. 2 a high vertex density, i.e. the next vertex is always close to the previous one.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ There is rotating calipers but that only works for convex polygons. Otherwise you can use it to as a base for a brute force solution. $\endgroup$
    – ratchet freak
    Commented Apr 22, 2016 at 9:51
  • 3
    $\begingroup$ Well if O(n^2) isnt a problem then test all point pairs $\endgroup$
    – joojaa
    Commented Apr 22, 2016 at 9:52
  • 2
    $\begingroup$ Actually it's a bit more involved: imagine 2 rooms connected by a narrow corridor. The largest diameter will end on the walls in the different rooms and won't end on any points. $\endgroup$
    – ratchet freak
    Commented Apr 22, 2016 at 11:19
  • 1
    $\begingroup$ Are you looking for an algorithm that works in the most general case or can it be restricted to e.g. the 2D case? This might be easier to solve with some more information or restrictions about the input. You use the word polygon which may hint at 2D-only, also the question you linked suggests the 2D case. Also, is it enough to consider vertex-vertex distances or do you need correct results for cases like ratchet freak mentioned in his comment? $\endgroup$
    – Nero
    Commented Apr 22, 2016 at 20:02
  • 2
    $\begingroup$ Also, I'm concerned about a C shape that has very narrow thickness, but a large an open interior; and so a large radius of curvature. Its diameter (as you define it) would be very small because it would only be a short that follows the curvature of the C. Yet a cancer nodule the size of the interior size would be quite concerning. So perhaps it is the convex hull that you want to compute the diameter of. $\endgroup$
    – Wyck
    Commented Jan 9, 2018 at 18:50

1 Answer 1

Reset to default
1
$\begingroup$

I don't have an exact answer for this, as the answer is far from trivial. I would suggest that you have a look into computational geometry as this clearly is a visibility problem - my guess is that a solution already exist. My own idea would be: for each line segment in polygon find the visible parts of the other line segments and then pick the pair of points that are furthest apart. Inspirational link: Wikipedia on 'visibility polygon'.

Improve this answer
$\endgroup$

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.