Checking convexity from outside [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

Is there any method or algorithm to determine convex (or non-convexity) property of a region from outside (perimeter) ?

One way is plotting tangent line in each point of perimeter and discuss how many times this line intersect the perimeter points. If no intersect shown (for all points of perimeter ) we can conclude region is convex. In otherwise region is non-convex.

Second way is determine interior angel of each point of perimeter and discuss if it's bigger than 180 or not. The region is non-convex if at least one point in perimeter exist it's interior angel bigger than 180.

Are there another simpler ways?

Any ideas or solution would be appreciated, thanks.

Answer 1

One thing to observe when doing this is that as you traverse the sides of a convex polygon, all the turns will be to the same side. That is, if you are traversing around the vertices in a counter-clockwise direction, all of the turns will be to the left; if you are traversing around the vertices in a clockwise direction, all of the turns will be to the right. If you ever observe a turn to the opposite side of any others observed, then you know you're dealing with a non-convex polygon. If all of the turns are to one side, then it is a convex polygon.

So, all you need to do is take look three vertices at a time, call them v_n, v_n+1 and v_n+2. You can then determine which side of the line segment connecting v_n and v_n+2 the vertex v_n+1 sits on. For CCW, v_n+1 should be on the right of the line segment, and for CW it should be on the left. There is an answer to another question which provides a method for determining this.

There are additional implementation details you should work out (like how to deal with n=N, the number of points in your polygon, but this should provide you with a place to start.

An implementation based on this approach will run in O(N) time and space.

UPDATE: In response to the question below, "how about non-polygonal regions"? In general this is much harder. Mathematically, a region can be shown to be non-convex by finding a line segment with endpoints in the interior of the region but which has some portion of the line segment exterior to the region. I suspect you're looking for a way of implementing this using a digital computer, and so the pure mathematical approach is not practical.

So, you're going to have to offer some sort of constraints as to the types regions before the problem becomes intractable. That is, you have to constrain your problem space so that things like Nyquist sampling of the perimeter of the boundary do not incorrectly identify a non-convex region as being convex.

Assuming you can properly constrain the problem, any solution you can come up with, which can be implemented on a digital computer will have to approximate the region. You can either generate a piece-wise linear approximation of the region in question and run the algorithm above, or pick the proper set of points along the boundary of the region and calculate their derivative. Each successive sample should rotate the angle of the tangent line by some increment in the same direction. But again, it gets downs to sampling.

If you have other information about the nature of any nonlinearities which comprise the boundary of your region, you may be able to symbolically demonstrate whether a segment of the boundary is convex. The problem then reduces to showing that it remains convex when joined to the adjacent sections, which again is going to be problem specific.

So, my suggestion is, for digital computer implementation, approximate as needed the boundary of the region by a polygon and run the method defined above on that approximation.

Answer 2

An algorithm I've used (in pseudo code):

function isConvex(vertices[Count] V):
  convex = true
  if Count <= 3 return convex
  for N = 0 to Count while convex:
    // line segment between previous and subsequent vertices
    LineSegment segment1 = new LineSegment(
         V[(N + Count - 1) % Count], V[(N + 1) % Count]);
    // line segment between the point and any other point
    LineSegment segment2 = new LineSegment((V[N], V[N+2 % Count]);
    if not segment1.intersects(segment2) then convex = false;
  return convex

I don't know if this is optimal or simpler than the algorithms you've already tried. The LineSegment.intersects() method already existed making this really easy to write.

The actual code used segment2 from the previous iteration as segment 1 of the current iteration making it faster but more complex to write even in pseudo code.

And also, for what it's worth, the original of this algorithm was written in assembly language on a processor that no longer exists, so I won't be providing actual code ;-).