This code determines if a point is inside a polygon by checking if any ray originating from the point intersects the polygon's edges.

Run example

npm run import -- "brush to vertex"

brush to vertex

  
// Given three colinear points p, q, r, the function checks if 
// point q lies on line segment 'pr' 
function onSegment(p, q, r) 
{
    if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && 
            q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y)) {
        return true; 
    }
    return false; 
} 
  
// To find orientation of ordered triplet (p, q, r). 
// The function returns following values 
// 0 --> p, q and r are colinear 
// 1 --> Clockwise 
// 2 --> Counterclockwise 
function orientation(p, q, r) 
{ 
    var val = (q.y - p.y) * (r.x - q.x) - 
              (q.x - p.x) * (r.y - q.y); 
  
    if (val == 0) return 0;  // colinear 
    return (val > 0)? 1: 2; // clock or counterclock wise 
} 
  
// The function that returns true if line segment 'p1q1' 
// and 'p2q2' intersect. 
function doIntersect(p1, q1, p2, q2) 
{ 
    // Find the four orientations needed for general and 
    // special cases 
    var o1 = orientation(p1, q1, p2); 
    var o2 = orientation(p1, q1, q2); 
    var o3 = orientation(p2, q2, p1); 
    var o4 = orientation(p2, q2, q1); 
  
    // General case 
    if (o1 != o2 && o3 != o4) {
        return true
    }
  
    // Special Cases 
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1 
    if (o1 == 0 && onSegment(p1, p2, q1)) return true
  
    // p1, q1 and p2 are colinear and q2 lies on segment p1q1 
    if (o2 == 0 && onSegment(p1, q2, q1)) return true
  
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2 
    if (o3 == 0 && onSegment(p2, p1, q2)) return true
  
     // p2, q2 and q1 are colinear and q1 lies on segment p2q2 
    if (o4 == 0 && onSegment(p2, q1, q2)) return true
  
    return false; // Doesn't fall in any of the above cases 
} 


// Returns true if the point p lies inside the polygon[] with n vertices 
function isInside(polygon, n, p) 
{ 
    // There must be at least 3 vertices in polygon[] 
    if (n < 3)  return false; 
  
    // Create a point for line segment from p to infinite 
    var extreme = {x: Number.MAX_VALUE, y: p.y}; 
  
    // Count intersections of the above line with sides of polygon 
    var count = 0, i = 0; 
    do
    { 
        var next = (i+1)%n; 
  
        // Check if the line segment from 'p' to 'extreme' intersects 
        // with the line segment from 'polygon[i]' to 'polygon[next]' 
        if (doIntersect(polygon[i], polygon[next], p, extreme)) 
        { 
            // If the point 'p' is colinear with line segment 'i-next', 
            // then check if it lies on segment. If it lies, return true, 
            // otherwise false 
            if (orientation(polygon[i], p, polygon[next]) == 0) 
               return onSegment(polygon[i], p, polygon[next]); 
  
            count++; 
        } 
        i = next; 
    } while (i != 0); 
  
    // Return true if count is odd, false otherwise 
    return (count%2 == 1);
} 


module.exports = {
    doIntersect,
    isInside
}

// Point class to represent a point in 2D space
class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

// Checks if point q lies on line segment 'pr'
function onSegment(p, q, r) {
  // Check if point q lies within the x-range of points p and r
  const minX = Math.min(p.x, r.x);
  const maxX = Math.max(p.x, r.x);
  // Check if point q lies within the y-range of points p and r
  const minY = Math.min(p.y, r.y);
  const maxY = Math.max(p.y, r.y);
  // Return true if point q lies within the range of points p and r
  return q.x >= minX && q.x <= maxX && q.y >= minY && q.y <= maxY;
}

// Checks the orientation of an ordered triplet of points
function orientation(p, q, r) {
  // Calculate the orientation using the cross product formula
  const crossProduct = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  // Return 0 if points are colinear, 1 if clockwise, 2 if counterclockwise
  return crossProduct === 0? 0 : crossProduct > 0? 1 : 2;
}

// Checks if two line segments intersect
function doIntersect(p1, q1, p2, q2) {
  // Find the four orientations needed for general and special cases
  const o1 = orientation(p1, q1, p2);
  const o2 = orientation(p1, q1, q2);
  const o3 = orientation(p2, q2, p1);
  const o4 = orientation(p2, q2, q1);
  // General case
  if (o1!== o2 && o3!== o4) return true;
  // Special cases
  if (o1 === 0 && onSegment(p1, p2, q1)) return true;
  if (o2 === 0 && onSegment(p1, q2, q1)) return true;
  if (o3 === 0 && onSegment(p2, p1, q2)) return true;
  if (o4 === 0 && onSegment(p2, q1, q2)) return true;
  // If none of the above cases are true, the line segments do not intersect
  return false;
}

// Checks if a point lies inside a polygon
function isInside(polygon, n, p) {
  if (n < 3) return false; // Minimum 3 points in the polygon
  const extreme = new Point(Number.MAX_VALUE, p.y);
  let count = 0;
  for (let i = 0; i < n; i++) {
    const next = (i + 1) % n;
    if (doIntersect(polygon[i], polygon[next], p, extreme)) {
      if (orientation(polygon[i], p, polygon[next]) === 0) {
        return onSegment(polygon[i], p, polygon[next]);
      }
      count++;
    }
  }
  return count % 2 === 1;
}

module.exports = {
  onSegment,
  orientation,
  doIntersect,
  isInside,
};

This code implements a polygon clipping algorithm to determine if a point lies inside a given polygon.

Here's a breakdown:

1. onSegment Function:

   • Takes three points (p, q, r) as input.
   • Checks if point q lies on the line segment defined by points p and r.
   • Returns true if q is on the segment, false otherwise.

2. orientation Function:

   • Takes three points (p, q, r) as input.
   • Determines the orientation of the triplet (p, q, r).
   • Returns:
     • 0 if the points are colinear.
     • 1 if the orientation is clockwise.
     • 2 if the orientation is counterclockwise.

3. doIntersect Function:

   • Takes two line segments defined by their endpoints (p1, q1 and p2, q2) as input.
   • Determines if the two line segments intersect.
   • Returns true if they intersect, false otherwise.
   • Uses the orientation function to check for different cases (colinear, intersecting, etc.).

4. isInside Function:

   • Takes a polygon (array of points), the number of vertices (n), and a point (p) as input.
   • Determines if point p lies inside the polygon.
   • Uses the doIntersect function to check if any ray originating from p intersects the polygon's edges.

Purpose:

This code provides a set of functions for geometric calculations related to polygons, including determining if a point lies inside a polygon, checking for line segment intersections, and calculating orientations. These functions can be used in various applications, such as game development, graphics rendering, or computer graphics algorithms.