Thursday, February 5, 2015

Simple polygon


"Write a function to check if polygon is simple based on given list of points"

I was stuck on the problem at first because I didn't know what is a "simple" polygon compares to what is a "complex" polygon. More information can always be found on Wikipedia, here I will just show you two figures. 


Yep, exactly what you are thinking, a simple polygon has no other intersections between two lines except for the point, a complex one involves more than one intersections. 

Then the rest of the problem becomes very easy: check every line and see if there exists another intersection. 


public static boolean isSimplePolygon(Point[] polygon) {
  if (polygon == null || polygon.length < 3)
   throw new IllegalArgumentException("invalid input!");
  Set slopes = new HashSet ();
  for (int i = 0; i < polygon.length - 1; i++) {
   slopes.clear();
   for (int j = i + 1; j < polygon.length; j++) {
    double slope;
    if (polygon[i].x == polygon[j].x) {
     slope = (double)Integer.MAX_VALUE;
    }
    else if (polygon[i].y == polygon[j].x) {
     slope = 0.0;
    }
    else {
     slope = (double) (polygon[i].y - polygon[j].y) / (double)(polygon[i].x + polygon[j].x);
    }
    if (slopes.contains(slope))
     return false;
    slopes.add(slope);
   }
  }
  return true;
 }

No comments:

Post a Comment