Ray-casting algorithm: Difference between revisions

Updated D code
(→‎{{header|Go}}: added closed polygon version)
(Updated D code)
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.
=={{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 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 with (edge) {
with (edge) { // puts if (a.y and> b.y) inswap(a, the namespaceb);
if (p.y == a.y >|| p.y == b.y)
swap(a, b) p.y += 0.00001; // epsilon
if ((p.y ==> ab.y || p.y ==< ba.y) || (p.x > max(a.x, b.x)))
p = Point(p.x, p.y +return EPS)false;
if (p.x < min(a.x, b.x))
 
if ((p.y > b.y || p.y < a.y) ||return (p.x > max(a.x, b.x)))true;
returnconst false;blue = (abs(a.x - p.x) > double.min) ?
((p.y - a.y) / (p.x - a.x)) :
 
if (p.x < min(a.x, b double.x))max;
returnconst true;red = (abs(a.x - b.x) > double.min) ?
((b.y - a.y) / (b.x - a.x)) :
else {
double m_blue, m_red double.max;
ifreturn (abs(a.x - b.x)blue >= double.min)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() {
enum Figure[] polys = [
Figure({"Square", [
{{ 0.0, 0.0}, Edge(Point({10.0, 0.0)}}, Point( {{10.0, 0.0}, {10.0, 10.0))}},
{{10.0, 10.0}, { 0.0, Edge(Point(10.0}}, {{ 0.0), Point(10.0}, 10)){ 0.0, 0.0}}]},
{"Square hole", [
Edge(Point(10, 10), Point(0, 10)),
{{ 0.0, 0.0}, Edge(Point({10.0, 0.0}}, {{10).0, Point( 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", [
{{ 7.5, 7.5}, Edge(Point(0{ 2.5, 0) 7.5}}, Point(10 {{ 2.5, 0)) 7.5}, { 2.5, 2.5}}]},
{"Strange", [
Edge(Point(10, 0), Point(10, 10)),
{{ 0.0, 0.0}, Edge(Point(10{ 2.5, 10) 2.5}}, Point( {{ 2.5, 2.5}, { 0.0, 10)).0}},
{{ 0.0, 10.0}, { Edge(Point(02.5, 10) 7.5}}, Point(0 {{ 2.5, 0)) 7.5}, { 7.5, 7.5}},
{{ 7.5, Edge(Point(27.5}, 2{10.5)0, Point(710.50}}, 2 {{10.5))0, 10.0}, {10.0, 0.0}},
{{10.0, 0}, Edge(Point(7.5, { 2.5), Point(7.5, 72.5))}}]},
{"Exagon", [
Edge(Point(7.5, 7.5), Point(2.5, 7.5)),
{{ 3.0, 0.0}, Edge(Point(2{ 7.50, 0.0}}, {{ 7.5)0, Point(2 0.50}, 2{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)),
enum Point[] testPoints = [{ Edge(Point(2.5, 2.5)}, Point(0{5, 8}, {-10)), 5}, {0, 5},
Edge(Point(0, {10), Point(2.5}, {8, 7.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) {
polyPrettyPrintwritefln(`Is point inside figure "%s"?`, poly.name);
writeln(" Point inside poly?");
foreach (p; testPoints)
writelnwritefln(" (%3s, %2s): %s", to!string(p).x, ": "p.y, isPointInsidecontains(poly,p, poly));
writeln();
}
}</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)5): false
( Edge(Point(10, 0 5),: Point(10, 10))true
( Edge(Point(108, 10 5),: Point(0, 10))true
( Edge(Point(010, 10),: Point(0, 0))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)): false
( Edge(Point(2.5, 2.5 8),: Point(0, 10))true
Edge(Point(0, -10), Point(2.5, 7.5)): false
( Edge(Point(2.50, 7. 5),: Point(7.5, 7.5))false
( 10, 5): true
Edge(Point(7.5, 7.5), Point(10, 10))
( Edge(Point(108, 10 5),: Point(10, 0))true
( Edge(Point(10, 010),: Point(2.5, 2.5))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(75, 0) 5): true
( Edge(Point(75, 0 8),: Point(10, 5))false
Edge(Point(-10, 5),: Point(7, 10))false
( Edge(Point(70, 10 5),: Point(3, 10))false
Edge(Point(3, 10), Point(0, 5)): true
( Edge(Point(08, 5),: Point(3, 0))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}}==
Anonymous user