I'm assuming from your explanation that you aren't actually just inerested in the convexhull, but simply inserting points into a polygon without creating self intersecting lines. In this case you can simply find the closest point and insert either before or after this, depending on which of the neighboring points are closest to the new point.

 insertIntoClosestEdge[line_, p_] := Module[{closest, neighbors, nearclosest}, closest = Nearest[line -> Automatic, p][[1]]; neighbors = closest // Mod[# + {1, -1}, Length@line, 1] &; nearclosest = Nearest[line[[neighbors]] -> neighbors, {.1, -.1}][[1]]; Insert[line, p, {Mod[closest - If[nearclosest < closest, 0, -1], Length@line]}] ] 

It may need extending to work in all cases, but it shows the gist of the suggested solution.

I'm assuming from your explanation that you aren't actually just interested in the convex hull, but simply inserting points into a polygon without creating self-intersecting lines. In this case, you can simply find the closest point and insert either before or after this, depending on which of the neighboring points are closest to the new point.

 insertIntoClosestEdge[line_, p_] := Module[{closest, neighbors, nearclosest}, closest = Nearest[line -> Automatic, p][[1]]; neighbors = closest // Mod[# + {1, -1}, Length@line, 1] &; nearclosest = Nearest[line[[neighbors]] -> neighbors, {.1, -.1}][[1]]; Insert[line, p, {Mod[closest - If[nearclosest < closest, 0, -1], Length@line]}] ] 

It may need extending to work in all cases, but it shows the gist of the suggested solution.