Division by zero for segment overlap

[Nycto]

I've found two situations where calling overlap for two Segment instances will cause a division by zero:

1. If the lines are parallel, for example:

   Segment(at: vec2(625.0, 22.0), to: vec2(629.0, 22.0))
   Segment(at: vec2(820.0, 80.0), to: vec2(828.0, 80.0))
   

2. If the length of a line is zero, for example:

   Segment(at: vec2(454.0, 124.0), to: vec2(454.0, 124.0))
   Segment(at: vec2(828.0, 81.0), to: vec2(828.0, 111.0))
   

On some CPUs, this is fine because division by zero returns NaN, which the rest of the method deals with just fine. For some CPUs, though, this causes a segfault. I'm happy to submit a patch, but I thought I would check whether this is an edge case you're interested in handling.

Cheers, and thanks!

[Nycto]

I should also say -- the implementation I would submit as an alternative is from here: https://gist.github.com/alexcpn/45c5026397e11751583891831cc36456

Implemented in Nim, it looks like:

proc overlaps*(d, s: Segment): bool =
  ## Test overlap: segment vs segment.

  let d1 = (d.to.x - d.at.x, d.to.y - d.at.y)
  let d2 = (s.to.x - s.at.x, s.to.y - s.at.y)
  let det = (d1[0] * d2[1]) - (d1[1] * d2[0])

  if det == 0:
    return false

  let t1 = ((d2[1] * (s.at.x - d.at.x)) - (d2[0] * (s.at.y - d.at.y))) / det
  let t2 = ((d1[1] * (s.at.x - d.at.x)) - (d1[0] * (s.at.y - d.at.y))) / det

  return 0 <= t1 and t1 <= 1 and 0 <= t2 and t2 <= 1

[treeform]

I tested this and just as I thought, the det check is not needed the infs are still valid floats and the if statement works out right. The branch that det == 0 is more significant slow down then the following float operations. Float operations get better optimization then there isn't a branch in the middle:

with the det == 0 check:

   min time    avg time  std dv   runs name
   3.838 ms    3.888 ms  ±0.008   x100 segment vs segment

without the det == 0 check:

   3.654 ms    3.688 ms  ±0.008   x100 segment vs segment

What CPUs create a segfault for a float point div by 0? That is very strange.

Sorry I don't think I will be taking this PR.

[Nycto]

No worries. I’ve got a fork that I’ve been using in the meantime, and I’m fine with continuing to use that.

I’m specifically running this on an ARM 168 MHz Cortex M7: https://help.play.date/hardware/the-specs/