stefansalewski / cdt Goto Github PK

I have interests in using Delaunay Triangulation for interpolation, but I can't seem to find any functions suitable for that. locatePoint was the one I found, but it just returns the nearest edge (2 out of 3 points). Am I just blind or is this still not implemented? And in such case, how hard would it be to add? 😄

We discovered a few random failures, and so commented out that line before the last one in the proc for now. The issue may occur when we insert new points with insertPoint(), and that new point is located on an existing edge. We have to investigate this issue carefully later, for now it seems to work without the assert. Actually we are using the CDT2 variant of this library, but it should be the same for initial CDT.

# Returns an edge e, s.t. either x is on e, or e is an edge of
# a triangle containing x. The search starts from startingEdge
# and proceeds in the general direction of x. Based on the
# pseudocode in Guibas and Stolfi (1985) p.121.
# http://www.karlchenofhell.org/cppswp/lischinski.pdf
# if point is in face, we return the closest edge -- triArea(e.org.point, e.dest.point, p) >= 0
proc xlocatePoint(p: Vector; startEdge: Edge): Edge =
  var e = startEdge
  assert e != nil
  while true: # TODO: can we get an infinite loop -- and how to best fix it?
    if p == e.org.point or p == e.dest.point:
      return e
    elif p.rightOf(e):
      e = e.sym
    elif not p.rightOf(e.onext):
      e = e.onext
    elif not p.rightOf(e.dprev):
      e = e.dprev
    else:
      break
  assert not p.rightOf(e)
  let a = triArea(e.org.point, e.dest.point, p)
  assert a >= 0
  if a > 0:
    e = minValueByIt([e, e.onext.sym, e.dprev.sym], linePointDistSqr(it.org.point, it.dest.point, p))
  ###assert not p.rightOf(e)
  return e

There are two issues: A simple one:

Line 112 in minmax.nim

func minValueBy*[T](s: openArray[T], cmp: proc (x, y: T): int {.closure, noSideEffect.}): T =
#func minValueBy*[T](s: openArray[T], cmp: proc (x, y: T): int {.closure.}): T =

More recent compiler versions needs the noSideEffect pragma (or we may make minValueBy() a plain proc.) Making
the symbol after cmp: a func seems not to work.

The other issue is

grep cursor /home/salewski/.nimble/pkgs/cdt-0.1.1/cdt/*
/home/salewski/.nimble/pkgs/cdt-0.1.1/cdt/types.nim:    next*{.cursor.}: Edge # added {.cursor.} for v 0.1.1

We added the cursor pragma years ago to make it compile with --gc:arc. Orc was not available at all that time.
Now, we can remove the cursor pragma, and it compiles with orc, arc, and refc. So the obvious fix is to remove that pragma now. But with arc the cdt module may leak memory, due to the complicated quad-edge data structure. May the cursor pragma avoid leaks for arc? We don't know currently.

But to avoid the ugly crashes, we will remove the cursor pragma for now.