# Find the longest straight line between two points on surface of polygon

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.

• 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. – ratchet freak Apr 22 '16 at 9:51
• Well if O(n^2) isnt a problem then test all point pairs – joojaa Apr 22 '16 at 9:52
• 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. – ratchet freak Apr 22 '16 at 11:19
• 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? – Nero Apr 22 '16 at 20:02
• 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. – Wyck Jan 9 '18 at 18:50