I have a simple hexagonal grid, where I'm selecting a group of hexagons, which will then be filled with some random points.
Let me explain the exact procedure of generating the points:
- Using a list of hex coordinates I'm selecting hexagons.
- Group hexagons into areas.
- Store all edge points, for each area individually.
- Loop through areas:
- Calculate area boundary ( required for definig the range for random point generator )
- Draw area (bounding) square. (to see whether the computation was correct)
- Based on the bounding square min,max values generate random points
- Test if point is inside the area shape. (The shape is defined by area edge points)
- If the point passed the above test, it's the pushed into an array.
- loop through the array of points and draw them on screen.
Now I tried these two methods to determine whether a point lies inside a specific shape.
cn_PnPoly: function( P, V, n ){ ///// Point , array of vertices , array size ////
var cn = 0, vt = 0.0;
for (var i=0; i< (n-1); i++) { // edge from V[i] to V[i+1]
if (((V[i].y <= P.y) && (V[i+1].y > P.y)) // an upward crossing
|| ((V[i].y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing
// compute the actual edge-ray intersect x-coordinate
vt = (P.y - V[i].y) / (V[i+1].y - V[i].y);
if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect
++cn; // a valid crossing of y=P.y right of P.x
}
}
return (cn&1); // 0 if even (out), and 1 if odd (in)
},
result:
isInHexBounary: function( p, points, l ){ ///// Point , array of vertices , array size ////
var result = false;
for (i = 0, j = l - 1; i < l; j = i++) {
if ((points[i].y > p.y) != (points[j].y > p.y) && (p.x < (points[j].x - points[i].x) * (p.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
result = !result;
}
}
return result;
},
result:
I suppose the first method requires to have all the points in specific order, and that's why it's not working properly. But the second one seems to be working almost correct , apart from some parts. Any idea what I'm doing wrong?
<body>
<canvas width="420px" height="420px" id="myCanvas" style="margin:0; padding:0; border:1px solid #d3d3d3;"></canvas>
</body>
<script id="hexagon">
function Point( pos ) {
this.x = 0;
this.y = 0;
if( typeof( pos ) !== "undefined" ){
this.x = pos[0];
this.y = pos[1];
}
};
function FractionalHex( q_, r_ ) {
this.q = q_;
this.r = r_;
this.s = -q_-r_;
};
function Cell( _q, _r, _s ){ //// direction ///
this.q = _q;
this.r = _r;
this.s = _s;
this._hashID = null;
this.generateHashID();
}
Cell.prototype = {
constructor: Cell,
add: function( d ){
this.q += d.q;
this.r += d.r;
this.s += d.s;
this.generateHashID();
return this;
},
copy: function( c ){
this.set( c.q, c.r, c.s );
return this;
},
set: function( _q, _r, _s ){
this.q = _q;
this.r = _r;
this.s = _s;
this.generateHashID();
return this;
},
generateHashID: function(){
this._hashID = this.q+"."+this.r+"."+this.s;
},
getHashID: function(){
return this._hashID;
},
round: function(){
var q = Math.trunc(Math.round(this.q));
var r = Math.trunc(Math.round(this.r));
var s = Math.trunc(Math.round(this.s));
var q_diff = Math.abs(q - this.q);
var r_diff = Math.abs(r - this.r);
var s_diff = Math.abs(s - this.s);
if (q_diff > r_diff && q_diff > s_diff){
q = -r - s;
}else if (r_diff > s_diff){
r = -q - s;
}else{
s = -q - r;
}
return this.set( q, r, s );
}
}
var Hex = function( coords, l_ ){ //// [axial], [cartesian] , layout
this.coords = new Cell( coords[0], coords[1], coords[2] );
this.content = -2;
this.pos = this.coords; //// set primary coorinate type ///
this.neighbors = [];
this.layout = l_;
this.corners = [];
this.area_index = null;
this.center = this.get_center_p();
//this.id = this.generate_id( cart_coord );
this.colors = {
"base" : {
filling : "#008844",
border : "#FFDD88",
},
"selected": {
filling: "#00cc00"
},
"hovered": {
filling: "#006600"
},
"path" : {
filling: "#80ff00"
},
"obstacle" : {
filling: "#86592d"
},
"neighbor": {
filling: "#ffbf00"
}
}
this.states = {
"selected" : false,
"hovered" : false,
"isPath": false,
"isObstacle": false,
"isNeighbor": false
}
//var r_n = Math.floor((Math.random() * 4) + 1);
/*if( r_n == 4 ){
this.setContent( 2 );
}*/
this.generate_corners();
//this.add_neightbors();
};
Hex.prototype = {
constructor: Hex,
get_corner_offset: function( corner ){
var angle = 2.0 * Math.PI * (corner + this.layout.orientation.start_angle) / 6;
return new Point( [ size.x * Math.cos(angle), size.y * Math.sin(angle) ] );
},
generate_corners: function( h ){
var offset = null, angle = 0;
var size = this.layout.size;
for (var i = 0; i < 6; i++) {
angle = 2.0 * Math.PI * (i + this.layout.orientation.start_angle) / 6;
offset = new Point( [ size.x * Math.cos(angle), size.y * Math.sin(angle )] );
this.corners.push(
new Point( [ this.center.x + offset.x, this.center.y + offset.y ] )
);
}
},
draw: function( ctx ){
var points = this.corners;
ctx.beginPath();
ctx.moveTo( points[0].x, points[0].y );
for(var i = 1; i < points.length; i++){
var p = points[i];
ctx.lineTo(p.x, p.y);
}
ctx.closePath();
//// fill Hex ///
if( this.checkState("selected") ){
ctx.fillStyle = this.colors.selected.filling;
}else if( this.checkState("hovered") ){
ctx.fillStyle = this.colors.hovered.filling;
}else if( this.checkState("isPath") ){
ctx.fillStyle = this.colors.path.filling;
}else if( this.checkState("isNeighbor") ){
ctx.fillStyle = this.colors.neighbor.filling;
}else if( this.checkState("isObstacle") ){
ctx.fillStyle = this.colors.obstacle.filling;
}else{
ctx.fillStyle = this.colors.base.filling;
}
ctx.fill();
//// draw border ///
ctx.lineWidth = 1;
ctx.strokeStyle = "#19334d";
ctx.stroke();
this.draw_coords( ctx );
this.draw_center_point( ctx );
},
add_neighbor: function( neighbor ){
this.neighbors.push( neighbor );
},
show_neighbors: function(){
for( var nb = 0, nb_l = this.neighbors.length; nb < nb_l; nb++ ){
this.neighbors[nb].changeState("isNeighbor", true);
}
},
hide_neighbors: function(){
for( var nb = 0, nb_l = this.neighbors.length; nb < nb_l; nb++ ){
this.neighbors[nb].changeState("isNeighbor", false);
}
},
draw_coords: function( ctx ){
var text = this.coords.q+" : "+ this.coords.s;
var text_z = this.coords.r;
var metrics1 = ctx.measureText(text);
var metrics2 = ctx.measureText(text_z);
var w1 = metrics1.width;
var w2 = metrics2.width;
var h = 8;
ctx.font = h+'pt Calibri bold';
ctx.textAlign = 'center';
ctx.fillStyle = '#FFFFFF';
ctx.fillText(text, this.center.x, this.center.y + (h/2) - 5 );
ctx.fillText(text_z, this.center.x, this.center.y + (h/2) + 7 );
},
get_center_p: function(){
var M = this.layout.orientation;
var x = ( M.f0 * this.pos.q + M.f1 * this.pos.r ) * this.layout.size.x;
var y = ( M.f2 * this.pos.q + M.f3 * this.pos.r ) * this.layout.size.y;
return new Point([
x + this.layout.origin.x,
y + this.layout.origin.y
]);
},
draw_center_point: function( ctx ){
ctx.beginPath();
ctx.lineWidth="1";
ctx.fillStyle="red";
ctx.arc( this.center.x , this.center.y , 2, 0 ,2*Math.PI);
ctx.closePath();
ctx.stroke();
ctx.fill();
},
generate_id: function( coords ){
return parseInt( coords[0]+''+coords[1] );
},
checkState: function( state ){
return this.states[ state ];
},
changeState: function( state , value){
this.states[ state ] = value;
},
trigger: function( ev_name ){
if( this.events[ ev_name ] ){
this.events[ ev_name ].call( this );
}
},
setContent: function( type ){
this.content = type;
this.changeState( "isObstacle" , true );
},
hover: function(){
if( ! this.checkState("isPath") ){
this.trigger("hover");
}
},
clear_hover: function(){
if( ! this.checkState("isPath") ){
this.trigger("clear_hover");
}
},
select: function(){
this.trigger("select");
//this.show_neighbors();
},
unselect: function(){
this.trigger("unselect");
},
events: {
select: function(){
this.changeState("selected", true);
this.changeState("hovered", false);
},
unselect: function(){
this.changeState("selected", false);
},
hover: function(){
this.changeState("hovered", true);
},
clear_hover: function(){
this.changeState("hovered", false);
}
}
};
</script>
<script id="grid">
var Grid = function( size, hex_size, origin, ctx_pos, layout_type ){
this.size = size;
this.grid_r = size/2;
this.layout_type = layout_type;
this.layout = this.set_layout( this.layout_types[this.layout_type], hex_size, origin );
this.hexes = [];
this.hovered = [null, null]; //// [cur, prev] ///
this.selected = [null, null]; ///// [cur , prev] ///
this.cur_path = null;
this.dots = [];
this._list = [];
this._cel = new Cell();
this._directions = [new Cell(+1, 0, -1), new Cell(+1, -1, 0), new Cell(0, -1, +1),
new Cell(-1, 0, +1), new Cell(-1, +1, 0), new Cell(0, +1, -1)];
this.generate();
this.add_neighbors();
this.obs_arr = [];
this.add_obstacles( [
[0, 2],
[2, -3],
[0, -2],
[0, -1],
[2, -2],
[1, -1],
[1, -2],
[-1, -1]
] );
this.mouse = new Point();
this.mouse_events( new Point( ctx_pos ) );
}
Grid.prototype = {
constructor: Grid,
layout_types: {
"pointy": [
[ Math.sqrt(3.0), Math.sqrt(3.0) / 2.0, 0.0, 3.0 / 2.0], //// 2x2 forward matrix
[ Math.sqrt(3.0) / 3.0, -1.0 / 3.0, 0.0, 2.0 / 3.0], ///// 2x2 inverse matrix
0.5
], //// starting angle in multiples of 60° /////
"flat": [
[3.0 / 2.0, 0.0, Math.sqrt(3.0) / 2.0, Math.sqrt(3.0)], //// 2x2 forward matrix
[2.0 / 3.0, 0.0, -1.0 / 3.0, Math.sqrt(3.0) / 3.0], ///// 2x2 inverse matrix
1.0
]
},
set_layout: function( orn_type , hex_s_, ogn_ ){
return {
orientation: this.set_orientation( orn_type ), ///// orientation type ///
size: new Point( [ hex_s_ , hex_s_ ] ), ///// hex size ///
origin: new Point( ogn_ ) //// Grid center /////
}
},
set_orientation: function( opts ){ /// [0] : forward_matrix, [1] : inverse_matrix, [2] : starting_angle
return {
f0: opts[0][0], f1: opts[0][1], f2: opts[0][2], f3: opts[0][3], b0: opts[1][0], b1: opts[1][1], b2: opts[1][2], b3: opts[1][3], start_angle: opts[2]
}
},
get_hex_at_p: function( p ){ //// point ///
var M = this.layout.orientation;
var pt = new Point( [ (p.x - this.layout.origin.x) / this.layout.size.x, (p.y - this.layout.origin.y) / this.layout.size.y ] );
var q = M.b0 * pt.x + M.b1 * pt.y;
var r = M.b2 * pt.x + M.b3 * pt.y;
var c = this._cel.set( q, r, -q-r );
return c.round();
},
generate: function(){
var n_hex = null;
//var row = 0, col = 0;
for (var q = -this.grid_r; q <= this.grid_r; q++) {
var r1 = Math.max(-this.grid_r, -q - this.grid_r);
var r2 = Math.min(this.grid_r, -q + this.grid_r);
//col = q + this.grid_r;
//this.hexes[ col ] = [];
for (var r = r1; r <= r2; r++) {
//row = r - r1;
n_hex = new Hex( [ q, r, -q-r ], this.layout );
this.hexes[ n_hex.coords.getHashID() ] = n_hex;
this.dots = this.dots.concat( n_hex.corners.slice() );
}
}
this.dots = this.removeDuplicateDots( this.dots, ["x", "y"]);
},
removeDuplicateDots: function( c_arr, axis ){
var result = c_arr.reduce( function(a,b){
var i = a.findIndex(function( o ){ //// find same coordinate value in aray ////
return parseInt(o[axis[0]]) == parseInt(b[axis[0]]) && parseInt(o[axis[1]]) == parseInt(b[axis[1]]);
});
if( i < 0 ){ a.push(b); }
return a;
}, [] );
return result;
},
add_obstacles: function( obstacles ){
this.obs_arr = [];
var hex = null;
for( var h in this.hexes ){
hex = this.hexes[h];
for( var o = 0, o_l = obstacles.length; o < o_l; o++ ){
if( obstacles[o][0] == hex.coords.s && obstacles[o][1] == hex.coords.q ){
hex.setContent( 2 );
this.obs_arr.push( hex )
break;
}
}
}
this.obs_arr = this.generateAreaEdges();
},
hex_corner_offset : function ( corner ) {
var size = this.layout.size;
var angle = 2.0 * Math.PI * (this.layout.orientation.start_angle - corner) / 6;
return new Point([size.x * Math.cos(angle), size.y * Math.sin(angle)]);
},
point_add : function(p, q) {
return new Point([p.x + q.x, p.y + q.y]);
},
generateAreaEdges: function( ctx ){
var edges = [];
var self = this;
var neighbor = null;
var area_index = 0;
var areas = [];
self.obs_arr.forEach( function( hex ){
for( var dir = 0, nb_l = hex.neighbors.length; dir < nb_l; dir++ ){
neighbor = hex.neighbors[dir];
if( neighbor !== null && hex.area_index === null ){
if( neighbor.area_index !== null ){
hex.area_index = neighbor.area_index;
}
}
if( neighbor === null || hex.content != neighbor.content ){
var p1 = self.point_add( hex.center, self.hex_corner_offset( dir) );
var p2 = self.point_add( hex.center, self.hex_corner_offset( dir + 1 ) );
edges.push( p1, p2 );
}
}
if( hex.area_index === null ){
area_index++;
if( typeof(areas[ area_index ]) === "undefined" ){
areas[ area_index ] = [];
}
hex.area_index = area_index;
}
areas[ area_index ] = areas[ area_index ].concat( edges.slice() );
edges.length = 0; ///reset array ///
});
return areas;
},
drawDots: function( dots, color ){
for( var p = 0, p_l = dots.length; p < p_l; p++ ){
this.drawDot( dots[p].x, dots[p].y, color );
}
},
drawDot: function( x, y, color ){
ctx.beginPath();
ctx.lineWidth="1";
ctx.fillStyle= color || "blue";
ctx.arc( x , y , 1, 0 ,2*Math.PI);
ctx.closePath();
ctx.stroke();
ctx.fill();
},
drawShape: function( points, color ){
ctx.beginPath();
ctx.moveTo( points[0].x, points[0].y ); //// start shape ///
ctx.lineWidth = 2;
ctx.strokeStyle = color || "#000000";
for( var p = 0, p_l = points.length; p < p_l; p++ ){
ctx.lineTo( points[p].x, points[p].y );
}
ctx.lineTo( points[0].x, points[0].y ); //// close the shape ////
ctx.stroke();
ctx.closePath();
},
generateBoundingBox: function( points ){
var min = { x: points[0].x , y: points[0].y };
var max = { x: points[0].x , y: points[0].y };
for( var p = 1, l = points.length; p < l; p++ ){
if( points[p].x < min.x ){ min.x = points[p].x; }
if( points[p].y < min.y ){ min.y = points[p].y; }
if( points[p].x > max.x ){ max.x = points[p].x; }
if( points[p].y > max.y ){ max.y = points[p].y; }
}
return {
min: min,
max: max
};
/*return [
{ x: min.x, y: min.y },
{ x: max.x, y: min.y },
{ x: max.x, y: max.y},
{ x: min.x, y: max.y }
];*/
},
generateBoxShape: function( min, max ){
return [
{ x: min.x, y: min.y },
{ x: max.x, y: min.y },
{ x: max.x, y: max.y},
{ x: min.x, y: max.y }
]
},
cn_PnPoly: function( P, V, n ){ ///// Point , array of verticles , array size ////
var cn = 0, vt = 0.0;
for (var i=0; i< (n-1); i++) { // edge from V[i] to V[i+1]
if (((V[i].y <= P.y) && (V[i+1].y > P.y)) // an upward crossing
|| ((V[i].y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing
// compute the actual edge-ray intersect x-coordinate
vt = (P.y - V[i].y) / (V[i+1].y - V[i].y);
if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect
++cn; // a valid crossing of y=P.y right of P.x
}
}
return (cn&1); // 0 if even (out), and 1 if odd (in)
},
isInHexBounary: function( p, points, l ){ ///// Point , array of verticles , array size ////
var result = false;
for (i = 0, j = l - 1; i < l; j = i++) {
if ((points[i].y > p.y) != (points[j].y > p.y) && (p.x < (points[j].x - points[i].x) * (p.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
result = !result;
}
}
return result;
},
GenerateRandomPoints: function( b, s, n ){ //// boundaries, shape, amount ////
var points = [];
var keys = [];
var point = { x: 0, y: 0 };
if( s.length > 0 ){
while( points.length < n ){
point.x = Math.floor( ( Math.random() * ( b.max.x - b.min.x + 1 ) ) + b.min.x);
point.y = Math.floor( ( Math.random() * ( b.max.y - b.min.y +1 ) ) + b.min.y);
if( this.isInHexBounary( point, s, s.length ) ){
//console.log( point )
points.push({
x: point.x,
y: point.y
});
}
}
}
return points.slice();
},
drawBorders: function( ctx ){
var areas = this.obs_arr;
for( var a in areas ){
var bbox = this.generateBoundingBox( areas[a] );
var box_shape = this.generateBoxShape( bbox.min, bbox.max )
this.drawShape( box_shape, "red" );
var r_points = this.GenerateRandomPoints( bbox, areas[a], 1000 );
this.drawDots( r_points, "blue" );
for( var p = 0, p_l = areas[a].length; p < p_l; p += 2 ){
ctx.beginPath();
ctx.lineWidth="4";
ctx.strokeStyle="yellow";
ctx.moveTo( areas[a][p].x , areas[a][p].y);
if( ( p +1 ) < p_l ){
ctx.lineTo( areas[a][p+1].x , areas[a][p+1].y );
}
ctx.closePath();
ctx.stroke();
}
}
},
add_neighbors: function(){
var nbor = null, hex = null;
for( var h in this.hexes ){
hex = this.hexes[h];
var i, n, l = this._directions.length;
this._list.length = 0;//// reset array ///
for ( i = 0; i < l; i++ ) {
this._cel.copy( hex.coords );
this._cel.add( this._directions[i] );
n = this.hexes[ this._cel.getHashID() ];
if (typeof(n) == "undefined") { ///// if doesn't exists ////
this._list.push( null );
continue;
}
this._list.push(n);
}
hex.neighbors = this._list.slice(); //// take copy of the array ////
}
},
draw: function( ctx ){
for( var h in this.hexes ){
this.hexes[h].draw( ctx );
}
if( this.obs_arr.length > 0 ){
this.drawBorders( ctx )
}
if( this.dots.length > 0){
this.drawDots( this.dots , "yellow");
}
},
checkCollisions: function(){
var h_pos = this.get_hex_at_p( this.mouse );
var hex = this.hexes[ h_pos.getHashID() ];
if( typeof(hex) !== "undefined" ){
if( this.hovered[0] == null ){ //// cur
this.hovered[0] = hex;
this.hovered[0].hover();
}else{
this.hovered[1] = this.hovered[0];
this.hovered[0] = hex;
if( this.hovered[0].coords._hashID != this.hovered[1].coords._hashID ){
this.hovered[1].clear_hover();
this.hovered[1] = null;
}
}
this.hovered[0].hover();
}
},
mouse_events: function( ctx_pos ){
var self = this;
window.addEventListener( 'mousemove', function(e){
self.mouse.x = ( e.clientX - ctx_pos.x );
self.mouse.y = ( e.clientY - ctx_pos.y );
});
window.addEventListener( 'mousedown', function(e){
//console.log( "a",self.hovered[0].neighbors )
});
}
}
</script>
<script id="main">
var c_el = document.getElementById("myCanvas");
var ctx = c_el.getContext("2d");
var nGrid = new Grid( 6, 25, [ c_el.width / 2, c_el.height / 2 ], [c_el.getBoundingClientRect().left, c_el.getBoundingClientRect().top], "pointy" );
function animate(){
//window.requestAnimationFrame( animate );
ctx.clearRect(0, 0, c_el.width, c_el.height);
nGrid.checkCollisions();
nGrid.draw( ctx);
}
animate();
</script>
Aucun commentaire:
Enregistrer un commentaire