Што такое эфектыўны спосаб знайсці, калі кропка ляжыць у выпуклай абалонцы аблокі кропак?

У мяне ёсць воблака кропак каардынат у NumPy. Для вялікай колькасці кропак, я хачу, каб высветліць, калі пункту ляжаць у выпуклай абалонцы аблокі кропак.

Я паспрабаваў pyhull, але я не магу зразумець, як праверыць, калі кропка знаходзіцца ў ConvexHull :

hull = ConvexHull(np.array([(1, 2), (3, 4), (3, 6)]))
for s in hull.simplices:
    s.in_simplex(np.array([2, 3]))

падымае LinAlgError: Масіў павінен быць квадратным.

27

9 адказы

Вось простае рашэнне, якое патрабуе толькі SciPy:

def in_hull(p, hull):
    """
    Test if points in `p` are in `hull`

    `p` should be a `NxK` coordinates of `N` points in `K` dimensions
    `hull` is either a scipy.spatial.Delaunay object or the `MxK` array of the 
    coordinates of `M` points in `K`dimensions for which Delaunay triangulation
    will be computed
    """
    from scipy.spatial import Delaunay
    if not isinstance(hull,Delaunay):
        hull = Delaunay(hull)

    return hull.find_simplex(p)>=0

Ён вяртае булева масіў, дзе True значэння паказваюць кропкі, якія ляжаць у дадзенай выпуклай абалонкі. Ён можа быць выкарыстаны, як гэта:

tested = np.random.rand(20,3)
cloud  = np.random.rand(50,3)

print in_hull(tested,cloud)

Калі Matplotlib ўстаноўлены, вы можаце таксама выкарыстоўваць наступную функцыю, якая выклікае першую і ўчасткі вынікаў. Для 2D толькі дадзеныя, што задавалася NX2 масівы:

def plot_in_hull(p, hull):
    """
    plot relative to `in_hull` for 2d data
    """
    import matplotlib.pyplot as plt
    from matplotlib.collections import PolyCollection, LineCollection

    from scipy.spatial import Delaunay
    if not isinstance(hull,Delaunay):
        hull = Delaunay(hull)

    # plot triangulation
    poly = PolyCollection(hull.points[hull.vertices], facecolors='w', edgecolors='b')
    plt.clf()
    plt.title('in hull')
    plt.gca().add_collection(poly)
    plt.plot(hull.points[:,0], hull.points[:,1], 'o', hold=1)


    # plot the convex hull
    edges = set()
    edge_points = []

    def add_edge(i, j):
        """Add a line between the i-th and j-th points, if not in the list already"""
        if (i, j) in edges or (j, i) in edges:
            # already added
            return
        edges.add( (i, j) )
        edge_points.append(hull.points[ [i, j] ])

    for ia, ib in hull.convex_hull:
        add_edge(ia, ib)

    lines = LineCollection(edge_points, color='g')
    plt.gca().add_collection(lines)
    plt.show()    

    # plot tested points `p` - black are inside hull, red outside
    inside = in_hull(p,hull)
    plt.plot(p[ inside,0],p[ inside,1],'.k')
    plt.plot(p[-inside,0],p[-inside,1],'.r')
48
дададзена
Гэта даволі проста на самай справе: няхай воблака ўяўляць сабой NxK масівы N кропак у памернасці K, ConvexHull (воблака) .vertices (ад scipy.spatial) дае індэксы кропак на выпуклай абалонцы, гэта значыць «знешнія кропкі»
дададзена аўтар Juh_, крыніца
гэты адказ працуе ў п вымярэннях!
дададзена аўтар joshua, крыніца
Гэта РБП можна знайсці знешнія пункту выпуклай абалонкі аблокі кропак? Таму што я хачу, каб выдаліць гэтыя пункты з разліку на адлегласці, якія ўтвараюць знешнія трыкутнікі і часта маюць вялікія адлегласці
дададзена аўтар Liwellyen, крыніца

Прывітанне Я не ўпэўнены, пра тое, як выкарыстоўваць бібліятэку праграм для дасягнення гэтай мэты. Але ёсць просты алгарытм для дасягнення гэтай мэты апісаць словы:

  1. create a point that is definitely outside your hull. Call it Y
  2. produce a line segment connecting your point in question (X) to the new point Y.
  3. loop around all edge segments of your convex hull. check for each of them if the segment intersects with XY.
  4. If the number of intersection you counted is even (including 0), X is outside the hull. Otherwise X is inside the hull.
  5. if so occurs XY pass through one of your vertexes on the hull, or directly overlap with one of your hull's edge, move Y a little bit.
  6. the above works for concave hull as well. You can see in below illustration (Green dot is the X point you are trying to determine. Yellow marks the intersection points. illustration
20
дададзена
Хоць гэта крыху nitpicky, ёсць некалькі выпадкаў, калі гэта страціць: 1) Калі вы выбіраеце пункт, коллинеарно з парай вяршыняў на корпусе і кантрольнай кропцы таксама коллинеарны з гэтымі вяршынямі, а таксама, то вы будзе тэхнічна атрымаць бясконцую колькасць перасячэнняў. 2) калі ваша кантрольная кропка і X і знешняя кропка Y коллинеарны з вяршыняй на скрыжаванні з няцотных лікам граняў (3d выпадку), то вы б памылкова заключыць, што тэставая кропка на самай справе ўнутры корпуса ... на прынамсі, вы, магчыма, спатрэбіцца праверыць для выпадку 2. Eg забяспечваць адсутнасць коллинеарность XYV
дададзена аўтар wmsmith, крыніца
+1 Добры падыход. Гэта, напэўна, прасцей, для выпуклай абалонкі, каб знайсці кропку, якая, безумоўна, усярэдзіне корпуса (сярэдняга усіх карпусных вяршыняў), а затым прытрымлівацца вашаму метадзе з зваротнымі ўмовамі поспеху.
дададзена аўтар Jaime, крыніца
Акрамя таго, звярніце ўвагу, што некаторыя з палігона ў прыкладзе не выпуклымі шалупіна, для выпуклай абалонкі вы знойдзеце больш чым на два скрыжаванні. Акрамя таго, не адразу да мяне, як выбраць кропку, «безумоўна, за межамі" корпус. Можа быць, прасцей знайсці кропку «вызначана ўнутры» (напрыклад, барицентр) і паглядзець, калі ён мае адзін або нуль скрыжаванняў, якія таксама ліквідаваць праблемы колинеарности (я мяркую, што корпус уяўляе сабой выпуклы шматкутнік).
дададзена аўтар Vincenzooo, крыніца

Па-першае, атрымаць выпуклую абалонку для вашага аблокі кропак.

Затым цыкл па ўсіх краях выпуклай абалонкі ў парадку супраць гадзінны стрэлкі. Для кожнага з рэбраў, праверыць ці ляжыць ваша мэтавая кропка «злева» ад гэтага краю. Пры гэтым, апрацаваць краю як вектары, якія паказваюць супраць гадзінны стрэлкі вакол выпуклай абалонкі. Калі мэтавая кропка з'яўляецца «левым» з усіх вектараў, то яно змяшчаецца ў шматкутніку; у адваротным выпадку, яна ляжыць па-за шматкутніка.

Loop and Check whether point is always to the

This other Stack Overflow topic includes a solution to finding which "side" of a line a point is on: Determine Which Side of a Line a Point Lies


The runtime complexity of this approach (once you already have the convex hull) is Аб (п) where n is the number of edges that the convex hull has.

Звярніце ўвагу, што гэта будзе працаваць толькі для выпуклых шматкутнікаў. Але вы маеце справу з выпуклай абалонкай, таму ён павінен задаволіць вашыя патрэбы.

It looks like you already have a way to get the convex hull for your point cloud. But if you find that you have to implement your own, Wikipedia has a nice list of convex hull algorithms here: Convex Hull Algorithms

16
дададзена
Калі хто-то ўжо вылічылі выпуклую абалонку кропак, то гэты падыход з'яўляецца найбольш просты.
дададзена аўтар CODError, крыніца

Я б не стаў выкарыстоўваць алгарытм оконтуривающий, таму што вам не трэба вылічыць выпуклую абалонку, вы проста хочаце, каб праверыць, ці з'яўляецца ваша кропка можа быць выяўлена ў выглядзе выпуклай камбінацыі мноства кропак з якіх падмноства вызначае выпуклую абалонку. Акрамя таго, знаходжанне выпуклай абалонкі з'яўляецца вылічальны дорага, асабліва ў больш высокіх вымярэннях.

На самай справе, сама па сабе праблеме высветліць, ці з'яўляецца кропка можа быць выяўлена ў выглядзе выпуклай камбінацыі іншага мноства кропак можа быць сфармуляваная ў выглядзе задачы лінейнага праграмавання.

import numpy as np
from scipy.optimize import linprog

def in_hull(points, x):
    n_points = len(points)
    n_dim = len(x)
    c = np.zeros(n_points)
    A = np.r_[points.T,np.ones((1,n_points))]
    b = np.r_[x, np.ones(1)]
    lp = linprog(c, A_eq=A, b_eq=b)
    return lp.success

n_points = 10000
n_dim = 10
Z = np.random.rand(n_points,n_dim)
x = np.random.rand(n_dim)
print(in_hull(Z, x))

Для прыкладу, я вырашыў праблему для 10000 кропак у 10 вымярэнняў. Час пакарання знаходзіцца ў дыяпазоне мс. Не хацелася б ведаць, колькі часу гэта заняло б з Qhull.

11
дададзена
Гэта не так лёгка зразумець, што вы толькі чытанне кода. Некаторыя каментары, паказваючы матэматыку ззаду было б карысна. Напрыклад: дзе няроўнасць абмежаванне на w_i ? і чаму гэта неабходна, каб дадаць «маштабаванне» вымярэнне (1с)?
дададзена аўтар Juh_, крыніца
Цяпер, калі я правільна разумею, вы толькі хочаце ведаць, калі лінейная задача мае рашэнне, і таму няма ніякай рэальнай аптымізацыі?
дададзена аўтар Juh_, крыніца
Гэта сапраўды крута
дададзена аўтар Juh_, крыніца
Ніца. Я таксама знайшоў, што гэта не з'яўляецца эфектыўным, каб вылічыць поўны корпус (аднак гэта сапраўды эфектыўна яго код). У вас ёсць спасылка на нейкі theorical фоне на «выпуклай камбінацыі мноства кропак»?
дададзена аўтар Juh_, крыніца
Нязначныя пытанне: Z.T ў радку 8 павінна быць points.T я думаю.
дададзена аўтар Bill, крыніца
Гэта самы правільны адказ тут, я думаю.
дададзена аўтар Alex Meiburg, крыніца
@Bill: Дзякуй за ўказанне на гэта. Я усталяваў свой адказ.
дададзена аўтар Nils, крыніца
@Juh_: Пазначым {x_1, ..., x_n} як сукупнасць п кропак, {w_1, ..., w_n} як зменнымі вагамі, і ў як кропкі, якую вы хочаце, каб апісаць з дапамогай камбінацыі гэтых п кропак. Тады \ sum_i w_i x_i = y_i і, то вы хочаце
дададзена аўтар Nils, крыніца
@Juh_: ... пераканайцеся, што \ sum_i w_i = 1 і w_i> = 0. Я выкарыстаў лінейнае праграмаванне, каб знайсці w_i, але могуць быць і іншыя спосабы.
дададзена аўтар Nils, крыніца
@Juh_ Гэта складана. Я не магу пісаць матэматыку тут. SciPy мяркуе, што вы ёсць наступная праблема: min_x {c'w | Авы = Ь, ш> = 0}, дзе ш з'яўляюцца зменнымі, з аб'ектыўнымі каэфіцыенты, і Aw = Ь абмежаванні (ш> = 0 па змаўчанні ў LP). Як з роўна нулю, няма ніякай рэальнай аптымізацыі. Солвер проста правярае магчымасць, то ёсць, ці існуе такое, што ш Ав = Ь выканана. Цяпер, у нашым выпадку Ь = [y_1, ..., y_d, 1] і А = [[x_11 w_1, ..., x_n1 w_n], ..., [x_1d w_1, ..., x_nd w_n], [w_1, ..., w_n]]. У прыведзеным вышэй кропцы запыту ў кода называюцца х, і мноства пункту х называюцца «кропкі».
дададзена аўтар Nils, крыніца
@Juh_ «Чаму неабходна дадаць" маштабаванне "вымярэнне (1с)?» Гэта патрабаванне мае выпуклую камбінацыю, у адваротным выпадку вы б праверыць, калі кропка ляжыць у конусе, які з'яўляецца не тое, што вы хочаце.
дададзена аўтар Nils, крыніца

Падобна на тое, што вы карыстаецеся воблака 2D пункту, таму я хацеў бы, каб накіраваць вас на тэсту ўключэння </а > для кропкі ў шматкутніку тэставання выпуклых шматкутнікаў.

Алгарытм выпуклай абалонкі SciPy дазваляе для знаходжання выпуклых абалонак у 2-й або больш памерах, з'яўляецца больш складаным, чым гэта павінна быць для аблокі кропак 2D. Таму я рэкамендую выкарыстоўваць іншы алгарытм, напрыклад,

гэтай адной . Гэта адбываецца таму, што, як вам сапраўды трэба для кропкі ў шматкутніку тэставання выпуклай абалонкі спіс выпуклых кропак корпуса па гадзінны стрэлцы, і кропка, якая знаходзіцца ўнутры палігона.

Прадукцыйнасці часу гэтага падыходу, як след:

    <�Літый> O (N увайсці N) для пабудовы выпуклай абалонкі </літый> <�Літый> Аб (з) у папярэдняй апрацоўцы, каб вылічыць (і захаваць) куты кліну ад унутранай пункту <�Літый> Аб (ўвайсці гадзіну) у пэўны момант запыту шматкутніка.

Дзе N ёсць лік кропак у воблаку кропак і ч ёсць лік кропак у воблаку кропак выпуклай абалонкі.

4
дададзена

Толькі для камплектнасць, вось рашэнне чалавека беднага па:

import pylab
import numpy
from scipy.spatial import ConvexHull

def is_p_inside_points_hull(points, p):
    global hull, new_points # Remove this line! Just for plotting!
    hull = ConvexHull(points)
    new_points = numpy.append(points, p, axis=0)
    new_hull = ConvexHull(new_points)
    if list(hull.vertices) == list(new_hull.vertices):
        return True
    else:
        return False

# Test:
points = numpy.random.rand(10, 2)   # 30 random points in 2-D
# Note: the number of points must be greater than the dimention.
p = numpy.random.rand(1, 2) # 1 random point in 2-D
print is_p_inside_points_hull(points, p)

# Plot:
pylab.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
    pylab.plot(points[simplex,0], points[simplex,1], 'k-')
pylab.plot(p[:,0], p[:,1], '^r')
pylab.show()

Ідэя простая: вяршыні выпуклай абалонкі мноства кропак P не зменіцца, калі дадаць кропку р , які трапляе «ўнутры» корпус; вяршыні выпуклай абалонкі для [P1, P2, ..., Pn] і [P1, P2, ..., Pn, р] аднолькавыя. Але калі р падае «па-за», то вяршыні павінны змяніцца. Гэта працуе для п-памераў, але вы павінны вылічыць ConvexHull двойчы.

Два прыкладу ўчастка ў 2-D:

мана:

New point (red) falls outside the convex hull

Праўда:

New point (red) falls inside the convex hull

4
дададзена
Я рою гэта! Але я скажу так: праклён памернасці. Больш за 8 памераў і расколы ядра.
дададзена аўтар Ulf Aslak, крыніца

Выкарыстоўвайце ўраўненні атрыбут ConvexHull :

def point_in_hull(point, hull, tolerance=1e-12):
    return all(
        (np.dot(eq[:-1], point) + eq[-1] <= tolerance)
        for eq in hull.equations)

На словах, кропка знаходзіцца ў корпусе, калі і толькі калі для кожнага ўраўненні (апісанні граняў) скалярны твор паміж кропкай і вектарам нармалі ( экв [: - 1] ) плюс зрушэнне ( экв [-1] ) менш або роўна нулю. Вы можаце параўнаць з невялікай станоўчай канстантай допуску = 1E-12 , а не да нуля з-за праблем колькаснага дакладнасці (у адваротным выпадку, вы можаце выявіць, што вяршыня выпуклай абалонкі не ў выпуклая абалонка).

дэманстрацыя:

import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import ConvexHull

points = np.array([(1, 2), (3, 4), (3, 6), (2, 4.5), (2.5, 5)])
hull = ConvexHull(points)

np.random.seed(1)
random_points = np.random.uniform(0, 6, (100, 2))

for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1])

plt.scatter(*points.T, alpha=.5, color='k', s=200, marker='v')

for p in random_points:
    point_is_in_hull = point_in_hull(p, hull)
    marker = 'x' if point_is_in_hull else 'd'
    color = 'g' if point_is_in_hull else 'm'
    plt.scatter(p[0], p[1], marker=marker, color=color)

output of demonstration

4
дададзена

Калі вы жадаеце захаваць з SciPy, вы павінны выпуклай абалонкі (вы зрабілі гэта)

>>> from scipy.spatial import ConvexHull
>>> points = np.random.rand(30, 2)   # 30 random points in 2-D
>>> hull = ConvexHull(points)

затым пабудаваць спіс кропак на корпусе. Вось код з дока пабудаваць корпус

>>> import matplotlib.pyplot as plt
>>> plt.plot(points[:,0], points[:,1], 'o')
>>> for simplex in hull.simplices:
>>>     plt.plot(points[simplex,0], points[simplex,1], 'k-')

Так, пачынаючы з гэтага, я хацеў бы прапанаваць для вылічэнні спісу кропак на корпусе

pts_hull = [(points[simplex,0], points[simplex,1]) 
                            for simplex in hull.simplices] 

(Хоць я не спрабаваў)

І вы таксама можаце прыйсці з вашым уласным кодам для вылічэнні корпуса, вяртаючы х, у кропкі.

If you want to know if a point from your original dataset is on the hull, then you are done.

I what you want is to know if a any point is inside the hull or outside, you must do a bit of work more. What you will have to do could be

  • для ўсіх рэбраў, якія вядуць у дзве сімплекс вашага корпуса: вырашыць, ці будзе вышэй або ніжэй ваша кропка

  • <�Літый> <�р> калі кропка знаходзіцца ніжэй за ўсіх ліній або ліній, перш за ўсё, яна знаходзіцца па-за корпусам </р>

Як хуткасць уверх, як толькі кропка была вышэй адной лініі і ніжэй адзін аднаго, ён знаходзіцца ўнутры корпуса.

1
дададзена
так вы задаволены адказам?
дададзена аўтар octoback, крыніца
можа быць, мы не ясна, пра тое, што знаходзіцца вышэй/пад лініяй. Я мяркую, што лінія мае толькі два бакі, над і пад. то тэст працуе, калі ўлічыць ўсе пары кропак з корпуса.
дададзена аўтар octoback, крыніца
Ваш адказ на ўнутры ці звонку корпуса не з'яўляецца правільным у тым, што вышэй і ніжэй не з'яўляецца дастатковым выпрабаваннем. Напрыклад, калі кропка знаходзіцца ў непасрэднай блізкасці ад корпуса, але, скажам, на паўшляху ўздоўж дыяганалі 45 градусаў, то ваш тэст пацерпіць няўдачу. Замест гэтага сумуюць куты паміж кантрольнай пунктам і ўсімі кропкамі выпуклай абалонкі: калі яна ўнутры кутоў падвядзе да 2pi, а калі звонку яны будуць падводзіць да 0 (ці я мог бы мець некаторыя падрабязнасці гэтага няправільна, але гэта асноўная ідэя).
дададзена аўтар tom10, крыніца
Я хачу, каб высветліць, калі адвольная кропка знаходзіцца ў выпуклай абалонцы кропкавага аблокі так i за яе межамі. :)
дададзена аўтар AME, крыніца

На аснове гэта пост, вось мой хуткае і бруднае рашэнне для выпуклых абласцей з 4-х бакоў (вы можаце лёгка пашырыць яго больш)

def same_sign(arr): return np.all(arr > 0) if arr[0] > 0 else np.all(arr < 0)

def inside_quad(pts, pt):
    a =  pts - pt
    d = np.zeros((4,2))
    d[0,:] = pts[1,:]-pts[0,:]
    d[1,:] = pts[2,:]-pts[1,:]
    d[2,:] = pts[3,:]-pts[2,:]
    d[3,:] = pts[0,:]-pts[3,:]
    res = np.cross(a,d)
    return same_sign(res), res

points = np.array([(1, 2), (3, 4), (3, 6), (2.5, 5)])

np.random.seed(1)
random_points = np.random.uniform(0, 6, (1000, 2))

print wlk1.inside_quad(points, random_points[0])
res = np.array([inside_quad(points, p)[0] for p in random_points])
print res[:4]
plt.plot(random_points[:,0], random_points[:,1], 'b.')
plt.plot(random_points[res][:,0], random_points[res][:,1], 'r.')

enter image description here

0
дададзена