Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I doubt it. That seems incredibly challenging if possible. I suspect that it is not unique, and that is the big problem. –  mixedmath Sep 25 '11 at 19:41
    
Don't you mean the circumcircles of the triangles? –  lhf Sep 25 '11 at 19:58
    
Hi lhf, no it is the incircles (circle within triangle tangent to each edge) –  Arthur Mamou-Mani Sep 25 '11 at 20:04
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. –  Henning Makholm Sep 25 '11 at 21:05

1 Answer 1

up vote 1 down vote accepted

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).

share|improve this answer
    
I assume you mean by neighbouring circles the incircles of the neighbouring triangles. So, each circle has 3 neighbouring circles. But how do you find out which circles are neighbouring circles? (The shortest distance to the centers does not help.) –  Jiri Sep 26 '11 at 16:20
    
The 'neighbouring circles' of circle A are three circles such that their convex hull contains circle A and no parts of any other circles. –  Angela Richardson Sep 27 '11 at 15:07
1  
This would not work. You can look at this Delaunay triangulation. 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. –  Jiri Sep 27 '11 at 16:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.