algorithmcomputational-geometrypointsconvexconcave

Find double-tangent in a polyline defined by (x,y) points


I have `System.Windows.Media.Point3D collection representing a cross-section of a freeform object.

It's always more or less shaped like a "seagull-wings", "M" pattern with two convex bulges and a "valley" in between. It's orientation in space is arbitrary, and there is no guarantee that the central valley is the only concavity in the cross-section.

I have already a method that detects one point which is guaranteed to lie between those valleys, and now I want to find the pair of points that represent the "double tangent" around the central point, that is, the line passing between two points that keeps every other points at the same side, and which also circunscribes the starting point.

Below is a figure showing what I want to achieve:

enter image description here

I believe the cross-product is a good way to find out if three points are "concave" or "convex", but have not figured out how to perform a loop (how to start, what to increment, and when to stop).

Also, although I could use brute-force (not so many points), that would surely hurt my feelings.


Solution

  • Determine the convex hull of the vertices. The sequences of vertices that are not part of the convex hull vertices correspond to concavities. From your description, it sounds like there will always be exactly one concavity. The first and last vertices of the concavity sequence of vertices are the endpoints of the line you are looking for.