An interactive polygon editor, which tests the concavity analysis introduced in this example.
Drag the vertices to modify the polygon. Try to make the polygon concave, then convex again. Also, try to reverse the vertices' ordering to see the polygon change to counterclockwise (blue) to clockwise (orange).
Please keep in mind that results are unspecified for complex (e.g self-intersecting) polygons and for coincident or colinear vertices.
| window.main = () -> | |
| width = 960 | |
| height = 500 | |
| svg = d3.select('body').append('svg') | |
| .attr('width', width) | |
| .attr('height', height) | |
| vis = svg.append('g') | |
| .attr('transform', 'translate(250,85)') | |
| ### define a drag behavior ### | |
| drag = d3.behavior.drag() | |
| .on 'drag', (d) -> | |
| ### move the circle ### | |
| d.x = d3.event.x | |
| d.y = d3.event.y | |
| refresh(vis, polygon, drag) | |
| polygon = { | |
| points: [{x:30, y:30}, {x:20, y:130}, {x:100, y:280}, {x:200, y:320}, {x:330, y:260}, {x:430, y:130}, {x:430, y:80}, {x:380, y:30}, {x:230, y:20}] | |
| } | |
| ### draw the base shapes ### | |
| vis.selectAll('.polygon') | |
| .data([polygon]) | |
| .enter().append('path') | |
| .attr('class', 'polygon') | |
| vis.selectAll('.vertex') | |
| .data(polygon.points) | |
| .enter().append('circle') | |
| .attr('class', 'vertex') | |
| .attr('r', 4) | |
| ### update the shapes according to the analysis ### | |
| refresh(vis, polygon, drag) | |
| refresh = (vis, polygon, drag) -> | |
| analyze_convexity(polygon) | |
| vis.selectAll('.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') | |
| vis.selectAll('.vertex') | |
| .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') | |
| .call(drag) | |
| ### 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 | |
| .polygon { | |
| stroke-width: 2px; | |
| opacity: 0.5; | |
| } | |
| .vertex { | |
| stroke-width: 1.5px; | |
| } | |
| .cw { | |
| fill: #ff8900; | |
| stroke: #ff8900; | |
| } | |
| .ccw { | |
| fill: #086fa1; | |
| stroke: #086fa1; | |
| } |
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta charset="utf-8"> | |
| <title>Concavity II</title> | |
| <link type="text/css" href="index.css" rel="stylesheet"/> | |
| <script src="http://d3js.org/d3.v3.min.js"></script> | |
| <script src="index.js"></script> | |
| </head> | |
| <body onload="main()"></body> | |
| </html> |
| (function() { | |
| var analyze_convexity, analyze_orientation, refresh; | |
| window.main = function() { | |
| var drag, height, polygon, svg, vis, width; | |
| width = 960; | |
| height = 500; | |
| svg = d3.select('body').append('svg').attr('width', width).attr('height', height); | |
| vis = svg.append('g').attr('transform', 'translate(250,85)'); | |
| /* define a drag behavior | |
| */ | |
| drag = d3.behavior.drag().on('drag', function(d) { | |
| /* move the circle | |
| */ d.x = d3.event.x; | |
| d.y = d3.event.y; | |
| return refresh(vis, polygon, drag); | |
| }); | |
| polygon = { | |
| points: [ | |
| { | |
| x: 30, | |
| y: 30 | |
| }, { | |
| x: 20, | |
| y: 130 | |
| }, { | |
| x: 100, | |
| y: 280 | |
| }, { | |
| x: 200, | |
| y: 320 | |
| }, { | |
| x: 330, | |
| y: 260 | |
| }, { | |
| x: 430, | |
| y: 130 | |
| }, { | |
| x: 430, | |
| y: 80 | |
| }, { | |
| x: 380, | |
| y: 30 | |
| }, { | |
| x: 230, | |
| y: 20 | |
| } | |
| ] | |
| }; | |
| /* draw the base shapes | |
| */ | |
| vis.selectAll('.polygon').data([polygon]).enter().append('path').attr('class', 'polygon'); | |
| vis.selectAll('.vertex').data(polygon.points).enter().append('circle').attr('class', 'vertex').attr('r', 4); | |
| /* update the shapes according to the analysis | |
| */ | |
| return refresh(vis, polygon, drag); | |
| }; | |
| refresh = function(vis, polygon, drag) { | |
| analyze_convexity(polygon); | |
| vis.selectAll('.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'; | |
| } | |
| }); | |
| return vis.selectAll('.vertex').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'; | |
| } | |
| }).call(drag); | |
| }; | |
| /* 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); |
| .polygon | |
| stroke-width: 2px | |
| opacity: 0.5 | |
| .vertex | |
| stroke-width: 1.5px | |
| .cw | |
| fill: #FF8900 | |
| stroke: #FF8900 | |
| .ccw | |
| fill: #086FA1 | |
| stroke: #086FA1 | |
