forked from miloyip/misc
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathconvexpolygon.htm
333 lines (257 loc) · 8.17 KB
/
convexpolygon.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
<!DOCTYPE html>
<!-- saved from url=(0041)http://tryhtml5.sinaapp.com/polycoll.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta charset="utf-8">
<title> 凸多边形 碰撞检测 </title>
<style>
html, body {
height : 100%;
background-color : #333333;
}
#info {
font-size : 12pt;
font-weight : bolder ;
color : white;
line-height :16pt;
padding :10px;
}
</style>
<script type="text/javascript">
// 判断 坐标点(px,py)是否在某IsoSquare内 (x,y 为菱形中心点坐标, h为高度,宽度为h*2)
function checkPointInIsoSquare( px, py, x, y, h){
return checkIsoSquareCollide(x,y,h,px,py,0);
}
// 判断 某两个IsoSquare是否相交 (x,y 为菱形中心点坐标, h为高度,宽度为h*2)
function checkIsoSquareCollide(x1,y1,h1, x2,y2,h2){
return Math.abs( (x1-x2)+ (y1 - y2)*2 )< h1+h2
&& Math.abs( (x1-x2)- (y1 - y2)*2 )< h1+h2;
}
// 判断 某两个矩形是否相交 (x,y 为矩形左上角坐标, w,h为宽高)
function checkRectCollide(x1,y1,w1,h1, x2,y2,w2,h2){
return x1-x2<w2 && y1-y2<h2 && x2-x1<w1 && y2-y1<h1 ;
}
// 判断 坐标点(px,py)是否在某矩形内 (x,y 为矩形左上角坐标, w,h为宽高)
function checkPointInRect(px, py, x, y, w, h){
return px>x && py>y && px-x<w && py-y<h ;
}
// 判断 坐标点(px,py)是否在某凸多边形内 (poly为多边形顶点坐标构成的二维数组)
function checkPointInPolygon( px, py, poly){
//这里偷懒了, 利用了多边形碰撞函数, 其实可以根据这种情况单独写一个更高效的函数.
return polygonCollision( poly ,[[px,py]]);
}
// 判断 某两个凸多边形是否相交 SAT算法. (poly为多边形顶点坐标构成的二维数组)
function polygonCollision(poly1, poly2) {
var len1 = poly1.length, len2 = poly2.length;
var currentPoint, nextPoint,
min1, max1, min2, max2, temp ,overlap ;
var cx,cy;
var k=0;
while(k<2){
// SAT算法的核心部分. 思路请参考网上的详细说明.
for(var i = 0; i < len1; i++){
currentPoint = poly1[i];
nextPoint = poly1[ (i+1)%len1 ];
cx = currentPoint[1] - nextPoint[1];
cy = nextPoint[0] - currentPoint[0];
//网上的一些实现还进行了下列操作(相当于向量标准化):
// var distance=Math.sqrt(cx*cx+cy*cy);
// cx/=distance;
// cy/=distance;
// 由于此函数只关心是否碰撞 而不关心如何碰撞碰撞程度等数值.
// 所以 此处可以省去了这部分操作,从而提升一点点性能.
min1 = max1 = poly1[0][0] * cx + poly1[0][1] * cy;
for(var j = 1; j < len1; j++){
temp = poly1[j][0] * cx + poly1[j][1] * cy;
if(temp > max1) max1 = temp;
else if(temp < min1) min1 = temp;
}
min2 = max2 = poly2[0][0] * cx + poly2[0][1] * cy;
for(j = 1; j < len2; j++){
temp = poly2[j][0] * cx + poly2[j][1] * cy;
if(temp > max2) max2 = temp;
else if(temp < min2) min2 = temp;
}
overlap = (min1 < min2) ? min2 - max1 : min1 - max2;
if(overlap >= 0) {
return false;
}
}
//如果 第二个多边形是一个"点",则在此刻退出;
if (len2<2){
return true;
}
k++;
//交换两个多边形
len1=len1^len2;
len2=len1^len2;
len1=len1^len2;
var _t=poly1;
poly1=poly2;
poly2=_t;
}
return true;
};
// Test if any hyperplane in polygon A satisfy SAT for polygon B.
// Return true if no separating hyperplane is found.
function polygonSAT(a, b) {
var alen = a.length;
var blen = b.length;
// For each edge PQ in A
var px = a[a.length - 1][0];
var py = a[a.length - 1][1];
for (var i = 0; i < alen; i++) {
var qx = a[i][0];
var qy = a[i][1];
// Compute normal vector of the hyperplane for edge PQ
// Assume winding orders of the polygons are counterclockwise
var nx = qy - py;
var ny = px - qx;
var NdotP = nx * px + ny * py;
// Test if all vertices V in B are outside of the hyperplane
var allOutside = true;
for (var j = 0; j < blen; j++) {
var vx = b[j][0];
var vy = b[j][1];
// det = N dot (V - P) = N dot V - N dot P
var det = nx * vx + ny * vy - NdotP;
if (det < 0) { // V is inside
allOutside = false;
break;
}
}
if (allOutside)
return false;
px = qx;
py = qy;
}
return true;
}
function polygonCollision(poly1, poly2) {
return polygonSAT(poly1, poly2) && polygonSAT(poly2, poly1);
}
//根据参数生成一个多边形 ( 变换后的 正n边形 )
function getPolygon(x,y,R, n,scaleX,scaleY){
if (!R){
return [ [x,y] ];
}
n=n||4;
scaleX=scaleX||1 , scaleY=scaleY||1;
var p1=[];
var perAng=Math.PI*2/n;
for (var i=0;i<n;i++){
var ang=perAng*i;
var _x= x+R*Math.cos(ang)*scaleX;
var _y= y+R*Math.sin(ang)*scaleY;
p1.push( [_x,_y]);
}
return p1;
}
//生成一个 IsoSquare菱形 (x,y 为菱形中心点坐标, h为高度,宽度为h*2)
function getIsoSquare(x,y,h){
return getPolygon(x,y,h,4,1,0.5);
}
//生成 [lower,higher]之间(闭区间)的整数随机数
function genRandom(lower, higher) {
lower = (lower||lower===0)?lower : 0;
higher = (higher||higher===0)?higher : 9999;
return Math.floor( (higher - lower + 1) * Math.random() ) + lower;
}
//在指定位置随机生成一个凸多边形
function getRandomPoly(x,y){
var r= genRandom(3,15)*5;
var n= genRandom(2,9);
var scaleX= genRandom(10,20)/10;
var scaleY= genRandom(10,20)/10;
var poly=getPolygon(x,y,r, n,scaleX,scaleY)
return poly;
}
//画点
function drawPoint(px,py,color){
context.fillStyle=color||"red";
context.fillRect(px-1,py-1,3,3);
}
//画多边形
function drawPolygon(poly, color){
context.strokeStyle=color||"black";
context.beginPath();
context.moveTo( poly[0][0] ,poly[0][1] );
for (var i=0,len=poly.length;i<len;i++){
var idx=(i+1)%len;
context.lineTo( poly[idx][0] ,poly[idx][1] );
}
context.stroke();
context.closePath();
}
//画IsoSquare菱形 (x,y 为菱形中心点坐标, h为高度,宽度为h*2)
function drawIsoSquare(x,y,h ,color){
var p=getIsoSquare(x,y,h);
drawPolygon(p,color);
}
// 碰撞的性能测试
function benchmark(n){
n=n||100;
var polyList=[];
var rs=[];
// Don't measure construction of polygons
// var t=Date.now();
for (var i=0;i<n;i++){
var x= genRandom(10,WIDTH-10);
var y= genRandom(10,HEIGHT-10);
var p=getRandomPoly(x,y);
// var coll=polygonCollision(DSquare,p);
// p.coll=coll;
polyList.push(p);
}
var t=Date.now();
for (var i = 0; i < n ; i++){
var p = polyList[i];
p.coll=polygonCollision(DSquare, p);
}
t=Date.now()-t;
document.getElementById("benchResult").innerHTML=t;
console.log("Benchmark result : "+t);
setTimeout(function(){
//绘制结果
for (var i=0;i<n;i++){
var p=polyList[i];
drawPolygon(p, p.coll?green:null);
}
drawPolygon(DSquare,"blue");
},10 );
}
// 画布参数
var canvas, context;
var WIDTH=640, HEIGHT=400;
//定义固定蓝色 IsoSquare菱形 的坐标和高度.
var DX=WIDTH/2, DY=HEIGHT/2 , DH=200 ;
var DSquare=getIsoSquare(DX, DY, DH);
var green="#00dd00";
function init(){
canvas=document.getElementById("canvas");
canvas.width=WIDTH;
canvas.height=HEIGHT;
canvas.style.backgroundColor="white";
context=canvas.getContext("2d");
context.lineWidth=1;
drawPolygon(DSquare,"blue");
canvas.addEventListener("click",function(event){
var x=event.offsetX||(event.pageX-canvas.offsetLeft),
y=event.offsetY||(event.pageY-canvas.offsetTop);
var ind=polygonCollision(DSquare, [[x,y]]);
drawPoint(x,y, ind?green:null);
var poly=getRandomPoly(x,y);
var coll=polygonCollision(DSquare,poly);
drawPolygon(poly, coll?green:null);
});
}
</script>
</head>
<body onload="init()">
<canvas id="canvas" width="640" height="400" style="background-color: white; "></canvas>
<div id="info">
点击画布, 在点击位置生成随机大小的 凸多边形, 如果生成的凸多边形与蓝色菱形相交,则为[绿色].<br>
点击的位置 如果在蓝色菱形内,则为[绿色].<br>
测试规模(随机生成指定数量的凸多边形与蓝色矩形进行碰撞检测)
<input type="text" value="123" id="pcount"><input type="button" value="点击开始测试" onclick="benchmark(document.getElementById('pcount').value)"> 测试耗时: <span id="benchResult">1</span>
</div>
<div id="menu_item" class="jjMenuItemDiv">Copy without formatting</div></body></html>