How can you determine a point is between two other points on a line segment

Question

Let s say you have a two dimensional plane with 2 points  called a and b  on it represented by an x integer and a y integer for each point   How can you determine if another point c is on the line segment defined by a and b   I use python most  but examples in any language would be helpful

User · Answer

Here is my solution with C  in Unity   private bool  isPointOnLine  Vector2 ptLineStart  Vector2 ptLineEnd  Vector2 ptPoint         bool bRes   false      if  Mathf Approximately ptPoint x  ptLineStart x     Mathf Approximately ptPoint x  ptLineEnd x                  if ptPoint y  gt  ptLineStart y  amp  amp  ptPoint y  lt  ptLineEnd y                        bRes   true                      else if  Mathf Approximately ptPoint y  ptLineStart y     Mathf Approximately ptPoint y  ptLineEnd y                  if ptPoint x  gt  ptLineStart x  amp  amp  ptPoint x  lt  ptLineEnd x                        bRes   true                      return bRes

User · Answer

c  From http   www faqs org faqs graphics algorithms-faq  -  Subject 1 02  How do I find the distance from a point to a line   Boolean Contains PointF from  PointF to  PointF pt  double epsilon                         double segmentLengthSqr    to X - from X     to X - from X     to Y - from Y     to Y - from Y               double r     pt X - from X     to X - from X     pt Y - from Y     to Y - from Y     segmentLengthSqr              if r lt 0    r gt 1  return false              double sl     from Y - pt Y     to X - from X  -  from X - pt X     to Y - from Y     System Math Sqrt segmentLengthSqr               return -epsilon  lt   sl  amp  amp  sl  lt   epsilon

User · Answer

Here s how I d do it   def distance a b       return sqrt  a x - b x   2    a y - b y   2   def is between a c b       return distance a c    distance c b     distance a b

User · Answer

I needed this for javascript for use in an html5 canvas for detecting if the users cursor was over or near a certain line  So I modified the answer given by Darius Bacon into coffeescript   is on    a b c  - gt         Return true if point c intersects the line segment from a to b          or the degenerate case that all 3 points are coincident      return  collinear a b c  and withincheck a b c    withincheck    a b c  - gt      if a 0     b 0          within a 0  c 0  b 0        else          within a 1  c 1  b 1    collinear    a b c  - gt         Return true if a  b  and c all lie on the same line         b 0 -a 0    c 1 -a 1    lt   c 0 -a 0    b 1 -a 1     1000  and   b 0 -a 0    c 1 -a 1    gt   c 0 -a 0    b 1 -a 1   - 1000   within    p q r  - gt         Return true if q is between p and r  inclusive        p  lt   q  lt   r or r  lt   q  lt   p

User · Answer

Here is some Java code that worked for me  boolean liesOnSegment Coordinate a  Coordinate b  Coordinate c                 double dotProduct    c x - a x     c x - b x     c y - a y     c y - b y       return  dotProduct  lt  0

User · Answer

Here is my solution with C  in Unity   private bool  isPointOnLine  Vector2 ptLineStart  Vector2 ptLineEnd  Vector2 ptPoint         bool bRes   false      if  Mathf Approximately ptPoint x  ptLineStart x     Mathf Approximately ptPoint x  ptLineEnd x                  if ptPoint y  gt  ptLineStart y  amp  amp  ptPoint y  lt  ptLineEnd y                        bRes   true                      else if  Mathf Approximately ptPoint y  ptLineStart y     Mathf Approximately ptPoint y  ptLineEnd y                  if ptPoint x  gt  ptLineStart x  amp  amp  ptPoint x  lt  ptLineEnd x                        bRes   true                      return bRes

User · Answer

Any point on the line segment  a  b   where a and b are vectors  can be expressed as a linear combination of the two vectors a and b   In other words  if c lies on the line segment  a  b    c   ma    1 - m b  where 0  lt   m  lt   1   Solving for m  we get   m    c x - b x   a x - b x     c y - b y   a y - b y    So  our test becomes  in Python    def is on a  b  c          Is c on the line segment ab          def  is zero  val            return -epsilon  lt  val  lt  epsilon      x1   a x - b x     x2   c x - b x     y1   a y - b y     y2   c y - b y      if  is zero x1  and  is zero y1             a and b are the same point            so check that c is the same as a and b         return  is zero x2  and  is zero y2       if  is zero x1             a and b are on same vertical line         m2   y2   1 0   y1         return  is zero x2  and 0  lt   m2  lt   1     elif  is zero y1             a and b are on same horizontal line         m1   x2   1 0   x1         return  is zero y2  and 0  lt   m1  lt   1     else          m1   x2   1 0   x1         if m1  lt  0 or m1  gt  1              return False         m2   y2   1 0   y1         return  is zero m2 - m1

User · Answer

Here s another approach      Lets assume the two points be A  x1 y1  and B  x2 y2  The equation of the line passing through those points is  x-x1   y-y1   x2-x1   y2-y1      just making equating the slopes    Point C  x3 y3  will lie between A  amp  B if    x3 y3 satisfies the above equation  x3 lies between x1  amp  x2 and y3 lies between y1  amp  y2  trivial check

User · Answer

Here s how I did it at school  I forgot why it is not a good idea   EDIT     Darius Bacon  cites a  Beautiful Code  book which contains an explanation why the belowed code is not a good idea      usr bin env python from   future   import division  epsilon   1e-6  class Point      def   init   self  x  y           self x  self y   x  y  class LineSegment               gt  gt  gt  ls   LineSegment Point 0 0   Point 2 4        gt  gt  gt  Point 1  2  in ls     True      gt  gt  gt  Point  5  1  in ls     True      gt  gt  gt  Point  5  1 1  in ls     False      gt  gt  gt  Point -1  -2  in ls     False      gt  gt  gt  Point  1  0 20000001  in ls     True      gt  gt  gt  Point  1  0 2001  in ls     False      gt  gt  gt  ls   LineSegment Point 1  1   Point 3  5        gt  gt  gt  Point 2  3  in ls     True      gt  gt  gt  Point 1 5  2  in ls     True      gt  gt  gt  Point 0  -1  in ls     False      gt  gt  gt  ls   LineSegment Point 1  2   Point 1  10        gt  gt  gt  Point 1  6  in ls     True      gt  gt  gt  Point 1  1  in ls     False      gt  gt  gt  Point 2  6  in ls      False      gt  gt  gt  ls   LineSegment Point -1  10   Point 5  10        gt  gt  gt  Point 3  10  in ls     True      gt  gt  gt  Point 6  10  in ls     False      gt  gt  gt  Point 5  10  in ls     True      gt  gt  gt  Point 3  11  in ls     False             def   init   self  a  b           if a x  gt  b x              a  b   b  a          self x0  self y0  self x1  self y1     a x  a y  b x  b y          self slope    self y1 - self y0     self x1 - self x0  if self x1    self x0 else None      def   contains   self  c           return  self x0  lt   c x  lt   self x1 and                 min self y0  self y1   lt   c y  lt   max self y0  self y1  and                  not self slope or -epsilon  lt   c y - self y c x    lt  epsilon        def y self  x                   return self slope    x - self x0    self y0  if   name         main         import  doctest     doctest testmod

User · Answer

how about just ensuring that the slope is the same and the point is between the others   given points  x1  y1  and  x2  y2    with x2   x1  and candidate point  a b   if   b-y1     a-x1     y2-y2     x2-x1   And x1  lt  a  lt  x2   Then  a b  must be on line between  x1 y1  and  x2  y2

User · Answer

Any point on the line segment  a  b   where a and b are vectors  can be expressed as a linear combination of the two vectors a and b   In other words  if c lies on the line segment  a  b    c   ma    1 - m b  where 0  lt   m  lt   1   Solving for m  we get   m    c x - b x   a x - b x     c y - b y   a y - b y    So  our test becomes  in Python    def is on a  b  c          Is c on the line segment ab          def  is zero  val            return -epsilon  lt  val  lt  epsilon      x1   a x - b x     x2   c x - b x     y1   a y - b y     y2   c y - b y      if  is zero x1  and  is zero y1             a and b are the same point            so check that c is the same as a and b         return  is zero x2  and  is zero y2       if  is zero x1             a and b are on same vertical line         m2   y2   1 0   y1         return  is zero x2  and 0  lt   m2  lt   1     elif  is zero y1             a and b are on same horizontal line         m1   x2   1 0   x1         return  is zero y2  and 0  lt   m1  lt   1     else          m1   x2   1 0   x1         if m1  lt  0 or m1  gt  1              return False         m2   y2   1 0   y1         return  is zero m2 - m1

User · Answer

The scalar product between  c-a  and  b-a  must be equal to the product of their lengths  this means that the vectors  c-a  and  b-a  are aligned and with the same direction   Moreover  the length of  c-a  must be less than or equal to that of  b-a   Pseudocode     epsilon   small constant  def isBetween a  b  c       lengthca2     c x - a x   c x - a x     c y - a y   c y - a y      lengthba2     b x - a x   b x - a x     b y - a y   b y - a y      if lengthca2  gt  lengthba2  return False     dotproduct    c x - a x   b x - a x     c y - a y   b y - a y      if dotproduct  lt  0 0  return False     if abs dotproduct dotproduct - lengthca2 lengthba2   gt  epsilon  return False      return True

User · Answer

Ok  lots of mentions of linear algebra  cross product of vectors  and this works in a real  ie continuous or floating point  space but the question specifically stated that the two points were expressed as integers and thus a cross product is not the correct solution although it can give an approximate solution   The correct solution is to use Bresenham s Line Algorithm between the two points and to see if the third point is one of the points on the line   If the points are sufficiently distant that calculating the algorithm is non-performant  and it d have to be really large for that to be the case  I m sure you could dig around and find optimisations

User · Answer

Ok  lots of mentions of linear algebra  cross product of vectors  and this works in a real  ie continuous or floating point  space but the question specifically stated that the two points were expressed as integers and thus a cross product is not the correct solution although it can give an approximate solution   The correct solution is to use Bresenham s Line Algorithm between the two points and to see if the third point is one of the points on the line   If the points are sufficiently distant that calculating the algorithm is non-performant  and it d have to be really large for that to be the case  I m sure you could dig around and find optimisations

User · Answer

Check if the cross product of b-a and c-a is0  that means all the points are collinear  If they are  check if c s coordinates are between a s and b s  Use either the x or the y coordinates  as long as a and b are separate on that axis  or they re the same on both    def is on a  b  c        Return true iff point c intersects the line segment from a to b          or the degenerate case that all 3 points are coincident      return  collinear a  b  c              and  within a x  c x  b x  if a x    b x else                   within a y  c y  b y     def collinear a  b  c        Return true iff a  b  and c all lie on the same line       return  b x - a x     c y - a y      c x - a x     b y - a y   def within p  q  r        Return true iff q is between p and r  inclusive        return p  lt   q  lt   r or r  lt   q  lt   p   This answer used to be a mess of three updates  The worthwhile info from them  Brian Hayes s chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background  Vincent s answer helped to improve this one  And it was Hayes who suggested testing only one of the x or the y coordinates  originally the code had and in place of if a x    b x else

User · Answer

Here is some Java code that worked for me  boolean liesOnSegment Coordinate a  Coordinate b  Coordinate c                 double dotProduct    c x - a x     c x - b x     c y - a y     c y - b y       return  dotProduct  lt  0

User · Answer

how about just ensuring that the slope is the same and the point is between the others   given points  x1  y1  and  x2  y2    with x2   x1  and candidate point  a b   if   b-y1     a-x1     y2-y2     x2-x1   And x1  lt  a  lt  x2   Then  a b  must be on line between  x1 y1  and  x2  y2

User · Answer

You can use the wedge and dot product   def dot v w   return v x w x   v y w y def wedge v w   return v x w y - v y w x  def is between a b c      v   a - b    w   b - c    return wedge v w     0 and dot v w   gt  0

User · Answer

Here s how I d do it   def distance a b       return sqrt  a x - b x   2    a y - b y   2   def is between a c b       return distance a c    distance c b     distance a b

User · Answer

how about just ensuring that the slope is the same and the point is between the others   given points  x1  y1  and  x2  y2    with x2   x1  and candidate point  a b   if   b-y1     a-x1     y2-y2     x2-x1   And x1  lt  a  lt  x2   Then  a b  must be on line between  x1 y1  and  x2  y2

User · Answer

The scalar product between  c-a  and  b-a  must be equal to the product of their lengths  this means that the vectors  c-a  and  b-a  are aligned and with the same direction   Moreover  the length of  c-a  must be less than or equal to that of  b-a   Pseudocode     epsilon   small constant  def isBetween a  b  c       lengthca2     c x - a x   c x - a x     c y - a y   c y - a y      lengthba2     b x - a x   b x - a x     b y - a y   b y - a y      if lengthca2  gt  lengthba2  return False     dotproduct    c x - a x   b x - a x     c y - a y   b y - a y      if dotproduct  lt  0 0  return False     if abs dotproduct dotproduct - lengthca2 lengthba2   gt  epsilon  return False      return True

User · Answer

C  version of Jules  answer   public static double CalcDistanceBetween2Points double x1  double y1  double x2  double y2        return Math Sqrt Math Pow  x1-x2  2    Math Pow  y1-y2  2       public static bool PointLinesOnLine  double x  double y  double x1  double y1  double x2  double y2  double allowedDistanceDifference        double dist1   CalcDistanceBetween2Points x  y  x1  y1       double dist2   CalcDistanceBetween2Points x  y  x2  y2       double dist3   CalcDistanceBetween2Points x1  y1  x2  y2       return Math Abs dist3 -  dist1   dist2    lt   allowedDistanceDifference

User · Answer

Check if the cross product of b-a and c-a is0  that means all the points are collinear  If they are  check if c s coordinates are between a s and b s  Use either the x or the y coordinates  as long as a and b are separate on that axis  or they re the same on both    def is on a  b  c        Return true iff point c intersects the line segment from a to b          or the degenerate case that all 3 points are coincident      return  collinear a  b  c              and  within a x  c x  b x  if a x    b x else                   within a y  c y  b y     def collinear a  b  c        Return true iff a  b  and c all lie on the same line       return  b x - a x     c y - a y      c x - a x     b y - a y   def within p  q  r        Return true iff q is between p and r  inclusive        return p  lt   q  lt   r or r  lt   q  lt   p   This answer used to be a mess of three updates  The worthwhile info from them  Brian Hayes s chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background  Vincent s answer helped to improve this one  And it was Hayes who suggested testing only one of the x or the y coordinates  originally the code had and in place of if a x    b x else

User · Answer

You can do it by solving the line equation for that line segment with the point coordinates you will know whether that point is on the line and then checking the bounds of the segment to know whether it is inside or outside of it  You can apply some threshold because well it is somewhere in space mostl likely defined by a floating point value and you must not hit the exact one  Example in php function getLineDefinition  p1 array 0 0    p2 array 0 0              k     p1 1 - p2 1     p1 0 - p2 0         q    p1 1 - k  p1 0            return array  k   q           function isPointOnLineSegment  line array array 0 0  array 0 0     pt array 0 0                GET THE LINE DEFINITION y   k x   q AS array k  q        def   getLineDefinition  line 0    line 1                use the line definition to find y for the x of your point      y    def 0   pt 0   def 1         yMin   min  line 0  1    line 1  1         yMax   max  line 0  1    line 1  1            exclude y values that are outside this segments bounds     if  y gt  yMax     y lt  yMin  return false              calculate the difference of your points y value from the reference value calculated from lines definition         in ideal cases this would equal 0 but we are dealing with floating point values so we need some threshold value not to lose results        this is up to you to fine tune      diff   abs  pt 1 - y             thr   0 000001           return  diff lt   thr

User · Answer

Using a more geometric approach  calculate the following distances   ab   sqrt  a x-b x   2    a y-b y   2  ac   sqrt  a x-c x   2    a y-c y   2  bc   sqrt  b x-c x   2    b y-c y   2    and test whether ac bc equals ab   is on segment   abs ac   bc - ab   lt  EPSILON   That s because there are three possibilities    The 3 points form a triangle    ac bc   ab They are collinear and c is outside the ab segment    ac bc   ab They are collinear and c is inside the ab segment    ac bc   ab

User · Answer

Check if the cross product of b-a and c-a is0  that means all the points are collinear  If they are  check if c s coordinates are between a s and b s  Use either the x or the y coordinates  as long as a and b are separate on that axis  or they re the same on both    def is on a  b  c        Return true iff point c intersects the line segment from a to b          or the degenerate case that all 3 points are coincident      return  collinear a  b  c              and  within a x  c x  b x  if a x    b x else                   within a y  c y  b y     def collinear a  b  c        Return true iff a  b  and c all lie on the same line       return  b x - a x     c y - a y      c x - a x     b y - a y   def within p  q  r        Return true iff q is between p and r  inclusive        return p  lt   q  lt   r or r  lt   q  lt   p   This answer used to be a mess of three updates  The worthwhile info from them  Brian Hayes s chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background  Vincent s answer helped to improve this one  And it was Hayes who suggested testing only one of the x or the y coordinates  originally the code had and in place of if a x    b x else

User · Answer

Here s how I did it at school  I forgot why it is not a good idea   EDIT     Darius Bacon  cites a  Beautiful Code  book which contains an explanation why the belowed code is not a good idea      usr bin env python from   future   import division  epsilon   1e-6  class Point      def   init   self  x  y           self x  self y   x  y  class LineSegment               gt  gt  gt  ls   LineSegment Point 0 0   Point 2 4        gt  gt  gt  Point 1  2  in ls     True      gt  gt  gt  Point  5  1  in ls     True      gt  gt  gt  Point  5  1 1  in ls     False      gt  gt  gt  Point -1  -2  in ls     False      gt  gt  gt  Point  1  0 20000001  in ls     True      gt  gt  gt  Point  1  0 2001  in ls     False      gt  gt  gt  ls   LineSegment Point 1  1   Point 3  5        gt  gt  gt  Point 2  3  in ls     True      gt  gt  gt  Point 1 5  2  in ls     True      gt  gt  gt  Point 0  -1  in ls     False      gt  gt  gt  ls   LineSegment Point 1  2   Point 1  10        gt  gt  gt  Point 1  6  in ls     True      gt  gt  gt  Point 1  1  in ls     False      gt  gt  gt  Point 2  6  in ls      False      gt  gt  gt  ls   LineSegment Point -1  10   Point 5  10        gt  gt  gt  Point 3  10  in ls     True      gt  gt  gt  Point 6  10  in ls     False      gt  gt  gt  Point 5  10  in ls     True      gt  gt  gt  Point 3  11  in ls     False             def   init   self  a  b           if a x  gt  b x              a  b   b  a          self x0  self y0  self x1  self y1     a x  a y  b x  b y          self slope    self y1 - self y0     self x1 - self x0  if self x1    self x0 else None      def   contains   self  c           return  self x0  lt   c x  lt   self x1 and                 min self y0  self y1   lt   c y  lt   max self y0  self y1  and                  not self slope or -epsilon  lt   c y - self y c x    lt  epsilon        def y self  x                   return self slope    x - self x0    self y0  if   name         main         import  doctest     doctest testmod

User · Answer

The scalar product between  c-a  and  b-a  must be equal to the product of their lengths  this means that the vectors  c-a  and  b-a  are aligned and with the same direction   Moreover  the length of  c-a  must be less than or equal to that of  b-a   Pseudocode     epsilon   small constant  def isBetween a  b  c       lengthca2     c x - a x   c x - a x     c y - a y   c y - a y      lengthba2     b x - a x   b x - a x     b y - a y   b y - a y      if lengthca2  gt  lengthba2  return False     dotproduct    c x - a x   b x - a x     c y - a y   b y - a y      if dotproduct  lt  0 0  return False     if abs dotproduct dotproduct - lengthca2 lengthba2   gt  epsilon  return False      return True

User · Answer

Check if the cross product of  b-a  and  c-a  is 0  as tells Darius Bacon  tells you if the points a  b and c are aligned   But  as you want to know if c is between a and b  you also have to check that the dot product of  b-a  and  c-a  is positive and is less than the square of the distance between a and b   In non-optimized pseudocode   def isBetween a  b  c       crossproduct    c y - a y     b x - a x  -  c x - a x     b y - a y         compare versus epsilon for floating point values  or    0 if using integers     if abs crossproduct   gt  epsilon          return False      dotproduct    c x - a x     b x - a x     c y - a y   b y - a y      if dotproduct  lt  0          return False      squaredlengthba    b x - a x   b x - a x     b y - a y   b y - a y      if dotproduct  gt  squaredlengthba          return False      return True

User · Answer

Here s how I d do it   def distance a b       return sqrt  a x - b x   2    a y - b y   2   def is between a c b       return distance a c    distance c b     distance a b

User · Answer

The length of the segment is not important  thus using a square root is not required and should be avoided since we could lose some precision   class Point      def   init   self  x  y           self x   x         self y   y  class Segment      def   init   self  a  b           self a   a         self b   b      def is between self  c             Check if slope of a to c is the same as a to b             that is  when moving from a x to c x  c y must be proportionally           increased than it takes to get from a x to b x              Then  c x must be between a x and b x  and c y must be between a y and b y              gt  c is after a and before b  or the opposite           that is  the absolute value of cmp a  b    cmp b  c  is either 0   1   -1                or 1   c    a or c    b           a  b   self a  self b                       return   b x - a x     c y - a y      c x - a x     b y - a y  and                  abs cmp a x  c x    cmp b x  c x    lt   1 and                 abs cmp a y  c y    cmp b y  c y    lt   1    Some random example of usage    a   Point 0 0  b   Point 50 100  c   Point 25 50  d   Point 0 8   print Segment a b  is between c  print Segment a b  is between d

User · Answer

Using a more geometric approach  calculate the following distances   ab   sqrt  a x-b x   2    a y-b y   2  ac   sqrt  a x-c x   2    a y-c y   2  bc   sqrt  b x-c x   2    b y-c y   2    and test whether ac bc equals ab   is on segment   abs ac   bc - ab   lt  EPSILON   That s because there are three possibilities    The 3 points form a triangle    ac bc   ab They are collinear and c is outside the ab segment    ac bc   ab They are collinear and c is inside the ab segment    ac bc   ab

User · Answer

Check if the cross product of  b-a  and  c-a  is 0  as tells Darius Bacon  tells you if the points a  b and c are aligned   But  as you want to know if c is between a and b  you also have to check that the dot product of  b-a  and  c-a  is positive and is less than the square of the distance between a and b   In non-optimized pseudocode   def isBetween a  b  c       crossproduct    c y - a y     b x - a x  -  c x - a x     b y - a y         compare versus epsilon for floating point values  or    0 if using integers     if abs crossproduct   gt  epsilon          return False      dotproduct    c x - a x     b x - a x     c y - a y   b y - a y      if dotproduct  lt  0          return False      squaredlengthba    b x - a x   b x - a x     b y - a y   b y - a y      if dotproduct  gt  squaredlengthba          return False      return True

User · Answer

The length of the segment is not important  thus using a square root is not required and should be avoided since we could lose some precision   class Point      def   init   self  x  y           self x   x         self y   y  class Segment      def   init   self  a  b           self a   a         self b   b      def is between self  c             Check if slope of a to c is the same as a to b             that is  when moving from a x to c x  c y must be proportionally           increased than it takes to get from a x to b x              Then  c x must be between a x and b x  and c y must be between a y and b y              gt  c is after a and before b  or the opposite           that is  the absolute value of cmp a  b    cmp b  c  is either 0   1   -1                or 1   c    a or c    b           a  b   self a  self b                       return   b x - a x     c y - a y      c x - a x     b y - a y  and                  abs cmp a x  c x    cmp b x  c x    lt   1 and                 abs cmp a y  c y    cmp b y  c y    lt   1    Some random example of usage    a   Point 0 0  b   Point 50 100  c   Point 25 50  d   Point 0 8   print Segment a b  is between c  print Segment a b  is between d

User · Answer

c  From http   www faqs org faqs graphics algorithms-faq  -  Subject 1 02  How do I find the distance from a point to a line   Boolean Contains PointF from  PointF to  PointF pt  double epsilon                         double segmentLengthSqr    to X - from X     to X - from X     to Y - from Y     to Y - from Y               double r     pt X - from X     to X - from X     pt Y - from Y     to Y - from Y     segmentLengthSqr              if r lt 0    r gt 1  return false              double sl     from Y - pt Y     to X - from X  -  from X - pt X     to Y - from Y     System Math Sqrt segmentLengthSqr               return -epsilon  lt   sl  amp  amp  sl  lt   epsilon

User · Answer

Check if the cross product of  b-a  and  c-a  is 0  as tells Darius Bacon  tells you if the points a  b and c are aligned   But  as you want to know if c is between a and b  you also have to check that the dot product of  b-a  and  c-a  is positive and is less than the square of the distance between a and b   In non-optimized pseudocode   def isBetween a  b  c       crossproduct    c y - a y     b x - a x  -  c x - a x     b y - a y         compare versus epsilon for floating point values  or    0 if using integers     if abs crossproduct   gt  epsilon          return False      dotproduct    c x - a x     b x - a x     c y - a y   b y - a y      if dotproduct  lt  0          return False      squaredlengthba    b x - a x   b x - a x     b y - a y   b y - a y      if dotproduct  gt  squaredlengthba          return False      return True

User · Answer

Here s a different way to go about it  with code given in C    Given two points  l1 and l2 it s trivial to express the line segment between them as  l1   A l2 - l1    where 0  lt   A  lt   1  This is known as the vector representation of a line if you re interested any more beyond just using it for this problem  We can split out the x and y components of this  giving   x   l1 x   A l2 x - l1 x  y   l1 y   A l2 y - l1 y    Take a point  x  y  and substitute its x and y components into these two expressions to solve for A  The point is on the line if the solutions for A in both expressions are equal and 0  lt   A  lt   1  Because solving for A requires division  there s special cases that need handling to stop division by zero when the line segment is horizontal or vertical  The final solution is as follows      Vec2 is a simple x y struct - it could very well be named Point for this use  bool isBetween double a  double b  double c           return if c is between a and b     double larger    a  gt   b    a   b      double smaller    a    larger    a   b       return c  lt   larger  amp  amp  c  gt   smaller     bool pointOnLine Vec2 lt double gt  p  Vec2 lt double gt  l1  Vec2 lt double gt  l2        if l2 x - l1 x    0  return isBetween l1 y  l2 y  p y      vertical line     if l2 y - l1 y    0  return isBetween l1 x  l2 x  p x      horizontal line      double Ax    p x - l1 x     l2 x - l1 x       double Ay    p y - l1 y     l2 y - l1 y           We want Ax    Ay  so check if the difference is very small  floating        point comparison is fun        return fabs Ax - Ay   lt  0 000001  amp  amp  Ax  gt   0 0  amp  amp  Ax  lt   1 0

User · Answer

Check if the cross product of  b-a  and  c-a  is 0  as tells Darius Bacon  tells you if the points a  b and c are aligned   But  as you want to know if c is between a and b  you also have to check that the dot product of  b-a  and  c-a  is positive and is less than the square of the distance between a and b   In non-optimized pseudocode   def isBetween a  b  c       crossproduct    c y - a y     b x - a x  -  c x - a x     b y - a y         compare versus epsilon for floating point values  or    0 if using integers     if abs crossproduct   gt  epsilon          return False      dotproduct    c x - a x     b x - a x     c y - a y   b y - a y      if dotproduct  lt  0          return False      squaredlengthba    b x - a x   b x - a x     b y - a y   b y - a y      if dotproduct  gt  squaredlengthba          return False      return True

User · Answer

Here s how I d do it   def distance a b       return sqrt  a x - b x   2    a y - b y   2   def is between a c b       return distance a c    distance c b     distance a b

User · Answer

The length of the segment is not important  thus using a square root is not required and should be avoided since we could lose some precision   class Point      def   init   self  x  y           self x   x         self y   y  class Segment      def   init   self  a  b           self a   a         self b   b      def is between self  c             Check if slope of a to c is the same as a to b             that is  when moving from a x to c x  c y must be proportionally           increased than it takes to get from a x to b x              Then  c x must be between a x and b x  and c y must be between a y and b y              gt  c is after a and before b  or the opposite           that is  the absolute value of cmp a  b    cmp b  c  is either 0   1   -1                or 1   c    a or c    b           a  b   self a  self b                       return   b x - a x     c y - a y      c x - a x     b y - a y  and                  abs cmp a x  c x    cmp b x  c x    lt   1 and                 abs cmp a y  c y    cmp b y  c y    lt   1    Some random example of usage    a   Point 0 0  b   Point 50 100  c   Point 25 50  d   Point 0 8   print Segment a b  is between c  print Segment a b  is between d

User · Answer

Ok  lots of mentions of linear algebra  cross product of vectors  and this works in a real  ie continuous or floating point  space but the question specifically stated that the two points were expressed as integers and thus a cross product is not the correct solution although it can give an approximate solution   The correct solution is to use Bresenham s Line Algorithm between the two points and to see if the third point is one of the points on the line   If the points are sufficiently distant that calculating the algorithm is non-performant  and it d have to be really large for that to be the case  I m sure you could dig around and find optimisations

User · Answer

Here s how I did it at school  I forgot why it is not a good idea   EDIT     Darius Bacon  cites a  Beautiful Code  book which contains an explanation why the belowed code is not a good idea      usr bin env python from   future   import division  epsilon   1e-6  class Point      def   init   self  x  y           self x  self y   x  y  class LineSegment               gt  gt  gt  ls   LineSegment Point 0 0   Point 2 4        gt  gt  gt  Point 1  2  in ls     True      gt  gt  gt  Point  5  1  in ls     True      gt  gt  gt  Point  5  1 1  in ls     False      gt  gt  gt  Point -1  -2  in ls     False      gt  gt  gt  Point  1  0 20000001  in ls     True      gt  gt  gt  Point  1  0 2001  in ls     False      gt  gt  gt  ls   LineSegment Point 1  1   Point 3  5        gt  gt  gt  Point 2  3  in ls     True      gt  gt  gt  Point 1 5  2  in ls     True      gt  gt  gt  Point 0  -1  in ls     False      gt  gt  gt  ls   LineSegment Point 1  2   Point 1  10        gt  gt  gt  Point 1  6  in ls     True      gt  gt  gt  Point 1  1  in ls     False      gt  gt  gt  Point 2  6  in ls      False      gt  gt  gt  ls   LineSegment Point -1  10   Point 5  10        gt  gt  gt  Point 3  10  in ls     True      gt  gt  gt  Point 6  10  in ls     False      gt  gt  gt  Point 5  10  in ls     True      gt  gt  gt  Point 3  11  in ls     False             def   init   self  a  b           if a x  gt  b x              a  b   b  a          self x0  self y0  self x1  self y1     a x  a y  b x  b y          self slope    self y1 - self y0     self x1 - self x0  if self x1    self x0 else None      def   contains   self  c           return  self x0  lt   c x  lt   self x1 and                 min self y0  self y1   lt   c y  lt   max self y0  self y1  and                  not self slope or -epsilon  lt   c y - self y c x    lt  epsilon        def y self  x                   return self slope    x - self x0    self y0  if   name         main         import  doctest     doctest testmod

User · Answer

The length of the segment is not important  thus using a square root is not required and should be avoided since we could lose some precision   class Point      def   init   self  x  y           self x   x         self y   y  class Segment      def   init   self  a  b           self a   a         self b   b      def is between self  c             Check if slope of a to c is the same as a to b             that is  when moving from a x to c x  c y must be proportionally           increased than it takes to get from a x to b x              Then  c x must be between a x and b x  and c y must be between a y and b y              gt  c is after a and before b  or the opposite           that is  the absolute value of cmp a  b    cmp b  c  is either 0   1   -1                or 1   c    a or c    b           a  b   self a  self b                       return   b x - a x     c y - a y      c x - a x     b y - a y  and                  abs cmp a x  c x    cmp b x  c x    lt   1 and                 abs cmp a y  c y    cmp b y  c y    lt   1    Some random example of usage    a   Point 0 0  b   Point 50 100  c   Point 25 50  d   Point 0 8   print Segment a b  is between c  print Segment a b  is between d

User · Answer

An answer in C  using a Vector2D class  public static bool IsOnSegment this Segment2D  this  Point2D c  double tolerance         var distanceSquared   tolerance tolerance          Start of segment to test point vector      var v   new Vector2D   this P0  c   To3D            Segment vector      var s   new Vector2D   this P0   this P1   To3D            Dot product of s      var ss   s s          k is the scalar we multiply s by to get the projection of c onto s         where we assume s is an infinte line      var k   v s ss          Convert our tolerance to the units of the scalar quanity k      var kd   tolerance   Math Sqrt  ss            Check that the projection is within the bounds      if  k  lt   -kd    k  gt    1 kd                  return false                 Find the projection point      var p   k s          Find the vector between test point and it s projection      var vp    v - p           Check the distance is within tolerance       return vp   vp  lt  distanceSquared      Note that  s   s   is the dot product of the segment vector via operator overloading in C   The key is taking advantage of the projection of the point onto the infinite line and observing that the scalar quantity of the projection tells us trivially if the projection is on the segment or not  We can adjust the bounds of the scalar quantity to use a fuzzy tolerance   If the projection is within bounds we just test if the distance from the point to the projection is within bounds   The benefit over the cross product approach is that the tolerance has a meaningful value

User · Answer

Using a more geometric approach  calculate the following distances   ab   sqrt  a x-b x   2    a y-b y   2  ac   sqrt  a x-c x   2    a y-c y   2  bc   sqrt  b x-c x   2    b y-c y   2    and test whether ac bc equals ab   is on segment   abs ac   bc - ab   lt  EPSILON   That s because there are three possibilities    The 3 points form a triangle    ac bc   ab They are collinear and c is outside the ab segment    ac bc   ab They are collinear and c is inside the ab segment    ac bc   ab

User · Answer

Here s how I did it at school  I forgot why it is not a good idea   EDIT     Darius Bacon  cites a  Beautiful Code  book which contains an explanation why the belowed code is not a good idea      usr bin env python from   future   import division  epsilon   1e-6  class Point      def   init   self  x  y           self x  self y   x  y  class LineSegment               gt  gt  gt  ls   LineSegment Point 0 0   Point 2 4        gt  gt  gt  Point 1  2  in ls     True      gt  gt  gt  Point  5  1  in ls     True      gt  gt  gt  Point  5  1 1  in ls     False      gt  gt  gt  Point -1  -2  in ls     False      gt  gt  gt  Point  1  0 20000001  in ls     True      gt  gt  gt  Point  1  0 2001  in ls     False      gt  gt  gt  ls   LineSegment Point 1  1   Point 3  5        gt  gt  gt  Point 2  3  in ls     True      gt  gt  gt  Point 1 5  2  in ls     True      gt  gt  gt  Point 0  -1  in ls     False      gt  gt  gt  ls   LineSegment Point 1  2   Point 1  10        gt  gt  gt  Point 1  6  in ls     True      gt  gt  gt  Point 1  1  in ls     False      gt  gt  gt  Point 2  6  in ls      False      gt  gt  gt  ls   LineSegment Point -1  10   Point 5  10        gt  gt  gt  Point 3  10  in ls     True      gt  gt  gt  Point 6  10  in ls     False      gt  gt  gt  Point 5  10  in ls     True      gt  gt  gt  Point 3  11  in ls     False             def   init   self  a  b           if a x  gt  b x              a  b   b  a          self x0  self y0  self x1  self y1     a x  a y  b x  b y          self slope    self y1 - self y0     self x1 - self x0  if self x1    self x0 else None      def   contains   self  c           return  self x0  lt   c x  lt   self x1 and                 min self y0  self y1   lt   c y  lt   max self y0  self y1  and                  not self slope or -epsilon  lt   c y - self y c x    lt  epsilon        def y self  x                   return self slope    x - self x0    self y0  if   name         main         import  doctest     doctest testmod

User · Answer

Here s another approach      Lets assume the two points be A  x1 y1  and B  x2 y2  The equation of the line passing through those points is  x-x1   y-y1   x2-x1   y2-y1      just making equating the slopes    Point C  x3 y3  will lie between A  amp  B if    x3 y3 satisfies the above equation  x3 lies between x1  amp  x2 and y3 lies between y1  amp  y2  trivial check

User · Answer

An answer in C  using a Vector2D class  public static bool IsOnSegment this Segment2D  this  Point2D c  double tolerance         var distanceSquared   tolerance tolerance          Start of segment to test point vector      var v   new Vector2D   this P0  c   To3D            Segment vector      var s   new Vector2D   this P0   this P1   To3D            Dot product of s      var ss   s s          k is the scalar we multiply s by to get the projection of c onto s         where we assume s is an infinte line      var k   v s ss          Convert our tolerance to the units of the scalar quanity k      var kd   tolerance   Math Sqrt  ss            Check that the projection is within the bounds      if  k  lt   -kd    k  gt    1 kd                  return false                 Find the projection point      var p   k s          Find the vector between test point and it s projection      var vp    v - p           Check the distance is within tolerance       return vp   vp  lt  distanceSquared      Note that  s   s   is the dot product of the segment vector via operator overloading in C   The key is taking advantage of the projection of the point onto the infinite line and observing that the scalar quantity of the projection tells us trivially if the projection is on the segment or not  We can adjust the bounds of the scalar quantity to use a fuzzy tolerance   If the projection is within bounds we just test if the distance from the point to the projection is within bounds   The benefit over the cross product approach is that the tolerance has a meaningful value

User · Answer

I needed this for javascript for use in an html5 canvas for detecting if the users cursor was over or near a certain line  So I modified the answer given by Darius Bacon into coffeescript   is on    a b c  - gt         Return true if point c intersects the line segment from a to b          or the degenerate case that all 3 points are coincident      return  collinear a b c  and withincheck a b c    withincheck    a b c  - gt      if a 0     b 0          within a 0  c 0  b 0        else          within a 1  c 1  b 1    collinear    a b c  - gt         Return true if a  b  and c all lie on the same line         b 0 -a 0    c 1 -a 1    lt   c 0 -a 0    b 1 -a 1     1000  and   b 0 -a 0    c 1 -a 1    gt   c 0 -a 0    b 1 -a 1   - 1000   within    p q r  - gt         Return true if q is between p and r  inclusive        p  lt   q  lt   r or r  lt   q  lt   p

User · Answer

Check if the cross product of b-a and c-a is0  that means all the points are collinear  If they are  check if c s coordinates are between a s and b s  Use either the x or the y coordinates  as long as a and b are separate on that axis  or they re the same on both    def is on a  b  c        Return true iff point c intersects the line segment from a to b          or the degenerate case that all 3 points are coincident      return  collinear a  b  c              and  within a x  c x  b x  if a x    b x else                   within a y  c y  b y     def collinear a  b  c        Return true iff a  b  and c all lie on the same line       return  b x - a x     c y - a y      c x - a x     b y - a y   def within p  q  r        Return true iff q is between p and r  inclusive        return p  lt   q  lt   r or r  lt   q  lt   p   This answer used to be a mess of three updates  The worthwhile info from them  Brian Hayes s chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background  Vincent s answer helped to improve this one  And it was Hayes who suggested testing only one of the x or the y coordinates  originally the code had and in place of if a x    b x else

User · Answer

Here s another approach      Lets assume the two points be A  x1 y1  and B  x2 y2  The equation of the line passing through those points is  x-x1   y-y1   x2-x1   y2-y1      just making equating the slopes    Point C  x3 y3  will lie between A  amp  B if    x3 y3 satisfies the above equation  x3 lies between x1  amp  x2 and y3 lies between y1  amp  y2  trivial check

User · Answer

C  version of Jules  answer   public static double CalcDistanceBetween2Points double x1  double y1  double x2  double y2        return Math Sqrt Math Pow  x1-x2  2    Math Pow  y1-y2  2       public static bool PointLinesOnLine  double x  double y  double x1  double y1  double x2  double y2  double allowedDistanceDifference        double dist1   CalcDistanceBetween2Points x  y  x1  y1       double dist2   CalcDistanceBetween2Points x  y  x2  y2       double dist3   CalcDistanceBetween2Points x1  y1  x2  y2       return Math Abs dist3 -  dist1   dist2    lt   allowedDistanceDifference

User · Answer

The scalar product between  c-a  and  b-a  must be equal to the product of their lengths  this means that the vectors  c-a  and  b-a  are aligned and with the same direction   Moreover  the length of  c-a  must be less than or equal to that of  b-a   Pseudocode     epsilon   small constant  def isBetween a  b  c       lengthca2     c x - a x   c x - a x     c y - a y   c y - a y      lengthba2     b x - a x   b x - a x     b y - a y   b y - a y      if lengthca2  gt  lengthba2  return False     dotproduct    c x - a x   b x - a x     c y - a y   b y - a y      if dotproduct  lt  0 0  return False     if abs dotproduct dotproduct - lengthca2 lengthba2   gt  epsilon  return False      return True

User · Answer

Here s a different way to go about it  with code given in C    Given two points  l1 and l2 it s trivial to express the line segment between them as  l1   A l2 - l1    where 0  lt   A  lt   1  This is known as the vector representation of a line if you re interested any more beyond just using it for this problem  We can split out the x and y components of this  giving   x   l1 x   A l2 x - l1 x  y   l1 y   A l2 y - l1 y    Take a point  x  y  and substitute its x and y components into these two expressions to solve for A  The point is on the line if the solutions for A in both expressions are equal and 0  lt   A  lt   1  Because solving for A requires division  there s special cases that need handling to stop division by zero when the line segment is horizontal or vertical  The final solution is as follows      Vec2 is a simple x y struct - it could very well be named Point for this use  bool isBetween double a  double b  double c           return if c is between a and b     double larger    a  gt   b    a   b      double smaller    a    larger    a   b       return c  lt   larger  amp  amp  c  gt   smaller     bool pointOnLine Vec2 lt double gt  p  Vec2 lt double gt  l1  Vec2 lt double gt  l2        if l2 x - l1 x    0  return isBetween l1 y  l2 y  p y      vertical line     if l2 y - l1 y    0  return isBetween l1 x  l2 x  p x      horizontal line      double Ax    p x - l1 x     l2 x - l1 x       double Ay    p y - l1 y     l2 y - l1 y           We want Ax    Ay  so check if the difference is very small  floating        point comparison is fun        return fabs Ax - Ay   lt  0 000001  amp  amp  Ax  gt   0 0  amp  amp  Ax  lt   1 0

User · Answer

how about just ensuring that the slope is the same and the point is between the others   given points  x1  y1  and  x2  y2    with x2   x1  and candidate point  a b   if   b-y1     a-x1     y2-y2     x2-x1   And x1  lt  a  lt  x2   Then  a b  must be on line between  x1 y1  and  x2  y2

User · Answer

Ok  lots of mentions of linear algebra  cross product of vectors  and this works in a real  ie continuous or floating point  space but the question specifically stated that the two points were expressed as integers and thus a cross product is not the correct solution although it can give an approximate solution   The correct solution is to use Bresenham s Line Algorithm between the two points and to see if the third point is one of the points on the line   If the points are sufficiently distant that calculating the algorithm is non-performant  and it d have to be really large for that to be the case  I m sure you could dig around and find optimisations

User · Answer

Here s another approach      Lets assume the two points be A  x1 y1  and B  x2 y2  The equation of the line passing through those points is  x-x1   y-y1   x2-x1   y2-y1      just making equating the slopes    Point C  x3 y3  will lie between A  amp  B if    x3 y3 satisfies the above equation  x3 lies between x1  amp  x2 and y3 lies between y1  amp  y2  trivial check

User · Answer

Using a more geometric approach  calculate the following distances   ab   sqrt  a x-b x   2    a y-b y   2  ac   sqrt  a x-c x   2    a y-c y   2  bc   sqrt  b x-c x   2    b y-c y   2    and test whether ac bc equals ab   is on segment   abs ac   bc - ab   lt  EPSILON   That s because there are three possibilities    The 3 points form a triangle    ac bc   ab They are collinear and c is outside the ab segment    ac bc   ab They are collinear and c is inside the ab segment    ac bc   ab

User · Answer

You can use the wedge and dot product   def dot v w   return v x w x   v y w y def wedge v w   return v x w y - v y w x  def is between a b c      v   a - b    w   b - c    return wedge v w     0 and dot v w   gt  0

User · Answer

You can do it by solving the line equation for that line segment with the point coordinates you will know whether that point is on the line and then checking the bounds of the segment to know whether it is inside or outside of it  You can apply some threshold because well it is somewhere in space mostl likely defined by a floating point value and you must not hit the exact one  Example in php function getLineDefinition  p1 array 0 0    p2 array 0 0              k     p1 1 - p2 1     p1 0 - p2 0         q    p1 1 - k  p1 0            return array  k   q           function isPointOnLineSegment  line array array 0 0  array 0 0     pt array 0 0                GET THE LINE DEFINITION y   k x   q AS array k  q        def   getLineDefinition  line 0    line 1                use the line definition to find y for the x of your point      y    def 0   pt 0   def 1         yMin   min  line 0  1    line 1  1         yMax   max  line 0  1    line 1  1            exclude y values that are outside this segments bounds     if  y gt  yMax     y lt  yMin  return false              calculate the difference of your points y value from the reference value calculated from lines definition         in ideal cases this would equal 0 but we are dealing with floating point values so we need some threshold value not to lose results        this is up to you to fine tune      diff   abs  pt 1 - y             thr   0 000001           return  diff lt   thr

[python] How can you determine a point is between two other points on a line segment?

Examples related to python

Examples related to math

Examples related to geometry