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.
(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);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Concavity II</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>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;
}
.polygon
stroke-width: 2px
opacity: 0.5
.vertex
stroke-width: 1.5px
.cw
fill: #FF8900
stroke: #FF8900
.ccw
fill: #086FA1
stroke: #086FA1