9

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.

jiggunjer
  • 191
  • 3
  • 1
    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 09:51
  • 3
    Well if O(n^2) isnt a problem then test all point pairs – joojaa Apr 22 '16 at 09:52
  • 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 Apr 22 '16 at 10:18
  • 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 Apr 22 '16 at 11:18
  • 2
    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
  • 1
    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
  • @Nero 2D is fine. Shapes are mostly organic. Cancer nodules in ultrasound. I suppose vertex vertex is OK. – jiggunjer Apr 23 '16 at 05:26
  • 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 Apr 23 '16 at 11:58
  • @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 Apr 23 '16 at 14:10
  • 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 Jan 09 '18 at 18:45
  • 2
    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 09 '18 at 18:50

1 Answers1

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'.

beyond
  • 315
  • 1
  • 5