3
\$\begingroup\$

I created this to count points in an area.

$(document).ready(function () {
    var area = [
        [4, 4],
        [4, -4],
        [-4, -4],
        [-2, -2],
        [-2, 2],
        [-4, 4],
        [4, 4]
    ];
    var points = [
        [2, 1],
        [1, 2],
        [5, 3]
    ];
    var res = countPoints(area, points);
    $('#result').text("count : " + res);
});

function countPoints(area, points) {
    var count = 0;
    var xptsOfArea = [];
    var yptsOfArea = [];
    for (var ii = 0; ii < area.length; ii++) {
        xptsOfArea.push(area[ii][0]);
        yptsOfArea.push(area[ii][1]);
    }
    var xptsToCount = [];
    var yptsToCount = [];
    for (var ii = 0; ii < points.length; ii++) {
        xptsToCount.push(points[ii][0]);
        yptsToCount.push(points[ii][1]);
    }

    for (var ii = 0; ii < points.length; ii++) {
        if (checkFor(xptsOfArea, xptsToCount[ii], 0) && checkFor(yptsOfArea, yptsToCount[ii], 0)) {
            count += 1;
            console.log('[' + xptsToCount[ii] + ',' + yptsToCount[ii] + ']');
        }
    }
    return count;
}

function checkFor(area, point, position) {
    if (area.length == position) return true;
    else {
        if (area[position] > 0) {
            if (area[position] >= point) {
                return checkFor(area, point, ++position);
            } else {
                return false;
            }
        } else {
            if (area[position] <= point) {
                return checkFor(area, point, ++position);
            } else {
                return false;
            }
        }
    }
}

I want to make this open source, so I have three main concerns:

  1. Naming
  2. Complexity
  3. Idiomaticness
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Doesn't seem to work all that well: See this jsfiddle... (the canvas is drawn at x10) \$\endgroup\$
    – Flambino
    Commented Oct 16, 2014 at 17:15
  • \$\begingroup\$ @Flambino you should turn that into a snippeted answer and get lots of rep ;) \$\endgroup\$
    – konijn
    Commented Oct 17, 2014 at 2:36
  • \$\begingroup\$ @yozawiratama Please read this: en.wikipedia.org/wiki/Point_in_polygon Your logic is nowhere near complete \$\endgroup\$
    – konijn
    Commented Oct 17, 2014 at 2:42
  • \$\begingroup\$ @Flambino thanks for your correction i trying to fix that error, as koniji said, "may be you should turn that into a snippeted answer and get lots of rep" :) \$\endgroup\$ Commented Oct 17, 2014 at 2:43

1 Answer 1

1
\$\begingroup\$

As mentioned in the comments your code doesn't seem to do what you intend; however, if you take a look at the Jordan Curve theorem then one aspect of the proof demonstrates that if you consider a point and a continuous loop (or polygon) and take a ray emanating from that point then: if it intersects the loop (polygon) an odd number of times then the point is inside the loop (polygon); and if it intersects an even number of times then the point is outside the loop (polygon).

We can use this to implement a test for this property but it is useful to define some data structures first.

Starting with a namespace:

Geometery = {};

Then defining a point "class":

Geometery.Point2D = function(x,y){
    if ( isNaN( x ) || !isFinite( x ) )
    {
        throw "Point2D - x co-ordinate is not a number.";
    }
    if ( isNaN( y ) || !isFinite( y ) )
    {
        throw "Point2D - y co-ordinate is not a number.";
    }
    this.x = x;
    this.y = y;
}

Geometery.Point2D.prototype.equals = function( point ){
    return point === this
        || ( point instanceof Geometery.Point2D &&
             point.x === this.x &&
             point.y === this.y
           );
}

Geometery.Point2D.prototype.toString = function(){
    return '(' + this.x + ',' + this.y + ')';
}

Geometery.Point2D.prototype.DRAW_RADIUS = 2;

Geometery.Point2D.prototype.draw = function( context ){
    context.beginPath();
    context.arc( this.x, this.y, this.DRAW_RADIUS, 0, 2 * Math.PI, false );
    context.fill();
    context.closePath();
    context.stroke();
}

Next it is useful to have some common functionality for a set of points:

Geometery.Point2DSet = function(){
    this.points = [];

    var index;
    var point;
    for ( index = 0; index < arguments.length; index++ )
    {
        point = arguments[index];
        if ( !( point instanceof Geometery.Point2D ) )
        {
            throw "Point2DSet - Constructor argument is not a Point2D.";
        }
        this.points.push( point );
    }
};

(function(){
    var calcBoundaryCoord = function(coord,fnct){
        return function(){
            var index;
            var val = this.points.length ? this.points[0][coord] : undefined;
            for ( index = 1; index < this.points.length; ++index )
            {
                val = Math[fnct]( val, this.points[index][coord] );
            }
            return val;
        }
    };

    Geometery.Point2DSet.prototype.minX = (calcBoundaryCoord('x','min'));
    Geometery.Point2DSet.prototype.minY = (calcBoundaryCoord('y','min'));
    Geometery.Point2DSet.prototype.maxX = (calcBoundaryCoord('x','max'));
    Geometery.Point2DSet.prototype.maxY = (calcBoundaryCoord('y','max'));
})();

Geometery.Point2DSet.prototype.draw = function( context ){
    for ( var index = 0; index < this.points.length; ++index )
    {
        this.points[index].draw( context );
    }
}

Geometery.Point2DSet.prototype.toString = function(){
    return '<' + this.points.join(',') + '>';
}

This can then be extended to define a line "class":

Geometery.Line2D = function(){
    if ( arguments.length != 2 )
    {
        throw "Line2D - A line must have exactly two end-points.";
    }
    Geometery.Point2DSet.apply( this, arguments );
    if ( this.points[0].equals( this.points[1] ) )
    {
        throw "Line2D - A line must have two distinct end-points.";
    }
}

Geometery.Line2D.prototype = Object.create( Geometery.Point2DSet.prototype );
Geometery.Line2D.prototype.constructor = Geometery.Line2D;

Geometery.Line2D.prototype.getGradient = function(){
    var p1 = this.points[0];
    var p2 = this.points[1];
    if ( p1.x == p2.x )
    {
        if ( p1.y < p2.y )
        {
            return Number.POSITIVE_INFINITY;
        }
        else
        {
            return Number.NEGATIVE_INFINITY;
        }
    }
    return ( p2.y - p1.y ) / ( p2.x - p1.x );
}

Geometery.Line2D.prototype.draw = function( context, startPath, endPath ){
    if ( startPath !== false )
    {
        context.beginPath();
        context.moveTo(this.points[0].x, this.points[0].y );
    }
    context.lineTo(this.points[1].x, this.points[1].y );
    if ( endPath !== false )
    {
        context.closePath();
        context.stroke();
    }
}

We can also determine how many times a ray emanating vertically upwards from a point intersects a line:

Geometery.Line2D.prototype.countIntersectionsOfVerticalRayAbovePoint = function( point ){
    // If it is to the left/right of the bounding box then return null.
    if ( point.x < this.minX() || point.x > this.maxX() )
    {
        return 0;
    }
    // If it is above the bounding box then return ABOVE.
    if ( point.y > this.maxY() )
    {
        return 0;
    }
    // If it is below the bounding box then return BELOW.
    if ( point.y < this.minY() )
    {
        return 1;
    }
    var p1 = this.points[0];
    var p2 = this.points[1];
    // Check for the special case of a vertical line.
    if ( p1.x == p2.x )
    {
        return null;
    }
    var deltaY = point.y - this.getGradient()*(point.x - p1.x) - p1.y;
    if ( deltaY == 0 )
    {
        return null;
    }
    else if ( deltaY > 0 )
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

We can then extend the concept of a set of points to be a polygon:

Geometery.Polygon2D = function(){
    if ( arguments.length < 3 )
    {
        throw "Polygon2D - A polygon must have at least 3 vertices."
    }
    Geometery.Point2DSet.apply( this, arguments );
    this.lines = [];
    var p1 = this.points[ this.points.length - 1 ];
    var p2;
    for ( var index = 0; index < this.points.length; ++index )
    {
        p2 = this.points[ index ];
        this.lines.push( new Geometery.Line2D( p1, p2 ) );
        p1 = p2;
    }
}

Geometery.Polygon2D.prototype = Object.create( Geometery.Point2DSet.prototype );
Geometery.Polygon2D.prototype.constructor = Geometery.Polygon2D;

Geometery.Polygon2D.prototype.draw = function( context ){
    for ( var index = 0; index < this.lines.length; ++index )
    {
        this.lines[index].draw( context, index == 0, false );
    }
    context.closePath();
    context.fill();
    context.stroke();
    Geometery.Point2DSet.prototype.draw.apply( this, arguments );
}

And finally we can check if a point is contained within a polygon by checking the number of intersections with lines in the polygon (and if the point is on any lines):

Geometery.Polygon2D.INSIDE   = 1;
Geometery.Polygon2D.OUTSIDE  = -1;
Geometery.Polygon2D.ONBORDER = 0;

Geometery.Polygon2D.prototype.contains = function( point ){
    var numRaysCrossing = 0;
    for ( var index = 0; index < this.lines.length; ++index )
    {
        var count = this.lines[index].countIntersectionsOfVerticalRayAbovePoint( point );
        if ( count === null )
        {
            return Geometery.Polygon2D.ONBORDER;
        }
        numRaysCrossing += count;
    }
    if ( numRaysCrossing % 2 )
    {
        return Geometery.Polygon2D.INSIDE;
    }
    else
    {
        return Geometery.Polygon2D.OUTSIDE;
    }
}

You can write your own function to then iterate over multiple points and count if they are inside/outside a polygon.

Here is a basic example of using the above:

var polygon = new Geometery.Polygon2D(
    new Geometery.Point2D( 20, 140 ),
    new Geometery.Point2D( 20, 60 ),
    new Geometery.Point2D( 60, 20 ),
    new Geometery.Point2D( 100, 60 ),

    new Geometery.Point2D( 100, 84 ),
    new Geometery.Point2D( 95, 84 ),
    new Geometery.Point2D( 95, 70 ),
    new Geometery.Point2D( 75, 70 ),
    new Geometery.Point2D( 75, 85 ),
    new Geometery.Point2D( 100, 85 ),

    new Geometery.Point2D( 100, 124 ),
    new Geometery.Point2D( 95, 124 ),
    new Geometery.Point2D( 95, 110 ),
    new Geometery.Point2D( 75, 110 ),
    new Geometery.Point2D( 75, 125 ),
    new Geometery.Point2D( 100, 125 ),

    new Geometery.Point2D( 100, 140 ),
    new Geometery.Point2D( 65, 140 ),
    new Geometery.Point2D( 65, 110 ),
    new Geometery.Point2D( 55, 110 ),
    new Geometery.Point2D( 55, 140 )
);

var canvas = document.getElementById('myCanvas');
var context = canvas.getContext('2d');
context.fillStyle   = 'red';
context.lineWidth   = 1;
context.strokeStyle = 'black';

polygon.draw( context );

var points = new Geometery.Point2DSet(
    new Geometery.Point2D( 85, 117 ),
    new Geometery.Point2D( 85, 100 ),
    new Geometery.Point2D( 85, 85 ),
    new Geometery.Point2D( 85, 78 ),
    new Geometery.Point2D( 85, 60 ),
    new Geometery.Point2D( 85, 45 ),
    new Geometery.Point2D( 85, 40 ),
    new Geometery.Point2D( 100, 100 ),
    new Geometery.Point2D( 60, 100 ),
    new Geometery.Point2D( 60, 130 ),
    new Geometery.Point2D( 10, 10 )
);

for ( var i = 0; i < points.points.length; ++i )
{
    var point = points.points[i];
    var contains = polygon.contains( point );
    if ( contains == Geometery.Polygon2D.OUTSIDE )
    {
        context.fillStyle   = 'green';
    }
    else if ( contains == Geometery.Polygon2D.ONBORDER )
    {
        context.fillStyle   = 'yellow';
    }
    else
    {
        context.fillStyle   = 'blue';
    }
    point.draw( context );
}
\$\endgroup\$
1
  • \$\begingroup\$ oh my god, i really want to make cool code like yours, thanks for the inspiration, really thanks \$\endgroup\$ Commented Oct 20, 2014 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.