3
$\begingroup$

I have drawn the incircles of triangles which were generated through a delaunay triangulation but lost the original delaunay mesh. Is it possible to invert the process and draw the triangles back from this list of circles?

Many thanks,

Arthur

  • 1
    Do you know which incircles correspond to neighboring triangles in the original triangulation? If so, there are only two possibilities for each edge, and since three or more edges have to coincide in the corners, it is likely to be possible to find a corner that can be identified uniquely, and from there it should be easy to select the right corners in the entire grid. Of course there are probably degenerate cases where there really are two equally good solutions.2011-09-25

1 Answers 1

1

If there is a way to find a line mutually tangent to a pair of circles, then drawing tangents to pairs of neighbouring circles would produce the mesh.

If the circles X and Y have radii of x and y and a distance between them of z then, because the radii meeting the tangent are parallel, the angles between the radii and the line connecting the centres of the circles are equal, and given by cos((x+y)/z).

  • 1
    This would not work. You can look at this [Delaunay triangulation](http://tinypic.com/r/vgk7tg/7). From the blue circle A you should get the 3 black neighbouring circles. But the convex hull will contain A, two black circles and the red circle - and this is wrong.2011-09-27