0

I have a doubly-linked list based Polygon2D class that needs to be searched and modified, and is to be used in a game engine for various utilities like collision detection and to define graphical shapes and possibly texture coordinates, among other things. The polygon should be able to be concave or convex, but it cannot intersect itself.

I'm having trouble coming up with a method to insert a point such that it doesn't cause an intersection with the polygon. What I've been doing is searching for the closest edge to the point to insert by having two pointers to nodes, both starting at the head and iterating in separate directions. When the "next" node for either is the other pointer, the search is complete and the point is inserted between the two. Otherwise, the node iterating forward goes until it gets to the closest point so far (stopping if the next node is the other pointer), then the node iterating "backwards" does the same.

Unfortunately, this still results in intersections in cases where the edge just before the forward iterating pointer or the edge just "after" the backwards iterating pointer intersects the new edge created when inserting a new point. After that, more and more intersections can easily slip in.

Here is the insert method's code.

Can I improve this algorithm and still keep it O(n) or is there an entirely different method which may work better?

As a side note, the "findClosest[Edge](vec2 pt)" search uses a slightly modified version of the algorithm, but I feel like there must be a more effective way to do these searches without using more memory or time.

Cave Dweller
  • 502
  • 2
  • 4
  • 17
  • 1
    I'm not sure if I get what you are trying to achieve. When inserting a new point it should automagically be inserted into the **edge** nearest to the point ? This would eliminate one edge and replace them with two new edges,is that right ? The code you are linking to only seems to minimize distances to vertexes not edges. For this you would have to calculate the euclidean distance of the new point on a line perpendicular to the edge. Elimination of intersections still would be a different issue. – Oncaphillis Nov 04 '14 at 22:42
  • It should be inserted in between the two points at the closest edge. This would at least minimize the chance of intersections (actually it should eliminate it entirely, if I'm understanding the logic correctly). And yes it would "break" one edge and create two more. How would I go about calculating the euclidean distance to the closest edge, then (or ideally find the closest edge without calculating the distance each time)? Or alternatively, if for some reason that doesn't eliminate intersections, how would I insert a point without creating intersections? – Cave Dweller Nov 05 '14 at 02:16

1 Answers1

1

As for the calculation of the distance from a given point to a vertex this Distance from a point to a polygon might help.

Community
  • 1
  • 1
Oncaphillis
  • 1,888
  • 13
  • 15