<p>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: <a href="https://en.wikipedia.org/wiki/Visibility_polygon" rel="nofollow noreferrer">Wikipedia on 'visibility polygon'</a>.</p>

CC BY-SA 4.0
2018-08-16T10:39:15.173Z
2018-08-16T10:39:15.173Z
beyond
<p>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.</p>

<p>Is there a general algorithm for this? </p>

<p>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. </p>

CC BY-SA 3.0
2016-04-22T09:51:58.693Z
There is [rotating calipers](https://en.wikipedia.org/wiki/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
CC BY-SA 3.0
2016-04-22T09:52:26.363Z
Well if O(n^2) isnt a problem then test all point pairs
joojaa
CC BY-SA 3.0
2016-04-22T10:18:05.417Z
Yes, diameter, intra-shape width, not sure if theres a proper name for it. E.g. how'd you measure the maximum length of a 5-point star shape?
jiggunjer
CC BY-SA 3.0
2016-04-22T11:18:34.263Z
was hoping for a simpler solution than this: https://gis.stackexchange.com/questions/32552/how-to-calculate-the-maximum-distance-within-a-polygon-in-x-direction-east-west
jiggunjer
CC BY-SA 3.0
2016-04-22T11:19:25.323Z
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
CC BY-SA 3.0
2016-04-22T20:02:12.510Z
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](http://computergraphics.stackexchange.com/questions/2355/find-the-longest-straight-line-between-two-points-on-surface-of-polygon#comment2806_2355)?
Nero
CC BY-SA 3.0
2016-04-23T05:26:46.540Z
@Nero 2D is fine. Shapes are mostly organic. Cancer nodules in ultrasound. I suppose vertex vertex is OK.
jiggunjer
CC BY-SA 3.0
2016-04-23T11:58:07.300Z
Is your raw data raster (pixel) data rather than a list of vertices? If so a raster approach which cuts out the intermediate step of converting to vertices may increase accuracy.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-23T14:10:34.943Z
@trichoplax yes, but I thought that would be slower and messier. The ROI was drawn in paint by hand. Convert to vertexes was just noting the coordinates of each white pixel.
jiggunjer
CC BY-SA 3.0
2018-01-09T18:45:44.260Z
Actually @ratchetfreak, There will be a line line of maximal length that __passes through__ two points.  In your case it will likely either hug one wall of the corridor, or connects the adjacent corners.  If neither of those are maximal then it will extend into a far corner.  So I think that the O(n^2) approach is valid, it's just that the two choices of vertices for the line to consider do not necessarily define the start and end of the line; they are merely ON the line.
Wyck
CC BY-SA 3.0
2018-01-09T18:50:07.150Z
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
<mathematics><computational-geometry><polygon>
Find the longest straight line between two points on surface of polygon
jiggunjer
# Find the longest straight line between two points on surface of polygon

(Asked by: username_0 on 2016-04-22)

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.

**Tags:** mathematics, computational-geometry, polygon

> **Comments:**
> **username_1**: There is [rotating calipers](https://en.wikipedia.org/wiki/Rotating_calipers) but that only works for convex polygons. Otherwise you can use it to as a base for a brute force solution.  
> **username_2**: Well if O(n^2) isnt a problem then test all point pairs  
> **username_0**: Yes, diameter, intra-shape width, not sure if theres a proper name for it. E.g. how'd you measure the maximum length of a 5-point star shape?  
> **username_0**: was hoping for a simpler solution than this: https://gis.stackexchange.com/questions/32552/how-to-calculate-the-maximum-distance-within-a-polygon-in-x-direction-east-west  
> **username_1**: 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.  
> **username_3**: 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 username_1 mentioned in [his comment](http://computergraphics.stackexchange.com/questions/2355/find-the-longest-straight-line-between-two-points-on-surface-of-polygon#comment2806_2355)?  
> **username_0**: @username_3 2D is fine. Shapes are mostly organic. Cancer nodules in ultrasound. I suppose vertex vertex is OK.  
> **username_4**: Is your raw data raster (pixel) data rather than a list of vertices? If so a raster approach which cuts out the intermediate step of converting to vertices may increase accuracy.  
> **username_0**: @username_4 yes, but I thought that would be slower and messier. The ROI was drawn in paint by hand. Convert to vertexes was just noting the coordinates of each white pixel.  
> **username_5**: Actually @username_1, There will be a line line of maximal length that __passes through__ two points.  In your case it will likely either hug one wall of the corridor, or connects the adjacent corners.  If neither of those are maximal then it will extend into a far corner.  So I think that the O(n^2) approach is valid, it's just that the two choices of vertices for the line to consider do not necessarily define the start and end of the line; they are merely ON the line.  
> **username_5**: 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.  

---

## 1 answers

### Answer by username_6 on 2018-08-16. Score: 1

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'](https://en.wikipedia.org/wiki/Visibility_polygon).


---

