How does this code for delaunay triangulation work?

by

Looks like what is described here http://en.wikipedia.org/wiki/Delaunay_triangulation :

The problem of finding the Delaunay triangulation of a set of points in d-dimensional Euclidean space can be converted to the problem of finding the convex hull of a set of points in (d + 1)-dimensional space, by giving each point p an extra coordinate equal to |p|2, taking the bottom side of the convex hull, and mapping back to d-dimensional space by deleting the last coordinate.

In your example d is 2.

The vector (xn,yn,zn) is the cross product of the vectors (point i -> point j) and (point i -> point k) or in other words a vector perpendicular to the triangle (point i, point j, point k).

The calculation of flag checks whether the normal of this triangle points towards the negative z direction and whether all other points are on the side opposite to the normal of the triangle (opposite because the other points need to be above the triangle’s plane because we’re interested in the bottom side of the convex hull). If this is the case, the triangle (i,j,k) is part of the 3D convex hull and therefore the x and y components (the projection of the 3D triangle onto the x,y plane) is part of the (2D) Delaunay triangulation.

More Related Contents:

  1. Null Pointer Exception in You Tube Analytics API using Java IntelliJ IDEA?
  2. Random Number Algorithm – Implementation in Java
  3. How to convert fuzzy hash string to a file? [closed]
  4. Can’t add parameter ‘this’
  5. How to solve expression with /=
  6. When to use StringBuilder in Java [duplicate]
  7. Java heap terminology: young, old and permanent generations?
  8. How to get frequency from fft result?
  9. How to avoid ‘instanceof’ when implementing factory design pattern?
  10. How do I get whole and fractional parts from double in JSP/Java?
  11. How to specify the JDK version in Android Studio?
  12. Using javafx.beans properties in model classes
  13. Android AudioRecord class – process live mic audio quickly, set up callback function
  14. How to filter string for unwanted characters using regex?
  15. Connection Java – MySQL : Public Key Retrieval is not allowed
  16. Why does the Java char primitive take up 2 bytes of memory?
  17. Java Spring @Scheduled tasks executing twice
  18. JPA: update only specific fields
  19. Should I avoid using Java Label Statements?
  20. How to log into Facebook programmatically using Java?
  21. Allowing the this reference to escape
  22. Create a Bitmap/Drawable from file path
  23. BitmapFactory.decodeStream returning null when options are set
  24. Local variable log defined in an enclosing scope must be final or effectively final
  25. Change DecimalFormat locale
  26. LOAD and CACHE application-scoped data with @Singleton and @Stateless
  27. Spring data JPA and parameters that can be null
  28. How to mock a static method from JMockit
  29. Binary presentation of negative integer in Java
  30. SecureRandom with NativePRNG vs SHA1PRNG

Leave a Comment