import points_and_lines
-# Convex Polygon class
-class ConvexPolygon
-
+# Abstraction of a Polygon
+abstract class APolygon
# Vertices of this polygon
- var points = new Array[Point[Float]]
+ var points: Array[Point[Float]]
- # Init this polygon with a list of `points`
- # REQUIRE `pts.length == 3`
- init with_vertices(pts: Array[Point[Float]]) do
- assert pts.length >= 3
- points.add_all(pts)
- end
+ init do assert points.length >= 3
# Get an array of the x coordinates of the vertices
private fun x_coordinates: Array[Float] do
# var p3 = new Point[Float](0.0, 5.0)
# var p4 = new Point[Float](5.0, 5.0)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# poly.sort_ccw
# assert poly.points == [p4, p2, p1, p3]
# ~~~
# var p3 = new Point[Float](0.0, 5.0)
# var p4 = new Point[Float](5.0, 5.0)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# poly.sort_cw
# assert poly.points == [p3, p1, p2, p4]
# ~~~
sorter.sort(points)
end
- # Does this polygon intersects `other` ?
+ # Is `self` convex ?
#
# ~~~
# var p1 = new Point[Float](0.0, 0.0)
# var p3 = new Point[Float](0.0, 5.0)
# var p4 = new Point[Float](5.0, 5.0)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# poly.sort_ccw
- # p1 = new Point[Float](2.5, 2.5)
- # p2 = new Point[Float](7.5, 2.5)
- # p3 = new Point[Float](2.5, 7.5)
- # p4 = new Point[Float](7.5, 7.5)
- # arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly2 = new ConvexPolygon.with_vertices(arr)
- # poly2.sort_ccw
- # assert poly.intersects(poly2)
+ # assert poly.is_convex
# ~~~
- fun intersects(other: ConvexPolygon): Bool do
- assert is_convex
-
- var axes1 = axes
- var axes2 = other.axes
- for axis in axes1 do
- var project1 = project(axis)
- var project2 = other.project(axis)
- if not project1.overlap(project2) then return false
- end
- for axis in axes2 do
- var project1 = project(axis)
- var project2 = other.project(axis)
- if not project1.overlap(project2) then return false
+ fun is_convex: Bool do
+ var prev = points[points.length - 2]
+ var curr = points[points.length - 1]
+ var next = points[0]
+ var is_ccw = turn_left(prev, curr, next)
+ for i in [1..points.length[ do
+ prev = curr
+ curr= next
+ next = points[i]
+ if turn_left(prev ,curr, next) != is_ccw then return false
end
return true
end
return projection
end
- # Is this polygon convex ?
+ # Remove `p` from the vertices, keeping at least 3 vertices
+ fun delete_vertex(p: Point[Float]) do
+ assert points.length > 3
+ points.remove(p)
+ end
+
+ # Does `self` intersects with `other`
+ fun intersects(other: APolygon): Bool is abstract
+
+ # Is `p` contained in `self` ?
+ fun contain(p: Point[Float]): Bool is abstract
+
+ # Add a vertex to `self`
+ fun add_vertex(p: Point[Float]): Bool do
+ points.add(p)
+ return true
+ end
+end
+
+# A simple polygon
+class Polygon
+ super APolygon
+ # TODO: implement algorithms for concave polygons ?
+end
+
+# Convex Polygon class
+class ConvexPolygon
+ super APolygon
+
+ # Does this polygon intersects `other` ?
#
# ~~~
# var p1 = new Point[Float](0.0, 0.0)
# var p3 = new Point[Float](0.0, 5.0)
# var p4 = new Point[Float](5.0, 5.0)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# poly.sort_ccw
- # assert poly.is_convex
+ # p1 = new Point[Float](2.5, 2.5)
+ # p2 = new Point[Float](7.5, 2.5)
+ # p3 = new Point[Float](2.5, 7.5)
+ # p4 = new Point[Float](7.5, 7.5)
+ # arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly2 = new ConvexPolygon(arr)
+ # poly2.sort_ccw
+ # assert poly.intersects(poly2)
# ~~~
- fun is_convex: Bool do
- var prev = points[points.length - 2]
- var curr = points[points.length - 1]
- var next = points[0]
- var is_ccw = turn_left(prev, curr, next)
- for i in [1..points.length[ do
- prev = curr
- curr= next
- next = points[i]
- if turn_left(prev ,curr, next) != is_ccw then return false
+ redef fun intersects(other) do
+ assert is_convex
+
+ var axes1 = axes
+ var axes2 = other.axes
+ for axis in axes1 do
+ var project1 = project(axis)
+ var project2 = other.project(axis)
+ if not project1.overlap(project2) then return false
+ end
+ for axis in axes2 do
+ var project1 = project(axis)
+ var project2 = other.project(axis)
+ if not project1.overlap(project2) then return false
end
return true
end
- # Check if `p` is in the polygon
- #
# ~~~
# var p1 = new Point[Float](0.0, 0.0)
# var p2 = new Point[Float](5.0, 0.0)
# var p4 = new Point[Float](5.0, 5.0)
# var p5 = new Point[Float](2.5, 2.5)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# poly.sort_ccw
# assert poly.contain(p5)
# ~~~
- fun contain(p : Point[Float]): Bool do
+ redef fun contain(p) do
var prev = points[points.length - 1]
var curr = p
var next = points[0]
# var p3 = new Point[Float](0.0, 5.0)
# var p4 = new Point[Float](5.0, 5.0)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# poly.sort_ccw
# assert poly.is_ccw
# ~~~
return not turn_left(prev, points[min_index], next)
end
- # Remove `p` from the vertices, keeping at least 3 vertices
- fun delete_vertex(p: Point[Float]) do
- if points.length > 3 then
- points.remove(p)
- end
- end
+
# Add a vertex to the polygon
#
# var p3 = new Point[Float](0.0, 5.0)
# var p4 = new Point[Float](5.0, 5.0)
# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
- # var poly = new ConvexPolygon.with_vertices(arr)
+ # var poly = new ConvexPolygon(arr)
# var p5 = new Point[Float](2.5, 7.5)
# assert poly.add_vertex(p5)
# ~~~
- fun add_vertex(p: Point[Float]): Bool do
+ redef fun add_vertex(p) do
assert points.length >= 3
var temp_list = points.clone
temp_list.add(p)
- var temp_polygon = new ConvexPolygon.with_vertices(temp_list)
+ var temp_polygon = new ConvexPolygon(temp_list)
temp_polygon.sort_ccw
if temp_polygon.is_convex then
points = temp_polygon.points
var min: Float is writable
var max: Float is writable
- fun overlap(other: Projection): Bool do
- return not (min > other.max or other.min > max)
- end
+ fun overlap(other: Projection): Bool do return not (min > other.max or other.min > max)
end
private class PointXCompare
redef type COMPARED: Point[Float]
- redef fun compare(a,b : COMPARED): Int do
+ redef fun compare(a,b) do
if a.x == b.x then
if a.y == b.y then return 0
if a.y > b.y then return - 1
end
end
+#TODO: CounterClockWise and ClockWise sorts are broken in some cases of concave polygons
+
# Sort the vertices of a polygon in counter clockwise order
private class CounterClockWiseSort
super PolygonSorter
- redef fun compare(a,b: COMPARED): Int do
+ redef fun compare(a,b) do
if a.x == b.x and a.y == b.y then return 0
if a.x - center.x >= 0.0 and b.x - center.x < 0.0 then return -1
if a.x - center.x < 0.0 and b.x - center.x >= 0.0 then return 1
- if a.x - center.x == 0.0 and b.x - center.x == 0 then
+ if a.x - center.x == 0.0 and b.x - center.x == 0.0 then
if a.y - center.y >= 0.0 or b.y - center.y >= 0.0 then
if a.y > b.y then return -1
return 1
private class ClockWiseSort
super PolygonSorter
- redef fun compare(a,b: COMPARED): Int do
+ redef fun compare(a,b) do
if a.x == b.x and a.y == b.y then return 0
if a.x - center.x >= 0.0 and b.x - center.x < 0.0 then return 1
if a.x - center.x < 0.0 and b.x - center.x >= 0.0 then return -1
end
end
-
# Get the convex hull of the set of `points`
#
# ~~~
pl1.remove_at(pl1.length - 1)
pl2.remove_at(pl2.length -1)
pl2.add_all(pl1)
- return new ConvexPolygon.with_vertices(pl2)
+ return new ConvexPolygon(pl2)
end
# Is the angle between [p1,p2] and [p2,p3] going left (counter clockwise) or right (clockwise) ?
fun turn_left(p1, p2, p3: Point[Float]): Bool do
return ((p2.x - p1.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p2.y - p1.y)) > 0.0
end
+
+# Split a polygon into triangles
+# Useful for converting a concave polygon into multiple convex ones
+fun triangulate(pts: Array[Point[Float]], results: Array[ConvexPolygon]) do
+ var poly = new Polygon(pts)
+ poly.sort_ccw
+ pts = poly.points
+ recursive_triangulate(pts, results)
+end
+
+private fun recursive_triangulate(pts: Array[Point[Float]], results: Array[ConvexPolygon]) do
+ if pts.length == 3 then
+ results.add(new ConvexPolygon(pts))
+ return
+ end
+ var prev = pts[pts.length - 1]
+ var curr = pts[0]
+ var next = pts[1]
+ for i in [1..pts.length[ do
+ if turn_left(prev, curr, next) then
+ prev = pts[i-1]
+ curr = next
+ if i+1 == pts.length then next = pts[pts.length - 1] else next = pts[i+1]
+ continue
+ end
+ var contains = false
+ var triangle = new ConvexPolygon(new Array[Point[Float]].with_items(prev, curr, next))
+ for p in pts do
+ if p != prev and p != curr and p != next then
+ if triangle.contain(p) then
+ contains = true
+ break
+ end
+ end
+ end
+ if not contains then
+ results.add(triangle)
+ pts.remove(curr)
+ recursive_triangulate(pts, results)
+ break
+ end
+ prev = pts[i-1]
+ curr = next
+ if i+1 == pts.length then next = pts[pts.length - 1] else next = pts[i+1]
+ end
+end
class OrderedTree[E: Object]
super Writable
super Collection[E]
+ super Cloneable
# The roots of the tree (in sequence)
var roots = new Array[E]
# For each element, the ordered array of its direct sub-elements.
var sub = new HashMap[E, Array[E]]
+ # The parent of each element.
+ #
+ # Roots have `null` as parent.
+ private var parents = new HashMap[E, nullable E]
+
+ redef fun length do return parents.length
+
+ redef fun has(e) do return parents.has_key(e)
+
+ # The parent of the element `e`
+ #
+ # Roots have `null` as parent.
+ #
+ # ~~~
+ # var tree = new OrderedTree[Int]
+ # tree.add(1, 2)
+ # assert tree.parent(2) == 1
+ # assert tree.parent(1) == null
+ # ~~~
+ fun parent(e: E): nullable E do return parents[e]
+
# Add a new element `e` in the tree.
+ #
# `p` is the parent of `e`.
- # if `p` is null, then `e` is a root element.
+ # If `p` is null, then `e` is a root element.
+ #
+ # If `e` is already in the tree, it is detached from its old
+ # parent and attached to the new parent `p`.
fun add(p: nullable E, e: E)
do
+ detach(e)
+ parents[e] = p
if p == null then
roots.add(e)
- else if sub.has_key(p) then
- sub[p].add(e)
else
- sub[p] = [e]
+ if not has(p) then add(null, p)
+ if sub.has_key(p) then
+ sub[p].add(e)
+ else
+ sub[p] = [e]
+ end
+ end
+ end
+
+ # Append all nodes `es` as children of `p`.
+ fun add_all(p: nullable E, es: Collection[E])
+ do
+ for e in es do add(p, e)
+ end
+
+ # Temporary remove `e`.
+ #
+ # Children of `e` are left untouched in the tree.
+ # This make the tree inconstant until `e` is added back.
+ private fun detach(e: E)
+ do
+ var old_parent = parents.get_or_null(e)
+ if old_parent != null then
+ sub[old_parent].remove(e)
+ else if roots.has(e) then
+ roots.remove(e)
end
end
# Order is preserved
#
# var tree = new OrderedTree[Int]
- # tree.add(null, 1)
- # tree.add(1, 11)
- # tree.add(11, 111)
- # tree.add(11, 112)
- # tree.add(1, 12)
- # tree.add(12, 121)
- # tree.add(12, 122)
- # tree.add(null, 2)
- # tree.add(2, 21)
- # tree.add(2, 22)
+ # tree.add_all(null, [1, 2])
+ # tree.add_all(1, [11, 12])
+ # tree.add_all(11, [111, 112])
+ # tree.add_all(12, [121, 122])
+ # tree.add_all(2, [21, 22])
# assert tree.to_a == [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
redef fun to_a: Array[E] do
var res = new Array[E]
redef fun first do return roots.first
# var tree = new OrderedTree[Int]
- # tree.add(null, 1)
- # tree.add(1, 11)
- # tree.add(11, 111)
- # tree.add(11, 112)
- # tree.add(1, 12)
- # tree.add(12, 121)
- # tree.add(12, 122)
- # tree.add(null, 2)
- # tree.add(2, 21)
- # tree.add(2, 22)
+ # tree.add_all(null, [1, 2])
+ # tree.add_all(1, [11, 12])
+ # tree.add_all(11, [111, 112])
+ # tree.add_all(12, [121, 122])
+ # tree.add_all(2, [21, 22])
# var order = [1, 11, 111, 112, 12, 121, 122, 2, 21, 22]
- # var res = new Array[Int]
- # for i in tree do res.add(i)
- # assert res == order
+ # assert tree.iterator.to_a == order
redef fun iterator do return new OrderedTreeIterator[E](self)
+
+ # Two trees are equal if they have the same nodes in the same order
+ #
+ # ~~~
+ # var t1 = new OrderedTree[Int]
+ # t1.add_all(null, [1, 2])
+ # t1.add_all(1, [11, 12])
+ #
+ # var t2 = new OrderedTree[Int]
+ # t2.add_all(null, [1, 2])
+ #
+ # assert t1 != t2
+ #
+ # t2.add_all(1, [11, 12])
+ #
+ # assert t1 == t2
+ # ~~~
+ redef fun ==(other)
+ do
+ if not other isa OrderedTree[Object] then return false
+ return roots == other.roots and sub == other.sub
+ end
+
+ redef fun hash
+ do
+ return roots.hash + sub.hash
+ end
+
+ # Shallow clone of the tree.
+ #
+ # ~~~
+ # var t = new OrderedTree[Int]
+ # t.add_all(null, [1, 2])
+ # t.add_all(1, [11, 12])
+ #
+ # assert t.clone == t
+ # ~~~
+ redef fun clone
+ do
+ var res = new OrderedTree[E]
+ res.add_all(null, roots)
+ for p, es in sub do
+ res.add_all(p, es)
+ end
+ return res
+ end
end
# An Iterator over an OrderedTree