block by nitaku 7235174

Concavity

Full Screen

Test if a polygon is convex or concave, regardless of its orientation (points given in clockwise or counterclockwise order). Also, highlight which vertices determine a concavity. Hollow polygons are concave, while filled ones are convex.

Polygons in the first line have a counterclockwise orientation, while the ones in the second line have a clockwise orientation.

First, an implementation of this algorithm computes the orientation of the polygon. The result determine the polygon’s color, blue for CCW, orange for CW.

Then, a variation of another algorithm computes the orientation of the inner angle for each triplet of vertices. This is shown as the vertex color, again, either blue (CCW) or orange (CW).

Finally, each vertex with an orientation that’s different from the one of the polygon is highlighted (represented as hollow). If there is already one of such vertices, then the polygon is concave (also represented as hollow).

In order for this method to work, polygons must be noncomplex (i.e. without self-intersections), their vertices must be at least three, must not be coincident and must not be colinear. I am convinced that there are better ways to obtain the same result, if you happen to know one, please comment on this example Gist page.

index.js

(function() {
  var analyze_convexity, analyze_orientation;

  window.main = function() {
    var all_points, height, polygon, polygons, svg, vis, width, _i, _len;
    width = 960;
    height = 500;
    svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
    svg.append('text').text('CCW').attr('class', 'ccw').attr('x', 50).attr('y', 160);
    svg.append('text').text('CW').attr('class', 'cw').attr('x', 50).attr('y', 360);
    vis = svg.append('g').attr('transform', 'translate(150,65)');
    polygons = [
      {
        points: [
          {
            x: 30,
            y: 30
          }, {
            x: 30,
            y: 130
          }, {
            x: 130,
            y: 130
          }, {
            x: 130,
            y: 30
          }
        ]
      }, {
        points: [
          {
            x: 30,
            y: 230
          }, {
            x: 130,
            y: 230
          }, {
            x: 130,
            y: 330
          }, {
            x: 30,
            y: 330
          }
        ]
      }, {
        points: [
          {
            x: 230,
            y: 30
          }, {
            x: 230,
            y: 130
          }, {
            x: 330,
            y: 130
          }, {
            x: 330,
            y: 80
          }, {
            x: 280,
            y: 80
          }, {
            x: 280,
            y: 30
          }
        ]
      }, {
        points: [
          {
            x: 230,
            y: 230
          }, {
            x: 280,
            y: 230
          }, {
            x: 280,
            y: 280
          }, {
            x: 330,
            y: 280
          }, {
            x: 330,
            y: 330
          }, {
            x: 230,
            y: 330
          }
        ]
      }, {
        points: [
          {
            x: 430,
            y: 30
          }, {
            x: 430,
            y: 130
          }, {
            x: 530,
            y: 130
          }, {
            x: 530,
            y: 80
          }, {
            x: 480,
            y: 30
          }
        ]
      }, {
        points: [
          {
            x: 430,
            y: 230
          }, {
            x: 480,
            y: 230
          }, {
            x: 530,
            y: 280
          }, {
            x: 530,
            y: 330
          }, {
            x: 430,
            y: 330
          }
        ]
      }, {
        points: [
          {
            x: 630,
            y: 30
          }, {
            x: 660,
            y: 80
          }, {
            x: 630,
            y: 130
          }, {
            x: 680,
            y: 100
          }, {
            x: 730,
            y: 130
          }, {
            x: 700,
            y: 80
          }, {
            x: 730,
            y: 30
          }, {
            x: 680,
            y: 60
          }
        ]
      }, {
        points: [
          {
            x: 630,
            y: 230
          }, {
            x: 680,
            y: 260
          }, {
            x: 730,
            y: 230
          }, {
            x: 700,
            y: 280
          }, {
            x: 730,
            y: 330
          }, {
            x: 680,
            y: 300
          }, {
            x: 630,
            y: 330
          }, {
            x: 660,
            y: 280
          }
        ]
      }
    ];
    for (_i = 0, _len = polygons.length; _i < _len; _i++) {
      polygon = polygons[_i];
      analyze_convexity(polygon);
    }
    /* draw the results
    */
    vis.selectAll('.polygon').data(polygons).enter().append('path').attr('class', 'polygon').attr('d', function(d) {
      return "M" + (d.points.map(function(p) {
        return p.x + ' ' + p.y;
      }).join('L')) + "Z";
    }).attr('stroke', function(d) {
      if (d.orientation === 'cw') {
        return '#FF8900';
      } else {
        return '#086FA1';
      }
    }).attr('fill', function(d) {
      if (d.convex) {
        if (d.orientation === 'cw') {
          return '#FF8900';
        } else {
          return '#086FA1';
        }
      } else {
        return 'white';
      }
    });
    all_points = polygons.reduce((function(p, c) {
      return p.concat(c.points);
    }), []);
    return vis.selectAll('.vertex').data(all_points).enter().append('circle').attr('class', 'vertex').attr('r', 4).attr('cx', function(d) {
      return d.x;
    }).attr('cy', function(d) {
      return d.y;
    }).attr('stroke', function(d) {
      if (d.orientation === 'cw') {
        return '#FF8900';
      } else {
        return '#086FA1';
      }
    }).attr('fill', function(d) {
      if (d.convex) {
        if (d.orientation === 'cw') {
          return '#FF8900';
        } else {
          return '#086FA1';
        }
      } else {
        return 'white';
      }
    });
  };

  /* write into the polygon whether it's in clockwise or counterclockwise orientation
  */

  analyze_orientation = function(polygon) {
    var i, j, z, z_sum, _ref;
    z_sum = 0;
    for (i = 0, _ref = polygon.points.length; 0 <= _ref ? i < _ref : i > _ref; 0 <= _ref ? i++ : i--) {
      j = (i + 1) % polygon.points.length;
      z = (polygon.points[j].x - polygon.points[i].x) * (polygon.points[j].y + polygon.points[i].y);
      z_sum += z;
    }
    return polygon.orientation = z_sum > 0 ? 'ccw' : 'cw';
  };

  /* write into the polygon wheter it is convex or concave
  */

  /* also, for each vertex, store its orientation (cw or ccw) and if it determines the concavity (i.e. if it falls inside the convex hull)
  */

  analyze_convexity = function(polygon) {
    var i, j, k, last_orientation, orientation, z, _ref, _results;
    analyze_orientation(polygon);
    /* WARNING no complex polygons, no less than 3 vertices, no colinear points
    */
    polygon.convex = true;
    _results = [];
    for (i = 0, _ref = polygon.points.length; 0 <= _ref ? i < _ref : i > _ref; 0 <= _ref ? i++ : i--) {
      j = (i + 1) % polygon.points.length;
      k = (i + 2) % polygon.points.length;
      z = (polygon.points[j].x - polygon.points[i].x) * (polygon.points[k].y - polygon.points[j].y);
      z -= (polygon.points[j].y - polygon.points[i].y) * (polygon.points[k].x - polygon.points[j].x);
      orientation = z > 0 ? 'cw' : 'ccw';
      polygon.points[j].orientation = orientation;
      polygon.points[j].convex = polygon.points[j].orientation === polygon.orientation;
      if ((typeof last_orientation !== "undefined" && last_orientation !== null) && orientation !== last_orientation) {
        polygon.convex = false;
      }
      _results.push(last_orientation = orientation);
    }
    return _results;
  };

}).call(this);

index.html

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>Concavity</title>
        <link type="text/css" href="index.css" rel="stylesheet"/>
        <script src="//d3js.org/d3.v3.min.js"></script>
        <script src="index.js"></script>
    </head>
    <body onload="main()"></body>
</html>

index.coffee

window.main = () ->
    width = 960
    height = 500
    
    svg = d3.select('body').append('svg')
        .attr('width', width)
        .attr('height', height)
        
    svg.append('text')
        .text('CCW')
        .attr('class', 'ccw')
        .attr('x', 50)
        .attr('y', 160)
        
    svg.append('text')
        .text('CW')
        .attr('class', 'cw')
        .attr('x', 50)
        .attr('y', 360)
        
    vis = svg.append('g')
        .attr('transform', 'translate(150,65)')
        
    polygons = [{
        points: [{x:30, y:30}, {x:30, y:130}, {x:130, y:130}, {x:130, y:30}]
    },{
        points: [{x:30, y:230}, {x:130, y:230}, {x:130, y:330}, {x:30, y:330}]
    },{
        points: [{x:230, y:30}, {x:230, y:130}, {x:330, y:130}, {x:330, y:80}, {x:280, y:80}, {x:280, y:30}]
    },{
        points: [{x:230, y:230}, {x:280, y:230}, {x:280, y:280}, {x:330, y:280}, {x:330, y:330}, {x:230, y:330}]
    },{
        points: [{x:430, y:30}, {x:430, y:130}, {x:530, y:130}, {x:530, y:80}, {x:480, y:30}]
    },{
        points: [{x:430, y:230}, {x:480, y:230}, {x:530, y:280}, {x:530, y:330}, {x:430, y:330}]
    },{
        points: [{x:630, y:30}, {x:660, y:80}, {x:630, y:130}, {x:680, y:100}, {x:730, y:130}, {x:700, y:80}, {x:730, y:30}, {x:680, y:60}]
    },{
        points: [{x:630, y:230}, {x:680, y:260}, {x:730, y:230}, {x:700, y:280}, {x:730, y:330}, {x:680, y:300}, {x:630, y:330}, {x:660, y:280}]
    }]
    
    analyze_convexity(polygon) for polygon in polygons
    
    ### draw the results ###
    vis.selectAll('.polygon')
        .data(polygons)
      .enter().append('path')
        .attr('class', 'polygon')
        .attr('d', (d) -> "M#{d.points.map((p)->p.x+' '+p.y).join('L')}Z")
        .attr('stroke', (d) -> if d.orientation is 'cw' then '#FF8900' else '#086FA1')
        .attr('fill', (d) -> if d.convex then (if d.orientation is 'cw' then '#FF8900' else '#086FA1') else 'white')
        
    all_points = polygons.reduce(((p,c) -> p.concat c.points),[])
    vis.selectAll('.vertex')
        .data(all_points)
      .enter().append('circle')
        .attr('class', 'vertex')
        .attr('r', 4)
        .attr('cx', (d) -> d.x)
        .attr('cy', (d) -> d.y)
        .attr('stroke', (d) -> if d.orientation is 'cw' then '#FF8900' else '#086FA1')
        .attr('fill', (d) -> if d.convex then (if d.orientation is 'cw' then '#FF8900' else '#086FA1') else 'white')
        
### write into the polygon whether it's in clockwise or counterclockwise orientation ###
analyze_orientation = (polygon) ->
    z_sum = 0
    
    for i in [0...polygon.points.length]
        j = (i+1) % polygon.points.length
        
        z = (polygon.points[j].x-polygon.points[i].x)*(polygon.points[j].y+polygon.points[i].y)
        
        z_sum += z
        
    polygon.orientation = if z_sum > 0 then 'ccw' else 'cw'
    
### write into the polygon wheter it is convex or concave ###
### also, for each vertex, store its orientation (cw or ccw) and if it determines the concavity (i.e. if it falls inside the convex hull) ###
analyze_convexity = (polygon) ->
    analyze_orientation(polygon)
    
    ### WARNING no complex polygons, no less than 3 vertices, no colinear points ###
    polygon.convex = true
    
    for i in [0...polygon.points.length]
        j = (i+1) % polygon.points.length
        k = (i+2) % polygon.points.length
        
        z  = (polygon.points[j].x - polygon.points[i].x) * (polygon.points[k].y - polygon.points[j].y)
        z -= (polygon.points[j].y - polygon.points[i].y) * (polygon.points[k].x - polygon.points[j].x)
        
        orientation = if z > 0 then 'cw' else 'ccw'
        
        polygon.points[j].orientation = orientation
        polygon.points[j].convex = polygon.points[j].orientation is polygon.orientation
        
        if last_orientation? and orientation isnt last_orientation
            polygon.convex = false
            
        last_orientation = orientation

index.css

.polygon {
  stroke-width: 2px;
  opacity: 0.5;
}

.vertex {
  stroke-width: 1.5px;
}

.cw {
  fill: #ff8900;
  stroke: #ff8900;
}

.ccw {
  fill: #086fa1;
  stroke: #086fa1;
}

text {
  font-family: sans-serif;
  font-size: 40px;
  stroke: none !important;
}

index.sass

.polygon
    stroke-width: 2px
    opacity: 0.5
    
.vertex
    stroke-width: 1.5px
    
.cw
    fill: #FF8900
    stroke: #FF8900
    
.ccw
    fill: #086FA1
    stroke: #086FA1
    
text
    font-family: sans-serif
    font-size: 40px
    stroke: none !important