proc xlocatePoint() may fail due to assert not p.rightOf(e) about cdt HOT 1 OPEN

The reason for this issue seems to be the triArea() proc and its wrong use:

func triArea*(a, b, c: Vector): float {.inline.} =
  (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

which is used by other procs

func ccw*(a, b, c: Vector): bool {.inline.} =
  triArea(a, b, c) > 0

func rightOf(x: Vector; e: Edge): bool {.inline.} =
  ccw(e.dest.point, e.org.point, x)

Due to numerical inaccuracy, for three nearly collinear points x, y, z, triArea(x, y, z) may be zero,
while triArea(y, x, z) is not zero.

To avoid inaccuracy issues and full symmetry, we should change rightOf() to

func rightOf(x: Vector; e: Edge): bool {.inline.} =
  triArea(e.org.point, e.dest.point, x) < 0

We will do some more tests, and than apply this fix for sdt and sdt2 package. You may think about this issue yourself, and consult the related papers.

from cdt.