Patterns Geometry
Here is a collection of different geometry algorithms.
Convex Hull
To find convex hull of points, it is better to use Monotone chains approach. If you need to find convex hull, use the following code.
def remove_middle(a, b, c):
cross = (a[0] - b[0]) * (c[1] - b[1]) - (a[1] - b[1]) * (c[0] - b[0])
dot = (a[0] - b[0]) * (c[0] - b[0]) + (a[1] - b[1]) * (c[1] - b[1])
return cross < 0 or cross == 0 and dot <= 0
def convex_hull(points):
spoints = sorted(points)
hull = []
for p in spoints + spoints[::-1]:
while len(hull) >= 2 and remove_middle(hull[-2], hull[-1], p):
hull.pop()
hull.append(p)
hull.pop()
return hull
If you need to find convex hull with all points on borders, you can use this code (TO CHECK)
def cross (a, b, c):
return (a[0] - b[0]) * (c[1] - b[1]) - (a[1] - b[1]) * (c[0] - b[0])
def convex_hull(self, points):
spoints = sorted((x, y) for x, y in points)
hull = []
for p in spoints + spoints[::-1]:
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) < 0:
hull.pop()
hull.append(p)
return set(hull)
Line functions
Here are some function to work with lines and points with integer coordinates.
get_2dline
: given two points, return equation of line in forma*x + b*y + c = 0
, wheregcd(a, b, c) > 0
.dist
is distance between two points.is_parallel
to check if two lines are paralles or equal.is_same
to check if two lines the same.collinear
is to check if3
points are on the same line.intersect
is to check if two lines have intersection and if they have, return point.rotate
is to rotate given pointp
around pointorigin
bytheta
radians.
def get_2dline(p1, p2):
if p1 == p2:
return (0, 0, 0)
_p1, _p2 = min(p1, p2), max(p1, p2)
a, b, c = _p2[1] - _p1[1], _p1[0] - _p2[0], _p1[1] * _p2[0] - _p1[0] * _p2[1]
g = gcd(gcd(a, b), c)
return (a // g, b // g, c // g)
dist = lambda p1, p2: sum((a - b) * (a - b) for a, b in zip(p1, p2))**0.5
is_parallel = lambda l1, l2: l1[0] * l2[1] == l2[0] * l1[1]
is_same = lambda l1, l2: is_parallel(l1, l2) and (l1[1] * l2[2] == l2[1] * l1[2])
collinear = lambda p1, p2, p3: is_same(get_2dline(p1, p2), get_2dline(p2, p3))
intersect = (lambda l1, l2: None if is_parallel(l1, l2) else (
(l2[1] * l1[2] - l1[1] * l2[2]) / (l2[0] * l1[1] - l1[0] * l2[1]),
(l1[0] * l2[2] - l1[2] * l2[0]) / (l2[0] * l1[1] - l1[0] * l2[1]),
))
rotate = lambda p, theta, origin=(0, 0): (
origin[0] + (p[0] - origin[0]) * math.cos(theta) - (p[1] - origin[1]) * math.sin(theta),
origin[1] + (p[0] - origin[0]) * math.sin(theta) + (p[1] - origin[1]) * math.cos(theta),
)
Polygon functions
Here are some function of polygons.
perimeter
is perimeter of polygon.area
is area of polygon.is_in_circle
is to ckeck if given point lies inside given circe.incircle_radius
is radius of incircle for given triangle.circumcircle_radius
is radius of circumcircle for given triangle.
perimeter = lambda *p: sum(dist(i, j) for i, j in zip(p, p[1:] + p[:1]))
area = lambda *p: abs(sum(i[0] * j[1] - j[0] * i[1] for i, j in zip(p, p[1:] + p[:1]))) / 2
is_in_circle = lambda p, c, r: sum(i * i - j * j for i, j in zip(p, c)) < r * r
incircle_radius = lambda a, b, c: area(a, b, c) / (perimeter(a, b, c) / 2)
circumcircle_radius = lambda a, b, c: (dist(a, b) * dist(b, c) * dist(c, a)) / (4 * area(a, b, c))
Vector functions
Here are some functions to work with vertors.
to_vec
is to create vector from two points.scale
is multiply vector by number.translate
is to translate vector by another vector.dot
is dot product of two vectors.norm_sq
is length of vector.angle
is angle between two vectors.cross2d
is length of vector product of two vectors.cross3d
is 3d vector: vector product of two 3d vectors.closest_point
is closest point on segmenta, b
(or linea, b
) to given pointp
.
to_vec = lambda p1, p2: (j - i for i, j in zip(p1, p2))
scale = lambda v, s: (i * s for i in v)
translate = lambda p, v: (pi + vi for pi, vi in zip(p, v))
dot = lambda v1, v2: sum(i * j for i, j in zip(v1, v2))
norm_sq = lambda v: sum(i * i for i in v)
angle = lambda oa, ob: math.acos(dot(oa, ob) / (norm_sq(oa) * norm_sq(ob))**0.5)
cross2d = lambda v1, v2: v1[0] * v2[1] - v1[1] * v2[0]
cross3d = lambda v1, v2: (v1[1] * v2[2] - v1[2] * v2[1], v1[2] * v2[0] - v1[0] * v2[2], v1[0] * v2[1] - v1[1] * v2[0])
def closest_point(p, a, b, segment=False):
ap, ab = to_vec(a, p), to_vec(a, b)
u = dot(ap, ab) / norm_sq(ab)
if segment:
if u < 0:
return a
if u > 1:
return b
return translate(a, scale(ab, u))