[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.

https://github.com/thi-ng/umbrella/blob/65dc2a5c6496854cfcd60b60682b407d06e058bc/packages/geom/src/classify-point.ts#L40

https://github.com/thi-ng/umbrella/blob/d48377c39a333d3e9c40ec816b81db1879ab534b/packages/geom-isec/src/point.ts#L184

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...)

[dennemark]

@postspectacular I stumbled over this one again. Used my above code in our repository, but nearly deleted it for the actualy thi.ng/geom function. Though I prefer the -1, 0, 1 check.

If there is some space, would you be able to look into this?

[postspectacular]

@dennemark I'm hoping to revisit this once more this week, since I've been working on another set of various major changes to the geom package, mainly related to better return types (#467), but also been adding various new shape types (incl. 3D) and updating type support for many operators....

[dennemark]

very nice! thanks a lot :) curious about the progress on types and 3d....

[postspectacular]

Hi @dennemark — so this should all be done now (updated your version to allow for specifying tolerance). Also included a new example to test & verify visually:

Demo: https://demo.thi.ng/umbrella/geom-classify-point/

Source: https://github.com/thi-ng/umbrella/blob/develop/examples/geom-classify-point/src/index.ts