# bisecting triangulation

Hi,

I have set of points in a plane and make triplot:

subplot(121)
plot(points[:,0], points[:,1], 'o')
title('Set of points')
subplot(122)
triplot(points[:,0], points[:,1])
title('Triangulation')

Does anyone know how to extract just the lines describing each circumscribed circle in this example?
Perhaps by using Delaunay from scipy.spatial?

Just to inform you, I want to do this through triangulation and above example is trivial that can be solved differently, while real problem doesn't contain circles...

Thanks

You need to use a matplotlib.tri.Triangulation (your use of triplot does this for you behind the scenes anyway), something like:

import matplotlib.tri as mtri
triang = mtri.Triangulation(xpoints, ypoints)

Now triang.triangles is an array of integers of shape (?, 3) such that triang.triangles[i,:] are the three indices of the points that comprise triangle i. You will need to use these to determine the information you want. The triplot example (http://matplotlib.org/examples/pylab_examples/triplot_demo.html) does something similar, identifying which triangles are within a particular circle; I guess in your case a simple approach would be to test if the distance from the centre of each triangle edge to your circle of interest is below some threshold or not.

Incidentally, if you have a Triangulation object then subsequent calls to functions like triplot can be of the form triplot(triang), which will be faster than repeated calls to triplot(xpoints, ypoints) as in the latter case a separate Delaunay triangulation needs to be performed for each triplot call.

Ian

···

On 1 July 2013 13:40, zetah <otrov@…4366…> wrote:

Hi,

I have set of points in a plane and make triplot:

``````subplot(121)

plot(points[:,0], points[:,1], 'o')

title('Set of points')

subplot(122)

triplot(points[:,0], points[:,1])

title('Triangulation')
``````

Does anyone know how to extract just the lines describing each circumscribed circle in this example?

Perhaps by using Delaunay from scipy.spatial?

Just to inform you, I want to do this through triangulation and above example is trivial that can be solved differently, while real problem doesn’t contain circles…

Using threshold like you described is not applicable as there is no
guarantee of minimum distance between pattern objects.

I wanted to replicate CGAL crust demo in Python, and in the meantime
I found the algorithm by Nina Amenta:

···

On вторник, 02 јули 2013 at 11:04 AM, Ian Thomas wrote:

You need to use a matplotlib.tri.Triangulation (your use of triplot does
this for you behind the scenes anyway), something like:

import matplotlib.tri as mtri
triang = mtri.Triangulation(xpoints, ypoints)

Now triang.triangles is an array of integers of shape (?, 3) such that
triang.triangles[i,:] are the three indices of the points that comprise
triangle i. You will need to use these to determine the information you
want. The triplot example (
http://matplotlib.org/examples/pylab_examples/triplot_demo.html)
does something similar, identifying which triangles are within a
particular circle; I guess in your case a simple approach would be to test if
the distance from the centre of each triangle edge to your circle of
interest is below some threshold or not.

# ======================================== compute Vor(P); let V be the Voronoi vertices of Vor(P); compute Del(P U V); E := 0; for each edge pq in Del(P U V) do   if p in P and q in P       E := E U pq;   endif output E.

So, Voronoi vertices have property to cluster wanted objects in a manner
that we can use edges of Delaunay triangulation from original points and
Voronoi vertices of that same points, and simply check if they lay on
original points.

I used Deleanay and Voronoi functions from scipy.spatial and worth
mentioning is that I had hard time finding that edges from triangulation
can be found by this command:

# ======================================== t = Delaunay(PUV) edges = t.points[t.vertices]

Cheers

Incidentally, if you have a Triangulation object then subsequent
calls to functions like triplot can be of the form triplot(triang), which
will be faster than repeated calls to triplot(xpoints, ypoints) as in the
latter case a separate Delaunay triangulation needs to be performed for
each triplot call.

Ian