Zametanie

Najbližšie dva body

body = [[1,3],[3,5],[5,7], [1,5]]

from scipy import spatial

min([ spatial.distance.euclidean(body[i], body[j]) for i in range(len(body)) for j in range(len(body)) if j != i ])

2.0

min([ spatial.distance.euclidean(body[i], body[j]) for i in range(len(body))  for j in range(i+1, len(body))])

2.0

min([((body[i][0]-body[j][0])**2+(body[i][1]-body[j][1])**2, i, j) for i in range(len(body))  for j in range(i+1, len(body))])

(4, 0, 3)

Konvexný obal

import numpy as np

points = np.random.rand(10, 2)
print(points)

[[0.51412586 0.41722561]
 [0.36744287 0.77738991]
 [0.16978844 0.7134169 ]
 [0.1317331  0.67063352]
 [0.52744301 0.62768359]
 [0.01540494 0.17863097]
 [0.42918258 0.3181358 ]
 [0.83455572 0.31432705]
 [0.5424763  0.54657784]
 [0.0114323  0.68381203]]

import matplotlib
import numpy as np
import matplotlib.pyplot as plt

plt.scatter(x=points[:, 0], y=points[:, 1])
plt.show()

points[np.argsort(points[:, 0])] #usporiadanie podla prvej zlozky

array([[0.0114323 , 0.68381203],
       [0.01540494, 0.17863097],
       [0.1317331 , 0.67063352],
       [0.16978844, 0.7134169 ],
       [0.36744287, 0.77738991],
       [0.42918258, 0.3181358 ],
       [0.51412586, 0.41722561],
       [0.52744301, 0.62768359],
       [0.5424763 , 0.54657784],
       [0.83455572, 0.31432705]])

def turn(A, B, C):
    "Is the turn from A->B->C a 'right', 'left', or 'straight' turn?"
    diff = (B.x - A.x) * (C.y - B.y)  -  (B.y - A.y) * (C.x - B.x) 
    return ('right' if diff < 0 else
            'left'  if diff > 0 else
            'straight')

def half_hull(sorted_points):
    "Return the half-hull from following points in sorted order."
    # Add each point C in order; remove previous point B if A->B-C is not a left turn.
    hull = []
    for C in sorted_points:
        # if A->B->C is not a left turn ...
        while len(hull) >= 2 and turn(hull[-2], hull[-1], C) != 'left':
            hull.pop() # ... then remove B from hull.
        hull.append(C)
    return hull

def convex_hull(points):
    "Find the convex hull of a set of points."
    if len(points) <= 3:
        return points
    # Find the two half-hulls and append them, but don't repeat first and last points
    upper = half_hull(sorted(points))
    lower = half_hull(reversed(sorted(points)))
    return upper + lower[1:-1]

import collections
import random

Point = collections.namedtuple('Point', 'x, y')

def Points(n, seed=42):
    "Generate n random points within a 3 x 2 box."
    random.seed((n, seed))
    b = 0.05 # border
    return {Point(random.uniform(b, 3-b), random.uniform(b, 2-b)) 
            for _ in range(n)}

convex_hull(Points(100))

[Point(x=0.05168007114109491, y=1.1480586159713213),
 Point(x=0.09951010812740813, y=0.7902950909195201),
 Point(x=0.5757840995300831, y=0.2569473753898331),
 Point(x=0.8240827449458622, y=0.06089568969131846),
 Point(x=2.3356164752830337, y=0.09831503370039404),
 Point(x=2.7122502662847188, y=0.20112873320065666),
 Point(x=2.776300999271257, y=0.2330877025982125),
 Point(x=2.894056167311511, y=0.47500331549040015),
 Point(x=2.909079099939879, y=1.4586207419747728),
 Point(x=2.623165629192698, y=1.6651480766872593),
 Point(x=1.742765799491593, y=1.9427220200780329),
 Point(x=0.9426285964842653, y=1.944841592916941),
 Point(x=0.46055049387807145, y=1.932286716578754),
 Point(x=0.11673188016236666, y=1.9182055054047538),
 Point(x=0.10224977464245122, y=1.8353471195736262)]

def plot_points(points, style='r.', labels=False, closed=False): 
    """Plot a collection of points. Optionally change the line style, label points with numbers, 
    and/or form a closed polygon by closing the line from the last point to the first."""
    if labels:
        for (i, (x, y)) in enumerate(points):
            plt.text(x, y, '  '+str(i))
    if closed:
        points = points + [points[0]]
    plt.plot([p.x for p in points], [p.y for p in points], style, linewidth=2.5)
    plt.axis('scaled'); plt.axis('off')
def plot_convex_hull(points):
    "Find the convex hull of these points, and show a plot."
    hull = convex_hull(points)
    plot_points(points)
    plot_points(hull, 'bs-', closed=True, labels=True)
    print(len(hull), 'of', len(points), 'points on hull')

plot_convex_hull(Points(100, seed=random.randint(0, 100)))

15 of 100 points on hull