Last active
December 17, 2020 07:19
-
-
Save annatomka/82715127b74473859054 to your computer and use it in GitHub Desktop.
Determine in Javascript wheather a polygon is convex or not? (using Openlayers polygon and algorithm describe here: http://stackoverflow.com/questions/471962/how-do-determine-if-a-polygon-is-complex-convex-nonconvex)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function calculateAllCrossProduct(points) { | |
var lastSign = null; | |
for (var i = 2; i < points.length; i++) { | |
//calculate crossproduct from 3 consecutive points | |
var crossproduct = calculateCrossProduct(points[i - 2], points[i - 1], points[i]); | |
console.log(i + ". crossproduct from ("+ points[i - 2].x +" "+points[i - 1].x +" "+points[i].x +"): " + crossproduct); | |
var currentSign = Math.sign(crossproduct); | |
if (lastSign == null) { | |
//last sign init | |
lastSign = currentSign; | |
} | |
console.log("Last sign: " + lastSign + " current sign: "+currentSign); | |
var checkResult = checkCrossProductSign(lastSign, currentSign); | |
if (checkResult == false) { | |
//different sign in cross products,no need to check the remaining points --> concave polygon --> return function | |
return false; | |
} | |
lastSign = currentSign; | |
} | |
//first point must check between second and last point, this is the last 3 points that can break convexity | |
var crossproductFirstPoint = calculateCrossProduct(points[points.length - 2], points[0], points[1]); | |
console.log("cross product first point: ", crossproductFirstPoint); | |
return checkCrossProductSign(lastSign, Math.sign(crossproductFirstPoint)); | |
} | |
function checkCrossProductSign(lastSign, newSign) { | |
if (lastSign !== newSign) { | |
//checked sign differs from the previous one --> concave polygon | |
return false; | |
} | |
return true; | |
} | |
function calculateCrossProduct(p1, p2, p3) { | |
var dx1 = p2.x - p1.x; | |
var dy1 = p2.y - p1.y; | |
var dx2 = p3.x - p2.x; | |
var dy2 = p3.y - p2.y; | |
var zcrossproduct = dx1 * dy2 - dy1 * dx2; | |
return zcrossproduct; | |
} | |
function isPolygonConvex(points) { | |
return calculateAllCrossProduct(points); | |
} | |
var pointsConvexPolygon = [{"x":2117708.7303958,"y":6024264.0003844},{"x":2118950.8321053,"y":6026690.8760321},{"x":2121110.178154,"y":6024187.5633561},{"x":2119361.6811323,"y":6023432.7477018},{"x":2117708.7303958,"y":6024264.0003844}]; | |
var pointsConcavePolygon = [{"x":2119934.9588443,"y":6024579.3031259},{"x":2118950.8321053,"y":6026690.8760321},{"x":2121110.178154,"y":6024187.5633561},{"x":2119361.6811323,"y":6023432.7477018},{"x":2119934.9588443,"y":6024579.3031259}]; | |
console.log(isPolygonConvex(pointsConvexPolygon)); | |
console.log(isPolygonConvex(pointsConcavePolygon)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment