Source

geoalg / geoalg / bruteforce.py

Full commit
#!/usr/bin/env python
#coding:utf-8
# Author:  mozman
# Purpose: bruteforce algorithms
# Created: 02.04.2010

from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import absolute_import


import math
from random import random

from geoalg import Line2D

def get_closest_pair(points):
    closest_pair = (points[0], points[1])
    points_count = len(points)
    min_so_far = _dist(points[0], points[1])
    for index1 in range(points_count-1):
        point1 = points[index1]
        for index2 in range(index1+1, points_count):
            point2 = points[index2]
            distance = _dist(point1, point2)
            if distance < min_so_far:
                min_so_far = distance
                closest_pair = (point1, point2)
    return closest_pair

def _dist(p1, p2):
    return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5

def intersection_points(lines):
    """Brute force algrithm to find all intersections points of <lines>.
    lines -- list of points tuples [(s1, e1), (s2, e2), ...]
        where s1, e1, s2, ... are xy-tuples like (10.4, 5,7)

    z-axis will be ignored.
    """
    intersection_points = []
    lines = list(lines)
    line_count = len(lines)
    for index1 in range(line_count):
        start, end = lines[index1]
        line1 = Line2D(start, end)
        for index2 in range(index1+1, line_count):
            start, end = lines[index2]
            point = line1.intersect(Line2D(start, end))
            if point:
                intersection_points.append(point)
    return intersection_points

def random_points(count, xdim=1000., ydim=1000.):
    points = []
    xhalf = xdim / 2.
    yhalf = ydim /2.
    for index in range(count):
        x = random() * xdim - xhalf
        y = random() * ydim - yhalf
        points.append( (x, y) )
    return points

def round_points(points, prec=6):
    return [(round(point[0], prec), round(point[1], prec)) for point in points]

def equalLists(list1, list2, prec=6):
    set1 = set(round_points(list1, prec))
    set2 = set(round_points(list2, prec))
    if len(list1) != len(list2):
        return False
    return set1 == set2