Получить альфа-форму (вогнутый корпус) из набора точек, используя Джулию - PullRequest
Новая
       64

Получить альфа-форму (вогнутый корпус) из набора точек, используя Джулию

0 голосов
/ 11 марта 2019

Я хочу вычислить альфа-форму (или даже только вогнутую оболочку) набора точек, используя Джулию. В других вопросах они решили эту проблему в python с помощью тесселяции Делоне Граница, охватывающая данный набор точек .

Этот пакет в Julia может получить тесселяцию Делоне https://github.com/JuliaGeometry/VoronoiDelaunay.jl (хотя я не уверен, обновлен ли он для julia v0.7). Мне интересно, есть ли уже реализация для julia v0.7, которая может получить альфа-форму или даже просто вогнутую оболочку из набора точек.

В качестве альтернативы, есть ли способ эффективно вызвать python (scipy.spatial.Delaunay) для выполнения этой работы?

1 Ответ

2 голосов
/ 12 марта 2019

VoronoiDelaunay.jl работает с Юлией 1.0 и 1.1.Следует также работать с Юлией 0.7.

VoronoiDelaunay.jl имеет некоторые числовые ограничения, например (1.0+eps(), 2.0-eps()), для координат, поэтому вам может потребоваться изменить масштаб точек данных.

Чтобы создать DelaunayTesselation с вашим собственным типом точкиУбедитесь, что ваш тип является подтипом AbstractPoint2D, то есть <: AbstractPoint2D, и определяет методы getx и gety.

Следующий пример кода, я полагаю, находит то, что вы называетеВогнутая оболочка набора точек, используя DelaunayTesselation и выводит результат.Он в основном использует тот же алгоритм в этом ответе .Вы можете легко отредактировать код, чтобы получить форму альфа.

Я не включил некоторые фрагменты кода в функцию.Если вам нужна высокая производительность, пожалуйста, сделайте это.Я использовал === при проверке на равенство точек, которая фактически проверяет, являются ли две точки одним и тем же объектом (то есть адресом в памяти).Если вы каким-то образом окажетесь в коде, который нарушает эту часть, вы можете расширить == и использовать его вместо ===. 

using Random, VoronoiDelaunay, Plots

import Base.==

struct MyEdge{T<:AbstractPoint2D}
    _a::T
    _b::T
end

==(e1::MyEdge{T}, e2::MyEdge{T}) where {T<:AbstractPoint2D} = ((e1._a === e2._a) && (e1._b === e2._b)) || ((e1._b === e2._a) && (e2._b === e1._a))

###==(p1::T, p2::T) where {T<:AbstractPoint2D} = (getx(p1) == getx(p2)) && (gety(p1) == gety(p2))

### Create a Delaunay tesselation from random points
tess = DelaunayTessellation2D(46)

for _ in 1:23
    push!(tess, Point2D(rand()+1, rand()+1))
end

edges = MyEdge[]

function add_edge!(edges, edge)
    i = findfirst(e -> e == edge, edges)

    if isnothing(i) # not found
        push!(edges, edge)
    else # found so not outer, remove this edge
        deleteat!(edges, i) 
    end
end

for trig in tess
    a, b, c = geta(trig), getb(trig), getc(trig)
    add_edge!(edges, MyEdge(b, c))
    add_edge!(edges, MyEdge(a, b))
    add_edge!(edges, MyEdge(a, c))
end

### PLOT
x, y = Float64[], Float64[] # outer edges
for edge in edges
    push!(x, getx(edge._a))
    push!(x, getx(edge._b))
    push!(x, NaN)
    push!(y, gety(edge._a))
    push!(y, gety(edge._b))
    push!(y, NaN)
end

xall, yall = getplotxy(delaunayedges(tess)) # all the edges

plot(xall, yall, color=:blue, fmt=:svg, size=(400,400))
plot!(x, y, color=:red, linewidth=3, opacity=0.5)
...