Cutting the edge of an circle if it overlaps another circle

[flaerpen]

Hello all, I've been seeking for an solutions but i'm stuck.

I'm generating a image of cells (circles, using ellipses) from a file where there is coordinates that i use (x,y,r). This function draws these cells (alot of them) to a image and it works great. But I would like to implement a function that looks if a cell overlaps another cell and if it does the cell shall be cut, both of them. I've included a nice little pic so you all can se what I mean:

[img]http://img339.imageshack.us/img339/8800/cellsmz9.png[/img]

What I think I have to do is to calculate where the cells edges is crossing eachother and then draw som sort of line between. But how do i do that? I should also mention that i use PIL for the moment but i'm flexible so i can change library if you have a better solution!

/flaerpen

[flaerpen]

I found this page: http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/

maybe it can be helpful! I'm pretty tired right now so I don't quite understand what is says :P but when I'm a little less tired I will try if I can get it work! But I would appreciate if someone helped me!

[jrcagle]

That site has a good clean solution. The outline of your code would be something like:

def intersects(circle0, circle1):
"""Returns pair of points of intersection, or None if circles are coincident or too far apart."""

    P0 = center(circle0)
    P1 = center(circle1)
    
    r0 = radius(circle0)
    r1 = radius(circle1)

    d = distance(P1,P0)
    if d > r0 + r1 or d == 0:
       return None
    compute a = (r0^2 - r1^2 + d^2)/2d
    compute P2 = P0 + a(P1 - P0)/d
    compute P3a = (x2 + h(y1-y0)/d, y2 - h(x1-x0)/d)
    compute P3b = (x2 - h(y1-y0)/d, y2 + h(x1-x0)/d)
    return (P3a, P3b)

Let us know how it goes...
Jeff

[flaerpen]

Thank you! But before I try the code I have some questions:

What is the value of circle0 and circle1? (x,y,r)?

def intersects(circle0, circle1):

P0,P1 and P2 is points with the value (x,y), a tuple? If they have that value, how can we use them in this formula? I need to know what 'compute' is, hehe, is it a 'real' function in Python or just pseudo-code?

compute P2 = P0 + a(P1 - P0)/d

I think thats was all of my question for now. Thank you again..

[flaerpen]

what does "|| r0 - r1 ||" mean? What kind of mathematical operator is this "|"?

[flaerpen]

what does "|| r0 - r1 ||" mean? What kind of mathematical operator is this "|"?

I got it. Its the absolute.. something (dont know the word in english) and the function I'll use is abs(x).

I alsop found a solution that might work. check this page: http://www.thescripts.com/forum/post2560149-3.html

[jrcagle]

"Absolute value", yes. (I keeping waiting for a Vodka advertisement with "Absolut Value" as the tagline :))

||A - B|| means "the distance between A and B" (in math-speak, "the norm of A - B"). If A and B are real numbers, as in this case, then

||A - B|| = abs(A-B). In the general case,
||A - B|| = sqrt((A1-B1)^2 + (A2-B2)^2 + ...), which is a ugly-looking version of the Pythagorean theorem, and collapses to the first formula when A and B have 1 dimension.

It sounds like you're making progress!

Jeff

[flaerpen]

I missed the code in http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/

there was already a whole program that use his mathematic. The only "problem" is that it is in C. I tried to change it to Python and it works for the moment, but if someone could rewrite it into Python I would be more than happy :D

here is the source-code http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/tvoght.c

[flaerpen]

As the topicname says I also wanted to 'cut'/erase/delete the edge/overlaping areas. Is there a solution for that?

Here is my image that I've done with mt script. I want to erase the overlaping areas.

[img]http://img456.imageshack.us/img456/269/mycellssa6.jpg[/img]

[flaerpen]

I think I'll use the chord to accomplish my mission :)

I wrote a code that returns the start and end angles. But I can only use this of the x and y position is the same for both circles!

n = 180
aStart = int(math.degrees(math.asin((-h)/r0))+n)
aEnd = int(math.degrees(math.asin(h/r0))+n)

draw.chord((x01,y01,x02,y02),aStart,aEnd, fill='green', outline='green')

It is counting arc sinus for the angle and converts it to degrees.

This is how it looks, [img]http://img360.imageshack.us/img360/9721/hallovz6.jpg[/img]
this function also only works if the right circle is over the other, if the left overlaps the right you shouldn't use n=180, only n=0..

Is there someone out there who can help me to return a correct value for every possible circle?

[flaerpen]

I made an image to show you all what I want:
[img]http://img263.imageshack.us/img263/9308/newcellchordsb1.gif[/img]

The two green lines angle is what I want a general formula so it works for all of my circles.. I hope the picture helps you to help me :D

[flaerpen]

Nobody who can help me to get a general formula for the two angles?

[flaerpen]

I got help from another forum, here is one answer that works! If the two intersecting points have the coordinates x,y and x1,y1. And the circles midpoint is x0,y0 then we have a simpel formula:

v0 = 360 - atan2(y - y0, x - x0)
v1 = 360 - atan2(y1 - y0, x1 - x0)

[bumsfeld]

Wouldn't it be simpler to create a polygon with coordinates x0,y0 and x,y and x1,y1 back to x0,y0 and fill it with the color to match?

[flaerpen]

I dont know.. could that really work? Anyway, I have the formula and this works for now so I dont know if i want to change the way of doing it to a polygon..