Create non-intersecting polygon passing through all given points

by

Our strategy is to make a plan where we are sure that the polygon
includes all points, and that we can find an order to connect them
where none of the lines intersect.

Algorithm:

  1. Find the leftmost points p
  2. Find the rightmost point q
  3. Partition the points into A, the set of points below pq, and B, the set of points above pq [you can use the left turn test on (p,q,?) to
    determine if a point is above the line].
  4. Sort A by x-coordinate (increasing)
  5. Sort B by x-coordinate (decreasing).
  6. Return the polygon defined by p, the points in A, in order, q, the points of B in order.

Runtime:

Steps 1,2,3 take O(n) time.
Steps 4,5 take O(nlogn) time.
Step 6 take O(n) time.
Total runtime is O(nlogn).

Correctness:

By construction, all points besides p,q are in set A or
set B. Our output polygon from line 6 therefore outputs a polygon with
all the points. We now need to argue that none of the line segments in
our output polygon intersect each other.

Consider each segment in the
output polygon. The first edge from p to the first point in A can’t
intersect any segment (because there is no segment yet). As we proceed
in order by x-coordinate through the points in A, from each point, the
next segment is going to the right, and all previous segments are to
the left. Thus, as we go from p, through all the points of A, to point
q, we will have no intersections.

The same is true as we go from q back
through the points of B. These segments cannot intersect each other
because they proceed from right to left. These segments also cannot
intersect anything in A because all points in A are below line pq, and
all points in B are above this line.

Thus, no segments intersect each
other and we have a simple polygon.

Source: Broken link

More Related Contents:

  1. How to determine if a point is in a 2D triangle? [closed]
  2. An algorithm for inflating/deflating (offsetting, buffering) polygons
  3. How do I calculate the area of a 2d polygon?
  4. Algorithm to detect intersection of two rectangles?
  5. How to calculate an angle from three points? [closed]
  6. Simple calculations for working with lat/lon and km distance?
  7. How to find the intersection point between a line and a rectangle?
  8. Sort points in clockwise order?
  9. How do I efficiently determine if a polygon is convex, non-convex or complex?
  10. How do you calculate the average of a set of circular data? [closed]
  11. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  12. Is there an efficient algorithm to generate a 2D concave hull?
  13. Largest circle inside a non-convex polygon
  14. How to check if line segment intersects a rectangle?
  15. How to compare two shapes?
  16. Combined area of overlapping circles
  17. Calculate largest inscribed rectangle in a rotated rectangle
  18. Circle-circle intersection points
  19. How to find two most distant points?
  20. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  21. Collision detection of huge number of circles
  22. How to find convex hull in a 3 dimensional space
  23. Calculating the position of points in a circle
  24. Find if a point is inside a convex hull for a set of points without computing the hull itself
  25. Algorithm for reflecting a point across a line
  26. Compute the area of intersection between a circle and a triangle?
  27. determine if a point sits inside an arbitrary shape?
  28. How can I perform Collision Detection on rotated rectangles? [closed]
  29. Location of highest density on a sphere
  30. Distance from a point to a polygon

Leave a Comment