How to determine if a Delaunay triangle is internal or external?

Question

I am writing a program that requires a implementation of Medial Axis extraction, of which Delaunay triangulation is a step. External medial axis is unwanted so the corresponding external triangles are intended to be removed. Luckily I came upon a page with a lot of diagrams, also a hint of a method to determine internal and external Delaunay triangles ("based on the broken line perimeter"), but it's just a hint, without detailed explanation. Anybody know the algorithm?

EDIT: I forgot mentioning the initial points are sampled from the boundary of a closed polygon, my intention is to determine whether each Delaunay triangle is inside the polygon.

Answer 1

Perhaps I'm making too many assumptions here, but it sounds like you have a polygon that consists of a bunch of points, and that you are triangulating those points. You then want to discard all the triangles that fall outside of the polygon, right?

Why not just triangulate the polygon (using monotone decomposition or something similar) so that you never create any external triangles? I suppose this might increase the running time (triangulate first in O(nlogn) time and then create a delaunay triangulation in O(n^2) time) but there might be a faster way of doing it.

Answer 2

Have you considered using a different form of triangulation that doesn't create external triangles? I once took a course that spent a great deal of time discussing the theoretical aspects of polygon triangulation. Maybe skimming through the course site will give you some insight? http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation

Edit: Actually, I just thought of something else. If you already have the polygon that you are trying to triangulate, you could use Green's theorem. Green's theorem uses a polygon's perimeter to compute its area! More importantly, in this case, you can determine whether a point is on one side of a line, or another, by looking at the sign of area. On polygons, Green's theorem works out to a simple subtraction problem. So take any point that you KNOW is inside the polygon, and compute the area against each edge of the polygon. This tells you on which side of each line your point needs to be. Now simply take a point inside each triangle and do the same thing. If any of the signs are wrong, then you have an external triangle. (Note: depending on the shape of your polygon this might not actually work. It should work fine for convex polygons, but concavities could introduce additional complications.)