Arrangements and Visibility

from skgeom import *

In this chapter we create a 2D arrangement, and explore how to use it in order to compute the visibility from different positions inside this arrangement.

A 2D arrangement consists of vertices, segments, and faces.

We can use the insert, and insert_point function on the arrangement to insert new points into it.

Then, the arrangement can be queried or iterated upon by using either the find function or the iterators.

M = 10
outer = [
    Segment2(Point2(-M, -M), Point2(-M, M)), Segment2(Point2(-M, M), Point2(M, M)),
    Segment2(Point2(M, M), Point2(M, -M)), Segment2(Point2(M, -M), Point2(-M, -M))
]

segments = [
    Segment2(Point2(0, 0), Point2(0, 4)), Segment2(Point2(2, 4), Point2(8, 4)),
    Segment2(Point2(3, 4), Point2(-8, 0)), Segment2(Point2(1, 0), Point2(0, 5)),
]
arr = arrangement.Arrangement()

for s in outer:
    arr.insert(s)

for s in segments:
    arr.insert(s)

Now the arrangement can be iterated upon with the halfedges iterator property. Note that the segments that have been inserted are split at their intersections.

for he in arr.halfedges:
    draw.draw(he.curve())

Finding things in the arrangement

We can find the face associated with a certain point in the arrangement, and use the outer_ccb circulator to iterate over the halfedges associated with the face.

q = Point2(-2.5, 5)
face = arr.find(q)

i = face.outer_ccb
first = next(i)
halfedge = next(i)

while first != halfedge:
    print(halfedge.source().point(), halfedge.target().point())
    halfedge = next(i)
print(halfedge.source().point(), halfedge.target().point())

PointC2(10, 10) PointC2(-10, 10)
PointC2(-10, 10) PointC2(-10, -10)
PointC2(-10, -10) PointC2(10, -10)
PointC2(10, -10) PointC2(10, 10)

Similarly, if we query a point that is lying on a halfedge, or a vertex itself we get either a halfedge or a vertex in return.

vertex = arr.find(Point2(0, 0))

vertex

<skgeom._skgeom.arrangement.Vertex at 0x7f41aa4a3d88>

Computing Visibility

We can use the RotationalSweepVisibility class to compute the visibility from a specific point inside the arrangement.

vs = RotationalSweepVisibility(arr)

q = Point2(-2.5, 5)
face = arr.find(q)
vx = vs.compute_visibility(q, face)

for he in arr.halfedges:
    draw.draw(he.curve(), visible_point=False)
for v in vx.halfedges:
    draw.draw(v.curve(), color='red', visible_point=False)

draw.draw(q, color='magenta')

An additional, faster method to compute the visibility is also available, the TriangularExpansionVisibility. However, the TriangularExpansionVisibility requires a one-time initialization cost to be paid. You can read more about both algorithms here: https://doc.cgal.org/latest/Visibility_2/index.html

ts = RotationalSweepVisibility(arr)
tx = ts.compute_visibility(q, face)

for he in arr.halfedges:
    draw.draw(he.curve(), visible_point=False)
for v in tx.halfedges:
    draw.draw(v.curve(), color='red', visible_point=False)

draw.draw(q, color='magenta')