stefansalewski / cdt Goto Github PK
View Code? Open in Web Editor NEWConstrained Delaunay Triangulation (2D), incremental / fully dynamic
License: MIT License
Constrained Delaunay Triangulation (2D), incremental / fully dynamic
License: MIT License
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.