///|
fn cross(origin : Point, first : Point, second : Point) -> Double {
(first.x - origin.x) * (second.y - origin.y) -
(first.y - origin.y) * (second.x - origin.x)
}
///|
fn sign(value : Double) -> Int32 {
if value > 0.0 {
1
} else if value < 0.0 {
-1
} else {
0
}
}
///|
fn point_on_segment(point : Point, start : Point, end : Point) -> Bool {
if cross(start, end, point) != 0.0 {
return false
}
let min_x = if start.x < end.x { start.x } else { end.x }
let max_x = if start.x > end.x { start.x } else { end.x }
let min_y = if start.y < end.y { start.y } else { end.y }
let max_y = if start.y > end.y { start.y } else { end.y }
point.x >= min_x && point.x <= max_x && point.y >= min_y && point.y <= max_y
}
///|
fn segments_intersect(a : Point, b : Point, c : Point, d : Point) -> Bool {
let ab_c = sign(cross(a, b, c))
let ab_d = sign(cross(a, b, d))
let cd_a = sign(cross(c, d, a))
let cd_b = sign(cross(c, d, b))
if ab_c * ab_d < 0 && cd_a * cd_b < 0 {
return true
}
(ab_c == 0 && point_on_segment(c, a, b)) ||
(ab_d == 0 && point_on_segment(d, a, b)) ||
(cd_a == 0 && point_on_segment(a, c, d)) ||
(cd_b == 0 && point_on_segment(b, c, d))
}
///|
fn edges_adjacent(first : Int32, second : Int32, count : Int32) -> Bool {
first == second ||
(first + 1) % count == second ||
(second + 1) % count == first
}
///|
fn validate_polygon(
id : Int32,
vertices : Array[Point],
) -> Unit raise AnalyticsError {
if id < 0 {
raise InvalidRegion("id must be non-negative")
}
let count = vertices.length()
if count < 3 {
raise InvalidRegion("at least three vertices are required")
}
let mut area_twice = 0.0
for index = 0; index < count; index = index + 1 {
let next = (index + 1) % count
if vertices[index] == vertices[next] {
raise InvalidRegion("adjacent vertices must differ")
}
area_twice += vertices[index].x * vertices[next].y -
vertices[next].x * vertices[index].y
}
if area_twice == 0.0 {
raise InvalidRegion("polygon area must be non-zero")
}
for first = 0; first < count; first = first + 1 {
for second = first + 1; second < count; second = second + 1 {
if edges_adjacent(first, second, count) {
continue
}
let first_end = (first + 1) % count
let second_end = (second + 1) % count
if segments_intersect(
vertices[first],
vertices[first_end],
vertices[second],
vertices[second_end],
) {
raise InvalidRegion("polygon edges must not self-intersect")
}
}
}
}
///|
/// Returns -1 for outside, 0 for boundary and 1 for inside.
fn PolygonRegion::classify(self : PolygonRegion, point : Point) -> Int32 {
let count = self.vertices.length()
let mut inside = false
for index = 0; index < count; index = index + 1 {
let next = (index + 1) % count
let first = self.vertices[index]
let second = self.vertices[next]
if point_on_segment(point, first, second) {
return 0
}
let spans_y = (first.y > point.y) != (second.y > point.y)
if spans_y {
let intersection_x = (second.x - first.x) *
(point.y - first.y) /
(second.y - first.y) +
first.x
if point.x < intersection_x {
inside = !inside
}
}
}
if inside {
1
} else {
-1
}
}
///|
/// Returns -1 for the right side, 0 on the line and 1 for the left side.
fn DirectedLine::classify(self : DirectedLine, point : Point) -> Int32 {
sign(cross(self.start, self.end, point))
}
///|
fn TrackSample::anchor_point(self : TrackSample, anchor : Anchor) -> Point {
let x = (self.bbox.x1() + self.bbox.x2()) / 2.0
let y = match anchor {
Center => (self.bbox.y1() + self.bbox.y2()) / 2.0
BottomCenter => self.bbox.y2()
}
{ x, y, }
}