Algorithms.Geometry.RedBlueSeparator.RIC

Given a set of red points and a set of blue points in \(\mathbb{R}^2\) finds a separating line in \(O(n)\) expected time, where \(n\) is the total number of points.

Documentation

separatingLine :: (MonadRandom m, Foldable1 f, Foldable1 g, Fractional r, Ord r) => f (Point 2 r :+ redData) -> g (Point 2 r :+ blueData) -> m (Maybe (Line 2 r))

Given a set of red points and a set of blue points in \(\mathbb{R}^2\) finds a separating line (if it exists). The result is non-strict in the sense that there may be points *on* the line.

running time: \(O(n)\) expected time, where \(n\) is the total number of points.

separatingLine' :: (MonadRandom m, Foldable1 f, Foldable1 g, Fractional r, Ord r) => f (Point 2 r :+ redData) -> g (Point 2 r :+ blueData) -> m (Maybe (Line 2 r))

Given a set of red points and a set of blue points in \(\mathbb{R}^2\) finds a separating line (if it exists) that has all red points *right* (or on) the line, and all blue points left (or on) the line.

running time: \(O(n)\) expected time, where \(n\) is the total number of points.

separatingLine''

Arguments

:: (MonadRandom m, Foldable1 f, Foldable1 g, Fractional r, Ord r)

=> Point 2 r

red point r

-> Point 2 r

a blue point b

-> f (Point 2 r :+ redData)

-> g (Point 2 r :+ blueData)

-> m (Maybe (Line 2 r))

given a red and blue point that are *NOT* vertically alligned, and all red and all blue points, try to find a non-vertical separating line.

running time: \(O(n)\) expected time, where \(n\) is the total number of points.

Vertical Separators

strictVerticalSeparatingLine :: (Foldable1 f, Foldable1 g, Fractional r, Ord r) => f (Point 2 r :+ redData) -> g (Point 2 r :+ blueData) -> Maybe (Line 2 r)

Computes a strict vertical separating line, if one exists

verticalSeparatingLine :: (Foldable1 f, Foldable1 g, Num r, Ord r) => f (Point 2 r :+ redData) -> g (Point 2 r :+ blueData) -> SP (Maybe (Line 2 r)) (Point 2 r :+ redData, Point 2 r :+ blueData)

Test if there is a vertical separating line that has all red points to its right (or on it) and all blue points to its left (or on it). This function also returns the two extremal points; in case a line is returned, the line actually goes through the blue (second) point, if there is no line, this pair provides evidence that there is no vertical separating line.

The line we return actually goes through one blue point.

extremalPoints :: (Foldable1 f, Foldable1 g, Ord r) => f (Point 2 r :+ redData) -> g (Point 2 r :+ blueData) -> (Point 2 r :+ redData, Point 2 r :+ blueData)

Get the the leftmost red point and the rightmost blue point.