Search code examples
javaconvex

Determine if vertex is convex. Help understanding


I am studying the following code.

boolean convex(double x1, double y1, double x2, double y2, 
       double x3, double y3)
{
if (area(x1, y1, x2, y2, x3, y3) < 0)
    return true;
else
    return false;
}


/* area:  determines area of triangle formed by three points
 */
double area(double x1, double y1, double x2, double y2,
    double x3, double y3)
{
double areaSum = 0;

areaSum += x1 * (y3 - y2);
areaSum += x2 * (y1 - y3);
areaSum += x3 * (y2 - y1);

/* for actual area, we need to multiple areaSum * 0.5, but we are
     * only interested in the sign of the area (+/-)
     */

return areaSum;
}

I do not understand the concept that area being negative. Shouldn't area be always positive? maybe I am lacking some understanding of terms here. I tried to contact the original writer but this code is about 8 years old and I have no way to contact the original writer. This method of determining if the given vertex x2y2 is convex seems really mobile. I really want to understand it. Any direction or reference to help me understand this piece of code will be appreciated greatly.

Source code : http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applets/BruteForceEarCut.java


Solution

  • The algorithm use a very simple formula with which you can compute twice the area of a triangle.

    This formula has two advantages:

    • it doesn't require any division
    • it returns a negative area if the point are in the counterclockwise order.

    In the code sample, the actual value of the area doesn't matter, only the sign of the result is needed.

    The formula can also be used to check if three points are colinear.

    You can find more information about this formula on this site : http://www.mathopenref.com/coordtrianglearea.html