Compute the visibility polygon from a point inside a simple polygon. More...

#include <geom_algorithms.H>

Classes
class	EdgeStatusTree
	BST-based sweep status for active edges, ordered by ray-intersection distance. More...

Public Member Functions
Polygon	operator() (const Polygon &polygon, const Point &query) const
	Compute the visibility polygon.

Static Private Member Functions
static int	angle_quadrant (const Geom_Number &dx, const Geom_Number &dy)
	Quadrant of direction (dx, dy): 0 = +x+y, 1 = -x+y, 2 = -x-y, 3 = +x-y.

static bool	angle_less (const Point &q, const Point &a, const Point &b)
	True if direction (a - q) has a smaller angle than (b - q).

static Geom_Number	ray_param (const Point &q, const Point &dir, const Point &e0, const Point &e1)
	Parametric t along ray q + t*(dir-q) for intersection with edge (e0,e1).

static Point	ray_edge_hit (const Point &q, const Point &dir, const Point &e0, const Point &e1)
	Intersection point of ray from q through dir with edge (e0, e1).

Detailed Description

Compute the visibility polygon from a point inside a simple polygon.

Uses a rotational plane sweep (Lee 1979). All angular comparisons are exact (quadrant + cross product — no atan2).

Complexity

Time: O(n log n) — rotational sweep with Treap-based status tree
Space: O(n)

Example: Polygon poly;

poly.add_vertex(Point(0,0)); poly.add_vertex(Point(4,0));

poly.add_vertex(Point(4,4)); poly.add_vertex(Point(0,4));

poly.close();

VisibilityPolygon vp;

auto vis = vp(poly, Point(2,2));

Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229

Aleph::Polygon
A general (irregular) 2D polygon defined by a sequence of vertices.
Definition polygon.H:246

Aleph::Polygon::add_vertex
void add_vertex(const Point &point)
Add a vertex to the polygon.
Definition polygon.H:677

Aleph::Polygon::close
void close()
Close the polygon.
Definition polygon.H:840

Aleph::VisibilityPolygon
Compute the visibility polygon from a point inside a simple polygon.
Definition geom_algorithms.H:9594

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Definition at line 9593 of file geom_algorithms.H.

Member Function Documentation

◆ angle_less()

static bool Aleph::VisibilityPolygon::angle_less	(	const Point &	q,
		const Point &	a,
		const Point &	b
	)

inlinestaticprivate

True if direction (a - q) has a smaller angle than (b - q).

Definition at line 9606 of file geom_algorithms.H.

References angle_quadrant(), Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by operator()().

◆ angle_quadrant()

static int Aleph::VisibilityPolygon::angle_quadrant	(	const Geom_Number &	dx,
		const Geom_Number &	dy
	)

inlinestaticprivate

Quadrant of direction (dx, dy): 0 = +x+y, 1 = -x+y, 2 = -x-y, 3 = +x-y.

Definition at line 9596 of file geom_algorithms.H.

References Aleph::and, and Aleph::divide_and_conquer_partition_dp().

Referenced by angle_less().

◆ operator()()

Polygon Aleph::VisibilityPolygon::operator()	(	const Polygon &	polygon,
		const Point &	query
	)		const

inline

Compute the visibility polygon.

Parameters

polygon	A closed simple polygon.
query	A point strictly inside the polygon.

Returns: The visibility polygon.

Definition at line 9753 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), ah_domain_error_if, Aleph::and, angle_less(), Aleph::Array< T >::append(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), Aleph::VisibilityPolygon::EdgeStatusTree::erase(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Dlink::Iterator::has_curr(), Aleph::HTList::Iterator::has_curr(), Aleph::VisibilityPolygon::EdgeStatusTree::insert(), Aleph::Polygon::is_closed(), Aleph::VisibilityPolygon::EdgeStatusTree::min(), Aleph::quicksort_op(), ray_edge_hit(), ray_param(), Aleph::Array< T >::reserve(), Aleph::Polygon::size(), and Aleph::PointInPolygonWinding::strictly_contains().

◆ ray_edge_hit()

static Point Aleph::VisibilityPolygon::ray_edge_hit	(	const Point &	q,
		const Point &	dir,
		const Point &	e0,
		const Point &	e1
	)

inlinestaticprivate

Intersection point of ray from q through dir with edge (e0, e1).

Definition at line 9652 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), and ray_param().

Referenced by operator()().

◆ ray_param()

static Geom_Number Aleph::VisibilityPolygon::ray_param	(	const Point &	q,
		const Point &	dir,
		const Point &	e0,
		const Point &	e1
	)

inlinestaticprivate

Parametric t along ray q + t*(dir-q) for intersection with edge (e0,e1).

Returns -1 if parallel / no intersection.

Definition at line 9629 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by Aleph::VisibilityPolygon::EdgeStatusTree::insert(), operator()(), and ray_edge_hit().

The documentation for this class was generated from the following file:

geom_algorithms.H

Classes

Public Member Functions

Static Private Member Functions

Detailed Description

Complexity

Member Function Documentation

◆ angle_less()

◆ angle_quadrant()

◆ operator()()

◆ ray_edge_hit()

◆ ray_param()