From: Jean Privat Date: Mon, 28 Sep 2015 14:35:27 +0000 (-0400) Subject: Merge: More ini X-Git-Tag: v0.7.8~8 X-Git-Url: http://nitlanguage.org?hp=f712d671875a67e5f6d884ab53ed51c7bd7f9c98 Merge: More ini Fix some package.ini so that there is no more `none` pseudo-tag in the catalog Pull-Request: #1733 Reviewed-by: Lucas Bajolet Reviewed-by: Alexis Laferrière --- diff --git a/benchmarks/polygons/nit/bench_polygon.nit b/benchmarks/polygons/nit/bench_polygon.nit index 695f4aa..d2224b9 100644 --- a/benchmarks/polygons/nit/bench_polygon.nit +++ b/benchmarks/polygons/nit/bench_polygon.nit @@ -25,7 +25,7 @@ fun bench_add_vertices(n: Int) do var randompoints = generate_points(n + 1) var points = randompoints.clone points.remove_at(points.length -1) - var poly = new ConvexPolygon.with_vertices(randompoints) + var poly = new ConvexPolygon(randompoints) poly.sort_ccw poly.add_vertex(randompoints.last) end @@ -45,7 +45,7 @@ end # Bench the convexity verificatioon fun bench_convexity(n : Int) do var randompoints = generate_points(n) - var poly = new ConvexPolygon.with_vertices(randompoints) + var poly = new ConvexPolygon(randompoints) poly.sort_ccw poly.is_convex end @@ -54,7 +54,7 @@ end fun bench_contain(n : Int) do srand_from(50) var randompoints = generate_points(n) - var poly = new ConvexPolygon.with_vertices(randompoints) + var poly = new ConvexPolygon(randompoints) poly.sort_ccw var point = new Point[Float](0.0, 0.0) poly.contain(point) @@ -64,7 +64,7 @@ end fun bench_sorting(n : Int) do var randompoints = generate_points(n) randompoints.shuffle - var poly = new ConvexPolygon.with_vertices(randompoints) + var poly = new ConvexPolygon(randompoints) poly.sort_ccw end @@ -73,8 +73,8 @@ end fun bench_intersection(n : Int) do var r1 = generate_points(n) var r2 = generate_points(n) - var poly1 = new ConvexPolygon.with_vertices(r1) - var poly2 = new ConvexPolygon.with_vertices(r2) + var poly1 = new ConvexPolygon(r1) + var poly2 = new ConvexPolygon(r2) poly1.sort_ccw poly2.sort_ccw poly1.intersects(poly2) diff --git a/lib/geometry/README.md b/lib/geometry/README.md new file mode 100644 index 0000000..3e20f59 --- /dev/null +++ b/lib/geometry/README.md @@ -0,0 +1,56 @@ +Basic geometry data structures and services. + +# Points and Lines + +The very basics of geometry needs, for two and three-dimensional space. + +# Boxes and detection collision + +Boxes module introduces Bounding boxes for Points and Lines and services to detect collision or inclusion between boxes. +It means a simple and fast way to test collision but not really accurate since it uses bounding boxes. + +# Quadtrees + +A QuadTree is a tree data structure in which each internal node has exactly four children +They're most often used to partition two-dimensional space by recursively subdividing +it into four quadrants or regions. + +* They decompose space into adaptable cells +* Each cell has a maximum capacity. When maximum is reached, the cell splits. + +Quadtrees are using Boxed objects to determine their distribution in the 2D space. + +This API provides two different types of Quadtree : Static and Dynamic (respectively `SQuadTree` and `DQuadTree`). + +* Static: When you create the QuadTree, you need to specify the region that it will cover + +* Dynamic: You just need to fill the quadtree with objects, and when the threshold is reached, +it will automatically divide the current region, depending on the distribution of objects already in the region. + +# Polygons + +Some basic polygon services. + +This module contains interesting algorithms for `ConvexPolygon`only at the moment. A Convex polygon can be defined as follow : + +* All its interior angles are less than 180°. this means that all the vertices of the polygon +will point outwards, away from the interior of the shape. + +* Every point on every line segment between two points inside or on the boundary of the polygon +remains inside or on the boundary. + +* The polygon is entirely contained in a closed half-plane defined by each of its edges. + +* For each edge, the interior points are all on the same side of the line that the edge defines. + +* The angle at each vertex contains all other vertices in its edges and interior. + +A polygon which is not convex is called concave. Convex polygon are used because most +geometric problems are simpler and faster on convex objects than on non-convex ones. + +Services provided : + +* Point in convex polygon +* Intersection of convex polygon +* Convex hull of a set of points +* Triangulation of polygon diff --git a/lib/geometry/polygon.nit b/lib/geometry/polygon.nit index 7d274a5..039fb94 100644 --- a/lib/geometry/polygon.nit +++ b/lib/geometry/polygon.nit @@ -19,18 +19,12 @@ module polygon 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 @@ -75,7 +69,7 @@ class ConvexPolygon # 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] # ~~~ @@ -92,7 +86,7 @@ class ConvexPolygon # 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] # ~~~ @@ -101,7 +95,7 @@ class ConvexPolygon sorter.sort(points) end - # Does this polygon intersects `other` ? + # Is `self` convex ? # # ~~~ # var p1 = new Point[Float](0.0, 0.0) @@ -109,31 +103,20 @@ class ConvexPolygon # 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 @@ -151,7 +134,36 @@ class ConvexPolygon 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) @@ -159,26 +171,35 @@ class ConvexPolygon # 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) @@ -186,11 +207,11 @@ class ConvexPolygon # 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] @@ -212,7 +233,7 @@ class ConvexPolygon # 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 # ~~~ @@ -230,12 +251,7 @@ class ConvexPolygon 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 # @@ -245,15 +261,15 @@ class ConvexPolygon # 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 @@ -269,9 +285,7 @@ private class Projection 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 @@ -279,7 +293,7 @@ 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 @@ -317,15 +331,17 @@ private abstract class PolygonSorter 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 @@ -349,7 +365,7 @@ end 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 @@ -373,7 +389,6 @@ private class ClockWiseSort end end - # Get the convex hull of the set of `points` # # ~~~ @@ -410,7 +425,7 @@ fun convex_hull(points: Array[Point[Float]]): ConvexPolygon do 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) ? @@ -424,3 +439,49 @@ end 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 diff --git a/lib/ordered_tree.nit b/lib/ordered_tree.nit index 2a6a10c..0b1d383 100644 --- a/lib/ordered_tree.nit +++ b/lib/ordered_tree.nit @@ -61,6 +61,7 @@ module ordered_tree class OrderedTree[E: Object] super Writable super Collection[E] + super Cloneable # The roots of the tree (in sequence) var roots = new Array[E] @@ -69,17 +70,67 @@ class OrderedTree[E: Object] # 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 @@ -130,16 +181,11 @@ class OrderedTree[E: Object] # 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] @@ -165,21 +211,60 @@ class OrderedTree[E: Object] 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