各种多边形算法
程序员文章站
2022-03-13 14:50:53
...
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<script src="/scripts/mathematicsAndPhysics/linearAlgebra/matrix/gl-matrix/2.7.1/dist/gl-matrix.js"></script>
<script src="../../../../scripts/mathematicsAndPhysics/geometry/shape-points/2.0.1/shapPoints.js"></script>
<script src="../../../../scripts/mathematicsAndPhysics/bezierCurve/jsbezier/0.9.3/jsbezier.js"></script>
<script src="../../../../scripts/mathematicsAndPhysics/bezierCurve/bezierjs/2.2.15/bezierjs.js"></script>
<title></title>
<style>
#canvas {
border: 1px solid #000;
}
</style>
</head>
<body>
<canvas id="canvas">
</canvas>
<script>
var canvas = document.getElementById('canvas')
canvas.width = 1000;
canvas.height = 1000;
var ctx = canvas.getContext('2d');
// 创建一个
var rotate = 20 / 180 * Math.PI;
var rectSize=vec2.fromValues(100,100)
var rectPosition = vec2.fromValues(100, 100);
var rectRotatePosition = vec2.rotate(vec2.create(), rectPosition, [0, 0], rotate)
// 创建一个矩阵
var m = mat2d.create();
m = mat2d.translate(mat2d.create(), m, [100, 100]);// 位移
m = mat2d.scale(mat2d.create(), m, [1, 1]);// 缩放
m = mat2d.rotate(mat2d.create(), m, rotate);// 旋转20
var m2=mat2d.multiply(mat2d.create(),mat2d.create(),[2,0,0,2,100,100])
// 创建一个矩形
ctx.fillStyle = 'red';
ctx.setTransform.apply(ctx, m)
ctx.fillRect(rectPosition[0], rectPosition[1], rectSize[0], rectSize[1]);
// ctx.setTransform.apply(ctx, mat2d.create())
// 创建一个圆
ctx.beginPath();
ctx.arc(400, 100, 50, 0, Math.PI * 2);
ctx.fill();
function drawPoints(points,fill) {
ctx.moveTo(points[0], points[1])
for (var i = 2; i < points.length; i += 2) {
ctx.lineTo(points[i], points[i + 1])
}
if (fill) {
ctx.fill();
return;
}
ctx.stroke()
}
//创建一个三次贝塞尔图形
var heartPoints = [];
function heart() {
var ops = {
x: 100,
y: 50,
width: 30,
height: 30
}, x = ops.x, y = ops.y, w = ops.width, h = ops.height;
ctx.beginPath();
ctx.moveTo(x, y);
heartPoints.push([{
x: x,
y:y
}, {
x: x + w / 2,
y: y - h * 2 / 3
}, {
x: x + w * 2,
y: y + h / 3
}, {
x: x,
y:y+h
}])
heartPoints.push([{
x: x,
y: y+h
}, {
x: x - w * 2,
y: y + h / 3
}, {
x: x - w / 2,
y: y - h * 2 / 3
}, {
x: x,
y: y
}])
ctx.bezierCurveTo(
x + w / 2, y - h * 2 / 3,
x + w * 2, y + h / 3,
x, y + h
);
ctx.bezierCurveTo(
x - w * 2, y + h / 3,
x - w / 2, y - h * 2 / 3,
x, y
);
window.isCurve = function (x2, y2) {
ctx.beginPath();
ctx.moveTo(x, y);
ctx.bezierCurveTo(
x + w / 2, y - h * 2 / 3,
x + w * 2, y + h / 3,
x, y + h
);
ctx.bezierCurveTo(
x - w * 2, y + h / 3,
x - w / 2, y - h * 2 / 3,
x, y
);
if (ctx.isPointInPath(x2, y2)) {
return true;
}
return false;
}
ctx.fill();
// 曲线转成直线
var p1=heartPoints[0].reduce(function(a,b){
return a.concat(b.x,b.y);
}, [])
var p2 = heartPoints[1].reduce(function (a, b) {
return a.concat(b.x, b.y);
}, [])
var p1Points = shapPoints.bezierCurveTo.apply(null, p1)
var p2Points = shapPoints.bezierCurveTo.apply(null, p2)
console.log(p1Points)
//drawPoints(p1Points, true)
// drawPoints(p2Points, true)
var heartBezierPoints = [];
var heartLinePoints = [];
var p4 = p1Points.concat(p2Points);
for (var i = 0,length=p4.length; i < length; i+=2) {
heartLinePoints.push([p4[i], p4[i + 1]])
}
window.heartLinePoints = heartLinePoints;
var b = new bezierjs(heartPoints[0])
var b2 = new bezierjs(heartPoints[1])
var b3 = new bezierjs.PolyBezier([b, b2]);
}
heart();
function Polygon(points) {
ctx.moveTo(points[0][0], points[0][1]);
for (var i = 1, l = points.length; i < l; i++) {
ctx.lineTo(points[i][0], points[i][1]);
}
}
var p2=vec2.fromValues(600,100)
ctx.beginPath();
ctx.strokeStyle = 'red';
ctx.lineWidth = 2;
var points=[[600,100],[700,100],[750,150],[700,200],[600,200],[550,150]];
Polygon(points);
ctx.closePath();
ctx.stroke();
function contian(a, b) {
var x = 0;
return a[0] - b[0] <= x && a[1] - b[1] <= x;
}
function windingLine(x0, y0, x1, y1, x, y) {
if ((y > y0 && y > y1) || (y < y0 && y < y1)) {
return 0;
}
// Ignore horizontal line
if (y1 === y0) {
return 0;
}
var dir = y1 < y0 ? 1 : -1;
var t = (y - y0) / (y1 - y0);
//当交点为两条多边形线的连接点时避免缠绕误差
// Avoid winding error when intersection point is the connect point of two line of polygon
if (t === 1 || t === 0) {
dir = y1 < y0 ? 0.5 : -0.5;
}
var x_ = t * (x1 - x0) + x0;
// If (x, y) on the line, considered as "contain".
return x_ === x ? Infinity : x_ > x ? dir : 0;
}
function isAroundEqual(a, b) {
return Math.abs(a - b) < EPSILON;
}
var EPSILON = 1e-8;
function isAroundEqual(a, b) {
return Math.abs(a - b) < EPSILON;
}
function contain(points, x, y) {
var w = 0;x
var p = points[0];
if (!p) {
return false;
}
for (var i = 1; i < points.length; i++) {
var p2 = points[i];
w += windingLine(p[0], p[1], p2[0], p2[1], x, y);
p = p2;
}
var p0 = points[0];
// 第一个点与最后一个点,值相差differ 大于0.00000001,再
if (!isAroundEqual(p[0], p0[0]) || !isAroundEqual(p[1], p0[1])) {
w += windingLine(p[0], p[1], p0[0], p0[1], x, y);
}
return w !== 0;
}
//
function linearRingContainsXY(flatCoordinates, offset, end, stride, x, y) {
// http://geomalgorithms.com/a03-_inclusion.html
/**
版权所有（C / / 2000年softsurfer丹，2012年《星期日泰晤士报
的这段代码可能会用到的*……和改性的任何用途
提供版权通知，这是与包含它。
softsurfer让好的保单在这个方法的代码，和不能被举行
liable任何房或imagined损伤的功能从它的使用。
用户的这段代码必须验证的正确性的方法及其应用。
*/
let wn = 0;
let x1 = flatCoordinates[end - stride];
let y1 = flatCoordinates[end - stride + 1];
for (; offset < end; offset += stride) {
const x2 = flatCoordinates[offset];
const y2 = flatCoordinates[offset + 1];
if (y1 <= y) {
if (y2 > y && ((x2 - x1) * (y - y1)) - ((x - x1) * (y2 - y1)) > 0) {
wn++;
}
} else if (y2 <= y && ((x2 - x1) * (y - y1)) - ((x - x1) * (y2 - y1)) < 0) {
wn--;
}
x1 = x2;
y1 = y2;
}
return wn !== 0;
}
function linearRingsContainsXY(flatCoordinates, offset, ends, stride, x, y) {
if (ends.length === 0) {
return false;
}
if (!linearRingContainsXY(flatCoordinates, offset, ends[0], stride, x, y)) {
return false;
}
for (let i = 1, ii = ends.length; i < ii; ++i) {
if (linearRingContainsXY(flatCoordinates, ends[i - 1], ends[i], stride, x, y)) {
return false;
}
}
return true;
}
// 绕线算法
function isContainPoint(points,x,y) {
var r=0;
for (var i = 0, length=points.length; i < length; i++) {
var j = (i + 1) % length;
var x2 = points[i][0], y2 = points[i][1];
var x3 = points[j][0], y3 = points[j][1];
//
// 判断点是否在两点之间
if (y >= y2 && y <= y3 && x < ((x3 - x2) * (y - y2) / (y3 - y2) + x2)) {
r++;
} else if (y <= y2 && y >= y3 && x < ((x3 - x2) * (y - y2) / (y3 - y2) + x2)) {
r--;
}
}
return r!=0;
}
function pointInPolygon(vertices, x, y) {
var a, b, i, j;
var xpi, ypi, xpj, ypj;
var c = false;
for (i = 0; i < vertices.length; i++) {
j = (i + 1) % vertices.length;
a = vertices[i];
b = vertices[j];
xpi = a[0];
ypi = a[1];
xpj = b[0];
ypj = b[1];
if ((((ypi <= y) && (y < ypj)) || ((ypj <= y) && (y < ypi))) &&
(x < (xpj - xpi) * (y - ypi) / (ypj - ypi) + xpi)) {
c = !c;
}
}
return c;
}
// x 100 y 100 150 150 x 200 y 200
//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/math/is-point-in-poly [rev. #0]
function isPointInPoly(poly, x,y) {
var c = false;
for (var i = -1, l = poly.length, j = l - 1; ++i < l; j = i) {
var px = poly[i][0];
var py = poly[i][1];
var px2 = poly[j][0];
var py2 = poly[j][1];
if (((py <= y && y < py2) || (py2 <= y &&y < py))&& (x< (px2- px) * (y - py) / (py2 - py) + px)){
c = !c;
}
}
return c;
}
function isPointInPath(x, y, poly){
var num = poly.length;
var i = 0;
var j = num - 1;
var c = false;
for(;i<num;i++){
if (((poly[i][1] > y) != (poly[j][1] > y)) &&
(x < poly[i][0] + (poly[j][0] - poly[i][0]) * (y - poly[i][1]) /
(poly[j][1] - poly[i][1]))) {
c = true;
}
j = i
}
return c
}
document.addEventListener('click', function (e) {
var x = e.pageX - canvas.offsetLeft, y = e.pageY - canvas.offsetTop;
var invertM = mat2d.invert(mat2d.create(), m);// 逆阵
var xy2 = vec2.transformMat2d(vec2.create(), vec2.fromValues(x, y), m)
// 计算当前图形位置
var xy4 = vec2.transformMat2d(vec2.create(), rectPosition, m)
// 当前鼠标位置
var xy3 = vec2.transformMat2d(vec2.create(), vec2.fromValues(x, y), invertM)
// 正方形
if (contian(rectPosition, xy3) && contian(xy3, vec2.add(vec2.create(), rectPosition, rectPosition)))
{
console.log('rect命中');
}
// 贝塞尔曲线
// console.log('bezier', jsBezier._distanceFromCurve({ x: xy3[0], y: xy3[1] }, heartPoints[0]))
if (isCurve(x, y)) {
console.log('heartLine命2中');
}
if (pointInPolygon(heartLinePoints, xy3[0], xy3[1])) {
console.log('heartLine命中');
}
// 圆形
if (vec2.distance([400, 100], xy3) <= 50) {
console.log('circle命中');
}
// 多边形
if (contain(points, xy3[0], xy3[1])) {
console.log('polygon命中');
}
if (pointInPolygon(points, xy3[0], xy3[1])) {
console.log('polygon3命中');
}
if (isPointInPoly(points, xy3[0], xy3[1])) {
console.log('polygon4命中');
}
if (isContainPoint(points, xy3[0], xy3[1])) {
console.log('polygon5命中');
}
var p2 = points.reduce(function (a, b) { return a.concat(b); }, []);
if (linearRingsContainsXY(p2,0, [p2.length], 2, xy3[0], xy3[1])) {
console.log('polygon2命中');
}
// console.log(x, y, invertM);
})
</script>
</body>
</html>
上一篇： 子弹与敌机的碰撞
下一篇： 涅磐成凰--读Ajax缺陷有感