Re: Delaunay: Determinant test

On May 13, 1:07 pm, all...@xxxxxxxxxxxx wrote:
Hi all.

I am struggling a bit to understand how the determinant test for
the Delaunay triangulation works.

Assume the triangle T(A,B,C) exists, and that a point P is introduced
to be included in the Delaunay triangulation of the set {A,B,C,P}.>From various sources (web, Preparata & Shamos, de Berg & al), I

have seens statements to the effect that "If the determinant D = ...
is positive, the Delaunay triangulation is <this>, else it is <that>."

I can get this up and running as far as one triangle goes: Given
the three points A, B and C, one knows that there can be constructed
a circle with radius R and centre S such that all points are located
on the circle.

The above is easy to formulate as a matrix:

(x_A-x_S)^2 + (y_A-y_S)^2= R^2
(x_B-x_S)^2 + (y_B-y_S)^2= R^2
(x_C-x_S)^2 + (y_C-y_S)^2= R^2

A little manipulation and one finds a matrix expression which
can be solved for x_S, y_S and R. From there on, I am stuck:

1) How does this idea extend to testing two triangles?
2) How does the test boil down to testing the sign of the
determinant?

I am probably just blind, since I haven't used determinants since
the intro course on linear algebra I took 15 years ago.

Rune

Hi, Rune.

Your honesty is appreciable. There is nothing wrong in admitting a
long lost concept, or lack of knowledge. Thats how we learn and share.

Have you come across the "Algorithms" section of this article?

http://en.wikipedia.org/wiki/Delaunay_triangulation

You see a matrix representation used to test in a 2D case whether to
add a point D as a new point for triangulation.

Given three points A, B, C forming a triangle with edges ordered
counter-clockwise, you introduce a fourth point D.

When you compute the determinant of that matrix, it is positive if and
only if D lies within the circumcircle of triangle ABC.

Now based on whether or not D lies inside the circumcircle, you take
the next step appropriately ( would you want to introduce a new point
inside ABC? would it be optimal? )

Hope this helps a bit,

Pixel.To.Life.

[ http://groups.google.com/group/medicalimagingscience ]



.

Relevant Pages

  • Re: area of a triangle determinant
    ... >My computational geometry book shows how you can find the area of a triangle ... >defined by 3 vertices using the cross product. ... >I understand how he shows the determinant and cross porduct way are the same ... operations and column operations on determinants, ...
    (sci.math)
  • Re: surface integration using unsorted numerical data
    ... I have one question though as to which numerical method you are using for ... the summation and what is it calculates for avez. ... that computes the area of each triangle. ... that determinant is also the ...
    (comp.soft-sys.matlab)
  • Re: Identifying edges in a triangle?
    ... I am trying to find a way to identify if L1 is a leftedge of if it a rightedge, but cannot seem to find a correct strict criteria. ... For example, if one side of the triangle is horizontal, then you have two sides of the triangle that can be qualified as L1. ... Then compute the determinant of the 2x2 matrix ... The sign indicates the orientation, and orientation is an artifact of the coordinate system you chose. ...
    (sci.math)
  • Re: Identifying edges in a triangle?
    ... I am trying to find a way to identify if L1 is a leftedge of if it a rightedge, but cannot seem to find a correct strict criteria. ... For example, if one side of the triangle is horizontal, then you have two sides of the triangle that can be qualified as L1. ... Then compute the determinant of the 2x2 matrix ...
    (sci.math)
  • Re: Internal Bisectors of a Triangle
    ... Given a triangle ABC ... angle AIB = pi/2 + angle ACI ... are either all interior angle bisectors, ...
    (sci.math)