Anonymous user
Talk:Ray-casting algorithm: Difference between revisions
→Elixir: new section
No edit summary |
(→Elixir: new section) |
||
| (2 intermediate revisions by one other user not shown) | |||
Line 13:
The C example claims to "reveal the meaning of coherent results", whereby it considers a point lying on the left edge of a square outside, but a point on right side inside. This must be a meaning of "coherent" that I wasn't aware of. Also, the intersection code is terrible: it uses an arbitrarily defined value as a floating point precision limit while not rigorously enforcing it, which will cause all kinds of unexpected behaviors when used in real work. --[[User:Ledrug|Ledrug]] 22:10, 25 July 2011 (UTC)
: You clearly failed to understand the actual meaning and also to cite correctly the text (<cite>this is italics on purpose</cite>). The text under C code '''correctly''' claimed to "reveal the meaning of <cite>coherent results</cite>". It referred to the text of the problem, where it was and it is stated: <cite>Points on the boundary or "on" a vertex are someway special and through this approach we do not obtain ''coherent results''.</cite> What does it mean that we don't obtain <cite>coherent results</cite>? The C code showed it, as expected and anticipated by <cite>through this approach</cite>, which was clearly the approach used in the implementation. So, it wasn't a dictionary problem on my part, but an understanding problem on your part.
: There was a second incredible misunderstanding: in the "original" C code, there wasn't anything to deal with <cite>a floating point precision limit</cite>, hence it was impossible such a limit was enforced rigorously (or not) anywhere. Clearly you failed to understand what the code did — and this is fine, maybe it was sloppy and messy to you. Nonetheless, the text of the problem says <cite>To avoid the "ray on vertex" problem, the point is moved upward of a small quantity ε</cite>. Maybe you missed this part, or you believed that every ε/eps/epsilon must be used to enforce <cite>a floating point precision limit</cite>.
: Instead in these cases (check other examples) ε/eps/epsilon is just the value we shift a point in order to '''simplistically''' cope with a specific problem. Not the best we can do, and it has "side effects": already considered in the text, thus no surprise (except for you, it seems).
: If we need to be pedantic and focus on all the details for a production ready implementation (which isn't the main aim of this wiki, as far as I understand it), floating point should be treated carefully in every comparisons, but many did the naive approach — I think because it isn't the point of the task (or maybe because we hope the target CPU has an instruction like FCMPE in MMIX — just joking). --- [[User:ShinTakezou|ShinTakezou]] ([[User talk:ShinTakezou|talk]]) 18:59, 23 February 2018 (UTC)
== D code generate false positive ==
Line 169 ⟶ 176:
</lang>
== Elixir ==
point_in_polygon.ex:
<lang Elixir>defmodule PointInPolygon do
require Integer
@doc """
Check if point is inside a polygon
## Example
iex> polygon = [[1, 2], [3, 4], [5, 2], [3, 0]]
iex> point = [3, 2]
iex> point_in_polygon?(polygon, point)
true
## Example
iex> polygon = [[1, 2], [3, 4], [5, 2], [3, 0]]
iex> point = [1.5, 3]
iex> point_in_polygon?(polygon, point)
false
"""
def point_in_polygon?(polygon, point) do
polygon
|> to_segments()
|> Enum.reduce(0, fn segment, count ->
apply(__MODULE__, :ray_intersects_segment, add_epsilon(segment, point)) + count
end)
|> Integer.is_odd()
end
def to_segments([p1 | _] = polygon) do
polygon |> Enum.chunk_every(2, 1, [p1]) |> Enum.map(fn segment -> orient_segment(segment) end)
end
def orient_segment([a = [_ax, ay], b = [_bx, by]]) when by >= ay do
[a, b]
end
def orient_segment([b, a]) do
[a, b]
end
def add_epsilon(segment = [[_ax, ay], [_bx, by]], [px, py]) when py == ay or py == by do
[segment, [px, py + 0.00000001]]
end
def add_epsilon(segment, point), do: [segment, point]
def ray_intersects_segment([[_ax, ay], [_bx, by]], [_px, py]) when py < ay or py > by do
0
end
# px >= max(ax, bx)
def ray_intersects_segment([[ax, _ay], [bx, _by]], [px, _py])
when (ax >= bx and px >= ax) or (bx >= ax and px >= bx) do
0
end
# px < min(ax, bx)
def ray_intersects_segment([[ax, _ay], [bx, _by]], [px, _py])
when (ax <= bx and px < ax) or (bx <= ax and px < bx) do
1
end
def ray_intersects_segment([[ax, ay], [bx, by]], [px, py]) do
m_red = m_red(ax, ay, bx, by)
m_blue = m_blue(ax, ay, px, py)
case {m_blue, m_red} do
{:infinity, _} ->
1
{_, :infinity} ->
0
{m_blue, m_red} when m_blue >= m_red ->
1
_ ->
0
end
end
def m_red(ax, ay, bx, by) when ax != bx do
(by - ay) / (bx - ax)
end
def m_red(_, _, _, _) do
:infinity
end
def m_blue(ax, ay, px, py) when ax != px do
(py - ay) / (px - ax)
end
def m_blue(_, _, _, _) do
:infinity
end
end</lang>
| |||