Programming Challenge: Polygon analysis.

#!/usr/bin/env python3

"""This program models 2D polygons and provides some basic geometric analysis 
of polygons to test if they are concave or convex."""

from math import atan2, degrees
from collections import namedtuple

def ngrams(iterable, n=1):
    """Generate ngrams from an iterable
    
    l = range(5)
    list(l) -> [0, 1, 2, 3, 4, 5]
    list(ngrams(l, n=1)) -> [(0,), (1,), (2,), (3,), (4,)]
    list(ngrams(l, n=2)) -> [(0, 1), (1, 2), (2, 3), (3, 4)]
    list(ngrams(l, n=3)) -> [(0, 1, 2), (1, 2, 3), (2, 3, 4)]
    
    """
    return zip(*(iterable[i:] for i in range(n)))

def angle(v1, v2, v3):
    """Compute the angle of 3 vertices in degrees"""
    return degrees(
        atan2(v1.x - v2.x, v2.y - v1.y) - atan2(v2.x - v3.x, v3.y - v2.y)
    )

def z(v1, v2, v3):
    """Compute the z component of the cross product of 3 vertices"""
    return (v1.x - v2.x) * (v2.y - v3.y) - (v1.y - v2.y) * (v2.x - v3.x)

Vertex = namedtuple('Vertex', ['x', 'y'])

class Polygon():
    """A class modeling a 2D polygon as a list of Vertices (where a Vertex
    is a namedtuple with 2 attributes: x and y)"""
    def __init__(self, *vertices):
        self.vertices = list(vertices)
        if not all((isinstance(v, Vertex) for v in self.vertices)):
            raise ValueError('expected iterable of Vertices')
        if not len(self.vertices) >= 3:
            raise ValueError(
                f'expected at least 3 Vertices (got {len(vertices)})'
            )
    
    def __str__(self):
        return f'{self.__class__.__name__}{self.vertices}'
    
    def __repr__(self):
        return str(self)
    
    def __len__(self):
        return len(self.vertices)
    
    def __iter__(self):
        return iter(self.vertices)
    
    def trigrams(self):
        """Generate all trigrams of Vertices in the Polygon"""
        first, second, *rest = self.vertices
        *rest, penultimate, ultimate = self.vertices
        yield from ngrams(self.vertices, n=3)
        yield penultimate, ultimate, first
        yield ultimate, first, second
    
    def angles(self):
        """Generate all the angles of the Vertices in the Polygon"""
        yield from (angle(*trigram) for trigram in self.trigrams())
    
    def convex(self):
        """Return True if the Polygon is convex and False otherwise"""
        zs = [z(*trigram) > 0 for trigram in self.trigrams()]
        return all(zs) or not any(zs)
    
    def concave(self):
        """Return True if the Polygon is concave and False otherwise"""
        return not self.convex()

if __name__ == '__main__':
    polygons = [
        Polygon(
            Vertex(x=0, y=0),
            Vertex(x=0, y=1),
            Vertex(x=1, y=0)
        ),
        Polygon(
            Vertex(x=0, y=0),
            Vertex(x=0, y=1),
            Vertex(x=1, y=1),
            Vertex(x=1, y=0)
        ),
        Polygon(
            Vertex(x=0, y=1),
            Vertex(x=0, y=0),
            Vertex(x=1, y=0),
            Vertex(x=-1, y=-1)
        )
    ]
    for polygon in polygons:
        print(f'{polygon}.convex(): {polygon.convex()}')

Run it:

$ ./polygons.py
Polygon(Vertex(x=0, y=0), Vertex(x=0, y=1), Vertex(x=1, y=0)).convex(): True
Polygon(Vertex(x=0, y=0), Vertex(x=0, y=1), Vertex(x=1, y=1), Vertex(x=1, y=0)).convex(): True
Polygon(Vertex(x=0, y=1), Vertex(x=0, y=0), Vertex(x=1, y=0), Vertex(x=-1, y=-1)).convex(): False

I originally tried to go through and check if there were any interior angles greater than 180 degrees. Unfortunately, math is definitely not my strong suit and I wasn't able to figure out how to calculate the correct angle from vectors.

There's good news though, I was able to figure out a much shorter approach that checks directionality instead. I think it's close to what @onyxleopard did from this link regarding cross products.

Here's my solution, in Ruby.

require 'matrix'

polygon_1 = [
  [1,1],
  [5,1],
  [5,5],
  [3,3],
  [1,5]
]

polygon_2 = [
  [1,1],
  [5,1],
  [5,5],
  [3,7],
  [1,5]
]

def convert_two_points_to_vector(point_1, point_2)
  result = Vector[point_2[0] - point_1[0], point_2[1]- point_1[1]]
end

def cross_product(v1, v2)
  v1[0] * v2[1] - v1[1] * v2[0]
end

def analyze_polygon(polygon)
  # go through the array backwards, since Ruby will wrap around backwards (but not forwards)
  concave = false;
  for i in (polygon.length - 1).downto(0)
    a = convert_two_points_to_vector(polygon[i], polygon[i-1])
    b = convert_two_points_to_vector(polygon[i-1], polygon[i-2])
    cross = cross_product(a, b)
    if (i == polygon.length - 1)
      dir = cross > 0 # set dir on the first time through
    elsif (dir == cross < 0) # check if the direction has changed
      concave = true
      break
    end
  end
  puts "Polygon #{polygon.to_s} is #{concave ? 'concave' : 'convex'}"
end

analyze_polygon(polygon_1)
analyze_polygon(polygon_2)

output:

$ ruby analysis.rb
Polygon [[1, 1], [5, 1], [5, 5], [3, 3], [1, 5]] is concave
Polygon [[1, 1], [5, 1], [5, 5], [3, 7], [1, 5]] is convex

I wanted to make sure I actually knew what was happening in my earlier Ruby solution and that I didn't just luck into some Ruby magic, so I reimplemented that same solution in Java.

import java.util.Arrays;

public class PolygonAnalysis {
  public static void main(String[] args) {
    double[][] polygon1 = {
      {1,1},
      {5,1},
      {5,5},
      {3,3},
      {1,5}
    };
    
    double[][] polygon2 = {
      {1,1},
      {5,1},
      {5,5},
      {3,7},
      {1,5}
    };

    double[][][] polygons = {
      polygon1,
      polygon2
    };

    for (double[][] polygon : polygons) {
      String msg = isConcave(polygon) ? "concave" : "convex";
      System.out.println("Polygon " + Arrays.deepToString(polygon) + " is " + msg);
    }
  }

  public static double crossProduct(double[] v1, double[] v2) {
    double c = (v1[0] * v2[1]) - (v1[1] * v2[0]);
    return c;
  }

  public static double[] createVector(double[] p1, double[] p2) {
    double[] newVector = {
      p2[0] - p1[0],
      p2[1] - p1[1]
    };
    return newVector;
  }

  public static boolean isConcave(double[][] polygon) {
    boolean dir = false;
    double cross = 0;

    if (polygon.length <= 3) 
      return false;

    for (int i = 0; i < polygon.length - 1 ; i++ ) {
      if (i == polygon.length - 2) {
        double[] v1 = createVector(polygon[i], polygon[i+1]);
        double[] v2 = createVector(polygon[i+1], polygon[0]);
        cross = crossProduct(v1, v2);
      }
      else if (i == polygon.length - 1) {
        double[] v1 = createVector(polygon[i], polygon[0]);
        double[] v2 = createVector(polygon[0], polygon[1]);
        cross = crossProduct(v1, v2);
      }
      else {
        double[] v1 = createVector(polygon[i], polygon[i+1]);
        double[] v2 = createVector(polygon[i+1], polygon[i+2]);
        cross = crossProduct(v1, v2);
      }

      if(i == 0)
        dir = cross > 0;
      else if (dir == cross < 0)
        return true;
    }

    return false;
  }
}

output:

$ java PolygonAnalysis
Polygon [[1.0, 1.0], [5.0, 1.0], [5.0, 5.0], [3.0, 3.0], [1.0, 5.0]] is concave
Polygon [[1.0, 1.0], [5.0, 1.0], [5.0, 5.0], [3.0, 7.0], [1.0, 5.0]] is convex

That’s too easy. Given a set of points on a plane, there is no more than one convex polygon with all vertices in those points.

If you have an ordered list, you can just start with the first vertex and check if the next angle is always less than 180 degrees (considering two cases, since the list can be oriented either clockwise or counter-clockwise).