Rosetta Code

Ray-casting algorithm: Difference between revisions

Page Discussion

Ray-casting algorithm (view source)

Revision as of 12:06, 28 August 2022

1,749 bytes added ,  1 year ago
m
syntax highlighting fixup automation
(→‎{{header|Wren}}: Now uses new core library method.)
m (syntax highlighting fixup automation)
Line 79:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">T Pt
Float x, y
 
Line 162:
print(‘ ’testpoints[0.<3].map(p -> ‘#.: #.’.format(p, I ispointinside(p, @poly) {‘True’} E ‘False’)).join("\t"))
print(‘ ’testpoints[3.<6].map(p -> ‘#.: #.’.format(p, I ispointinside(p, @poly) {‘True’} E ‘False’)).join("\t"))
print(‘ ’testpoints[6.. ].map(p -> ‘#.: #.’.format(p, I ispointinside(p, @poly) {‘True’} E ‘False’)).join("\t"))</langsyntaxhighlight>
 
{{out}}
Line 221:
=={{header|Ada}}==
polygons.ads:
<langsyntaxhighlight Adalang="ada">package Polygons is
 
type Point is record
Line 234:
function Is_Inside (Who : Point; Where : Polygon) return Boolean;
 
end Polygons;</langsyntaxhighlight>
 
polygons.adb:
<langsyntaxhighlight Adalang="ada">package body Polygons is
EPSILON : constant := 0.00001;
 
Line 323:
end Is_Inside;
 
end Polygons;</langsyntaxhighlight>
 
Example use:
 
main.adb:
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
with Polygons;
procedure Main is
Line 418:
Ada.Text_IO.New_Line;
end loop;
end Main;</langsyntaxhighlight>
 
Output:
Line 459:
=={{header|ANSI Standard BASIC}}==
{{trans|FreeBASIC}}
<langsyntaxhighlight ANSIlang="ansi Standardstandard BASICbasic">1000 PUBLIC NUMERIC x,y
1010 LET x=1
1020 LET y=2
Line 642:
2810 NEXT z
2820 END
</syntaxhighlight>
</lang>
 
=={{header|AutoHotkey}}==
{{works with|AutoHotkey L}}
<langsyntaxhighlight lang="ahk">Points :=[{x: 5.0, y: 5.0}
, {x: 5.0, y: 8.0}
, {x:-10.0, y: 5.0}
Line 739:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>---------------------------
Line 778:
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <math.h>
Line 918:
 
return 0;
}</langsyntaxhighlight>
 
=={{header|C++}}==
{{works with|C++|11}}
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <cstdlib>
#include <iomanip>
Line 1,003:
 
return EXIT_SUCCESS;
}</langsyntaxhighlight>
{{output}}
As D.
Line 1,009:
=={{header|CoffeeScript}}==
Takes a polygon as a list of points joining segments, and creates segments between them.
<langsyntaxhighlight lang="coffeescript"> Point = (@x,@y) ->
 
pointInPoly = (point,poly) ->
Line 1,036:
mAB = (b.y - a.y) / (b.x - a.x)
mAP = (p.y - a.y) / (p.x - a.x)
mAP > mAB</langsyntaxhighlight>
 
=={{header|Common Lisp}}==
Points are represented as cons cells whose car is an x value and whose cdr is a y value. A line segment is a cons cell of two points. A polygon is a list of line segments.
<langsyntaxhighlight lang="lisp">(defun point-in-polygon (point polygon)
(do ((in-p nil)) ((endp polygon) in-p)
(when (ray-intersects-segment point (pop polygon))
Line 1,069:
((null m-blue) t)
((null m-red) nil)
(t (>= m-blue m-red)))))))))</langsyntaxhighlight>
 
Testing code
<langsyntaxhighlight lang="lisp">(defparameter *points*
#((0 . 0) (10 . 0) (10 . 10) (0 . 10)
(2.5 . 2.5) (7.5 . 2.5) (7.5 . 7.5) (2.5 . 7.5)
Line 1,106:
do (format t "~&~w ~:[outside~;inside ~]."
test-point
(point-in-polygon test-point polygon)))))</langsyntaxhighlight>
 
=={{header|D}}==
<langsyntaxhighlight lang="d">import std.stdio, std.math, std.algorithm;
 
immutable struct Point { double x, y; }
Line 1,176:
writeln;
}
}</langsyntaxhighlight>
{{out}}
<pre>Is point inside figure "Square"?
Line 1,216:
=={{header|Factor}}==
To test whether a ray intersects a line, we test that the starting point is between the endpoints in y value, and that it is to the left of the point on the segment with the same y value. Note that this implementation does not support polygons with horizontal edges.
<langsyntaxhighlight lang="factor">USING: kernel prettyprint sequences arrays math math.vectors ;
IN: raycasting
 
Line 1,234:
[ dup first suffix [ rest-slice ] [ but-last-slice ] bi ] dip
[ ray ] curry 2map
f [ xor ] reduce ;</langsyntaxhighlight>
Usage:
<langsyntaxhighlight lang="factor">( scratchpad ) CONSTANT: square { { -2 -1 } { 1 -2 } { 2 1 } { -1 2 } }
( scratchpad ) square { 0 0 } raycast .
t
Line 1,242:
f
( scratchpad ) square { 2 0 } raycast .
f</langsyntaxhighlight>
 
=={{header|Fortran}}==
Line 1,249:
 
This module ''defines'' "polygons".
<langsyntaxhighlight lang="fortran">module Polygons
use Points_Module
implicit none
Line 1,283:
end subroutine free_polygon
 
end module Polygons</langsyntaxhighlight>
 
The ray casting algorithm module:
<langsyntaxhighlight lang="fortran">module Ray_Casting_Algo
use Polygons
implicit none
Line 1,362:
end function point_is_inside
 
end module Ray_Casting_Algo</langsyntaxhighlight>
 
'''Testing'''
<langsyntaxhighlight lang="fortran">program Pointpoly
use Points_Module
use Ray_Casting_Algo
Line 1,404:
end do
 
end program Pointpoly</langsyntaxhighlight>
 
=={{header|FreeBASIC}}==
Inpolygon by Winding number method
<langsyntaxhighlight FreeBASIClang="freebasic">Type Point
As Single x,y
End Type
Line 1,521:
End Select
Next z
Sleep</langsyntaxhighlight>
Output:
<pre>squared
Line 1,563:
 
The first solution given here follows the model of most other solutions on the page in defining a polygon as a list of segments. Unfortunately this representation does not require that the polygon is ''closed''. Input to the ray-casting algorithm, as noted in the WP article though, is specified to be a closed polygon. The "strange" shape defined here is not a closed polygon and so gives incorrect results against some points. (Graphically it may appear closed but mathematically it needs an additional segment returning to the starting point.)
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,664:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,711:
 
Here input is given as a list of N vertices defining N segments, where one segment extends from each vertex to the next, and one more extends from the last vertex to the first. In the case of the "strange" shape, this mathematically closes the polygon and allows the program to give correct results.
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,786:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,807:
 
This solution is preferred over the two above.
<syntaxhighlight lang="text">package main
 
import "fmt"
Line 1,856:
}
}
}</langsyntaxhighlight>
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.Ratio
 
type Point = (Rational, Rational)
Line 1,907:
(py /= by || ay < py)
((ax, ay), (bx, by)) = side
line = carrier side</langsyntaxhighlight>
 
=={{header|J}}==
<langsyntaxhighlight lang="j">NB.*crossPnP v point in closed polygon, crossing number
NB. bool=. points crossPnP polygon
crossPnP=: 4 : 0"2
Line 1,918:
p2=. (x0-/X) < (x0-x1) * (y0-/Y) % (y0 - y1)
2|+/ p1*.p2
)</langsyntaxhighlight>
 
Sample data:
<langsyntaxhighlight lang="j">SQUAREV=: 0 0 , 10 0 , 10 10 ,: 0 10
SQUAREV=: SQUAREV, 2.5 2.5 , 7.5 0.1 , 7.5 7.5 ,: 2.5 7.5
 
Line 1,931:
STRANGE=: (0 4,4 3,3 7,7 6,6 2,2 1,1 5,:5 0) , .{ SQUAREV
 
POINTS=: 5 5,5 8,2 2,0 0,10 10,2.5 2.5,0.01 5,2.2 7.4,0 5,10 5,:_4 10</langsyntaxhighlight>
 
Testing:
<langsyntaxhighlight lang="j"> (<POINTS) crossPnP every ESA;SQUARE;SQUAREHOLE;STRANGE
1 1 1 0 0 1 1 1 0 1 0
1 1 1 0 0 1 1 1 0 1 0
0 1 1 0 0 1 1 1 0 1 0
1 0 0 0 0 0 0 1 0 1 0</langsyntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">import static java.lang.Math.*;
 
public class RayCasting {
Line 1,996:
 
final static int[][][] shapes = {square, squareHole, strange, hexagon};
}</langsyntaxhighlight>
 
<pre>
Line 2,006:
 
=={{header|Javascript}}==
<langsyntaxhighlight lang="javascript">
/**
* @return {boolean} true if (lng, lat) is in bounds
Line 2,065:
}
}
</syntaxhighlight>
</lang>
 
=={{header|Julia}}==
Line 2,071:
 
'''Module''':
<langsyntaxhighlight lang="julia">module RayCastings
 
export Point
Line 2,115:
[(a, b) for (a, b) in zip(vcat(a, b...), vcat(b..., a))]
 
end # module RayCastings</langsyntaxhighlight>
 
'''Main''':
<langsyntaxhighlight lang="julia">using Printf
 
let A = Point(0.0, 0.0),
Line 2,150:
end
end
end</langsyntaxhighlight>
 
{{out}}
Line 2,223:
=={{header|Kotlin}}==
{{trans|D}}
<langsyntaxhighlight lang="scala">import java.lang.Double.MAX_VALUE
import java.lang.Double.MIN_VALUE
import java.lang.Math.abs
Line 2,258:
}
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="scala">fun main(args: Array<String>) {
val figures = arrayOf(Figure("Square", arrayOf(Edge(Point(0.0, 0.0), Point(10.0, 0.0)), Edge(Point(10.0, 0.0), Point(10.0, 10.0)),
Edge(Point(10.0, 10.0), Point(0.0, 10.0)),Edge(Point(0.0, 10.0), Point(0.0, 0.0)))),
Line 2,275:
 
Ray_casting.check(figures, points)
}</langsyntaxhighlight>
{{out}}
<pre>points: [Point(x=5.0, y=5.0), Point(x=5.0, y=8.0), Point(x=-10.0, y=5.0), Point(x=0.0, y=5.0), Point(x=10.0, y=5.0), Point(x=8.0, y=5.0), Point(x=10.0, y=10.0)]
Line 2,317:
 
Displays interactively on-screen.
<langsyntaxhighlight lang="lb">NoMainWin
Global sw, sh, verts
 
Line 2,392:
Function rand(loNum,hiNum)
rand = Int(Rnd(0)*(hiNum-loNum+1)+loNum)
End Function </langsyntaxhighlight>
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">function Point(x,y) return {x=x, y=y} end
 
function Polygon(name, points)
Line 2,432:
end
print()
end</langsyntaxhighlight>
{{out}}
<pre>Does 'square' contain..
Line 2,472:
=={{header|Nim}}==
{{trans|D}}
<langsyntaxhighlight Nimlang="nim">import fenv, sequtils, strformat
 
type
Line 2,536:
echo &"Is point inside figure {poly.name}?"
for p in TestPoints:
echo &" ({p.x:3},{p.y:3}): {poly.contains(p)}"</langsyntaxhighlight>
 
{{out}}
Line 2,574:
=={{header|OCaml}}==
{{Trans|C}}
<langsyntaxhighlight lang="ocaml">type point = { x:float; y:float }
type polygon = {
Line 2,670:
print_newline()
) test_points;
;;</langsyntaxhighlight>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use strict;
use List::Util qw(max min);
 
Line 2,710:
 
return ($m_blue >= $m_red) ? 1 : 0;
}</langsyntaxhighlight>
 
Testing:
<langsyntaxhighlight lang="perl"># the following are utilities to use the same Fortran data...
sub point
{
Line 2,751:
( point_in_polygon($tp, $rp) ? "INSIDE" : "OUTSIDE" ) . "\n";
}
}</langsyntaxhighlight>
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">-->
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span>
Line 2,859:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 2,881:
 
=={{header|PHP}}==
<langsyntaxhighlight lang="php">
<?php
 
Line 2,967:
echo json_encode($testPoint) . "\tin " . $shape['name'] . "\t" . contains($shape['bounds'], $testPoint['lat'], $testPoint['lng']) . PHP_EOL;
}
}</langsyntaxhighlight>
{{out}}<pre>{"lng":10,"lat":10} in square 1
{"lng":10,"lat":16} in square 1
Line 2,999:
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(scl 4)
 
(de intersects (Px Py Ax Ay Bx By)
Line 3,025:
(when (apply intersects Edge (car Pt) (cdr Pt))
(onOff Res) ) )
Res ) )</langsyntaxhighlight>
Test data:
<pre style="height:20em;overflow:scroll">(de Square
Line 3,122:
=={{header|PureBasic}}==
The code below is includes a GUI for drawing a polygon with the mouse that constantly tests whether the mouse is inside or outside the polygon. It displays a message and changes the windows color slightly to indicate if the pointer is inside or outside the polygon being drawn. The routine that does the checking is called inpoly() and it returns a value of one if the point is with the polygon and zero if it isn't.
<langsyntaxhighlight PureBasiclang="purebasic">Structure point_f
x.f
y.f
Line 3,204:
FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow</langsyntaxhighlight>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">from collections import namedtuple
from pprint import pprint as pp
import sys
Line 3,308:
for p in testpoints[3:6]))
print (' ', '\t'.join("%s: %s" % (p, ispointinside(p, poly))
for p in testpoints[6:]))</langsyntaxhighlight>
 
'''Sample output'''
Line 3,364:
 
'''Helper routine to convert Fortran Polygons and points to Python'''
<langsyntaxhighlight lang="python">def _convert_fortran_shapes():
point = Pt
pts = (point(0,0), point(10,0), point(10,10), point(0,10),
Line 3,390:
print ' ', ',\n '.join(str(e) for e in p.edges) + '\n )),'
print ' ]'
_convert_fortran_shapes()</langsyntaxhighlight>
 
=={{header|R}}==
<langsyntaxhighlight Rlang="r">point_in_polygon <- function(polygon, p) {
count <- 0
for(side in polygon) {
Line 3,436:
}
}
}</langsyntaxhighlight>
 
<langsyntaxhighlight Rlang="r">######## utility functions #########
 
point <- function(x,y) list(x=x, y=y)
Line 3,450:
}
pol
}</langsyntaxhighlight>
 
<langsyntaxhighlight Rlang="r">#### testing ####
 
pts <- list(point(0,0), point(10,0), point(10,10), point(0,10),
Line 3,477:
p$x, p$y, point_in_polygon(polygons[[polysi]], p), names(polygons[polysi])))
}
}</langsyntaxhighlight>
 
=={{header|Racket}}==
Straightforward implementation of pseudocode
<langsyntaxhighlight lang="scheme">
#lang racket
 
Line 3,563:
(test-figure square "square")
(test-figure exagon "exagon")
</syntaxhighlight>
</lang>
 
{{out}}
Line 3,588:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" perl6line>constant ε = 0.0001;
sub ray-hits-seg([\Px,\Py], [[\Ax,\Ay], [\Bx,\By]] --> Bool) {
Line 3,659:
say "\t(@point.fmt('%.1f',','))\t{ point-in-poly(@point, @poly) ?? 'IN' !! 'OUT' }";
}
}</langsyntaxhighlight>
{{out}}
<pre>squared
Line 3,698:
 
Code was added to facilitate easier specification of polygon sides by just specifying their &nbsp; ''vertices'' &nbsp; instead of specifying their &nbsp; ''line segments''.
<langsyntaxhighlight lang="rexx">/*REXX program verifies if a horizontal ray from point P intersects a polygon. */
call points 5 5, 5 8, -10 5, 0 5, 10 5, 8 5, 10 10
A= 2.5; B= 7.5 /* ◄───── used for shorter arguments (below).*/
Line 3,747:
right( word('outside inside', in$out(k) + 1), 7)
end /*k*/
return /* [↑] format the output nicely*/</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 3,785:
=={{header|Rust}}==
{{trans|Python}}
<langsyntaxhighlight lang="rust">use std::f64;
 
const _EPS: f64 = 0.00001;
Line 3,915:
}
println!();
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,926:
=={{header|Scala}}==
{{trans|D}}
<langsyntaxhighlight lang="scala">package scala.ray_casting
 
case class Edge(_1: (Double, Double), _2: (Double, Double)) {
Line 3,972:
 
private implicit def to_edge(p: ((Double, Double), (Double, Double))): Edge = Edge(p._1, p._2)
}</langsyntaxhighlight>
{{out}}
<pre>points: List((5.0,5.0), (5.0,8.0), (-10.0,5.0), (0.0,5.0), (10.0,5.0), (8.0,5.0), (10.0,10.0))
Line 3,992:
{{works with|GNU Smalltalk}}
The class Segment holds the code to test if a ray starting from a point (and going towards "right") intersects the segment (method <tt>doesIntersectRayFrom</tt>); while the class Polygon hosts the code to test if a point is inside the polygon (method <tt>pointInside</tt>).
<langsyntaxhighlight lang="smalltalk">Object subclass: Segment [
|pts|
Segment class >> new: points [ |a|
Line 4,068:
^ ( cnt \\ 2 = 0 ) not
]
].</langsyntaxhighlight>
 
'''Testing'''
<langsyntaxhighlight lang="smalltalk">|points names polys|
 
points := {
Line 4,112:
].
' ' displayNl.
]</langsyntaxhighlight>
 
=={{header|Tcl}}==
<langsyntaxhighlight Tcllang="tcl">package require Tcl 8.5
proc point_in_polygon {point polygon} {
Line 4,172:
} {
puts "$point in $poly = [point_in_polygon $point $poly]"
}</langsyntaxhighlight>
 
=={{header|Ursala}}==
Line 4,179:
value if it's outside, using the algorithm described above.
For points on the boundary the result is unspecified.
<langsyntaxhighlight Ursalalang="ursala">#import flo
 
in =
Line 4,185:
@lrzyCipPX ~|afatPRZaq ~&EZ+fleq~~lrPrbr2G&& ~&B+fleq~~lrPrbl2G!| -&
~&Y+ ~~lrPrbl2G fleq,
^E(fleq@lrrPX,@rl fleq\0.)^/~&lr ^(~&r,times)^/minus@llPrll2X vid+ minus~~rbbI&-</langsyntaxhighlight>
This test program tries it on a couple of examples.
<langsyntaxhighlight Ursalalang="ursala">#cast %bL
 
examples =
Line 4,193:
in* <
((0.5,0.6),<(0.,0.),(1.,2.),(1.,0.)>),
((0.5,0.6),<(0.,0.),(1.,1.),(1.,0.)>)></langsyntaxhighlight>
output:
<pre><true,false></pre>
Line 4,199:
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<langsyntaxhighlight lang="vbnet">Imports System.Math
 
Module RayCasting
Line 4,245:
Return red >= blue
End Function
End Module</langsyntaxhighlight>
{{out}}
<pre>
Line 4,257:
{{trans|Java}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight lang="ecmascript">import "/fmt" for Fmt
 
class RayCasting {
Line 4,294:
for (pnt in testPoints) Fmt.write("$7s ", RayCasting.contains(shape, pnt))
System.print()
}</langsyntaxhighlight>
 
{{out}}
Line 4,306:
=={{header|zkl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="zkl">const E = 0.0001;
fcn rayHitsSeg([(Px,Py)],[(Ax,Ay)],[(Bx,By)]){ // --> Bool
Line 4,322:
})
.len().isOdd; // True if crossed an odd number of borders ie inside polygon
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">polys:=T( //(name,( ((a,b),(c,d)),((a,b),(c,d))... ), ... )==(nm,(ln,ln..) ..)
T("squared",
T(T(T( 0.0, 0.0), T(10.0, 0.0)),
Line 4,372:
pointInPoly(testPoint,polywanna) and "IN" or "OUT");
}
}</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328253"