topic Re: I have a polygon shaped something like a sausage and need to find two points that are approximately at the ends on the polygon. Convex or concave, it can be on any angle when created. Does anyone know of a routine/algorithm for this? in Developers Questions

I have a polygon shaped something like a sausage and need to find two points that are approximately at the ends on the polygon. Convex or concave, it can be on any angle when created. Does anyone know of a routine/algorithm for this?

JohnAdlersparre — Tue, 14 Jun 2016 20:55:37 GMT

I have tried thinning but the results are not accurate. I will code the algorithm in Vb.Net.

Re: I have a polygon shaped something like a sausage and need to find two points that are approximately at the ends on the polygon. Convex or concave, it can be on any angle when created. Does anyone know of a routine/algorithm for this?

DanPatterson_Retired — Tue, 14 Jun 2016 21:01:59 GMT

ideally what you want is the medial axis, but there are no builtin tools to do this (yet). However, you can approximate the location using a Minimum Area Bounding Rectangle (MABR) which will give you the axis diameters and you can derive the corner points and average them in the long axis direction... a bit of work, but your other option is to find an existing implementation of the medial axis

addendum, a quick approximation would be to intersect the MABR with the polygon returning points...there will probably be at most 4 intersecting points and you can select those that best represent the axis

Re: I have a polygon shaped something like a sausage and need to find two points that are approximately at the ends on the polygon. Convex or concave, it can be on any angle when created. Does anyone know of a routine/algorithm for this?

JohnAdlersparre — Wed, 15 Jun 2016 02:52:42 GMT

Hi Dan,

Thanks very much for your reply and suggestions. I will attempt a routine

to simulate the medial axis using the bounding rectangle which sounds like

the best approach. So far I can find points close to the "ends" of the

polygon but not the best points.

John

Re: I have a polygon shaped something like a sausage and need to find two points that are approximately at the ends on the polygon. Convex or concave, it can be on any angle when created. Does anyone know of a routine/algorithm for this?

DanPatterson_Retired — Wed, 15 Jun 2016 03:21:28 GMT

If you could show some sample shapes it might help, since S and C shaped figures and other self-enclosing ones will obviously require a medial axis (also look up 'skeleton') approach