Aleph::ConvexPolygonIntersectionBasic Class Reference

Basic exact intersection for closed convex polygons. More...

#include <geom_algorithms.H>

Public Member Functions
Polygon	operator() (const Polygon &subject, const Polygon &clip) const
	Intersect two closed convex polygons.

Static Private Member Functions
static Array< Point >	extract_vertices (const Polygon &poly)
static Geom_Number	signed_double_area (const Array< Point > &verts)
static bool	is_convex (const Array< Point > &verts)
static bool	inside_half_plane (const Point &p, const Point &a, const Point &b, const bool clip_ccw)
static Point	line_intersection (const Point &s, const Point &e, const Point &a, const Point &b)
static void	push_clean (Array< Point > &out, const Point &p)
static Array< Point >	normalize_vertices (const Array< Point > &pts)
static Polygon	build_polygon (const Array< Point > &pts)

Detailed Description

Basic exact intersection for closed convex polygons.

Computes the intersection of two closed convex polygons using the Sutherland-Hodgman clipping algorithm.

Scope

• Convex subject polygon.
• Convex clip polygon.
• Exact arithmetic (Geom_Number) through robust predicates.

Complexity

• Time: O(n * m), where n and m are vertex counts.
• Space: O(n + m).

Definition at line 1576 of file geom_algorithms.H.

Member Function Documentation

build_polygon()

static Polygon Aleph::ConvexPolygonIntersectionBasic::build_polygon ( const Array< Point > &  pts )

inlinestaticprivate

Definition at line 1672 of file geom_algorithms.H.

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

Referenced by operator()().

extract_vertices()

static Array< Point > Aleph::ConvexPolygonIntersectionBasic::extract_vertices ( const Polygon &  poly )

inlinestaticprivate

Definition at line 1578 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::GeomPolygonUtils::extract_vertices(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

Referenced by operator()().

inside_half_plane()

static bool Aleph::ConvexPolygonIntersectionBasic::inside_half_plane ( const Point &  p, const Point &  a, const Point &  b, const bool  clip_ccw  )

inlinestaticprivate

Definition at line 1599 of file geom_algorithms.H.

References Aleph::CCW, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), and Aleph::orientation().

Referenced by operator()().

is_convex()

static bool Aleph::ConvexPolygonIntersectionBasic::is_convex ( const Array< Point > &  verts )

inlinestaticprivate

Definition at line 1592 of file geom_algorithms.H.

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

Referenced by operator()().

line_intersection()

static Point Aleph::ConvexPolygonIntersectionBasic::line_intersection ( const Point &  s, const Point &  e, const Point &  a, const Point &  b  )

inlinestaticprivate

Definition at line 1607 of file geom_algorithms.H.

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

Referenced by operator()().

normalize_vertices()

static Array< Point > Aleph::ConvexPolygonIntersectionBasic::normalize_vertices ( const Array< Point > &  pts )

inlinestaticprivate

Definition at line 1659 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), push_clean(), and Aleph::Array< T >::reserve().

Referenced by build_polygon(), and operator()().

operator()()

Polygon Aleph::ConvexPolygonIntersectionBasic::operator() ( const Polygon &  subject, const Polygon &  clip  ) const

inline

Intersect two closed convex polygons.

Parameters

subject	Convex subject polygon.
clip	Convex clipping polygon.

Returns

Intersection polygon (possibly empty, segment, or polygonal area).

Exceptions

domain_error

if any polygon is open, has < 3 vertices, or is non-convex.

Definition at line 1696 of file geom_algorithms.H.

References ah_domain_error_if, build_polygon(), Aleph::divide_and_conquer_partition_dp(), extract_vertices(), inside_half_plane(), is_convex(), line_intersection(), normalize_vertices(), output, push_clean(), and signed_double_area().

push_clean()

static void Aleph::ConvexPolygonIntersectionBasic::push_clean ( Array< Point > &  out, const Point &  p  )

inlinestaticprivate

Definition at line 1632 of file geom_algorithms.H.

References Aleph::COLLINEAR, Aleph::divide_and_conquer_partition_dp(), Aleph::on_segment(), and Aleph::orientation().

Referenced by normalize_vertices(), and operator()().

signed_double_area()

static Geom_Number Aleph::ConvexPolygonIntersectionBasic::signed_double_area ( const Array< Point > &  verts )

inlinestaticprivate

Definition at line 1587 of file geom_algorithms.H.

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

Referenced by operator()().

---

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

• geom_algorithms.H