Ray-casting algorithm: Difference between revisions

Content added Content deleted
Line 88: Line 88:


=={{header|C}}==
=={{header|C}}==

Required includes and definitions:
Required includes and definitions:

<lang c>#include <stdio.h>
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
Line 211: Line 209:


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}}==
Modified from the Python version.
<lang d>import std.stdio, std.math, std.algorithm, std.conv, std.string;

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

enum double EPS = 0.00001;

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

if ((p.y > b.y || p.y < a.y) || (p.x > max(a.x, b.x)))
return false;

if (p.x < min(a.x, b.x))
return true;
else {
double m_blue, m_red;
if (abs(a.x - b.x) > double.min)
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;
}
}
}

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 polys = [
Figure("Square", [
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))
]),
Figure("Square hole", [
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))
]),
Figure("Strange", [
Edge(Point(0, 0), Point(2.5, 2.5)),
Edge(Point(2.5, 2.5), Point(0, 10)),
Edge(Point(0, 10), Point(2.5, 7.5)),
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) {
polyPrettyPrint(poly);
writeln(" Point inside poly?");
foreach (p; testPoints)
writeln(" ", to!string(p), ": ", isPointInside(p, poly));
writeln();
}
}</lang>
Output:
<pre>Testing whether points are within figures:

Figure(name="Square", 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))
))
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

Figure(name="Strange", edges=(
Edge(Point(0, 0), Point(2.5, 2.5))
Edge(Point(2.5, 2.5), Point(0, 10))
Edge(Point(0, 10), Point(2.5, 7.5))
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))
))
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

Figure(name="Exagon", edges=(
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))
))
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

</pre>


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