1. Algoritm — orınlawshı ushın málim bir máseleni sheshiwge qaratılǵan kórsetpelerdiń anıq izbe-izligi. Algoritmlar bul kompyuter programmaları artı daǵı ideyalar. Algoritm orınlawshısı



Yüklə 339,36 Kb.
səhifə20/20
tarix05.09.2022
ölçüsü339,36 Kb.
#63425
1   ...   12   13   14   15   16   17   18   19   20
shpor

38.Andrew Algoritimi
Endryuning monoton shınjırı qabarıq korpus algoritmı eki ólshewli noqatlar kompleksiniń konveks korpusın jaratadı. O (n*log n) waqıt boyinsha.
Ol bunı birinshi náwbette noqatlardı leksikografik tárepten saralaw (birinshi náwbette x - koordinatası boyınsha, hám teń bolsa, y - koordinatası boyınsha ), keyininen noqatlardıń joqarı hám tómengi korpusların qurıw arqalı ámelge asıradı. O (n) waqıt.
Joqarı korpus - bul joqarıdan kórinetuǵın qabarıq korpustıń bir bólegi. Ol óziniń eń oń noqatınan eń shep noqatına saat miliga teris tártipte isleydi. Tómengi korpus konveks korpustıń qalǵan bólegi bolıp tabıladı.


def convex_hull(points):
points = sorted(set(points))
if len(points) <= 1:
return points
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

lower = []


for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)

upper = []


for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]


assert convex_hull([(i//10, i%10) for i in range(100)]) == [(0, 0), (9, 0), (9, 9), (0, 9)]






Yüklə 339,36 Kb.

Dostları ilə paylaş:
1   ...   12   13   14   15   16   17   18   19   20




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin