-
Notifications
You must be signed in to change notification settings - Fork 79
/
sutherlandhodgman.jl
62 lines (46 loc) · 1.57 KB
/
sutherlandhodgman.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# ------------------------------------------------------------------
# Licensed under the MIT License. See LICENSE in the project root.
# ------------------------------------------------------------------
"""
SutherlandHodgman()
The Sutherland-Hodgman algorithm for clipping polygons.
## References
* Sutherland, I.E. & Hodgman, G.W. 1974. [Reentrant Polygon Clipping]
(https://dl.acm.org/doi/pdf/10.1145/360767.360802)
### Notes
* The algorithm assumes that the clipping geometry is convex.
"""
struct SutherlandHodgman <: ClippingMethod end
function clip(poly::Polygon, other::Geometry, method::SutherlandHodgman)
c = [clip(ring, boundary(other), method) for ring in rings(poly)]
r = [r for r in c if !isnothing(r)]
isempty(r) ? nothing : PolyArea(r)
end
function clip(ring::Ring{Dim,T}, other::Ring{Dim,T}, ::SutherlandHodgman) where {Dim,T}
# make sure other ring is CCW
occw = orientation(other) == CCW ? other : reverse(other)
r = vertices(ring)
o = vertices(occw)
for i in 1:length(o)
lₒ = Line(o[i], o[i + 1])
n = length(r)
u = Point{Dim,T}[]
for j in 1:n
r₁ = r[j]
r₂ = r[mod1(j + 1, n)]
lᵣ = Line(r₁, r₂)
isinside₁ = (sideof(r₁, lₒ) != RIGHT)
isinside₂ = (sideof(r₂, lₒ) != RIGHT)
if isinside₁ && isinside₂
push!(u, r₁)
elseif isinside₁ && !isinside₂
push!(u, r₁)
push!(u, lᵣ ∩ lₒ)
elseif !isinside₁ && isinside₂
push!(u, lᵣ ∩ lₒ)
end
end
r = u
end
isempty(r) ? nothing : Ring(unique(r))
end