Voronoi diagram, Delaunay triangulation and 3D Convex Hull

(Still refinining... this blog entry. More images will be added to aid understanding... hopefully)

Introduction:

In the following discussion, Voronoi diagram and halfplane intersection refer to the 2D case, unless otherwise specified.

I hope I can list some nice properties of as well as some relationships between the following three structures in computational geometry:

• Voronoi diagram
  
  
  
  [You need to understand what is going on on the right image.The left and the middle will be discussed below.]
• Delaunay triangulation
• 3D convex hull 

[舊帖] UVa 11275 3D Triangles

Old Post in Xanga on 2010-02-18

---

Problem Statement:
Given 2 triangles in R³, check whether they share at least 1 common point.

---

今日 Research 有 3D 野要搞...
Google... 無意間見到 一個 theorem - SAT (?)
原 來 SAT = Separating Axis Theorem

發覺 ACM 可能有用喎!

應 用落呢題之後... Runtime 快過以前 Ray / Plane Intersection !
而且對比之下, 呢個方法更加 mechanical, 貌似好多地方都用得著