Determine if two points are on the same side of a line in javascript

Question

Suppose I have two points representing a line A, such as:

var A = [ { x: 385, y: 380 }, { x: 420, y: 400 }]

And I have two other points B and C such as:

var B = { x: 385, y: 420 }
var C = { x: 405, y: 423 }

How would I determine if B and C are both on the same side of line A? To add a little context, I am trying to do hit testing for a hexagon, where B is the center point of the hexagon, C is the current mouse position and A is each line of the hexagon. All of these points are essentially pixel coordinates where 0,0 is the upper left hand corner.

I don't need this to be blazing fast I am just trying to create the simplest possible hexagon hit test algorithm I can. My theory is that if I can determine that C is on the same side of each line of the hexagon as B then the hit test is successful. I have read several mathematical algorithms for doing this but they always seem to be in a different type of coordinate system and I'm struggling to translate it into something usable in javascript.

EDIT: here is my actual Hexagon function given the answer below. The answer to this question is in the update function.

var TILE_WIDTH = 70
var TILE_HEIGHT = 80

function Hexagon(x, y) {
    var normalColor = 'rgb(207, 226, 243)'
    var hilightColor = 'rgb(204, 204, 204)'
    var currentColor = normalColor

    var coords = new TileCoordinates(x, y)
    var points = [
        { x: coords.x, y: coords.y - TILE_HEIGHT / 2 },
        { x: coords.x + TILE_WIDTH / 2, y: coords.y - TILE_HEIGHT / 4 },
        { x: coords.x + TILE_WIDTH / 2, y: coords.y + TILE_HEIGHT / 4 },
        { x: coords.x, y: coords.y + TILE_HEIGHT / 2 },
        { x: coords.x - TILE_WIDTH / 2, y: coords.y + TILE_HEIGHT / 4 },
        { x: coords.x - TILE_WIDTH / 2, y: coords.y - TILE_HEIGHT / 4 },
    ]

    var sides = [
        [points[0], points[1]],
        [points[1], points[2]],
        [points[2], points[3]],
        [points[3], points[4]],
        [points[4], points[5]],
        [points[5], points[0]]
    ]

    this.update = function (totalTime, updateTime) {

        var B = coords
        var C = Mouse.state
        var inside = C != null
        if (inside) {
            for (i in sides) {
                var A = sides[i]
                var w = { y: A[1].x - A[0].x, x: -(A[1].y - A[0].y) }
                var P = A[1]

                inside = ((B.x - P.x) * w.x + (B.y - P.y) * w.y) * ((C.x - P.x) * w.x + (C.y - P.y) * w.y) > 0
                if (!inside) break
            }
        }

        if (inside)
            currentColor = hilightColor
        else
            currentColor = normalColor
    }

    this.draw = function (ctx) {
        ctx.fillStyle = currentColor
        ctx.strokeStyle = 'rgb(11, 83, 148)'
        ctx.beginPath()
        ctx.moveTo(points[0].x, points[0].y)
        ctx.lineTo(points[1].x, points[1].y)
        ctx.lineTo(points[2].x, points[2].y)
        ctx.lineTo(points[3].x, points[3].y)
        ctx.lineTo(points[4].x, points[4].y)
        ctx.lineTo(points[5].x, points[5].y)
        ctx.lineTo(points[0].x, points[0].y)
        ctx.fill()
        ctx.stroke()

        ctx.fillStyle = '#000'
        var text = coords.pos_x + ',' + coords.pos_y
        var measure = ctx.measureText(text)
        ctx.fillText(text, coords.x - measure.width / 2, coords.y + 12 + (TILE_HEIGHT / 4))
    }
}

// this is in a separate function because other objects that render into the hex
// need the pixel coordinates of the tile also
function TileCoordinates(x, y) {
    this.pos_x = x
    this.pos_y = y
    this.x = x * TILE_WIDTH + ((y + 1) * TILE_WIDTH / 2)
    this.y = (y + 1) * (3 / 4 * TILE_HEIGHT)
}

To determine same-sidedness I multiplied the results of B and C and if the result is > 0 then they are either both positive or both negative. I'm rendering and updating the hexagon into a canvas on a loop using setInterval.

If you aren't going to post an algorithm you've chosen, at least post some links to those you've found. Off the top of my head, if the line is AB and the points are C and D, then if the angles ABD and ABC are either both greater than 180 or both less than 180, D and C are "on the same side". — RobG
Not exactly answering your question, but stackoverflow.com/questions/217578/… has some good answers for polygon hit testing in general. — servn
possible duplicate of How to tell wether a point is right or left of a line — Mr.Wizard
Yes, I think thats pretty close. Though I was specifically trying to put it into javascript terms and in a way I could understand. Thanks. — justin.m.chase

btilly btilly · Accepted Answer · 2011-05-12T05:45:07

The line representing A is described by the vector v = { x: 420 - 385, y: 400 - 380 } = { x: 35, y: 20 } and the starting point P = { x: 385, y: 380 }. Given a vector (x, y) in 2d, the vector (y, -x) is always at right angles to it. So the vector w = { x: 20, y: -35 } is at right angles to v. Linear algebra tells us that the sign of (B - P) dot w tells us which side of the line you are on where dot is the standard dot product. (The line itself is at zero.)

Therefore in your example the calculation we need to do is this:

For B:
(B - P) dot w
  = { x: 385 - 385, y: 420 - 380 } dot { x: 20, y: -35 }
  = { x: 0, y: 40} dot { x: 20, y: -35 }
  = (0 * 20) + (40 * (-35))
  = -1400

For C:
(C - P dot w
  = { x: 405 - 385, y: 423 - 380 } dot { x: 20, y: -35 }
  = { x: 20, y: 43} dot { x: 20, y: -35 }
  = (20 * 20) + (43 * (-35))
  = -1105

Since the sign is the same, they are on the same side.

In fact we can say more. If you are at the starting point of A and are facing the ending point, both points will be on your left hand side. (The left side will be negative, the right side will be positive.)

Determine if two points are on the same side of a line in javascript

1 Answers