MapInfo Products KnowledgeBase

Product: MapInfo
Version: 6.5
Platform: Not Platform Related
Category: Object Manipulation

Summary:
What is the logic behind the "CONVEX HULL" object processing function?

Question:
How does the "CONVEX HULL" function determine what the convex hull is? What points are included on the perimeter and which ones are not?

For example, consider this data:



Using OBJECTS>CONVEX HULL gives this:



But, why is this not a valid answer?



How does the function "decide" what points to include? Is there a formula or expression?

Answer:

The second image above is concave, not convex.

There are numerous ways to think of what the convex hull is. Given a set of points, there will be one and only one convex hull that can be created. Think of putting a rubber band around all of the points. The convex hull is the path that is formed by the rubber band.

Another way to think of it is that the convex hull is created by connecting the minimum number of points such that all of the points are either inside the convex hull, or are part of the boundary. In the second example, the added point can be eliminated from the set of points with this criteria. When connecting the other two points, then there is one fewer point comprising the boundary (a minimal set) and the other point is now internal to the boundary. It isn't possible to eliminate any other point from the boundary and still have all the points be inside the boundary or on the boundary.

Another way to look at it is that it isn't possible to have an angle, as measured on the interior of the polygon, that is greater than 180 degrees. That rule is broken in the second image.

With a convex polygon, it isn't possible to produce a line where each endpoint of the line is inside the polygon, and the line travels outside of the polygon. If such a line can be created, then the polygon is concave.

Here are some links to pages with convex hull algorithms:

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

http://www.cs.princeton.edu/~ah/alg_anim/version1/ConvexHull.html

http://www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/convex_hull/convex_hull.html

Last Modified: 11/28/2001 01:58:32 PM
Document URL: http://testdrive.mapinfo.com/techsupp/miprod.nsf/kbase_by_product/9BB36BEF079FF392CA2568FB00040754

What is the logic behind the "CONVEX HULL" object processing function?^9BB36BEF079FF392CA2568FB00040754^Y