7180ab87890bb64e762715c125d912788cf1ffae

Committed 31 Mar 2025 02:28PM UTC coverage: 96.93% (+0.08%) from 96.847%

Build # 7180ab87890bb64e762715c125d912788cf1ffae

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1 from eskil/docs-cleanup

V3 branch

Run Details

77 of 80 new or added lines in 5 files covered. (96.25%)

1 existing line in 1 file now uncovered.

221 of 228 relevant lines covered (96.93%)

245.82 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.1

/lib/polygon_map.ex

defmodule Scurry.PolygonMap do
  @moduledoc """
  Utility functions to work on a polygon map.

  A polygon map is a set of a primary polygon - the **main** boundary that
  outlines the world - and a list of polygons that make **holes** in the main
  polygon.

  See `Polygon` for details on how polygons are composed.

  The use case is eg. making a map (the **main** polygon) with obstacles (the
  **holes**), and use the `Astar` module to find the shortest path between
  points in the map.

  See [Quickstart](quickstart.html) for a concrete end-to-end example of
  defining a world and holes/obstacles, then using `PolygonMap` and `Astar`
  modules to do path finding within this.
  """

  alias Scurry.Polygon
  alias Scurry.Vector
  use Scurry.Types
  use Scurry.Astar.Types

  @doc """
  Given a polygon map (`world` & `holes`), returns a list of vertices for a
  walkmap for A-star search


  ## Params

  * `world` (`t:polygon/0`), the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.

  ## Returns

  The walkmap as a `t:list/0` of `t:vector/0` that are the `worlds`'s concave
  vertices and the convex ones of the `holes`.

  These are used when generating the walk map, since only the `world`'s concave
  and the `holes`' convex ones limit where you can traverse in a 2D map. Any
  path has to walk around the holes' convex points and the world's concave.

  See [Quickstart](quickstart.html) for a concrete example.
  """
  @spec get_vertices(polygon(), list(polygon())) :: list(vector())
  def get_vertices(world, holes) do
    {concave, _convex} = Polygon.classify_vertices(world)

    convex =
      Enum.reduce(holes, [], fn points, acc ->
        {_concave, convex} = Polygon.classify_vertices(points)
        acc ++ convex
      end)

    concave ++ convex
  end

  @doc """
  Given a polygon map (`world` & `holes`) and list of vertices, makes the walk
  graph for a A-star search.

  ## Params

  * `world` (`t:polygon/0`) the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
  * `vertices` (`t:list/0`), the result of `get_vertices/2`.
  * `cost_fun` (`t:cost_fun/0`) a "cost" function.

  The `cost_fun` is a function that indicates the of traversing between to
  points. It defaults to `Scurry.Vector.distance/2`, which is suitable for
  basic 2D map walking.

  ## Returns

  A `t:graph/0`, which is a map of all node to node reachable edges and their
  cost. This graphs is one of the parameters for a call to `Astar.search/4`.

  > ## Todo
  >
  > This should ideally take `line_of_sight/3` as a function so users can
  > customise which vertices can reach each other. But for now, users can make
  > the graph themselves just as easily.

  """
  @spec create_graph(polygon(), list(polygon()), list(vector()), cost_fun()) :: graph()
  def create_graph(world, holes, vertices, cost_fun \\ nil)

  def create_graph(world, holes, vertices, nil) do
    create_graph(world, holes, vertices, &Vector.distance/2)
  end

  def create_graph(world, holes, vertices, cost_fun) do
    get_edges(world, holes, vertices, vertices, cost_fun)
  end

  @doc """
  Given a polygon map (main & holes), list of vertices and the initial graph
  from `create_graph/4`, extend the graph with extra `points`.

  This is used to "temporarily" expand the created walk graph with a start and
  end-point. This is a minor performance optimisation that saves work by
  reusing the fixed nodes and extend it with the moveable points.

  ## Params

  * `graph` (`t:graph/0`) the walk graph, as created by `create_graph/4`. This is used to return a new graph that's extended with `points`.
  * `world` (`t:polygon/0`) the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
  * `vertices` (`t:list/0`) the list of vertices returned by `get_vertices/4`
    and used for `create_graph/4` to get `graph`.
  * `points` (`t:list/0`) a list of vectors (`t:vector/0`), `[{x, y}, {x, y}...]`, to extend with. Eg. a stop
  * `cost_fun` (`t:cost_fun/0`) a "cost" function.

  `world` and `holes` need to be passed in in addition to `graph`, so the
  function can determine line-of-sights between the existing graph and new
  points from `points`.

  The `cost_fun` is a function that indicates the of traversing between to
  points. It defaults to `Scurry.Vector.distance/2`, which is suitable for
  basic 2D map walking.

  ## Returns

  A tuple with the extended graph plus the combined list of vertices and new
  points, `{new_graph, new_vertices}`. The `new_graph` is intended to be used
  in calls to `Astar.search/4`, and `new_vertices` is solely provided as
  informational, eg. for displaying the graphs visually.
  """
  def extend_graph(graph, world, holes, vertices, points, cost_fun \\ nil)

  def extend_graph(graph, world, holes, vertices, points, nil) do
    extend_graph(graph, world, holes, vertices, points, &Vector.distance/2)
  end

  def extend_graph(graph, world, holes, vertices, points, cost_fun) do
    # To extend the graph `graph` made up up `vertices` with new points
    # `points`, we need to find three sets of edges (sub-graphs). The ones from
    # the new points to the existing vertices, vice-versa, and between the new
    # points.
    set_a = get_edges(world, holes, points, vertices, cost_fun)
    set_b = get_edges(world, holes, vertices, points, cost_fun)
    set_c = get_edges(world, holes, points, points, cost_fun)

    # Merge the three new sub-graphs into graph. This uses Map.merge with a
    # merge func that combines values for identical keys to extend them instead
    # of replacing, and dedupes.
    merge_fun = fn _k, v1, v2 ->
      Enum.dedup(v1 ++ v2)
    end

    graph =
      graph
      |> Map.merge(set_a, merge_fun)
      |> Map.merge(set_b, merge_fun)
      |> Map.merge(set_c, merge_fun)

    {graph, vertices ++ points}
  end

  @doc """

  Find the nearest point on the line that is inside the world polygion and
  outside all hole polygons.

  The purpose of this function is to determine compute a suitable end for the
  `points` parameter for `extend_graph/6`. Imagine a UI in which the users
  clicks on a point to walk to. If that click is outside the world map or
  inside a hole/obstacle, we can either refuse to compute a path, or we can use
  `nearest_point/3` to find the closest reachable point to the click.

  ## Params

  * `world` (`t:polygon/0`) the polygon that defines the outer boundary.
  * `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
  * `point` (`t:vector/0`) the point for which to find the nearst point.

  ## Returns

  A new point (`t:vector/0`) `p={x, y}` such that;

  * if `point` is _outside_ the world polygon, the new `p` is the closest point *on*
    the edge of the `world` polygon.

  * if `point` is _inside_ the world polygon, but also *inside* any hole
  polygon, the `p` the closest point on the edge of the hole it's in.

  """
    def nearest_point([], _, point) do point end

  def nearest_point(world, holes, point) do
    nearest_point_helper(world, holes, point, Polygon.is_inside?(world, point))
  end

  defp nearest_point_helper(_, holes, point, true) do
    nearest_point_in_holes(holes, point)
  end

  defp nearest_point_helper(points, _holes, point, false) do
    nearest_boundary_point_helper(points, point)
  end

  defp nearest_point_in_holes([], point) do
    point
  end

  defp nearest_point_in_holes([hole | holes], point) do
    nearest_point_in_holes_helper(
      [hole | holes],
      point,
      Polygon.is_inside?(hole, point, allow_border: false)
    )
  end

  defp nearest_point_in_holes_helper([_hole | holes], point, false) do
    nearest_point_in_holes(holes, point)
  end

  defp nearest_point_in_holes_helper([hole | _holes], point, true) do
    nearest_boundary_point_helper(hole, point)
  end

  defp nearest_boundary_point_helper(world, point) do
    {x, y} = Polygon.nearest_point_on_edge(world, point)

    # This is a problematic area - we want to round towards the start of the
    # line Eg. in complex.json scene, clicking {62, 310} yields {64.4, 308.8},
    # which naive rounding makes {64, 309}. This however places us *back*
    # *inside* the hole.

    # Some options are; try all four combos or floor/ceil and see which yields
    # the minimal distance - wrong, since the start might be on the far side of
    # a hole.

    # Shorten towards start? Same thing.

    # Actually run A-star to compute all four rounding and pick the shortest
    # path - that's a bit cpu heavy.

    # Compute all four rounding options and pick one that's *not* inside the
    # hole, and don't allow it to be on the border.

    p = {round(x), round(y)}
    a = {ceil(x), ceil(y)}
    b = {ceil(x), floor(y)}
    c = {floor(x), ceil(y)}
    d = {floor(x), floor(y)}

    cond do
      Polygon.is_outside?(world, p, allow_border: false) ->
        p

      Polygon.is_outside?(world, a, allow_border: false) ->
        a

      Polygon.is_outside?(world, b, allow_border: false) ->
        b

      Polygon.is_outside?(world, c, allow_border: false) ->
        c

      Polygon.is_outside?(world, d, allow_border: false) ->
        d
    end

    # If none of the points are outside, we'll pleasantly crash and we should
    # improve this to continuously move outwards a reasonable amount until
    # we're outside.
  end

  @doc """
  Checks if there's a line-of-sight (LOS) from `start` to `stop` within the map.

  ## Params
  * `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
  * `holes`, a list of lists of `{x, y}` vertices. These are holes within
    `polygon`.
  * `line` a tuple of points (`{{ax, ay}, {bx, by}}`) describing a line.

  Returns `true` if there's a line-of-sight and none of the main polygon or
  holes obstruct the path. `false` otherwise.

  As the map consists of a boundary polygon with holes, LOS implies a few things;

  * If either `start` or `stop` is outside `polygon`, the result will be
    false. Even if both are outside, that's not considered a valid LOS.
  * If the distance between `start` and `stop` is tiny (< 0.1 arbitrarily), LOS
    is true.
  * Next, it checks that the line between `start` and `stop` has no
    intersections with `polygon` or `holes`.
  * Finally it checks if the middle of the line between `start` and `stop` is
    inside `polygon` and outside all holes - this ensures that corner-to-corner
    across a hole isn't considered a LOS.
  """
  def is_line_of_sight?(polygon, holes, line) do
    {start, stop} = line

    cond do
      not Polygon.is_inside?(polygon, start) or not Polygon.is_inside?(polygon, stop) ->
        false

      Vector.distance(start, stop) < 0.1 ->
        true

      not Enum.all?([polygon] ++ holes, fn points -> is_line_of_sight_helper(points, line) end) ->
        false

      true ->
        # This part ensures that two vertices across from each other are not
        # considered LOS. Without this, eg. a box-shaped hole would have
        # opposing corners be a LOS, except that the middle of the line falls
        # inside the hole per this check.
        middle = Vector.div(Vector.add(start, stop), 2)

        cond do
          not Polygon.is_inside?(polygon, middle) ->
            false

          Enum.all?(holes, fn hole -> Polygon.is_outside?(hole, middle, allow_border: false) end) ->
            true

          true ->
            false
        end
    end
  end

  defp is_line_of_sight_helper(polygon, {x, y} = line) do
    # We get all intersections and reject the ones that are identical to the
    # line. This allows us to enable "allow_points: true", but only see
    # intersections with other lines and _other_ polygon vertices (points).
    # This is necessary since we're always calling this with a line between two
    # polygon vertices. Without this, having "allow_points: true", every such
    # line would immediately intersect at both ends.

    Polygon.intersections(polygon, line, allow_points: true)
    |> Enum.map(fn {x, y} -> {round(x), round(y)} end)
    |> Enum.reject(fn p -> p == x or p == y end) ==
      []
  end

  # Get all edges from points_a and point_b for which there's line-of-sight.
  defp get_edges(world, holes, points_a, points_b, cost_fun) do
    is_reachable? = fn a, b -> is_line_of_sight?(world, holes, {a, b}) end

    # O(n^2) check all vertice combos for reachability...
    {_, all_edges} =
      Enum.reduce(points_a, {0, %{}}, fn a, {a_idx, acc1} ->
        {_, inner_edges} =
          Enum.reduce(points_b, {0, []}, fn b, {b_idx, acc2} ->
            # NOTE: this is where the edge value is becomes the key in the
            # graph. This is why a_idx and b_idx are available here, in case we
            # want to change it up to be the indexes into points. Unless those
            # two sets are the same, using the indexes makes no sense.
            if a != b and is_reachable?.(a, b) do
              {b_idx + 1, acc2 ++ [{b, cost_fun.(a, b)}]}
            else
              {b_idx + 1, acc2}
            end
          end)

        {a_idx + 1, Map.put(acc1, a, inner_edges)}
      end)

    Map.new(all_edges)
  end
end

1	defmodule Scurry.PolygonMap do
2	@moduledoc """
3	Utility functions to work on a polygon map.
4
5	A polygon map is a set of a primary polygon - the main boundary that
6	outlines the world - and a list of polygons that make holes in the main
7	polygon.
8
9	See `Polygon` for details on how polygons are composed.
10
11	The use case is eg. making a map (the main polygon) with obstacles (the
12	holes), and use the `Astar` module to find the shortest path between
13	points in the map.
14
15	See [Quickstart](quickstart.html) for a concrete end-to-end example of
16	defining a world and holes/obstacles, then using `PolygonMap` and `Astar`
17	modules to do path finding within this.
18	"""
19
20	alias Scurry.Polygon
21	alias Scurry.Vector
22	use Scurry.Types
23	use Scurry.Astar.Types
24
25	@doc """
26	Given a polygon map (`world` & `holes`), returns a list of vertices for a
27	walkmap for A-star search
28
29
30	## Params
31
32	* `world` (`t:polygon/0`), the polygon that defines the outer boundary.
33	* `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
34
35	## Returns
36
37	The walkmap as a `t:list/0` of `t:vector/0` that are the `worlds`'s concave
38	vertices and the convex ones of the `holes`.
39
40	These are used when generating the walk map, since only the `world`'s concave
41	and the `holes`' convex ones limit where you can traverse in a 2D map. Any
42	path has to walk around the holes' convex points and the world's concave.
43
44	See [Quickstart](quickstart.html) for a concrete example.
45	"""
46	@spec get_vertices(polygon(), list(polygon())) :: list(vector())
47	def get_vertices(world, holes) do
48	{concave, _convex} = Polygon.classify_vertices(world)	5✔
49
50	convex =	5✔
51	Enum.reduce(holes, [], fn points, acc ->
52	{_concave, convex} = Polygon.classify_vertices(points)	6✔
53	acc ++ convex	6✔
54	end)
55
56	concave ++ convex	5✔
57	end
58
59	@doc """
60	Given a polygon map (`world` & `holes`) and list of vertices, makes the walk
61	graph for a A-star search.
62
63	## Params
64
65	* `world` (`t:polygon/0`) the polygon that defines the outer boundary.
66	* `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
67	* `vertices` (`t:list/0`), the result of `get_vertices/2`.
68	* `cost_fun` (`t:cost_fun/0`) a "cost" function.
69
70	The `cost_fun` is a function that indicates the of traversing between to
71	points. It defaults to `Scurry.Vector.distance/2`, which is suitable for
72	basic 2D map walking.
73
74	## Returns
75
76	A `t:graph/0`, which is a map of all node to node reachable edges and their
77	cost. This graphs is one of the parameters for a call to `Astar.search/4`.
78
79	> ## Todo
80	>
81	> This should ideally take `line_of_sight/3` as a function so users can
82	> customise which vertices can reach each other. But for now, users can make
83	> the graph themselves just as easily.
84
85	"""
86	@spec create_graph(polygon(), list(polygon()), list(vector()), cost_fun()) :: graph()
87	def create_graph(world, holes, vertices, cost_fun \\ nil)	2✔
88
89	def create_graph(world, holes, vertices, nil) do
90	create_graph(world, holes, vertices, &Vector.distance/2)	2✔
91	end
92
93	def create_graph(world, holes, vertices, cost_fun) do
94	get_edges(world, holes, vertices, vertices, cost_fun)	4✔
95	end
96
97	@doc """
98	Given a polygon map (main & holes), list of vertices and the initial graph
99	from `create_graph/4`, extend the graph with extra `points`.
100
101	This is used to "temporarily" expand the created walk graph with a start and
102	end-point. This is a minor performance optimisation that saves work by
103	reusing the fixed nodes and extend it with the moveable points.
104
105	## Params
106
107	* `graph` (`t:graph/0`) the walk graph, as created by `create_graph/4`. This is used to return a new graph that's extended with `points`.
108	* `world` (`t:polygon/0`) the polygon that defines the outer boundary.
109	* `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
110	* `vertices` (`t:list/0`) the list of vertices returned by `get_vertices/4`
111	and used for `create_graph/4` to get `graph`.
112	* `points` (`t:list/0`) a list of vectors (`t:vector/0`), `[{x, y}, {x, y}...]`, to extend with. Eg. a stop
113	* `cost_fun` (`t:cost_fun/0`) a "cost" function.
114
115	`world` and `holes` need to be passed in in addition to `graph`, so the
116	function can determine line-of-sights between the existing graph and new
117	points from `points`.
118
119	The `cost_fun` is a function that indicates the of traversing between to
120	points. It defaults to `Scurry.Vector.distance/2`, which is suitable for
121	basic 2D map walking.
122
123	## Returns
124
125	A tuple with the extended graph plus the combined list of vertices and new
126	points, `{new_graph, new_vertices}`. The `new_graph` is intended to be used
127	in calls to `Astar.search/4`, and `new_vertices` is solely provided as
128	informational, eg. for displaying the graphs visually.
129	"""
130	def extend_graph(graph, world, holes, vertices, points, cost_fun \\ nil)	1✔
131
132	def extend_graph(graph, world, holes, vertices, points, nil) do
133	extend_graph(graph, world, holes, vertices, points, &Vector.distance/2)	1✔
134	end
135
136	def extend_graph(graph, world, holes, vertices, points, cost_fun) do
137	# To extend the graph `graph` made up up `vertices` with new points
138	# `points`, we need to find three sets of edges (sub-graphs). The ones from
139	# the new points to the existing vertices, vice-versa, and between the new
140	# points.
141	set_a = get_edges(world, holes, points, vertices, cost_fun)	2✔
142	set_b = get_edges(world, holes, vertices, points, cost_fun)	2✔
143	set_c = get_edges(world, holes, points, points, cost_fun)	2✔
144
145	# Merge the three new sub-graphs into graph. This uses Map.merge with a
146	# merge func that combines values for identical keys to extend them instead
147	# of replacing, and dedupes.
148	merge_fun = fn _k, v1, v2 ->	2✔
149	Enum.dedup(v1 ++ v2)	14✔
150	end
151
152	graph =	2✔
153	graph
154	\|> Map.merge(set_a, merge_fun)
155	\|> Map.merge(set_b, merge_fun)
156	\|> Map.merge(set_c, merge_fun)
157
158	{graph, vertices ++ points}
159	end
160
161	@doc """
162
163	Find the nearest point on the line that is inside the world polygion and
164	outside all hole polygons.
165
166	The purpose of this function is to determine compute a suitable end for the
167	`points` parameter for `extend_graph/6`. Imagine a UI in which the users
168	clicks on a point to walk to. If that click is outside the world map or
169	inside a hole/obstacle, we can either refuse to compute a path, or we can use
170	`nearest_point/3` to find the closest reachable point to the click.
171
172	## Params
173
174	* `world` (`t:polygon/0`) the polygon that defines the outer boundary.
175	* `holes` (`t:list/0`), a list of `t:polygon/0` that define holes/obstacles inside `world`.
176	* `point` (`t:vector/0`) the point for which to find the nearst point.
177
178	## Returns
179
180	A new point (`t:vector/0`) `p={x, y}` such that;
181
182	* if `point` is _outside_ the world polygon, the new `p` is the closest point on
183	the edge of the `world` polygon.
184
185	* if `point` is _inside_ the world polygon, but also inside any hole
186	polygon, the `p` the closest point on the edge of the hole it's in.
187
188	"""
189	def nearest_point([], _, point) do point end	1✔
190
191	def nearest_point(world, holes, point) do
192	nearest_point_helper(world, holes, point, Polygon.is_inside?(world, point))	6✔
193	end
194
195	defp nearest_point_helper(_, holes, point, true) do
196	nearest_point_in_holes(holes, point)	5✔
197	end
198
199	defp nearest_point_helper(points, _holes, point, false) do
200	nearest_boundary_point_helper(points, point)	1✔
201	end
202
203	defp nearest_point_in_holes([], point) do
204	point	1✔
205	end
206
207	defp nearest_point_in_holes([hole \| holes], point) do
208	nearest_point_in_holes_helper(	6✔
209	[hole \| holes],
210	point,
211	Polygon.is_inside?(hole, point, allow_border: false)
212	)
213	end
214
215	defp nearest_point_in_holes_helper([_hole \| holes], point, false) do
216	nearest_point_in_holes(holes, point)	2✔
217	end
218
219	defp nearest_point_in_holes_helper([hole \| _holes], point, true) do
220	nearest_boundary_point_helper(hole, point)	4✔
221	end
222
223	defp nearest_boundary_point_helper(world, point) do
224	{x, y} = Polygon.nearest_point_on_edge(world, point)	5✔
225
226	# This is a problematic area - we want to round towards the start of the
227	# line Eg. in complex.json scene, clicking {62, 310} yields {64.4, 308.8},
228	# which naive rounding makes {64, 309}. This however places us back
229	# inside the hole.
230
231	# Some options are; try all four combos or floor/ceil and see which yields
232	# the minimal distance - wrong, since the start might be on the far side of
233	# a hole.
234
235	# Shorten towards start? Same thing.
236
237	# Actually run A-star to compute all four rounding and pick the shortest
238	# path - that's a bit cpu heavy.
239
240	# Compute all four rounding options and pick one that's not inside the
241	# hole, and don't allow it to be on the border.
242
243	p = {round(x), round(y)}	5✔
244	a = {ceil(x), ceil(y)}	5✔
245	b = {ceil(x), floor(y)}	5✔
246	c = {floor(x), ceil(y)}	5✔
247	d = {floor(x), floor(y)}	5✔
248
249	cond do	5✔
250	Polygon.is_outside?(world, p, allow_border: false) ->
251	p	3✔
252
253	Polygon.is_outside?(world, a, allow_border: false) ->	2✔
254	a	1✔
255
256	Polygon.is_outside?(world, b, allow_border: false) ->	1✔
257	b	1✔
258
NEW 259	Polygon.is_outside?(world, c, allow_border: false) ->	×
260	c	×
261
NEW 262	Polygon.is_outside?(world, d, allow_border: false) ->	×
UNCOV 263	d	×
264	end
265
266	# If none of the points are outside, we'll pleasantly crash and we should
267	# improve this to continuously move outwards a reasonable amount until
268	# we're outside.
269	end
270
271	@doc """
272	Checks if there's a line-of-sight (LOS) from `start` to `stop` within the map.
273
274	## Params
275	* `polygon`, a list of `{x, y}` vertices. This is the main boundary map.
276	* `holes`, a list of lists of `{x, y}` vertices. These are holes within
277	`polygon`.
278	* `line` a tuple of points (`{{ax, ay}, {bx, by}}`) describing a line.
279
280	Returns `true` if there's a line-of-sight and none of the main polygon or
281	holes obstruct the path. `false` otherwise.
282
283	As the map consists of a boundary polygon with holes, LOS implies a few things;
284
285	* If either `start` or `stop` is outside `polygon`, the result will be
286	false. Even if both are outside, that's not considered a valid LOS.
287	* If the distance between `start` and `stop` is tiny (< 0.1 arbitrarily), LOS
288	is true.
289	* Next, it checks that the line between `start` and `stop` has no
290	intersections with `polygon` or `holes`.
291	* Finally it checks if the middle of the line between `start` and `stop` is
292	inside `polygon` and outside all holes - this ensures that corner-to-corner
293	across a hole isn't considered a LOS.
294	"""
295	def is_line_of_sight?(polygon, holes, line) do
296	{start, stop} = line	136✔
297
298	cond do	136✔
299	not Polygon.is_inside?(polygon, start) or not Polygon.is_inside?(polygon, stop) ->	136✔
300	false
301
302	Vector.distance(start, stop) < 0.1 ->	133✔
303	true
304
305	not Enum.all?([polygon] ++ holes, fn points -> is_line_of_sight_helper(points, line) end) ->	133✔
306	false
307
308	true ->	98✔
309	# This part ensures that two vertices across from each other are not
310	# considered LOS. Without this, eg. a box-shaped hole would have
311	# opposing corners be a LOS, except that the middle of the line falls
312	# inside the hole per this check.
313	middle = Vector.div(Vector.add(start, stop), 2)	98✔
314
315	cond do	98✔
316	not Polygon.is_inside?(polygon, middle) ->	1✔
317	false
318
319	Enum.all?(holes, fn hole -> Polygon.is_outside?(hole, middle, allow_border: false) end) ->	97✔
320	true
321
322	true ->	17✔
323	false
324	end
325	end
326	end
327
328	defp is_line_of_sight_helper(polygon, {x, y} = line) do
329	# We get all intersections and reject the ones that are identical to the
330	# line. This allows us to enable "allow_points: true", but only see
331	# intersections with other lines and _other_ polygon vertices (points).
332	# This is necessary since we're always calling this with a line between two
333	# polygon vertices. Without this, having "allow_points: true", every such
334	# line would immediately intersect at both ends.
335
336	Polygon.intersections(polygon, line, allow_points: true)
337	\|> Enum.map(fn {x, y} -> {round(x), round(y)} end)	292✔
338	\|> Enum.reject(fn p -> p == x or p == y end) ==	256✔
339	[]
340	end
341
342	# Get all edges from points_a and point_b for which there's line-of-sight.
343	defp get_edges(world, holes, points_a, points_b, cost_fun) do
344	is_reachable? = fn a, b -> is_line_of_sight?(world, holes, {a, b}) end	10✔
345
346	# O(n^2) check all vertice combos for reachability...
347	{_, all_edges} =	10✔
348	Enum.reduce(points_a, {0, %{}}, fn a, {a_idx, acc1} ->
349	{_, inner_edges} =	38✔
350	Enum.reduce(points_b, {0, []}, fn b, {b_idx, acc2} ->
351	# NOTE: this is where the edge value is becomes the key in the
352	# graph. This is why a_idx and b_idx are available here, in case we
353	# want to change it up to be the indexes into points. Unless those
354	# two sets are the same, using the indexes makes no sense.
355	if a != b and is_reachable?.(a, b) do	148✔
356	{b_idx + 1, acc2 ++ [{b, cost_fun.(a, b)}]}
357	else
358	{b_idx + 1, acc2}
359	end
360	end)
361
362	{a_idx + 1, Map.put(acc1, a, inner_edges)}
363	end)
364
365	Map.new(all_edges)	10✔
366	end
367	end

eskil / scurry / 7180ab87890bb64e762715c125d912788cf1ffae

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous