2 Replies - 224 Views - Last Post: 16 July 2014 - 07:37 PM Rate Topic: -----

#1 rnjreddy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 :"))
radius=int(input("Enter the radius :"))
print("circumference:",2*math.pi*radius)

'''
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])
        xsect.append((ip(complex(i[0],i[1]),complex(j[0],j[1]),radius)))
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  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4423
  • View blog
  • Posts: 12,293
  • 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

Was This Post Helpful? 1
  • +
  • -

#3 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • 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...
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1