<commit_before>//
// Copyright (c) 2011-2014 <NAME> <<EMAIL>>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
use ooc-collections
import math
import FloatPoint2D
import FloatBox2D
import FloatTransform2D

// Note: Points must be in clockwise order
FloatConvexHull2D: class {
	_points: VectorList<FloatPoint2D>
	points ::= this _points
	count ::= this _points count
	init: func ~fromPoints (=_points, computeHull := false) { //TODO: Compute the convex hull per default
		if (computeHull)
			this computeHull()
	}
	init: func ~fromBox (box: FloatBox2D) {
		this _points = VectorList<FloatPoint2D> new(4)
		this _points add(box leftTop)
		this _points add(box leftBottom)
		this _points add(box rightBottom)
		this _points add(box rightTop)
	}
	free: override func {
		this _points free()
		super()
	}
	contains: func ~Point (point: FloatPoint2D) -> Bool {
		result := true
		for (i in 0 .. this count)
			if (This _isOnLeft(this _points[i], this _points[(i + 1) % this count], point)) {
				result = false
				break
			}
		result
	}
	contains: func ~ConvexHull (other: This) -> Bool {
		result := true
		for (i in 0 .. other count)
			if (!this contains(other _points[i])) {
				result = false
				break
			}
		result
	}
	contains: func ~FloatBox2D (box: FloatBox2D) -> Bool {
		this contains(box leftBottom) && this contains(box rightBottom) && this contains(box leftTop) && this contains(box rightTop)
	}
	transform: func (transform: FloatTransform2D) -> This {
		newPoints := VectorList<FloatPoint2D> new(this count)
		for (i in 0 .. this count)
			newPoints add(transform * this _points[i])
		This new(newPoints)
	}
	computeHull: func {
		if (this count > 2) {
			// Uses the Quickhull algorithm if more than two points, average complexity O(n log n)
			// https://en.wikipedia.org/wiki/Quickhull
			points := this _points copy()
			this _points clear()
			leftMostIndex := 0
			rightMostIndex := 0
			for (i in 1 .. points count)
				if (points[i] x < points[leftMostIndex] x)
					leftMostIndex = i
				else if (points[i] x > points[rightMostIndex] x)
					rightMostIndex = i
			leftEndpoint := points[leftMostIndex]
			rightEndpoint := points[rightMostIndex]
			leftSet := VectorList<FloatPoint2D> new()
			rightSet := VectorList<FloatPoint2D> new()
			for (i in 0 .. points count)
				if (i != leftMostIndex && i != rightMostIndex)
					if (This _isOnLeft(points[leftMostIndex], points[rightMostIndex], points[i]))
						leftSet add(points[i])
					else
						rightSet add(points[i])
			this _points add(leftEndpoint)
			this _findHull(leftSet, leftEndpoint, rightEndpoint)
			this _points add(rightEndpoint)
			this _findHull(rightSet, rightEndpoint, leftEndpoint)<commit_msg>No copy() needed<commit_after>//
// Copyright (c) 2011-2014 <NAME> <<EMAIL>>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
use ooc-collections
import math
import FloatPoint2D
import FloatBox2D
import FloatTransform2D

// Note: Points must be in clockwise order
FloatConvexHull2D: class {
	_points: VectorList<FloatPoint2D>
	points ::= this _points
	count ::= this _points count
	init: func ~fromPoints (=_points, computeHull := false) { //TODO: Compute the convex hull per default
		if (computeHull)
			this computeHull()
	}
	init: func ~fromBox (box: FloatBox2D) {
		this _points = VectorList<FloatPoint2D> new(4)
		this _points add(box leftTop)
		this _points add(box leftBottom)
		this _points add(box rightBottom)
		this _points add(box rightTop)
	}
	free: override func {
		this _points free()
		super()
	}
	contains: func ~Point (point: FloatPoint2D) -> Bool {
		result := true
		for (i in 0 .. this count)
			if (This _isOnLeft(this _points[i], this _points[(i + 1) % this count], point)) {
				result = false
				break
			}
		result
	}
	contains: func ~ConvexHull (other: This) -> Bool {
		result := true
		for (i in 0 .. other count)
			if (!this contains(other _points[i])) {
				result = false
				break
			}
		result
	}
	contains: func ~FloatBox2D (box: FloatBox2D) -> Bool {
		this contains(box leftBottom) && this contains(box rightBottom) && this contains(box leftTop) && this contains(box rightTop)
	}
	transform: func (transform: FloatTransform2D) -> This {
		newPoints := VectorList<FloatPoint2D> new(this count)
		for (i in 0 .. this count)
			newPoints add(transform * this _points[i])
		This new(newPoints)
	}
	computeHull: func {
		if (this count > 2) {
			// Uses the Quickhull algorithm if more than two points, average complexity O(n log n)
			// https://en.wikipedia.org/wiki/Quickhull
			points := this _points
			this _points = VectorList<FloatPoint2D> new()
			leftMostIndex := 0
			rightMostIndex := 0
			for (i in 1 .. points count)
				if (points[i] x < points[leftMostIndex] x)
					leftMostIndex = i
				else if (points[i] x > points[rightMostIndex] x)
					rightMostIndex = i
			leftEndpoint := points[leftMostIndex]
			rightEndpoint := points[rightMostIndex]
			leftSet := VectorList<FloatPoint2D> new()
			rightSet := VectorList<FloatPoint2D> new()
			for (i in 0 .. points count)
				if (i != leftMostIndex && i != rightMostIndex)
					if (This _isOnLeft(points[leftMostIndex], points[rightMostIndex], points[i]))
						leftSet add(points[i])
					else
						rightSet add(points[i])
			this _points add(leftEndpoint)
			this _findHull(leftSet, leftEndpoint, rightEndpoint)
			this _points add(rightEndpoint)
			this _findHull(rightSet, rightEndpoint, leftEndpoint)
{'fraction_non_alphanumeric': 0.10396861324883054, 'fraction_numerical': 0.010110155424777426, 'mean_word_length': 3.700709219858156, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 34, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4718778', 'n_tokens_mistral': 2309, 'n_tokens_neox': 2037, 'n_words': 745}