c++ - Adding a point to a 2D polygon -

c++ - Adding a point to a 2D polygon -

i have doubly-linked list based polygon2d class needs searched , modified, , used in game engine various utilities collision detection , define graphical shapes , perchance texture coordinates, among other things. polygon should able concave or convex, cannot intersect itself.

i'm having problem coming method insert point such doesn't cause intersection polygon. i've been doing searching closest border point insert having 2 pointers nodes, both starting @ head , iterating in separate directions. when "next" node either other pointer, search finish , point inserted between two. otherwise, node iterating forwards goes until gets closest point far (stopping if next node other pointer), node iterating "backwards" same.

unfortunately, still results in intersections in cases border before forwards iterating pointer or border "after" backwards iterating pointer intersects new border created when inserting new point. after that, more , more intersections can slip in.

here insert method's code.

can improve algorithm , still maintain o(n) or there exclusively different method may work better?

as side note, "findclosest[edge](vec2 pt)" search uses modified version of algorithm, sense there must more effective way these searches without using more memory or time.

as calculation of distance given point vertex distance point polygon might help.

c++ algorithm geometry polygon game-physics