geometry.py

from SimpleCV.Features import Detection
import numpy as np
import math

def segments_distance(x11, y11, x12, y12, x21, y21, x22, y22):
    """ distance between two segments in the plane:
        one segment is (x11, y11) to (x12, y12)
        the other is   (x21, y21) to (x22, y22)
    """
    if segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22):
        return 0
    # try each of the 4 vertices w/the other segment
    distances = []
    distances.append(point_segment_distance(x11, y11, x21, y21, x22, y22))
    distances.append(point_segment_distance(x12, y12, x21, y21, x22, y22))
    distances.append(point_segment_distance(x21, y21, x11, y11, x12, y12))
    distances.append(point_segment_distance(x22, y22, x11, y11, x12, y12))
    return min(distances)

def segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22):
    """ whether two segments in the plane intersect:
        one segment is (x11, y11) to (x12, y12)
        the other is   (x21, y21) to (x22, y22)
    """
    dx1 = x12 - x11
    dy1 = y12 - y11
    dx2 = x22 - x21
    dy2 = y22 - y21
    delta = dx2 * dy1 - dy2 * dx1
    if delta == 0: return False  # parallel segments
    s = (dx1 * (y21 - y11) + dy1 * (x11 - x21)) / delta
    t = (dx2 * (y11 - y21) + dy2 * (x21 - x11)) / (-delta)
    return (0 <= s <= 1) and (0 <= t <= 1)

def point_segment_distance(px, py, x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    if dx == dy == 0:  # the segment's just a point
        return math.hypot(px - x1, py - y1)

    # Calculate the t that minimizes the distance.
    t = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy)

    # See if this represents one of the segment's
    # end points or a point in the middle.
    if t < 0:
        dx = px - x1
        dy = py - y1
    elif t > 1:
        dx = px - x2
        dy = py - y2
    else:
        near_x = x1 + t * dx
        near_y = y1 + t * dy
        dx = px - near_x
        dy = py - near_y

    return math.hypot(dx, dy)

def lines_distance(a, b):
    if a.angle() <= 0:
        x, y = a.bottomLeftCorner()
        x2, y2 = a.topRightCorner()
    else:
        x, y = a.bottomRightCorner()
        x2, y2 = a.topLeftCorner()

    if a.angle() <= 0:
        x3, y3 = b.bottomLeftCorner()
        x4, y4 = b.topRightCorner()
    else:
        x3, y3 = b.bottomRightCorner()
        x4, y4 = b.topLeftCorner()

    return segments_distance(float(x), float(y),
                             float(x2), float(y2),
                             float(x3), float(y3),
                             float(x4), float(y4))

def lines_intersect(a, b):
    if a.angle() <= 0:
        x, y = a.bottomLeftCorner()
        x2, y2 = a.topRightCorner()
    else:
        x, y = a.bottomRightCorner()
        x2, y2 = a.topLeftCorner()

    if a.angle() <= 0:
        x3, y3 = b.bottomLeftCorner()
        x4, y4 = b.topRightCorner()
    else:
        x3, y3 = b.bottomRightCorner()
        x4, y4 = b.topLeftCorner()

    return segments_intersect(float(x), float(y),
                             float(x2), float(y2),
                             float(x3), float(y3),
                             float(x4), float(y4))

def cluster_lines(lines):
    sets = []
    unused = set(lines)
    used = set()

    while unused:
        c = unused.pop()
        current_set = set([c])
        used.add(c)
        for ln in unused:
            for curline in current_set:
                if lines_distance(ln, curline) < 10:
                    used.add(ln)
                    current_set.add(ln)
                    break
        sets.append(current_set)
        unused = unused - used

    res = list(sets)
    res.sort(key=lambda s: min(x.minX() for x in s))
    return res

def combine_lines(img, lines):
    # TODO: there should be a smarter way of combining lines than by using
    # bounding boxes
    minx = float('inf')
    miny = float('inf')
    maxx = 0.0
    maxy = 0.0

    pos = 0
    for line in lines:
        pos += line.length() if line.angle() > 0 else -line.length()
    pos = bool(pos >= 0)
    for line in lines:
        if pos is None:
            pos = bool(line.angle() > 0)

        if pos:
            x1, y1 = line.bottomLeftCorner()
            x2, y2 = line.topRightCorner()
        else:
            x1, y1 = line.bottomRightCorner()
            x2, y2 = line.topLeftCorner()
        minx = min(minx, x1, x2)
        miny = min(miny, y1, y2)
        maxx = max(maxx, x1, x2)
        maxy = max(maxy, y1, y2)

    if pos:
        pta = np.array([minx, miny])
        ptb = np.array([maxx, maxy])
    else:
        pta = np.array([maxx, miny])
        ptb = np.array([minx, maxy])

    # Adjust the center of the new segment to be the average of the centers of
    # the inputs, weighted by length
    center = np.array([0.0, 0.0])
    tot_len = 0.0
    for line in lines:
        center += np.asarray(line.coordinates()) * line.length()
        tot_len += line.length()
    center /= tot_len

    diff = (ptb - pta) / 2.0
    return Detection.Line(img, (center - diff, center + diff))

def get_corners(line):
    if line.angle() < 0:
        c1 = line.bottomLeftCorner()
        c2 = line.topRightCorner()
    else:
        c1 = line.bottomRightCorner()
        c2 = line.topLeftCorner()
    return c1, c2

def lines_cost(line1, line2):
    dist = lines_distance(line1, line2)
    return dist * dist

def offset_line(line, offset):
    offset = np.asarray(offset)
    c1, c2 = get_corners(line)
    c1 = np.asarray(c1) + offset
    c2 = np.asarray(c2) + offset
    return Detection.Line(line.image, (c1, c2))