Checking for intersection points

Question

The aim of the program is to find those points which comes under the intersection of at least 2 circles.(space is a 1000x1000 matrix)

n=input()
mat=[[0 for i in range(1005)] for i in range(1005)]
circles=[]

for i in range(n):
    circles.append(map(int,raw_input().split()))

ans=0 
for circle in circles:
    minx=circle[0]-circle[2]
    maxx=circle[0]+circle[2]
    miny=circle[1]-circle[2]
    maxy=circle[1]+circle[2]
    for i in range(minx,maxx+1):
        for j in range(miny,maxy+1):
            if mat[i][j]<=1:
                if ((i-circle[0])**2+(j-circle[1])**2)<=(circle[2]**2):
                    mat[i][j]+=1
                    if mat[i][j]>1:
                        ans+=1
print ans

n denoted the number of circle circles contain circle center and radius in the format [x,y,r]. For example, let circles = [[3,2,4],[2,5,2]]. Then it contains two circles centered at (3,2) and (2,5) with radius 4 and 2 respectively.

Is the logic correct? Will it trigger any exceptions?

Answer 1

Bad things will happen if any part of any circle strays outside the 0-to-1005 bounds. It's up to you to decide whether error handling for straying out of bounds is essential.

Mild rewrite

Representing each circle as a list is not quite appropriate. Using indexes circle[0], circle[1], and circle.[2] to mean x, y, and r, respectively, is awkward. As a remedy, I strongly recommend namedtuple.

from collections import namedtuple

Circle = namedtuple('Circle', ['x', 'y', 'r'])
n = int(raw_input())
circles = []
for i in range(n):
    circles.append(Circle(*map(int, raw_input().split())))

Initialization of a 1005 × 1005 grid is better written as:

mat = [[0] * 1005] * 1005

The rest of the program is straightforward. You should avoid switching nomenclature from x, y to i, j. To reduce nesting, you can eliminate one nested if by using and.

ans = 0 
for circle in circles:
    minx, maxx = circle.x - circle.r, circle.x + circle.r
    miny, maxy = circle.y - circle.r, circle.y + circle.r
    for x in range(minx, maxx+1):
        for y in range(miny, maxy+1):
            if mat[x][y] <= 1 and (x-circle.x)**2 + (y-circle.y)**2 <= circle.r**2:
                mat[x][y] += 1
                if mat[x][y] == 2:
                    ans += 1
print ans

Going further

The nesting of for: for: for: if: if is still rather overwhelming. I think it would be beneficial to split out some of that complexity.

class Circle (namedtuple('Circle', ['x', 'y', 'r'])):
    def contains(self, x, y):
        return (x - self.x)**2 + (y - self.y)**2 <= self.r**2

    def grid_points(self):
        for x in xrange(self.x - self.r, self.x + self.r + 1):
            for y in xrange(self.y - self.r, self.y + self.r + 1):
                if self.contains(x, y):
                    yield x, y

def read_ints():
    return map(int, raw_input().split())

n = int(raw_input())
circles = [Circle(*read_ints()) for _ in xrange(n)]

mat = [[0] * 1005] * 1005
ans = 0 
for circle in circles:
    for x, y in circle.grid_points():
        mat[x][y] += 1
        if mat[x][y] == 2:
            ans += 1
print ans

The way I've written it, I've removed the optimization of skipping grid points that are already known to be in the intersection of previously analyzed circles. I think it's probably a worthwhile tradeoff in favour of readability.

Answer 2

You don't really need to maintain a big empty grid, the empty cells aren't telling you anything. Instead, you can use a dictionary to store grid points that are contained by a particular circle, then just collect all of the dictionary entries with more than one reference.

@200's class is a great approach, so I'll steal it but I'm switching to itertools to generate the point lists

import itertools
from collections import  namedtuple

class Circle (namedtuple('Circle', ['x', 'y', 'r'])):

     def points(self):
         x_range = int(self.x - self.r), int(self.x + self.r + 1)
         y_range = int(self.y - self.r), int(self.y + self.r + 1)
         contained = lambda xy: (xy[0] - self.x)**2 + (xy[1] - self.y)**2 <= self.r**2
         return itertools.ifilter(contained, itertools.product(xrange(*x_range), xrange(*y_range)))

class CircleSet(dict):
    def __init__(self):
        self.intersections = set()

    def add(self, circle):
        for point in circle.points():
            try:
                self[point].append(circle)
                self.intersections.add(point)
            except KeyError:
                self[point] = [circle]

    def overlaps(self):
        return [(p, self[p]) for p in self.intersections]

The main idea here is to use the dictionary CircleSet as a sparse grid: it will only have keys where a point falls into a circle. I'm using a separate set() object to track intersections so that the 'overlaps' function does not have to look at every value and see if there are multiple entries, but you could ditch that and do

    def overlaps(self):
        return [(p, self[p]) for p in self if len(self[p] > 1 ]

The first version will be faster but you're storing redundant copies of the indices, which might matter for big data sets

Usage:

c1  = Circle (2,2,2)
c2 = Circle(3,3,2.5)
c3 = Circle(5,5,1)
c4 = Circle(2,3,2)
test = CircleSet()


for c in [c1, c2, c3, c4]:
    test.add(c)

for i in test.overlaps():
    print i

The results include a printout of the point and the circles which it overlaps. Or you can just get the points which are included in more than one circle with .intersections Note that there are no bounds on the grid, although it would be trivial to add them (probably by setting a range on the CircleSet and rejecting points outside that range in the add method).

Answer 3

The first thing that irks me with the code is the use of input. This is evil incarnate, bring equivalent to eval(raw_input()). You should use int(raw_input()) instead.

Your circles can be generated with a list comprehension. I suggest you do so.

You should move things out of the global scope, even if you just put it in a main function. You get free speed improvements out of it and it's easier to refactor.

Your loop is very straightforward, which is good, but there isn't a real need for the second if; we could just calculate the start and ends:

for circle in circles:
    for x_rel in range(-circle[2], circle[2]+1):
        i = x_rel + circle[0]

        # A circle on the origin is bounded on x² + y² = r²
        # Solving for y, we have x = ± √(r² - x²)
        y_bound = int((circle[2] ** 2 - x_rel ** 2) ** 0.5)

        for y_rel in range(-y_bound, y_bound+1):
            j = y_rel + circle[1]

            if mat[i][j]<=1:
                mat[i][j]+=1
                if mat[i][j]>1:
                    ans+=1

The last if section would look nicer as:

            mat[i][j] += 1

            if mat[i][j] == 2:
                ans += 1

or even

            mat[i][j] += 1
            ans += mat[i][j] == 2

You should consider unpacking the circle in the outer loop:

for center_x, center_y, radius in circles:

This gives:

def main():
    n = int(raw_input())
    circles = [map(int, raw_input().split()) for _ in range(n)]

    mat = [[0 for i in range(1005)] for i in range(1005)]

    ans = 0

    for center_x, center_y, radius in circles:
        for x_rel in range(-radius, radius+1):
            i = x_rel + center_x

            # A circle on the origin is bounded on x² + y² = r²
            # Solving for y, we have x = ± √(r² - x²)
            y_bound = int((radius ** 2 - x_rel ** 2) ** 0.5)

            for j in range(center_y-y_bound, center_y+y_bound+1):
                mat[i][j] += 1
                ans += mat[i][j] == 2

    print ans

main()

---

Here's an idea for how to improve the algorithm.

Your code is O(size of grid + total area of circles). Using a dictionary instead of a list of lists would reduce that to O(total area of circles).

My algorithm is instead approximately O(total perimeter of circles · log number of circles) where n is the number of circles. This comes from building something similar to an interval tree for each column:

 drawing    trees             stored as
 _______
| ...   |   1(..)3            [(1, +1), (3, -1)]
|.   .  |   0(..)4            [(0, +1), (4, -1)]
|.  ... |   0(...3(..)4..)5   [(0, +1), (3, +1), (4, -1), (5, -1)]
|. . . .|   0(...2(..)4..)6   [(0, +1), (2, +1), (4, -1), (6, -1)]
| ...  .|   1(...2(..)3..)6   [(1, +1), (2, +1), (3, -1), (6, -1)]
|  .   .|   2(..)6            [(2, +1), (6, -1)]
|   ... |   3(..)5            [(3, +1), (5, -1)]
 -------

Instead of storing the whole grid, each row is stores where each circle starts (()and where they end ()).

If you have many tiny circles, the original method could be better. If you have even somewhat large circles this should be faster.

# encoding: utf8

from collections import defaultdict, namedtuple
from math import ceil, floor

Circle = namedtuple("Circle", ["x", "y", "r"])

def read_circle():
    x, y, r = raw_input().split()
    return Circle(int(x), int(y), int(r))

def project_circles(circles):
    columns = defaultdict(list)

    for circle in circles:
        for x_rel in range(-circle.r, circle.r+1):
            # A circle on the origin is bounded on x² + y² = r²
            # Solving for y, we have x = ± √(r² - x²)
            y_rel = (circle.r ** 2 - x_rel ** 2) ** 0.5

            columns[circle.x + x_rel].append((circle.y - y_rel, +1))
            columns[circle.x + x_rel].append((circle.y + y_rel, -1))

    return columns

def extract_overlaps(column):
    # Keep deltas in order, because 0-width slices
    # should still count if they cover an integer
    column = sorted(column, key=lambda pos_delta: (pos_delta[0], -pos_delta[1]))
    num_active = 0

    for position, delta in column:
        if num_active == 1 and delta == 1:
            start = position

        if num_active == 2 and delta == -1:
            # Yield the number of dots (integers) between them, inclusive
            yield int(floor(position)) - int(ceil(start)) + 1

        num_active += delta

def main():
    circles = [read_circle() for _ in range(int(raw_input()))]

    columns = project_circles(circles)
    overlaps = (sum(extract_overlaps(column)) for column in columns.values())

    print(sum(overlaps))

main()

project_circles builds the tree-like structure and extract_overlaps finds the areas with an overlap of at least 2.

Unfortunately this is much more complex.