1
$\begingroup$

I am using Melkman's algorithm for the convex hull of simple polygons, which is a gem.

In addition to the convex hull itself, I need to know what are the contact points, i.e. the vertices that are the endpoints of edges that were not in the original polygon (red points/blue edges in the figure).

I can find these points by comparing the initial polygon to the convex hull in linear time, but I was wondering if a simple modification of Melkman's algorithm could produce these points as a byproduct.

enter image description here

$\endgroup$
1
$\begingroup$

Save the indices of the vertices, not the points.

Green edges correspond to consecutive indices. Blue bridges correspond to jumps.

Take care to handle $n \to 1$ as green.

$\endgroup$
  • $\begingroup$ Right, then it suffices to find the discontinuities in the indexing. Simple as that. Thanks. $\endgroup$ – Yves Daoust Nov 16 '17 at 15:35
  • $\begingroup$ If I am right, I need to way until the polygon is completely processed, as the last edge can invalidate all the hull edges so far. $\endgroup$ – Yves Daoust Nov 16 '17 at 15:38
  • $\begingroup$ @YvesDaoust, I think so, yes. $\endgroup$ – lhf Nov 16 '17 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.