Ray-casting algorithm: Difference between revisions

{{task|Classic CS problems and programs}}

{{Wikipedia|Point_in_polygon}}

Given a point and a polygon, check if the point is inside or outside the polygon using the [[wp:Point in polygon#Ray casting algorithm|ray-casting algorithm]].

 

[[Image:posslope.png|128px|thumb|right]]

[[Image:negslope.png|128px|thumb|right]]

Let us take into account a segment AB (the point A having y coordinate always smaller than B's y coordinate, i.e. point A is always below point B) and a point P. Let us use the cumbersome notation PAX to denote the angle between segment AP and AX, where X is always a point on the horizontal line passing by A with x coordinate bigger than the maximum between the x coordinate of A and the x coordinate of B. As explained graphically by the figures on the right, if PAX is greater than the angle BAX, then the ray starting from P intersects the segment AB. (In the images, the ray starting from P_A does not intersect the segment, while the ray starting from P_B in the second picture, intersects the segment).

 

'''if''' Py < Ay '''or''' Py > By '''then'''

'''return''' false

'''return''' false

'''else'''

'''end''' '''if'''

 

 

=={{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(8.0,5.0): TRUE

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

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey L}}

, {x: 5.0, y: 8.0}

, {x:-10.0, y: 5.0}

}

}

{{out}}

<pre>---------------------------

OK

---------------------------</pre>

 

=={{header|C}}==

#include <stdlib.h>

#include <math.h>

 

return 0;

 

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

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

{{trans|D}}

#include <cstdlib>

#include <iomanip>

const double MAX = DOUBLE.max();

 

 

struct Edge {

 

bool operator()(const Point& p) const

 

struct Figure {

 

bool contains(const Point& p) const

{

auto c = 0;

return c % 2 != 0;

}

 

template<unsigned char W = 3>

{

os << "Is point inside figure " << name << '?' << endl;

int main()

{

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

};

 

{ {{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}}, {{7.5, 7.5}, {2.5, 7.5}}, {{2.5, 7.5}, {2.5, 2.5}}

};

 

{ {{0.0, 0.0}, {2.5, 2.5}}, {{2.5, 2.5}, {0.0, 10.0}}, {{0.0, 10.0}, {2.5, 7.5}}, {{2.5, 7.5}, {7.5, 7.5}},

{{7.5, 7.5}, {10.0, 10.0}}, {{10.0, 10.0}, {10.0, 0.0}}, {{10.0, 0}, {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}}

 

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

End Type

 

Function inpolygon(p1() As Point,p2 As Point) As Integer

-Sgn( (L(1).x-L(2).x)*(p.y-L(2).y) - (p.x-L(2).x)*(L(1).y-L(2).y))

End If

End Function

 

 

Dim As Point exagon(1 To 6) ={(3,0),(7,0),(10,5),(7,10),(3,10),(0,5)}

'printouts

For z As Integer=1 To 4

Case 1: Print "squared"

Next z

Output:

(5,5) in

(5,8) in

(10,5) in

(8,5) in

 

=={{header|Go}}==

 

import (

"math"

)

 

}

 

 

func main() {

}

}

<pre>

square:

{8 5} true

{10 10} false

square hole:

{5 5} false

{8 5} true

{10 10} false

strange:

{5 5} true

{8 5} true

{10 10} false

exagon:

{5 5} true

{8 5} true

{10 10} false

</pre>

'''Closed polygon solution'''

 

 

import (

}

}

<pre>

square:

{2 1} false

</pre>

 

=={{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|Liberty BASIC}}==

 

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>

********** ********** **** ******

********** ********** * ****

</pre>

 

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

 

(module pip racket

(require racket/contract)

(provide point)

(provide seg)

 

(struct point (x y) #:transparent)

(define ε 0.000001)

(define (neq? x y) (not (eq? x y)))

(eq? Pyo By))

ε 0))])

[(> Px (max Ax Bx)) #f]

 

(define (point-in-polygon? point polygon)

(test-figure square "square")

(test-figure exagon "exagon")

 

{{out}}

</pre>

 

 

 

 

<pre>

 

 

 

</pre>

 

 

 

 

 

}

 

}

 

 

=={{header|Smalltalk}}==

{{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|zkl}}==

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>