Skip to content

Instantly share code, notes, and snippets.

@nitaku
Last active December 27, 2015 00:08
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save nitaku/7235174 to your computer and use it in GitHub Desktop.
Concavity

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.

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
.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;
}
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Concavity</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;
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);
.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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment