# Finding a hole in the random deployment of circles.

Page 1 of 1

## 2 Replies - 188 Views - Last Post: 16 July 2014 - 07:37 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=350323&amp;s=165e3881b752f20897f61f24f00d7334&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 rnjreddy

• New D.I.C Head

Reputation: 0
• Posts: 1
• Joined: 14-July 14

# Finding a hole in the random deployment of circles.

Posted 14 July 2014 - 04:05 AM

I have been trying on a problem of finding a hole(basically which is not in the area of any circle) during the deployment of random circles in a 2d plane.I found out the intersection points and start and end angles with respect to each circle.Then i implemented a function of my known by considering the total inscribed angle of a circle and by gradually deleting the intersected arcs angles from the list..i.e.initially the list is [[0,360]]..then in iterations deleting the angular portion from the list nd changing it accordingly.
I have almost completed the part of finding the arc which is not inscribed in any circle which is the basis of finding the hole.I am struck at this point.i need some suggestion and help to know where i m going wrong.
thank you

```import random
from math import sqrt
import math
import operator
from operator import itemgetter
from collections import OrderedDict

def IntersectPoints(P0, P1,r):
if type(P0) != complex or type(P1) != complex:
raise TypeError("P0 and P1 must be complex types")
# d = distance
d = sqrt((P1.real - P0.real)**2 + (P1.imag - P0.imag)**2)
# n**2 in Python means "n to the power of 2"
# note: d = a + b

if d > 2*r:
return []
elif d==0:
return []
else:
a = (r**2 - r**2 + d**2) / (2 * d)
b = d - a
h = sqrt(r**2 - a**2)
P2 = P0 + a * (P1 - P0) / d

i1x = P2.real + h * (P1.imag - P0.imag) / d
i1y = P2.imag - h * (P1.real - P0.real) / d
i2x = P2.real - h * (P1.imag - P0.imag) / d
i2y = P2.imag + h * (P1.real - P0.real) / d

i1 = complex(i1x, i1y)
i2 = complex(i2x, i2y)

return [(i1x,i1y), (i2x,i2y)]

def CompToStr(c):
return "(" + str(c.real) + ", " + str(c.imag) + ")"

def PairToStr(p):
return CompToStr(p[0]) + " , " + CompToStr(p[1])

ip=IntersectPoints
no_points = int(input("the no.of points  : "))
width=int(input("The width size :"))
height=int(input("the height is :"))

'''
i = ip(complex(0,0), complex(1, 0), 2, 2)
s = ip(complex(0,0), complex(4, 0), 2, 2)
print ("Intersection: ", PairToStr(i))
print ("Wholly inside:", ip(complex(0,0), complex(1, 0), 5, 2))
print ("Single-point edge collision:", PairToStr(s))
print ("Intersection:", PairToStr(ip(complex(1.2,3.4),  complex(3, 0), 2, 2)))
'''
x_value=[]
y_value=[]
xsect=[]
random.seed(width)
random.seed(height)

for j in range(no_points):
x_value.append(random.uniform(0,width))
y_value.append(random.uniform(0,height))

centre=[(x, y) for x in x_value for y in y_value if x_value.index(x)==y_value.index(y)]
#print(centre)

for i in centre:
for j in centre:
#print(i[0])
intersect_list=[xsect[i:i+no_points] for i in range(0,len(xsect),no_points)]
#print(intersect_list)

dct1={}
dct2={}
for m in intersect_list:
l=intersect_list.index(m)
for n in m:
if n!=[]:
k=m.index(n)
dct1[k]=sqrt(( n[1][0]- n[0][0])**2 + (n[1][1] - n[0][1])**2)

dct2[l]=dct1
dct1={}
#print(dct2)

#temp=list(dct2.values())
#print(temp)

start_ang_dct={}
end_ang_dct={}
start={}
end={}

for i in intersect_list:
l=intersect_list.index(i)
#print(centre[l])
for j in i:
if j!=[]:
k=i.index(j)
#print(l)
#print(centre[l][1])
start_ang_dct[k+1]=(math.atan2(j[0][1]-centre[l][1],j[0][0]-centre[l][0]))*180/math.pi
if start_ang_dct[k+1] <0:
start_ang_dct[k+1]+=360
end_ang_dct[k+1]=(math.atan2(j[1][1]-centre[l][1],j[1][0]-centre[l][0]))*180/math.pi
if end_ang_dct[k+1] <0:
end_ang_dct[k+1]+=360
start[l+1]=start_ang_dct
end[l+1]=end_ang_dct
start_ang_dct={}
end_ang_dct={}
#print(start)
#print(end)

temp1=list(start.values())
temp2=list(end.values())

#print(temp1)
print('***************End angles******************')
#print(temp2)

start_final=[]
for i in temp1:
start_final.append(OrderedDict(sorted(i.items(),key=itemgetter(1))))

#sorted(i.values())
#s=sorted(i.items(),key=itemgetter(1))
#sorted_start=sorted(i.iteritems(),key=operator.itemgetter(1))
#print(s)
#print(start_final)

started=[]
for i in start_final:
dct=i
started.append(list(dct.items()))
print('********************Sorted_Start_angles******************')
#print(started)

ch_dct={}
for i in started:
checksum_list=[[0,360]]
k=started.index(i)
l=0
for j in i:
n=i.index(j)
p=j[0]
if(j[1]>checksum_list[l][0]) and (temp2[k][p]<checksum_list[l][1]):
Itemp=checksum_list[l][1]
checksum_list[l][1]=j[1]
checksum_list.insert(l+1,[temp2[k][p],Itemp])

elif (j[1] <= checksum_list[l][0]):
if (temp2[k][p]>j[l]):
if (temp2[k][p]<=checksum_list[l][0]):
pass
elif (checksum_list[l][0]<temp2[k][p]<checksum_list[l][1]):
checksum_list[l][0]=temp2[k][p]
l-=1
elif(temp2[k][p]<j[l]):
checksum_list[l-1][1]=j[1]

if (temp2[k][p]<=checksum_list[l][0]):
pass
elif(checksum_list[l][0]<temp2[k][p]<checksum_list[l][1]):
checksum_list[l][0]=temp2[k][p]
l-=1

if(checksum_list[l]==checksum_list[(len(checksum_list))-1]):
break
else:l+=1

ch_dct[k]=checksum_list
print('*****************************orifice list******************************')
print(ch_dct)

```

Is This A Good Question/Topic? 0

## Replies To: Finding a hole in the random deployment of circles.

### #2 Martyr2

• Programming Theoretician

Reputation: 4332
• Posts: 12,127
• Joined: 18-April 07

## Re: Finding a hole in the random deployment of circles.

Posted 14 July 2014 - 01:03 PM

Maybe I am thinking a bit simplistic here, but couldn't you just run through each point in the 2D plane and see if it is within radius distance of any of your random circles center points (aka intersects a circle)? It would result in a nested loop which which of course will be m x n in speed, but if the area is not too big and the circles are not too numerous, then it should be fairly quick.

Sounds like far less operations than what you are doing.

This post has been edited by Martyr2: 14 July 2014 - 01:04 PM

### #3 DK3250

Reputation: 27
• Posts: 105
• Joined: 27-December 13

## Re: Finding a hole in the random deployment of circles.

Posted 16 July 2014 - 07:37 PM

I agree with Martyr2.
If you can accept a graphical solution (not a matematical exact solution), just make all circles black on a white surface.
Then you just need to check the color of each pixel to get your answer - don't even need to do any calculation.
Naturally, you can do this with any grid but pixels are handy...

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }