Ray-casting algorithm: Difference between revisions

Content added Content deleted
(→‎{{header|Go}}: added closed polygon version)
(Updated D code)
Line 450: Line 450:
The test's output reveals the meaning of <cite>coherent results</cite>: a point on the leftmost vertical side of the square (coordinate 0,5) is considered outside; while a point on the rightmost vertical side of the square (coordinate 10,5) is considered inside, but on the top-right vertex (coordinate 10,10), it is considered outside again.
The test's output reveals the meaning of <cite>coherent results</cite>: a point on the leftmost vertical side of the square (coordinate 0,5) is considered outside; while a point on the rightmost vertical side of the square (coordinate 10,5) is considered inside, but on the top-right vertex (coordinate 10,10), it is considered outside again.
=={{header|D}}==
=={{header|D}}==
<lang d>import std.stdio, std.math, std.algorithm, std.conv;
Modified from the Python version.
<lang d>import std.stdio, std.math, std.algorithm, std.conv, std.string;


struct Figure { string name; Edge[] edges; }
struct Edge { Point a, b; } // Figure edge from a to b
struct Point { double x, y; }
struct Point { double x, y; }
struct Edge { Point a, b; } // Figure edge from a to b
struct Figure { string name; Edge[] edges; }


bool contains(/*in*/ Figure poly, in Point p) pure nothrow {
enum double EPS = 0.00001;
static bool raySegI(Point p, Edge edge) pure nothrow {

bool rayIntersectSeg(Point p, Edge edge) {
with (edge) {
with (edge) { // puts a and b in the namespace
if (a.y > b.y) swap(a, b);
if (a.y > b.y)
if (p.y == a.y || p.y == b.y)
swap(a, b);
p.y += 0.00001; // epsilon
if (p.y == a.y || p.y == b.y)
if ((p.y > b.y || p.y < a.y) || (p.x > max(a.x, b.x)))
p = Point(p.x, p.y + EPS);
return false;
if (p.x < min(a.x, b.x))

if ((p.y > b.y || p.y < a.y) || (p.x > max(a.x, b.x)))
return true;
return false;
const blue = (abs(a.x - p.x) > double.min) ?
((p.y - a.y) / (p.x - a.x)) :

if (p.x < min(a.x, b.x))
double.max;
return true;
const red = (abs(a.x - b.x) > double.min) ?
((b.y - a.y) / (b.x - a.x)) :
else {
double m_blue, m_red;
double.max;
if (abs(a.x - b.x) > double.min)
return blue >= red;
m_red = (b.y - a.y) / (b.x - a.x);
else
m_red = double.max;

if (abs(a.x - p.x) > double.min)
m_blue = (p.y - a.y) / (p.x - a.x);
else
m_blue = double.max;

return m_blue >= m_red;
}
}
}
}
}


return count!((e){ return raySegI(p,e); })(poly.edges) % 2 == 1;
bool isPointInside(const Point p, const Figure poly) {
int tot;
foreach (edge; poly.edges)
tot += rayIntersectSeg(p, edge);
return tot % 2 == 1;
}

void polyPrettyPrint(Figure poly) {
writefln("Figure(name=\"%s\", edges=(", poly.name);
writeln(" ", to!string(poly.edges, "", "\n ", ""), "\n ))");
}
}


void main() {
void main() {
enum polys = [
enum Figure[] polys = [
Figure("Square", [
{"Square", [
Edge(Point(0, 0), Point(10, 0)),
{{ 0.0, 0.0}, {10.0, 0.0}}, {{10.0, 0.0}, {10.0, 10.0}},
Edge(Point(10, 0), Point(10, 10)),
{{10.0, 10.0}, { 0.0, 10.0}}, {{ 0.0, 10.0}, { 0.0, 0.0}}]},
{"Square hole", [
Edge(Point(10, 10), Point(0, 10)),
Edge(Point(0, 10), Point(0, 0))
{{ 0.0, 0.0}, {10.0, 0.0}}, {{10.0, 0.0}, {10.0, 10.0}},
{{10.0, 10.0}, { 0.0, 10.0}}, {{ 0.0, 10.0}, { 0.0, 0.0}},
]),
{{ 2.5, 2.5}, { 7.5, 2.5}}, {{ 7.5, 2.5}, { 7.5, 7.5}},
Figure("Square hole", [
Edge(Point(0, 0), Point(10, 0)),
{{ 7.5, 7.5}, { 2.5, 7.5}}, {{ 2.5, 7.5}, { 2.5, 2.5}}]},
{"Strange", [
Edge(Point(10, 0), Point(10, 10)),
Edge(Point(10, 10), Point(0, 10)),
{{ 0.0, 0.0}, { 2.5, 2.5}}, {{ 2.5, 2.5}, { 0.0, 10.0}},
Edge(Point(0, 10), Point(0, 0)),
{{ 0.0, 10.0}, { 2.5, 7.5}}, {{ 2.5, 7.5}, { 7.5, 7.5}},
Edge(Point(2.5, 2.5), Point(7.5, 2.5)),
{{ 7.5, 7.5}, {10.0, 10.0}}, {{10.0, 10.0}, {10.0, 0.0}},
Edge(Point(7.5, 2.5), Point(7.5, 7.5)),
{{10.0, 0}, { 2.5, 2.5}}]},
{"Exagon", [
Edge(Point(7.5, 7.5), Point(2.5, 7.5)),
Edge(Point(2.5, 7.5), Point(2.5, 2.5))
{{ 3.0, 0.0}, { 7.0, 0.0}}, {{ 7.0, 0.0}, {10.0, 5.0}},
{{10.0, 5.0}, { 7.0, 10.0}}, {{ 7.0, 10.0}, { 3.0, 10.0}},
]),
{{ 3.0, 10.0}, { 0.0, 5.0}}, {{ 0.0, 5.0}, { 3.0, 0.0}}]}
Figure("Strange", [
];
Edge(Point(0, 0), Point(2.5, 2.5)),
Edge(Point(2.5, 2.5), Point(0, 10)),
enum Point[] testPoints = [{ 5, 5}, {5, 8}, {-10, 5}, {0, 5},
Edge(Point(0, 10), Point(2.5, 7.5)),
{10, 5}, {8, 5}, { 10, 10}];
Edge(Point(2.5, 7.5), Point(7.5, 7.5)),
Edge(Point(7.5, 7.5), Point(10, 10)),
Edge(Point(10, 10), Point(10, 0)),
Edge(Point(10, 0), Point(2.5, 2.5))
]),
Figure("Exagon", [
Edge(Point(3, 0), Point(7, 0)),
Edge(Point(7, 0), Point(10, 5)),
Edge(Point(10, 5), Point(7, 10)),
Edge(Point(7, 10), Point(3, 10)),
Edge(Point(3, 10), Point(0, 5)),
Edge(Point(0, 5), Point(3, 0))
])
];


enum testPoints = [Point(5, 5), Point(5, 8), Point(-10, 5),
Point(0, 5), Point(10, 5), Point(8, 5),
Point(10, 10)];

writeln("Testing whether points are within figures:\n");
foreach (poly; polys) {
foreach (poly; polys) {
polyPrettyPrint(poly);
writefln(`Is point inside figure "%s"?`, poly.name);
writeln(" Point inside poly?");
foreach (p; testPoints)
foreach (p; testPoints)
writeln(" ", to!string(p), ": ", isPointInside(p, poly));
writefln(" (%3s, %2s): %s", p.x, p.y, contains(poly,p));
writeln();
writeln();
}
}
}</lang>
}</lang>
Output:<pre>Is point inside figure "Square"?
Output:
( 5, 5): true
<pre>Testing whether points are within figures:
( 5, 8): true

(-10, 5): false
Figure(name="Square", edges=(
Edge(Point(0, 0), Point(10, 0))
( 0, 5): false
Edge(Point(10, 0), Point(10, 10))
( 10, 5): true
Edge(Point(10, 10), Point(0, 10))
( 8, 5): true
Edge(Point(0, 10), Point(0, 0))
( 10, 10): false
))
Point inside poly?
Point(5, 5): true
Point(5, 8): true
Point(-10, 5): false
Point(0, 5): false
Point(10, 5): true
Point(8, 5): true
Point(10, 10): false

Figure(name="Square hole", edges=(
Edge(Point(0, 0), Point(10, 0))
Edge(Point(10, 0), Point(10, 10))
Edge(Point(10, 10), Point(0, 10))
Edge(Point(0, 10), Point(0, 0))
Edge(Point(2.5, 2.5), Point(7.5, 2.5))
Edge(Point(7.5, 2.5), Point(7.5, 7.5))
Edge(Point(7.5, 7.5), Point(2.5, 7.5))
Edge(Point(2.5, 7.5), Point(2.5, 2.5))
))
Point inside poly?
Point(5, 5): false
Point(5, 8): true
Point(-10, 5): false
Point(0, 5): false
Point(10, 5): true
Point(8, 5): true
Point(10, 10): false


Is point inside figure "Square hole"?
Figure(name="Strange", edges=(
Edge(Point(0, 0), Point(2.5, 2.5))
( 5, 5): false
Edge(Point(2.5, 2.5), Point(0, 10))
( 5, 8): true
Edge(Point(0, 10), Point(2.5, 7.5))
(-10, 5): false
Edge(Point(2.5, 7.5), Point(7.5, 7.5))
( 0, 5): false
( 10, 5): true
Edge(Point(7.5, 7.5), Point(10, 10))
Edge(Point(10, 10), Point(10, 0))
( 8, 5): true
Edge(Point(10, 0), Point(2.5, 2.5))
( 10, 10): false
))
Point inside poly?
Point(5, 5): true
Point(5, 8): false
Point(-10, 5): false
Point(0, 5): false
Point(10, 5): true
Point(8, 5): true
Point(10, 10): false


Is point inside figure "Strange"?
Figure(name="Exagon", edges=(
Edge(Point(3, 0), Point(7, 0))
( 5, 5): true
Edge(Point(7, 0), Point(10, 5))
( 5, 8): false
Edge(Point(10, 5), Point(7, 10))
(-10, 5): false
Edge(Point(7, 10), Point(3, 10))
( 0, 5): false
Edge(Point(3, 10), Point(0, 5))
( 10, 5): true
Edge(Point(0, 5), Point(3, 0))
( 8, 5): true
))
( 10, 10): false
Point inside poly?
Point(5, 5): true
Point(5, 8): true
Point(-10, 5): false
Point(0, 5): false
Point(10, 5): true
Point(8, 5): true
Point(10, 10): false


Is point inside figure "Exagon"?
</pre>
( 5, 5): true
( 5, 8): true
(-10, 5): false
( 0, 5): false
( 10, 5): true
( 8, 5): true
( 10, 10): false</pre>


=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
Retrieved from "https://rosettacode.org/wiki/Ray-casting_algorithm"