Determine whether a point is behind a line?

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
Jasoco
Inner party member
Posts: 3725
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

Determine whether a point is behind a line?

Post by Jasoco »

Say I have a plane, like the green line below, how would I determine that the red circle is in front of the line and the blue one is behind it mathematically?
help.png
help.png (2.72 KiB) Viewed 2699 times
Hard to explain in words. But I think you can understand what I'm saying.

I feel like it should be simple. A usage of maybe sin or cos or tan or sqrt or something. But I can't figure out the math and I've been playing around for a while. lol
User avatar
GVovkiv
Party member
Posts: 668
Joined: Fri Jan 15, 2021 7:29 am

Re: Determine whether a point is behind a line?

Post by GVovkiv »

Jasoco wrote: Mon Jan 24, 2022 6:25 pm Say I have a plane, like the green line below, how would I determine that the red circle is in front of the line and the blue one is behind it mathematically?

help.png

Hard to explain in words. But I think you can understand what I'm saying.

I feel like it should be simple. A usage of maybe sin or cos or tan or sqrt or something. But I can't figure out the math and I've been playing around for a while. lol
Something like LOS? https://en.wikipedia.org/wiki/Line_of_s ... deo_games)
User avatar
Froyok
Prole
Posts: 27
Joined: Tue Nov 16, 2021 4:53 pm
Contact:

Re: Determine whether a point is behind a line?

Post by Froyok »

A simple dot product should be enough:
- Your first vector is the line itself (let's say a line made from two points A and B)
- The second vector is the direction from the line toward the point you want to check (say point C, the vector is made from A and C).
- Perform a dot product between the two vectors.

The dot will give a result between -1.0 (say left) and 1.0 (right) while 0 means the point C is on the A-B line. The direction of your vectors will matter to define which side is left or right in the end.
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: Determine whether a point is behind a line?

Post by darkfrei »

If the point is above or below the line: Just lerp and compare y1 and y2.

If you check if the one point can see the second one - check the intersection between two lines: the green line and a sight line from one point to the other one.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Determine whether a point is behind a line?

Post by pgimeno »

Froyok is on the right track, that a dot product is the right tool for this task. His explanation may be a bit confusing though. So I'll try to clarify.

First, you need a vector that is *normal* to the plane or line. It's usually easy to get a normal vector, but it depends on how you have the line/plane stored.

In the case of a line:
- If your line is given by a direction vector d=(dx,dy), then you can calculate a normal vector using this formula: n=(-dy,dx).
- If your line is given by two points a=(ax,ay) and b=(bx,by) then calculate d=(bx-ax,by-ay) and then you have a direction vector, so use the formula above.

In the case of a plane:
- If you have a normal vector then you're ready.
- If you have three points, a=(ax,ay,az), b=(bx,by,bz) and c=(cx,cy,cz), calculate two vectors parallel to the plane, v1=(bx-ax,by-ay,bz-az) and v2=(cx-ax,cy-ay,cz-az). The cross product of these two vectors will give you a normal vector.
- If you have four points, ignore one and apply the three points case.

Besides the normal vector, you need a vector that goes from any point in the line or plane to the point you want to check. You will normally have one point in the line or plane, let's call it a=(ax,ay,az); if the point to check is p=(px,py,pz), calculate the vector v=(px-ax,py-ay,pz-az). Now calculate the dot product n·v, which is a number.
- If the dot product is positive, the normal vector and the point to check are on the same side.
- If the dot product is negative, they are on opposite sides.
- If it is zero, the point to check lies on the line or plane.

But since you have two points, and want to determine whether they are on the same side of the line or not, you need to calculate two dot products, one for each point: first calculate the vectors from a point in the plane or line to each of them, and then the dot product of each of these vectors with the normal. You'll get two numbers, one per dot product:
- If the two numbers have the same sign, they are on the same side of the line or plane.
- If they have opposite signs, they are on opposite sides.

Edit: Simple proof of concept:

Code: Select all

local function dot(x1, y1, z1, x2, y2, z2)
  return x1*x2 + y1*y2 + z1*z2
end

local function cross(x1, y1, z1, x2, y2, z2)
  return y1*z2 - y2*z1, z1*x2 - z2*x1, x1*y2 - x2*y1
end

-- Plane given by three points
local plane = {
   p1 = {200, 240, 0};
   p2 = {220, 300, 0};
   p3 = {200, 240, 200};
}
local p1 = {100, 500, 100}
local p2 = {0, 0, 200}

-- p2 tracks the mouse
function love.mousemoved(x, y)
  p2[1] = x
  p2[2] = y
end

-- Determine if points p1 and p2 are on the same side of the given plane
local function sameside(plane, p1, p2)
  -- Set ax, ay, az to a point in the plane
  local ax = plane.p1[1]
  local ay = plane.p1[2]
  local az = plane.p1[3]

  -- Find two vectors v1, v2 parallel to the plane
  local v1x = plane.p2[1] - ax
  local v1y = plane.p2[2] - ay
  local v1z = plane.p2[3] - az

  local v2x = plane.p3[1] - ax
  local v2y = plane.p3[2] - ay
  local v2z = plane.p3[3] - az

  -- Calculate a normal vector to the plane
  local nx, ny, nz = cross(v1x, v1y, v1z, v2x, v2y, v2z)

  -- Calculate the vector from a to p1 and from a to p2
  v1x, v1y, v1z = p1[1] - ax, p1[2] - ay, p1[3] - az
  v2x, v2y, v2z = p2[1] - ax, p2[2] - ay, p2[3] - az

  -- Calculate the dot product of each of the vectors with the normal
  local d1 = dot(v1x, v1y, v1z, nx, ny, nz)
  local d2 = dot(v2x, v2y, v2z, nx, ny, nz)

  -- Finally, return whether the signs match
  return (d1 < 0) == (d2 < 0)
end

function love.draw()
  love.graphics.line(plane.p1[1], plane.p1[2], plane.p2[1], plane.p2[2])
  love.graphics.rectangle("fill", p1[1]-1, p1[2]-1, 3, 3)
  love.graphics.rectangle("fill", p2[1]-1, p2[2]-1, 3, 3)

  if sameside(plane, p1, p2) then
    love.graphics.print("Same side")
  else
    love.graphics.print("Different sides")
  end
end
User avatar
Jasoco
Inner party member
Posts: 3725
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

Re: Determine whether a point is behind a line?

Post by Jasoco »

GVovkiv wrote: Mon Jan 24, 2022 6:28 pm Something like LOS? https://en.wikipedia.org/wiki/Line_of_s ... deo_games)
Yes actually. Basically I'm working with g3d and I have a third person camera but I also have large trees and buildings that get in between the camera and player so I'm hoping to figure out a way to check the "area" between the camera plane and the distance from the player to determine if an object should be hidden. (or made partially transparent, shrunken or whatever) Just so I'm not constantly looking at trees. lol
Froyok wrote: Mon Jan 24, 2022 7:24 pm A simple dot product should be enough:
- Your first vector is the line itself (let's say a line made from two points A and B)
- The second vector is the direction from the line toward the point you want to check (say point C, the vector is made from A and C).
- Perform a dot product between the two vectors.

The dot will give a result between -1.0 (say left) and 1.0 (right) while 0 means the point C is on the A-B line. The direction of your vectors will matter to define which side is left or right in the end.
You know, I posted this at work on my lunch and a half hour later thought "wait. Don't I have a function for this already?" It's actually on the Wiki I think. I used it in my recent 3D ray caster for doing thin walls and doors (Very expensive when you do it once for every line on screen multiplied by once for every door/line in a level) as I couldn't figure out a proper way to actually cast those.

I don't know how I forgot about that. But I thought maybe there was a simpler less expensive solution. But let me try and implement that method and see if it works first...
User avatar
Froyok
Prole
Posts: 27
Joined: Tue Nov 16, 2021 4:53 pm
Contact:

Re: Determine whether a point is behind a line?

Post by Froyok »

A dot product is a very, very cheap operation (see the dot function in Pgimeno very good example). Especially if you use a proper vector library (I believe there are a few available for love, potentially g3d has it own). Game engines usually perform tons of dot product per frame.
Last edited by Froyok on Tue Jan 25, 2022 11:26 pm, edited 1 time in total.
User avatar
Jasoco
Inner party member
Posts: 3725
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

Re: Determine whether a point is behind a line?

Post by Jasoco »

I got something that works after a lot of work. It's not the exact effect I wanted, but it does the job for now. Not the fault of the algorithm though. Just something I have to figure out.

Thanks for all the help so far.
Post Reply

Who is online

Users browsing this forum: Google [Bot] and 44 guests