Determining if a polygon is convex (small correction)

Determining if a polygon is convex (small correction)

Post by Tom Wrig » Thu, 22 Oct 1992 09:39:49



#include <stdio.h>

int convex(int *x, int *y, int n)
   {
   int  iMinus1, i, iPlus1;
   long cross, oldCross;

   for (iMinus1=n-2, i=n-1, oldCross=iPlus1=0; iPlus1<n; iPlus1++)
      {
      cross = (long) (x[iPlus1]-x[i])*(long) (y[iMinus1]-y[i]) -
              (long) (y[iPlus1]-y[i])*(long) (x[iMinus1]-x[i]);
      if (oldCross && cross && cross!=oldCross)
         return 0;
      if (!oldCross && cross)
         oldCross = cross;
      iMinus1 = i;
      i = iPlus1;
      }
   return 1;
   }

static int x1[] = {0, 0, 1};
static int y1[] = {0, 1, 0};
static int x2[] = {0, 1, 0};
static int y2[] = {0, 0, 1};
static int x3[] = {0, 0, 1, 4};
static int y3[] = {0, 4, 1, 0};

main()
   {
   printf("%d\n", convex(x1, y1, 3));
   printf("%d\n", convex(x2, y2, 3));
   printf("%d\n", convex(x3, y3, 4));
   return 0;
   }

 
 
 

1. Determining if a polygon is convex (CORRECTION)

The sameside procedure is wrong. It is really a silly mistake, I used
cross product rather than determinant to test this. The corrected
version is

bool sameside(v1,v2,l1,l2)
point v1,v2,l1,l2;
{
  int dx,dy;

  dx = l2.x - l1.x;
  dy = l2.y - l1.y;
  return(sgn(dx*(v1.y-l1.y)-dy*(v1.x-l1.x))
         == sgn(dx*(v2.y-l1.y)-dy*(v2.x-l1.x)));

If you can have colinear vertices, the procedure can be modified to
accept a point on the line to be at any side of it.

bool sameside(v1,v2,l1,l2)
point v1,v2,l1,l2;
{
  int dx,dy, s1,s2;

  dx = l2.x - l1.x;
  dy = l2.y - l1.y;
  s1 = sgn(dx*(v1.y-l1.y)-dy*(v1.x-l1.x));
  s2 = sgn(dx*(v2.y-l1.y)-dy*(v2.x-l1.x));
  return(s1 == s2 || s1 == 0 || s2 == 0);


2. Q:problems rendering to bitmap

3. Looking for Intersection of Non-Convex polygons or Non-Convex to Convex polygons

4. Help!! An Accelerated Subspace Iteration Method

5. Determining if a polygon is convex

6. File ID: PDF-1.2 %a??รณ 14 0 obj

7. Audio editing

8. How to determine if a polygon is convex?

9. Circumscribing a convex polygon by another convex polygon

10. Help: Smallest convex polygon enclosing a set of points

11. Convex polygon inscribed in Non Convex

12. convex hull for convex polygons (3D)