1

I have been tasked with allowing a user to enter any number of arbitrary points on a canvas and link them together in the order that they were specified to draw a polygon.

However, each time the user tries to add a point I must validate whether the polygon can still be drawn without intersecting itself.

I have searched SO and found only this post which doesn't help me.

I need to form constraints everytime a new point is added to the canvas, and check that the next point doesn't validate those constraints.

I've added some poorly drawn illustrations of what I'm trying to achieve below. It might help to define the coordinate system I'm using: point 1 is the origin (0,0), x is positive to the right, and y is positive towards the top.

Adding Point 3

The first two points have only the constraint that 1 != 2, Adding point 3 I have to make sure that it doesn't sit anywhere on the line that passes through both 1 and 2.

adding point 3

Adding Point 4

Now, having added point 3, point 4 is blocked out as illustrated below:

Adding point 4

The Yellow areas are constrained by line 1-2 and the Green areas are constrained by the line 2-3. In pretty unreadable markup (there's no MathJax or anything) I figured the constraints for 4 are:

Y_4 < ( (Y_2 - Y_1) / (X_2 - X_1) )*X_4 + Y_1

Y_3 < ( (Y_2 - Y_1) / (X_2 - X_1) )*X_3 ? Y_4 > ( (Y_3 - Y_2) / (X_3 - X_2) )*X_4 + Y_2 : Y_4 < ( (Y_3 - Y_2) / (X_3 - X_2) )*X_4 + Y_2  

Y_4 =/= ( (Y_3 - Y_1) / (X_3 - X_1) )*X_4 + Y_1

Adding Point 5

Now adding on point 5 the constrained areas are:

Adding point 4

And it's starting to get complicated to do.

I was wondering If there are any established algorithms for these kind of things, or if there are general equations in terms of vertex n to generate the constraint equations. There could feasibly be tens, if not hundreds of points, so figuring out by brute force and hand coding doesn't seem to be an option.

Community
  • 1
  • 1
James
  • 3,957
  • 4
  • 37
  • 82

2 Answers2

3

You can do it like that:

  1. Add a new point.
  2. Add two new edges adjacent to this point.
  3. Check if there is a pair of intersecting edges by iterating over all pairs of edges and checking if they intersect or not.

This algorithm has O(n^2) time complexity per addition of a new point. If it is too slow, you can make it linear using the following observation:
If the polygon was valid before a new point was added, no edges could intersect. That's why there is no need to iterate over all pairs of edges. So you can iterate only over the pairs <new, any>, where new is a newly created edge and any is any edge of the polygon. There are 2 * n = O(n) such pairs(because adding one points yields only 2 new edges).

This algorithm has O(n) time complexity per point so it should be fast enough for tens or hundreds of points.

Checking if two edges intersect is simple: an edge is just a segment and checking if two segments intersect is a well-known problem.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
1

What you want to achieve is called a polygon simplicity test. You will find relevant information in this article: "Orientation, simplicity, and inclusion test for planar polygons", F. FEITO, J. C. TORRES and A. URENA.

  • Thank you, this is a really nice algorithm, they also reference a paper by Balbes and Siegel: "A robust method for calculating the simplicity and orientation of planar polygons" 1991 which is worth checking out. – James Oct 08 '14 at 12:49
  • Thank you for this feedback. Robustness is indeed an important topic, as in practice you meet degenerate or quasi-degenerate situations more often than wished. –  Oct 08 '14 at 13:18