[geom] Point Inside Polygon - Point on Polygon

[dennemark]

I am wondering, if it is possible to extend the pointInside function and add a possibility to know if point is on polygon.
Since classifyPoint works with -1, 0 and 1 instead of boolean like pointInside, I think it would be possible to integrate the following functions inside classifyPoint and keep pointInside as is.
The algorithm looses a bit of efficiency though.

umbrella/packages/geom/src/classify-point.ts

Line 40 in 65dc2a5

export const classifyPoint: MultiFn2O<IShape, ReadonlyVec, number, number> =

umbrella/packages/geom-isec/src/point.ts

Line 184 in d48377c

export const classifyPointPolyPair: FnN7 = (px, py, ax, ay, bx, by, inside) =>

const pointInPolygon2 = (p: vec.Vec, pts: vec.Vec[]) => {
  return classifyPointPolygon(p, pts) > 0
}
export const classifyPointPolygon = (p: vec.Vec, pts: vec.Vec[], checkOnPoly?: boolean) => {
  const n = pts.length - 1
  const px = p[0]
  const py = p[1]
  let a = pts[n]
  let b = pts[0]
  let inside = -1
  for (let i = 0; i <= n; a = b, b = pts[++i]) {
    inside = classifyPointPolyPair(px, py, a[0], a[1], b[0], b[1], inside)
    if (inside === 0) {
      break
    }
  }
  return inside
}

export const classifyPointPolyPair = (
  px: number,
  py: number,
  ax: number,
  ay: number,
  bx: number,
  by: number,
  inside: number
) => {
  const onRay = (ax - px) * (by - py) - (ay - py) * (bx - px) === 0
  const inYRange = (ay <= py && by >= py) || (ay >= py && by <= py)
  const inXRange = (ax <= px && bx >= px) || (ax >= px && bx <= px)
  const onLine = onRay && inYRange && inXRange

  return onLine
    ? 0
    : ((ay < py && by >= py) || (by < py && ay >= py)) && (ax <= px || bx <= px)
    ? // check if outside of line
      // if inside = 1  && tx > px return 1
      // if inside = 1  && tx < px return -1
      // if inside = -1 && tx < px return 1
      // if inside = -1 && tx > px return -1
      -((inside ^ (ax + ((py - ay) / (by - ay)) * (bx - ax) < px ? 1 : -1)) + 1)
    : inside
}

Tested for these cases, feel free to test more.

[
          { pt: [0, 0], result: -1 },
          { pt: [0, 0.5], result: 0 },
          { pt: [0, 1], result: -1 },
          { pt: [1, 1], result: -1 },
          { pt: [0.5, 0], result: 0 },
          { pt: [1, 0], result: -1 },
          { pt: [0.5, 0.5], result: 1 },
          { pt: [-0.5, 0], result: -1 },
        ].map((x) => {
          const res = classifyPointPolygon(x.pt, [
            [0, 0.5],
            [0.5, 1],
            [1, 0.5],
            [0.5, 0],
          ])
          expect(res).toBe(x.result)
        }),
        [
          { pt: [0, 0], result: 0 },
          { pt: [0, 0.5], result: 0 },
          { pt: [0, 1], result: 0 },
          { pt: [1, 1], result: 0 },
          { pt: [0.5, 0], result: 0 },
          { pt: [1, 0], result: 0 },
          { pt: [0.5, 0.5], result: 1 },
          { pt: [-0.5, 0], result: -1 },
        ].map((x) => {
          const res = classifyPointPolygon(x.pt, [
            [0, 0],
            [0, 1],
            [1, 1],
            [1, 0],
          ])
          expect(res).toBe(x.result)
        })

[dennemark]

I am not sure if it is worth implementing this approach within pointInside component. Maybe it can be a separate classifyPolygon function. Since the only reasonable way to get on polygon functionality, is by really checking, if a point is on each line of polygon, therefore creating additional checks within classifyPointPolyPair.

The checks for pt within y range within classifyPointPolyPair vary just slightly ay <= py and by <= py vs ay < py and by < py . The latter is necessary for inside check, the former for on line check.

While this decreases performance for point inside checking, it might actually be bit faster, if point is on polygon, since we can just skip iterating over follow up lines of a polygon.

I have it in my code base now...
Not sure what you prefer @postspectacular

[postspectacular]

@dennemark - Looks good & I'm thinking about this, but will have to refamiliarize with the details of that code first (in a different head space right now...)