Ray-casting algorithm: Difference between revisions

(To avoid the "ray on vertex" problem, the point is moved upward of a small quantity &nbsp; <big>&epsilon;</big>.)

<br><br>

 

=={{header|Ada}}==

polygons.ads:

 

type Point is record

function Is_Inside (Who : Point; Where : Polygon) return Boolean;

 

 

polygons.adb:

EPSILON : constant := 0.00001;

 

end Is_Inside;

 

 

Example use:

 

main.adb:

with Polygons;

procedure Main is

Ada.Text_IO.New_Line;

end loop;

 

Output:

Point(10.0,10.0): FALSE</pre>

 

{{trans|FreeBASIC}}

1010 LET x=1

1020 LET y=2

2810 NEXT z

2820 END

 

 

 

 

=={{header|C}}==

#include <stdlib.h>

#include <math.h>

 

return 0;

 

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

{{works with|C++|11}}

{{trans|D}}

#include <cstdlib>

#include <iomanip>

 

return EXIT_SUCCESS;

{{output}}

As D.

=={{header|CoffeeScript}}==

Takes a polygon as a list of points joining segments, and creates segments between them.

 

pointInPoly = (point,poly) ->

mAB = (b.y - a.y) / (b.x - a.x)

mAP = (p.y - a.y) / (p.x - a.x)

 

=={{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.

(do ((in-p nil)) ((endp polygon) in-p)

(when (ray-intersects-segment point (pop polygon))

((null m-blue) t)

((null m-red) nil)

 

Testing code

#((0 . 0) (10 . 0) (10 . 10) (0 . 10)

(2.5 . 2.5) (7.5 . 2.5) (7.5 . 7.5) (2.5 . 7.5)

do (format t "~&~w ~:[outside~;inside ~]."

test-point

 

=={{header|D}}==

 

immutable struct Point { double x, y; }

writeln;

}

{{out}}

<pre>Is point inside figure "Square"?

=={{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.

IN: raycasting

 

[ dup first suffix [ rest-slice ] [ but-last-slice ] bi ] dip

[ ray ] curry 2map

Usage:

( scratchpad ) square { 0 0 } raycast .

t

f

( scratchpad ) square { 2 0 } raycast .

 

=={{header|Fortran}}==

 

This module ''defines'' "polygons".

use Points_Module

implicit none

end subroutine free_polygon

 

 

The ray casting algorithm module:

use Polygons

implicit none

end function point_is_inside

 

 

'''Testing'''

use Points_Module

use Ray_Casting_Algo

end do

 

 

=={{header|FreeBASIC}}==

Inpolygon by Winding number method

As Single x,y

End Type

End Select

Next z

Output:

<pre>squared

 

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.)

 

import (

}

}

{{out}}

<pre>

 

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.

 

import (

}

}

{{out}}

<pre>

 

This solution is preferred over the two above.

 

import "fmt"

}

}

 

=={{header|Haskell}}==

 

type Point = (Rational, Rational)

(py /= by || ay < py)

((ax, ay), (bx, by)) = side

 

=={{header|J}}==

NB. bool=. points crossPnP polygon

crossPnP=: 4 : 0"2

p2=. (x0-/X) < (x0-x1) * (y0-/Y) % (y0 - y1)

2|+/ p1*.p2

 

Sample data:

SQUAREV=: SQUAREV, 2.5 2.5 , 7.5 0.1 , 7.5 7.5 ,: 2.5 7.5

 

STRANGE=: (0 4,4 3,3 7,7 6,6 2,2 1,1 5,:5 0) , .{ SQUAREV

 

 

Testing:

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

 

=={{header|Java}}==

 

public class RayCasting {

 

final static int[][][] shapes = {square, squareHole, strange, hexagon};

 

<pre>

 

=={{header|Javascript}}==

/**

* @return {boolean} true if (lng, lat) is in bounds

}

}

 

=={{header|Julia}}==

 

'''Module''':

 

export Point

[(a, b) for (a, b) in zip(vcat(a, b...), vcat(b..., a))]

 

 

'''Main''':

 

let A = Point(0.0, 0.0),

end

end

 

{{out}}

=={{header|Kotlin}}==

{{trans|D}}

import java.lang.Double.MIN_VALUE

import java.lang.Math.abs

}

}

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)))),

 

Ray_casting.check(figures, points)

{{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)]

 

Displays interactively on-screen.

Global sw, sh, verts

 

Function rand(loNum,hiNum)

rand = Int(Rnd(0)*(hiNum-loNum+1)+loNum)

 

=={{header|OCaml}}==

{{Trans|C}}

type polygon = {

print_newline()

) test_points;

 

=={{header|Perl}}==

use List::Util qw(max min);

 

 

return ($m_blue >= $m_red) ? 1 : 0;

 

Testing:

sub point

{

( point_in_polygon($tp, $rp) ? "INSIDE" : "OUTSIDE" ) . "\n";

}

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PHP}}==

<?php

 

echo json_encode($testPoint) . "\tin " . $shape['name'] . "\t" . contains($shape['bounds'], $testPoint['lat'], $testPoint['lng']) . PHP_EOL;

}

{{out}}<pre>{"lng":10,"lat":10} in square 1

{"lng":10,"lat":16} in square 1

 

=={{header|PicoLisp}}==

 

(de intersects (Px Py Ax Ay Bx By)

(when (apply intersects Edge (car Pt) (cdr Pt))

(onOff Res) ) )

Test data:

<pre style="height:20em;overflow:scroll">(de Square

=={{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.

x.f

y.f

FlipBuffers()

 

=={{header|Python}}==

from pprint import pprint as pp

import sys

for p in testpoints[3:6]))

print (' ', '\t'.join("%s: %s" % (p, ispointinside(p, poly))

 

'''Sample output'''

 

'''Helper routine to convert Fortran Polygons and points to Python'''

point = Pt

pts = (point(0,0), point(10,0), point(10,10), point(0,10),

print ' ', ',\n '.join(str(e) for e in p.edges) + '\n )),'

print ' ]'

 

=={{header|R}}==

count <- 0

for(side in polygon) {

}

}

 

 

point <- function(x,y) list(x=x, y=y)

}

pol

 

 

pts <- list(point(0,0), point(10,0), point(10,10), point(0,10),

p$x, p$y, point_in_polygon(polygons[[polysi]], p), names(polygons[polysi])))

}

 

=={{header|Racket}}==

Straightforward implementation of pseudocode

#lang racket

 

(test-figure square "square")

(test-figure exagon "exagon")

 

{{out}}

=={{header|Raku}}==

(formerly Perl 6)

sub ray-hits-seg([\Px,\Py], [[\Ax,\Ay], [\Bx,\By]] --> Bool) {

say "\t(@point.fmt('%.1f',','))\t{ point-in-poly(@point, @poly) ?? 'IN' !! 'OUT' }";

}

{{out}}

<pre>squared

 

Code was added to facilitate easier specification of polygon sides by just specifying their &nbsp; ''vertices'' &nbsp; instead of specifying their &nbsp; ''line segments''.

call points 5 5, 5 8, -10 5, 0 5, 10 5, 8 5, 10 10

call poly 0 0, 10 0, 10 10, 0 10 ; call test 'square'

call poly 0 0, 10 0, 10 10, 0 10, A A, B A, B B, A B ; call test 'square hole'

call poly 0 0, A A, 0 10, A B, B B, 10 10, 10 0 ; call test 'irregular'

call poly 3 0, 7 0, 10 5, 7 10, 3 10, 0 5 ; call test 'hexagon'

/*──────────────────────────────────────────────────────────────────────────────────────*/

return # // 2 /*ODD is inside. EVEN is outside.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

if Ay>By then parse value Ax Ay Bx By with Bx By Ax Ay

if Py<Ay | Py>By | Px>max(Ax, Bx) then return 0

if Px<min(Ax, Bx) then return 1

if Ax\=Bx then red = (By-Ay) / (Bx-Ax)

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*j*/

call value point.0, j-1 /*define the number of points. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

poly: @= 'POLY.'; parse arg Fx Fy /* [↓] process the X,Y points.*/

call value @ || n'.X', xx ; call value @ || n".Y", yy

call value @ || n'.X', xx ; call value @ || n".Y", yy

end /*j*/

call value @ || n'.X', Fx; call value @ || n".Y", Fy; call value @'0', n

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

say right(' ['arg(1)"] point:", 30),

right( right(point.k.x, wx)', 'right(point.k.y, wy), w) " is ",

right( word('outside inside', in$out(k) + 1), 7)

end /*k*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Rust}}==

{{trans|Python}}

 

const _EPS: f64 = 0.00001;

}

println!();

{{out}}

<pre>

=={{header|Scala}}==

{{trans|D}}

 

case class Edge(_1: (Double, Double), _2: (Double, Double)) {

 

private implicit def to_edge(p: ((Double, Double), (Double, Double))): Edge = Edge(p._1, p._2)

{{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))

{{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>).

|pts|

Segment class >> new: points [ |a|

^ ( cnt \\ 2 = 0 ) not

]

 

'''Testing'''

 

points := {

].

' ' displayNl.

 

=={{header|Tcl}}==

proc point_in_polygon {point polygon} {

} {

puts "$point in $poly = [point_in_polygon $point $poly]"

 

=={{header|Ursala}}==

value if it's outside, using the algorithm described above.

For points on the boundary the result is unspecified.

 

in =

@lrzyCipPX ~|afatPRZaq ~&EZ+fleq~~lrPrbr2G&& ~&B+fleq~~lrPrbl2G!| -&

~&Y+ ~~lrPrbl2G fleq,

This test program tries it on a couple of examples.

 

examples =

in* <

((0.5,0.6),<(0.,0.),(1.,2.),(1.,0.)>),

output:

<pre><true,false></pre>

=={{header|Visual Basic .NET}}==

{{trans|Java}}

 

Module RayCasting

Return red >= blue

End Function

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Java}}

{{libheader|Wren-fmt}}

 

class RayCasting {

if (a[1] > b[1]) return intersects(b, a, p)

if (p[1] == a[1] || p[1] == b[1]) p[1] = p[1] + 0.0001

var red = (p[1] - a[1]) / (p[0] - a[0])

var blue = (b[1] - a[1]) / (b[0] - a[0])

for (pnt in testPoints) Fmt.write("$7s ", RayCasting.contains(shape, pnt))

System.print()

 

{{out}}

=={{header|zkl}}==

{{trans|Raku}}

fcn rayHitsSeg([(Px,Py)],[(Ax,Ay)],[(Bx,By)]){ // --> Bool

})

.len().isOdd; // True if crossed an odd number of borders ie inside polygon

T("squared",

T(T(T( 0.0, 0.0), T(10.0, 0.0)),

pointInPoly(testPoint,polywanna) and "IN" or "OUT");

}

{{out}}

<pre>