Ray-casting algorithm: Difference between revisions
Added Algol 68
(Added Algol 68) |
|||
(43 intermediate revisions by 23 users not shown) | |||
Line 49:
'''if''' Py < Ay '''or''' Py > By '''then'''
'''return''' false
'''else''' '''if''' Px >= max(Ax, Bx) '''then'''
'''return''' false
'''else'''
Line 75:
(To avoid the "ray on vertex" problem, the point is moved upward of a small quantity <big>ε</big>.)
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">T Pt
Float x, y
F (x, y)
.x = x
.y = y
F String()
R ‘Pt(x=#., y=#.)’.format(.x, .y)
T Edge
Pt a, b
F (a, b)
.a = a
.b = b
F String()
R ‘Edge(a=#., b=#.)’.format(.a, .b)
T Poly
String name
[Edge] edges
F (name, edges)
.name = name
.edges = edges
V _eps = 0.00001
V _huge = 1e+100
V _tiny = 1e-100
F rayintersectseg(=p, edge)
V a = edge.a
V b = edge.b
I a.y > b.y
swap(&a, &b)
I p.y == a.y | p.y == b.y
p = Pt(p.x, p.y + :_eps)
V intersect = 0B
I (p.y > b.y | p.y < a.y) | (p.x > max(a.x, b.x))
R 0B
I p.x < min(a.x, b.x)
intersect = 1B
E
Float m_red, m_blue
I abs(a.x - b.x) > :_tiny
m_red = (b.y - a.y) / Float(b.x - a.x)
E
m_red = :_huge
I abs(a.x - p.x) > :_tiny
m_blue = (p.y - a.y) / Float(p.x - a.x)
E
m_blue = :_huge
intersect = m_blue >= m_red
R intersect
F ispointinside(p, poly)
R sum(poly.edges.map(edge -> Int(rayintersectseg(@p, edge)))) % 2 == 1
F polypp(poly)
print("\n Polygon(name='#.', edges=(".format(poly.name))
print(‘ ’(poly.edges.map(e -> String(e)).join(",\n ")"\n ))"))
V polys = [
Poly(name' ‘square’, edges' [Edge(Pt(0, 0), Pt(10, 0)), Edge(Pt(10, 0), Pt(10, 10)), Edge(Pt(10, 10), Pt(0, 10)), Edge(Pt(0, 10), Pt(0, 0))]),
Poly(name' ‘square_hole’, edges' [Edge(Pt(0, 0), Pt(10, 0)), Edge(Pt(10, 0), Pt(10, 10)), Edge(Pt(10, 10), Pt(0, 10)), Edge(Pt(0, 10), Pt(0, 0)), Edge(Pt(2.5, 2.5), Pt(7.5, 2.5)), Edge(Pt(7.5, 2.5), Pt(7.5, 7.5)), Edge(Pt(7.5, 7.5), Pt(2.5, 7.5)), Edge(Pt(2.5, 7.5), Pt(2.5, 2.5))]),
Poly(name' ‘strange’, edges' [Edge(Pt(0, 0), Pt(2.5, 2.5)), Edge(Pt(2.5, 2.5), Pt(0, 10)), Edge(Pt(0, 10), Pt(2.5, 7.5)), Edge(Pt(2.5, 7.5), Pt(7.5, 7.5)), Edge(Pt(7.5, 7.5), Pt(10, 10)), Edge(Pt(10, 10), Pt(10, 0)), Edge(Pt(10, 0), Pt(2.5, 2.5))]),
Poly(name' ‘exagon’, edges' [Edge(Pt(3, 0), Pt(7, 0)), Edge(Pt(7, 0), Pt(10, 5)), Edge(Pt(10, 5), Pt(7, 10)), Edge(Pt(7, 10), Pt(3, 10)), Edge(Pt(3, 10), Pt(0, 5)), Edge(Pt(0, 5), Pt(3, 0))])]
V testpoints = [Pt(5, 5), Pt(5, 8),
Pt(-10, 5), Pt(0, 5),
Pt(10, 5), Pt(8, 5),
Pt(10, 10)]
print("\n TESTING WHETHER POINTS ARE WITHIN POLYGONS")
L(poly) polys
polypp(poly)
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"))</syntaxhighlight>
{{out}}
<pre style="height:20em;overflow:scroll">
TESTING WHETHER POINTS ARE WITHIN POLYGONS
Polygon(name='square', edges=(
Edge(a=Pt(x=0, y=0), b=Pt(x=10, y=0)),
Edge(a=Pt(x=10, y=0), b=Pt(x=10, y=10)),
Edge(a=Pt(x=10, y=10), b=Pt(x=0, y=10)),
Edge(a=Pt(x=0, y=10), b=Pt(x=0, y=0))
))
Pt(x=5, y=5): True Pt(x=5, y=8): True Pt(x=-10, y=5): False
Pt(x=0, y=5): False Pt(x=10, y=5): True Pt(x=8, y=5): True
Pt(x=10, y=10): False
Polygon(name='square_hole', edges=(
Edge(a=Pt(x=0, y=0), b=Pt(x=10, y=0)),
Edge(a=Pt(x=10, y=0), b=Pt(x=10, y=10)),
Edge(a=Pt(x=10, y=10), b=Pt(x=0, y=10)),
Edge(a=Pt(x=0, y=10), b=Pt(x=0, y=0)),
Edge(a=Pt(x=2.5, y=2.5), b=Pt(x=7.5, y=2.5)),
Edge(a=Pt(x=7.5, y=2.5), b=Pt(x=7.5, y=7.5)),
Edge(a=Pt(x=7.5, y=7.5), b=Pt(x=2.5, y=7.5)),
Edge(a=Pt(x=2.5, y=7.5), b=Pt(x=2.5, y=2.5))
))
Pt(x=5, y=5): False Pt(x=5, y=8): True Pt(x=-10, y=5): False
Pt(x=0, y=5): False Pt(x=10, y=5): True Pt(x=8, y=5): True
Pt(x=10, y=10): False
Polygon(name='strange', edges=(
Edge(a=Pt(x=0, y=0), b=Pt(x=2.5, y=2.5)),
Edge(a=Pt(x=2.5, y=2.5), b=Pt(x=0, y=10)),
Edge(a=Pt(x=0, y=10), b=Pt(x=2.5, y=7.5)),
Edge(a=Pt(x=2.5, y=7.5), b=Pt(x=7.5, y=7.5)),
Edge(a=Pt(x=7.5, y=7.5), b=Pt(x=10, y=10)),
Edge(a=Pt(x=10, y=10), b=Pt(x=10, y=0)),
Edge(a=Pt(x=10, y=0), b=Pt(x=2.5, y=2.5))
))
Pt(x=5, y=5): True Pt(x=5, y=8): False Pt(x=-10, y=5): False
Pt(x=0, y=5): False Pt(x=10, y=5): True Pt(x=8, y=5): True
Pt(x=10, y=10): False
Polygon(name='exagon', edges=(
Edge(a=Pt(x=3, y=0), b=Pt(x=7, y=0)),
Edge(a=Pt(x=7, y=0), b=Pt(x=10, y=5)),
Edge(a=Pt(x=10, y=5), b=Pt(x=7, y=10)),
Edge(a=Pt(x=7, y=10), b=Pt(x=3, y=10)),
Edge(a=Pt(x=3, y=10), b=Pt(x=0, y=5)),
Edge(a=Pt(x=0, y=5), b=Pt(x=3, y=0))
))
Pt(x=5, y=5): True Pt(x=5, y=8): True Pt(x=-10, y=5): False
Pt(x=0, y=5): False Pt(x=10, y=5): True Pt(x=8, y=5): True
Pt(x=10, y=10): False
</pre>
=={{header|Ada}}==
polygons.ads:
<
type Point is record
Line 91 ⟶ 234:
function Is_Inside (Who : Point; Where : Polygon) return Boolean;
end Polygons;</
polygons.adb:
<
EPSILON : constant := 0.00001;
Line 180 ⟶ 323:
end Is_Inside;
end Polygons;</
Example use:
main.adb:
<
with Polygons;
procedure Main is
Line 275 ⟶ 418:
Ada.Text_IO.New_Line;
end loop;
end Main;</
Output:
Line 313 ⟶ 456:
Point(8.0,5.0): TRUE
Point(10.0,10.0): FALSE</pre>
=={{header|ALGOL 68}}==
{{Trans|Lua}}
<syntaxhighlight lang="algol68">
BEGIN
MODE POINT = STRUCT( REAL x, y );
MODE POLYGON = STRUCT( STRING name, FLEX[ 1 : 0 ]POINT points );
PROC contains = ( POLYGON self, POINT p )BOOL:
BEGIN
BOOL odd := FALSE, REAL eps = 1e-9;
PROC rayseg = ( POINT p in, a in, b in )BOOL:
BEGIN
PROC max = ( REAL m, n )REAL: IF m > n THEN m ELSE n FI;
PROC min = ( REAL m, n )REAL: IF m < n THEN m ELSE n FI;
POINT p := p in, a := a in, b := b in;
IF y OF a > y OF b THEN POINT t = a; a := b; b := t FI;
IF y OF p = y OF a OR y OF p = y OF b THEN y OF p+:= eps FI;
IF y OF p < y OF a OR y OF p > y OF b OR x OF p > max( x OF a, x OF b )
THEN FALSE
ELIF x OF p < min( x OF a, x OF b )
THEN TRUE
ELSE
REAL red = IF x OF a = x OF b THEN max real ELSE ( y OF b - y OF a ) / ( x OF b - x OF a ) FI;
REAL blu = IF x OF a = x OF p THEN max real ELSE ( y OF p - y OF a ) / ( x OF p - x OF a ) FI;
blu >= red
FI
END # rayseq # ;
INT len points = ( UPB points OF self - LWB points OF self ) + 1;
FOR i FROM LWB points OF self TO UPB points OF self DO
POINT a = ( points OF self )[ i ];
POINT b = ( points OF self )[ ( i MOD len points ) + 1 ];
IF rayseg( p, a, b ) THEN odd := NOT odd FI
OD;
odd
END # contains # ;
[]POLYGON polygons =
( ( "square"
, ( ( 0, 0 ), ( 10, 0 ), ( 10, 10 ), ( 0, 10 ) )
)
, ( "squarehole"
, ( ( 0, 0 ), ( 10, 0 ), ( 10, 10 ), ( 0, 10 ), ( 2.5, 2.5 ), ( 7.5, 2.5 ), ( 7.5, 7.5 ), ( 2.5, 7.5 ) )
)
, ( "strange"
, ( ( 0, 0 ), ( 2.5, 2.5 ), ( 0, 10 ), ( 2.5, 7.5 ), ( 7.5, 7.5 ), ( 10, 10 ), ( 10, 0 ), ( 2.5, 2.5 ) )
)
, ( "hexagon"
, ( ( 3, 0 ), ( 7, 0 ), ( 10, 5 ), ( 7, 10 ), ( 3, 10 ), ( 0, 5 ) )
)
);
[]POINT points = ( ( 5, 5 ), (5 , 8 ), ( -10, 5 ), ( 0, 5 ), ( 10, 5 ), ( 8, 5 ), ( 10, 10 ) );
FOR p FROM LWB polygons TO UPB polygons DO
POLYGON poly = polygons[ p ];
print(( "Does '", name OF poly, "' contain the point..", newline ) );
FOR i FROM LWB points TO UPB points DO
POINT pt = points[ i ];
print( ( " ( ", fixed( x OF pt, -5, 1 ), ", ", fixed( y OF pt, -5, 1 ), " ) " ) );
print( ( IF contains( poly, pt ) THEN " true" ELSE " false" FI, newline ) )
OD;
print( ( newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre>
Does 'square' contain the point..
( 5.0, 5.0 ) true
( 5.0, 8.0 ) true
( -10.0, 5.0 ) false
( 0.0, 5.0 ) false
( 10.0, 5.0 ) true
( 8.0, 5.0 ) true
( 10.0, 10.0 ) false
Does 'squarehole' contain the point..
( 5.0, 5.0 ) false
( 5.0, 8.0 ) true
( -10.0, 5.0 ) false
( 0.0, 5.0 ) false
( 10.0, 5.0 ) true
( 8.0, 5.0 ) true
( 10.0, 10.0 ) false
Does 'strange' contain the point..
( 5.0, 5.0 ) true
( 5.0, 8.0 ) false
( -10.0, 5.0 ) false
( 0.0, 5.0 ) false
( 10.0, 5.0 ) true
( 8.0, 5.0 ) true
( 10.0, 10.0 ) false
Does 'hexagon' contain the point..
( 5.0, 5.0 ) true
( 5.0, 8.0 ) true
( -10.0, 5.0 ) false
( 0.0, 5.0 ) false
( 10.0, 5.0 ) true
( 8.0, 5.0 ) true
( 10.0, 10.0 ) false
</pre>
=={{header|AutoHotkey}}==
{{works with|AutoHotkey L}}
<
, {x: 5.0, y: 8.0}
, {x:-10.0, y: 5.0}
Line 409 ⟶ 658:
}
}
}</
{{out}}
<pre>---------------------------
Line 446 ⟶ 695:
OK
---------------------------</pre>
=={{header|BASIC}}==
==={{header|ANSI BASIC}}===
{{trans|FreeBASIC}}
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">1000 PUBLIC NUMERIC x,y
1010 LET x=1
1020 LET y=2
1030 !
1040 DEF isLeft2(L(,),p()) = -SGN( (L(1,x)-L(2,x))*(p(y)-L(2,y)) - (p(x)-L(2,x))*(L(1,y)-L(2,y)))
1050 !
1060 FUNCTION inpolygon(p1(,),p2())
1070 LET k=UBOUND(p1,1)+1
1080 DIM send (1 TO 2,2)
1090 LET wn=0
1100 FOR n=1 TO UBOUND(p1,1)
1110 LET index=MOD(n, k)
1120 LET nextindex=MOD(n+1, k)
1130 IF nextindex=0 THEN LET nextindex=1
1140 LET send(1,x)=p1(index,x)
1150 LET send(2,x)=p1(nextindex,x)
1160 LET send(1,y)=p1(index,y)
1170 LET send(2,y)=p1(nextindex,y)
1180 IF p1(index,y)<=p2(y) THEN
1190 IF p1(nextindex,y)>p2(y) THEN
1200 IF isleft2(send,p2)>=0 THEN !'=
1210 LET wn=wn+1
1220 END IF
1230 END IF
1240 ELSE
1250 IF p1(nextindex,y)<=p2(y) THEN
1260 IF isleft2(send,p2)<=0 THEN !'=
1270 LET wn=wn-1
1280 END IF
1290 END IF
1300 END IF
1310 NEXT n
1320 LET inpolygon = wn
1330 END FUNCTION
1340 !
1350 DIM type(1 TO 2)
1360 !
1370 DIM square(4,2)
1380 MAT READ square
1390 DATA 0,0,10,0,10,10,0,10
1400 !
1410 DIM hole(4,2)
1420 MAT READ hole
1430 DATA 2.5,2.5,7.5,2.5,7.5,7.5,2.5,7.5
1440 !
1450 DIM strange(8,2)
1460 MAT READ strange
1470 DATA 0,0,2.5,2.5,0,10,2.5,7.5,7.5,7.5,10,10,10,0,2.5,2.5
1480 !
1490 DIM exagon(6,2)
1500 MAT READ exagon
1510 DATA 3,0,7,0,10,5,7,10,3,10,0,5
1520 !
1530 ! printouts
1540 FOR z=1 TO 4
1550 SELECT CASE z
1560 CASE 1
1570 PRINT "squared"
1580 PRINT "(5,5) ";TAB(12);
1590 MAT READ type
1600 DATA 5,5
1610 IF inpolygon(square,type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1620 MAT READ type
1630 DATA 5,8
1640 PRINT "(5,8) ";TAB(12);
1650 IF inpolygon(square,type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1660 PRINT "(-10,5) ";TAB(12);
1670 MAT READ type
1680 DATA -10,5
1690 IF inpolygon(square,type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1700 Print "(0,5) ";Tab(12);
1710 MAT READ type
1720 DATA 0,5
1730 IF inpolygon(square,type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1740 Print "(10,5) ";Tab(12);
1750 MAT READ type
1760 DATA 10,5
1770 IF inpolygon(square,type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1780 PRINT "(8,5) ";TAB(12);
1790 MAT READ type
1800 DATA 8,5
1810 IF inpolygon(square,Type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1820 PRINT "(10,10) ";TAB(12);
1830 MAT READ type
1840 DATA 10,10
1850 IF inpolygon(square,Type) <> 0 THEN PRINT "in" ELSE PRINT "out"
1860 PRINT
1870 CASE 2
1880 PRINT "squared hole"
1890 PRINT "(5,5) ";TAB(12);
1900 MAT READ type
1910 DATA 5,5
1920 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
1930 Print "(5,8) ";Tab(12);
1940 MAT READ type
1950 DATA 5,8
1960 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
1970 PRINT "(-10,5) ";TAB(12);
1980 MAT READ type
1990 DATA -10,5
2000 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2010 PRINT "(0,5) ";TAB(12);
2020 MAT READ type
2030 DATA 0,5
2040 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2050 PRINT "(10,5) ";TAB(12);
2060 MAT READ type
2070 DATA 10,5
2080 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2090 PRINT "(8,5) ";TAB(12);
2100 MAT READ type
2110 DATA 8,5
2120 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2130 PRINT "(10,10) ";TAB(12);
2140 MAT READ type
2150 DATA 10,10
2160 IF NOT inpolygon(hole,Type)<>0 AND inpolygon(square,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2170 PRINT
2180 CASE 3
2190 PRINT "strange"
2200 PRINT "(5,5) ";TAB(12);
2210 MAT READ type
2220 DATA 5,5
2230 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2240 PRINT "(5,8) ";TAB(12);
2250 MAT READ type
2260 DATA 5,8
2270 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2280 PRINT "(-10,5) ";TAB(12);
2290 MAT READ type
2300 DATA -10,5
2310 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2320 PRINT "(0,5) ";TAB(12);
2330 MAT READ type
2340 DATA 0,5
2350 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2360 PRINT "(10,5) ";TAB(12);
2370 MAT READ type
2380 DATA 10,5
2390 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2400 PRINT "(8,5) ";TAB(12);
2410 MAT READ type
2420 DATA 8,5
2430 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2440 PRINT "(10,10) ";TAB(12);
2450 MAT READ type
2460 DATA 10,10
2470 IF inpolygon(strange,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2480 PRINT
2490 CASE 4
2500 PRINT "exagon"
2510 PRINT "(5,5) ";TAB(12);
2520 MAT READ type
2530 DATA 5,5
2540 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2550 PRINT "(5,8) ";TAB(12);
2560 MAT READ type
2570 DATA 5,8
2580 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2590 PRINT "(-10,5) ";TAB(12);
2600 MAT READ type
2610 DATA -10,5
2620 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2630 PRINT "(0,5) ";TAB(12);
2640 MAT READ type
2650 DATA 0,5
2660 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2670 PRINT "(10,5) ";TAB(12);
2680 MAT READ type
2690 DATA 10,5
2700 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2710 PRINT "(8,5) ";TAB(12);
2720 MAT READ type
2730 DATA 8,5
2740 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2750 PRINT "(10,10) ";TAB(12);
2760 MAT READ type
2770 DATA 10,10
2780 IF inpolygon(exagon,Type)<>0 THEN PRINT "in" ELSE PRINT "out"
2790 PRINT
2800 END SELECT
2810 NEXT z
2820 END
</syntaxhighlight>
{{out}}
<pre>
squared
(5,5) in
(5,8) in
(-10,5) out
(0,5) out
(10,5) in
(8,5) in
(10,10) out
squared hole
(5,5) out
(5,8) in
(-10,5) out
(0,5) out
(10,5) in
(8,5) in
(10,10) out
strange
(5,5) in
(5,8) out
(-10,5) out
(0,5) out
(10,5) in
(8,5) in
(10,10) out
exagon
(5,5) in
(5,8) in
(-10,5) out
(0,5) out
(10,5) in
(8,5) in
(10,10) out
</pre>
=={{header|C}}==
<
#include <stdlib.h>
#include <math.h>
Line 588 ⟶ 1,064:
return 0;
}</
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
class RayCasting {
static bool Intersects(int[] A, int[] B, double[] P) {
if (A[1] > B[1])
return Intersects(B, A, P);
if (P[1] == A[1] || P[1] == B[1])
P[1] += 0.0001;
if (P[1] > B[1] || P[1] < A[1] || P[0] >= Math.Max(A[0], B[0]))
return false;
if (P[0] < Math.Min(A[0], B[0]))
return true;
double red = (P[1] - A[1]) / (P[0] - A[0]);
double blue = (B[1] - A[1]) / (B[0] - A[0]);
return red >= blue;
}
static bool Contains(int[][] shape, double[] pnt) {
bool inside = false;
int len = shape.Length;
for (int i = 0; i < len; i++) {
if (Intersects(shape[i], shape[(i + 1) % len], pnt))
inside = !inside;
}
return inside;
}
public static void Main(string[] args) {
double[][] testPoints = new double[][] {
new double[] { 10, 10 }, new double[] { 10, 16 }, new double[] { -20, 10 },
new double[] { 0, 10 }, new double[] { 20, 10 }, new double[] { 16, 10 },
new double[] { 20, 20 }
};
foreach (int[][] shape in shapes) {
foreach (double[] pnt in testPoints)
Console.Write($"{Contains(shape, pnt),7} ");
Console.WriteLine();
}
}
readonly static int[][] square = new int[][] {
new int[] { 0, 0 }, new int[] { 20, 0 }, new int[] { 20, 20 }, new int[] { 0, 20 }
};
readonly static int[][] squareHole = new int[][] {
new int[] { 0, 0 }, new int[] { 20, 0 }, new int[] { 20, 20 }, new int[] { 0, 20 },
new int[] { 5, 5 }, new int[] { 15, 5 }, new int[] { 15, 15 }, new int[] { 5, 15 }
};
readonly static int[][] strange = new int[][] {
new int[] { 0, 0 }, new int[] { 5, 5 }, new int[] { 0, 20 }, new int[] { 5, 15 },
new int[] { 15, 15 }, new int[] { 20, 20 }, new int[] { 20, 0 }
};
readonly static int[][] hexagon = new int[][] {
new int[] { 6, 0 }, new int[] { 14, 0 }, new int[] { 20, 10 }, new int[] { 14, 20 },
new int[] { 6, 20 }, new int[] { 0, 10 }
};
readonly static int[][][] shapes = new int[][][] { square, squareHole, strange, hexagon };
}
</syntaxhighlight>
{{out}}
<pre>
True True False True False True False
False True False False False True False
True False False False False True False
True True False False False True False
</pre>
=={{header|C++}}==
{{works with|C++|11}}
{{trans|D}}
<
#include <cstdlib>
#include <iomanip>
Line 673 ⟶ 1,231:
return EXIT_SUCCESS;
}</
{{output}}
As D.
Line 679 ⟶ 1,237:
=={{header|CoffeeScript}}==
Takes a polygon as a list of points joining segments, and creates segments between them.
<
pointInPoly = (point,poly) ->
Line 706 ⟶ 1,264:
mAB = (b.y - a.y) / (b.x - a.x)
mAP = (p.y - a.y) / (p.x - a.x)
mAP > mAB</
=={{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))
Line 739 ⟶ 1,297:
((null m-blue) t)
((null m-red) nil)
(t (>= m-blue m-red)))))))))</
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)
Line 776 ⟶ 1,334:
do (format t "~&~w ~:[outside~;inside ~]."
test-point
(point-in-polygon test-point polygon)))))</
=={{header|D}}==
<
immutable struct Point { double x, y; }
Line 846 ⟶ 1,404:
writeln;
}
}</
{{out}}
<pre>Is point inside figure "Square"?
Line 886 ⟶ 1,444:
=={{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
Line 904 ⟶ 1,462:
[ dup first suffix [ rest-slice ] [ but-last-slice ] bi ] dip
[ ray ] curry 2map
f [ xor ] reduce ;</
Usage:
<
( scratchpad ) square { 0 0 } raycast .
t
Line 912 ⟶ 1,470:
f
( scratchpad ) square { 2 0 } raycast .
f</
=={{header|Fortran}}==
Line 919 ⟶ 1,477:
This module ''defines'' "polygons".
<
use Points_Module
implicit none
Line 953 ⟶ 1,511:
end subroutine free_polygon
end module Polygons</
The ray casting algorithm module:
<
use Polygons
implicit none
Line 1,032 ⟶ 1,590:
end function point_is_inside
end module Ray_Casting_Algo</
'''Testing'''
<
use Points_Module
use Ray_Casting_Algo
Line 1,074 ⟶ 1,632:
end do
end program Pointpoly</
=={{header|FreeBASIC}}==
Inpolygon by Winding number method
<syntaxhighlight lang
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
If p1(nextindex).y<=p2.y Then
If isleft2(send,p2)<=0 Then'=
wn=wn-1
End If
End If
End If
Next n
Return wn
End Function
Line 1,122 ⟶ 1,679:
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"
Print "(5,5) " ;Tab(12);
If inpolygon(square(),Type<Point>(5,5)) Then Print "in" Else Print "out"
Print "(5,8) " ;Tab(12);
If inpolygon(square(),Type<Point>(5,8)) Then Print "in" Else Print "out"
Print "(-10,5) " ;Tab(12);
If inpolygon(square(),Type<Point>(-10,5)) Then Print "in" Else Print "out"
Print "(0,5) " ;Tab(12);
If inpolygon(square(),Type<Point>(0,5)) Then Print "in" Else Print "out"
Print "(10,5) " ;Tab(12);
If inpolygon(square(),Type<Point>(10,5)) Then Print "in" Else Print "out"
Print "(8,5) " ;Tab(12);
If inpolygon(square(),Type<Point>(8,5)) Then Print "in" Else Print "out"
Print "(10,10) " ;Tab(12);
If inpolygon(square(),Type<Point>(10,10)) Then Print "in" Else Print "out"
Print
Case 2:Print "squared hole"
Print "(5,5) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(5,5)) And inpolygon(square(),Type<Point>(5,5)) Then Print "in" Else Print "out"
Print "(5,8) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(5,8)) And inpolygon(square(),Type<Point>(5,8))Then Print "in" Else Print "out"
Print "(-10,5) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(-10,5))And inpolygon(square(),Type<Point>(-10,5)) Then Print "in" Else Print "out"
Print "(0,5) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(0,5))And inpolygon(square(),Type<Point>(0,5)) Then Print "in" Else Print "out"
Print "(10,5) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(10,5))And inpolygon(square(),Type<Point>(10,5)) Then Print "in" Else Print "out"
Print "(8,5) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(8,5))And inpolygon(square(),Type<Point>(8,5)) Then Print "in" Else Print "out"
Print "(10,10) " ;Tab(12);
If Not inpolygon(hole(),Type<Point>(10,10))And inpolygon(square(),Type<Point>(10,10)) Then Print "in" Else Print "out"
Print
Case 3:Print "strange"
Print "(5,5) " ;Tab(12);
If inpolygon(strange(),Type<Point>(5,5)) Then Print "in" Else Print "out"
Print "(5,8) " ;Tab(12);
If inpolygon(strange(),Type<Point>(5,8)) Then Print "in" Else Print "out"
Print "(-10,5) " ;Tab(12);
If inpolygon(strange(),Type<Point>(-10,5)) Then Print "in" Else Print "out"
Print "(0,5) " ;Tab(12);
If inpolygon(strange(),Type<Point>(0,5)) Then Print "in" Else Print "out"
Print "(10,5) " ;Tab(12);
If inpolygon(strange(),Type<Point>(10,5)) Then Print "in" Else Print "out"
Print "(8,5) " ;Tab(12);
If inpolygon(strange(),Type<Point>(8,5)) Then Print "in" Else Print "out"
Print "(10,10) " ;Tab(12);
If inpolygon(strange(),Type<Point>(10,10)) Then Print "in" Else Print "out"
Print
Case 4:Print "exagon"
Print "(5,5) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(5,5)) Then Print "in" Else Print "out"
Print "(5,8) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(5,8)) Then Print "in" Else Print "out"
Print "(-10,5) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(-10,5)) Then Print "in" Else Print "out"
Print "(0,5) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(0,5)) Then Print "in" Else Print "out"
Print "(10,5) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(10,5)) Then Print "in" Else Print "out"
Print "(8,5) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(8,5)) Then Print "in" Else Print "out"
Print "(10,10) " ;Tab(12);
If inpolygon(exagon(),Type<Point>(10,10)) Then Print "in" Else Print "out"
Print
End Select
Next z
Sleep</syntaxhighlight>
Output:
<pre>squared
(5,5) in
(5,8) in
Line 1,229 ⟶ 1,785:
(10,5) in
(8,5) in
(10,10) out</pre>
=={{header|Go}}==
Line 1,236 ⟶ 1,791:
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 (
Line 1,337 ⟶ 1,892:
}
}
}</
{{out}}
<pre>
Line 1,384 ⟶ 1,939:
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 (
Line 1,459 ⟶ 2,014:
}
}
}</
{{out}}
<pre>
Line 1,480 ⟶ 2,035:
This solution is preferred over the two above.
<syntaxhighlight lang="text">package main
import "fmt"
Line 1,529 ⟶ 2,084:
}
}
}</
=={{header|Haskell}}==
<
type Point = (Rational, Rational)
Line 1,580 ⟶ 2,135:
(py /= by || ay < py)
((ax, ay), (bx, by)) = side
line = carrier side</
=={{header|J}}==
<
NB. bool=. points crossPnP polygon
crossPnP=: 4 : 0"2
Line 1,591 ⟶ 2,146:
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
Line 1,604 ⟶ 2,159:
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</
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
1 0 0 0 0 0 0 1 0 1 0</
=={{header|Java}}==
<
public class RayCasting {
Line 1,625 ⟶ 2,180:
P[1] += 0.0001;
if (P[1] > B[1] || P[1] < A[1] || P[0] >= max(A[0], B[0]))
return false;
Line 1,669 ⟶ 2,224:
final static int[][][] shapes = {square, squareHole, strange, hexagon};
}</
<pre>
false
true
true true false false false true false
</pre>
=={{header|Javascript}}==
<
/**
* @return {boolean} true if (lng, lat) is in bounds
Line 1,697 ⟶ 2,254:
function west(A, B, x, y) {
if (A.y <= B.y) {
if (y <= A.y || y > B.y ||
x >= A.x && x >= B.x) {
return false;
Line 1,736 ⟶ 2,293:
}
}
</syntaxhighlight>
=={{header|Julia}}==
{{trans|Python}}
'''Module''':
<syntaxhighlight lang="julia">module RayCastings
export Point
struct Point{T}
x::T
y::T
end
Base.show(io::IO, p::Point) = print(io, "($(p.x), $(p.y))")
const Edge = Tuple{Point{T}, Point{T}} where T
Base.show(io::IO, e::Edge) = print(io, "$(e[1]) ∘-∘ $(e[2])")
function rayintersectseg(p::Point{T}, edge::Edge{T}) where T
a, b = edge
if a.y > b.y
a, b = b, a
end
if p.y ∈ (a.y, b.y)
p = Point(p.x, p.y + eps(p.y))
end
rst = false
if (p.y > b.y || p.y < a.y) || (p.x > max(a.x, b.x))
return false
end
if p.x < min(a.x, b.x)
rst = true
else
mred = (b.y - a.y) / (b.x - a.x)
mblu = (p.y - a.y) / (p.x - a.x)
rst = mblu ≥ mred
end
return rst
end
isinside(poly::Vector{Tuple{Point{T}, Point{T}}}, p::Point{T}) where T =
isodd(count(edge -> rayintersectseg(p, edge), poly))
connect(a::Point{T}, b::Point{T}...) where T =
[(a, b) for (a, b) in zip(vcat(a, b...), vcat(b..., a))]
end # module RayCastings</syntaxhighlight>
'''Main''':
<syntaxhighlight lang="julia">using Printf
let A = Point(0.0, 0.0),
B = Point(0.0, 10.0),
C = Point(10.0, 10.0),
D = Point(10.0, 0.0),
E = Point(2.5, 2.5),
F = Point(2.5, 7.5),
G = Point(7.5, 7.5),
H = Point(7.5, 2.5),
I = Point(3.0, 0.0),
J = Point(7.0, 0.0),
K = Point(10.0, 5.0),
L = Point(7.0, 10.0),
M = Point(3.0, 10.0),
N = Point(0.0, 5.0),
testpts = (Point(5.0, 5.0), Point(5.0, 8.0), Point(-10.0, 5.0), Point(0.0, 5.0),
Point(10.0, 5.0), Point(8.0, 5.0), Point(10.0, 10.0))
square = RayCastings.connect(A, B, C, D)
square_withhole = vcat(square, RayCastings.connect(E, F, G, H))
strange = RayCastings.connect(A, E, B, F, G, C, D, E)
exagon = RayCastings.connect(I, J, K, L, M, N)
println("\n# TESTING WHETHER POINTS ARE WITHIN POLYGONS")
for poly in (square, square_withhole, strange, exagon)
println("\nEdges: \n - ", join(poly, "\n - "))
println("Inside/outside:")
for p in testpts
@printf(" - %-12s is %s\n", p, RayCastings.isinside(poly, p) ? "inside" : "outside")
end
end
end</syntaxhighlight>
{{out}}
<pre># TESTING WHETHER POINTS ARE WITHIN POLYGONS
Edges:
- (0.0, 0.0) ∘-∘ (0.0, 10.0)
- (0.0, 10.0) ∘-∘ (10.0, 10.0)
- (10.0, 10.0) ∘-∘ (10.0, 0.0)
- (10.0, 0.0) ∘-∘ (0.0, 0.0)
Inside/outside:
- (5.0, 5.0) is inside
- (5.0, 8.0) is inside
- (-10.0, 5.0) is outside
- (0.0, 5.0) is outside
- (10.0, 5.0) is inside
- (8.0, 5.0) is inside
- (10.0, 10.0) is outside
Edges:
- (0.0, 0.0) ∘-∘ (0.0, 10.0)
- (0.0, 10.0) ∘-∘ (10.0, 10.0)
- (10.0, 10.0) ∘-∘ (10.0, 0.0)
- (10.0, 0.0) ∘-∘ (0.0, 0.0)
- (2.5, 2.5) ∘-∘ (2.5, 7.5)
- (2.5, 7.5) ∘-∘ (7.5, 7.5)
- (7.5, 7.5) ∘-∘ (7.5, 2.5)
- (7.5, 2.5) ∘-∘ (2.5, 2.5)
Inside/outside:
- (5.0, 5.0) is outside
- (5.0, 8.0) is inside
- (-10.0, 5.0) is outside
- (0.0, 5.0) is outside
- (10.0, 5.0) is inside
- (8.0, 5.0) is inside
- (10.0, 10.0) is outside
Edges:
- (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.0) ∘-∘ (2.5, 2.5)
- (2.5, 2.5) ∘-∘ (0.0, 0.0)
Inside/outside:
- (5.0, 5.0) is inside
- (5.0, 8.0) is outside
- (-10.0, 5.0) is outside
- (0.0, 5.0) is outside
- (10.0, 5.0) is inside
- (8.0, 5.0) is inside
- (10.0, 10.0) is outside
Edges:
- (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)
Inside/outside:
- (5.0, 5.0) is inside
- (5.0, 8.0) is inside
- (-10.0, 5.0) is outside
- (0.0, 5.0) is outside
- (10.0, 5.0) is inside
- (8.0, 5.0) is inside
- (10.0, 10.0) is outside</pre>
=={{header|Kotlin}}==
{{trans|D}}
<syntaxhighlight lang="scala">import java.lang.Double.MAX_VALUE
import java.lang.Double.MIN_VALUE
import java.lang.
data class Point(val x: Double, val y: Double)
data class Edge(val s: Point, val e: Point) {
s.y > e.y -> Edge(e, s).invoke(p)
p.y == s.y || p.y == e.y -> invoke(Point(p.x, p.y + epsilon))
p.y > e.y || p.y < s.y || p.x > Math.max(s.x, e.x) -> false
p.x < Math.min(s.x, e.x) -> true
else -> {
val blue = if (abs(s.x - p.x) > MIN_VALUE) (p.y - s.y) / (p.x - s.x) else MAX_VALUE
Line 1,763 ⟶ 2,473:
}
}
object Ray_casting {
println("points: " + points)
figures.forEach { f ->
println("figure: " + f.name)
f.edges.forEach { println(" " + it) }
println("result: " + (points.map {
}
}
}</syntaxhighlight>
<syntaxhighlight 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 1,797 ⟶ 2,503:
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)]
Line 1,839 ⟶ 2,545:
Displays interactively on-screen.
<
Global sw, sh, verts
Line 1,914 ⟶ 2,620:
Function rand(loNum,hiNum)
rand = Int(Rnd(0)*(hiNum-loNum+1)+loNum)
End Function </
=={{header|Lua}}==
<syntaxhighlight lang="lua">function Point(x,y) return {x=x, y=y} end
function Polygon(name, points)
local function contains(self, p)
local odd, eps = false, 1e-9
local function rayseg(p, a, b)
if a.y > b.y then a, b = b, a end
if p.y == a.y or p.y == b.y then p.y = p.y + eps end
if p.y < a.y or p.y > b.y or p.x > math.max(a.x, b.x) then return false end
if p.x < math.min(a.x, b.x) then return true end
local red = a.x == b.x and math.huge or (b.y-a.y)/(b.x-a.x)
local blu = a.x == p.x and math.huge or (p.y-a.y)/(p.x-a.x)
return blu >= red
end
for i, a in ipairs(self.points) do
local b = self.points[i%#self.points+1]
if rayseg(p, a, b) then odd = not odd end
end
return odd
end
return {name=name, points=points, contains=contains}
end
polygons = {
Polygon("square", { Point(0,0), Point(10,0), Point(10,10), Point(0,10) }),
Polygon("squarehole", { Point(0,0), Point(10,0), Point(10,10), Point(0,10), Point(2.5,2.5), Point(7.5,2.5), Point(7.5,7.5), Point(2.5,7.5) }),
Polygon("strange", { Point(0,0), Point(2.5,2.5), Point(0, 10), Point(2.5,7.5), Point(7.5,7.5), Point(10,10), Point(10,0), Point(2.5,2.5) }),
Polygon("hexagon", { Point(3,0), Point(7,0), Point(10,5), Point(7,10), Point(3,10), Point(0,5) })
}
points = { Point(5,5), Point(5,8), Point(-10,5), Point(0,5), Point(10,5), Point(8,5), Point(10,10) }
for _,poly in ipairs(polygons) do
print("Does '"..poly.name.."' contain the point..")
for _,pt in ipairs(points) do
print(string.format(" (%3.f, %2.f)? %s", pt.x, pt.y, tostring(poly:contains(pt))))
end
print()
end</syntaxhighlight>
{{out}}
<pre>Does 'square' contain..
( 5, 5)? true
( 5, 8)? true
(-10, 5)? false
( 0, 5)? false
( 10, 5)? true
( 8, 5)? true
( 10, 10)? false
Does 'squarehole' contain..
( 5, 5)? false
( 5, 8)? true
(-10, 5)? false
( 0, 5)? false
( 10, 5)? true
( 8, 5)? true
( 10, 10)? false
Does 'strange' contain..
( 5, 5)? true
( 5, 8)? false
(-10, 5)? false
( 0, 5)? false
( 10, 5)? true
( 8, 5)? true
( 10, 10)? false
Does 'hexagon' contain..
( 5, 5)? true
( 5, 8)? true
(-10, 5)? false
( 0, 5)? false
( 10, 5)? true
( 8, 5)? true
( 10, 10)? false</pre>
=={{header|Nim}}==
{{trans|D}}
<syntaxhighlight lang="nim">import fenv, sequtils, strformat
type
Point = tuple[x, y: float]
Edge = tuple[a, b: Point]
Figure = tuple[name: string; edges: seq[Edge]]
func contains(poly: Figure; p: Point): bool =
func raySegI(p: Point; edge: Edge): bool =
const Epsilon = 0.00001
if edge.a.y > edge.b.y:
# Swap "a" and "b".
return p.raySegI((edge.b, edge.a))
if p.y == edge.a.y or p.y == edge.b.y:
# p.y += Epsilon.
return (p.x, p.y + Epsilon).raySegI(edge)
if p.y > edge.b.y or p.y < edge.a.y or p.x > max(edge.a.x, edge.b.x):
return false
if p.x < min(edge.a.x, edge.b.x):
return true
let blue = if abs(edge.a.x - p.x) > minimumPositiveValue(float):
(p.y - edge.a.y) / (p.x - edge.a.x)
else:
maximumPositiveValue(float)
let red = if abs(edge.a.x - edge.b.x) > minimumPositiveValue(float):
(edge.b.y - edge.a.y) / (edge.b.x - edge.a.x)
else:
maximumPositiveValue(float)
result = blue >= red
result = (poly.edges.filterIt(p.raySegI(it)).len and 1) != 0
when isMainModule:
const
Polys: array[4, Figure] =
[("Square",
@[(( 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))]),
("Square hole",
@[(( 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))]),
("Strange",
@[(( 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.0), ( 2.5, 2.5))]),
("Hexagon",
@[(( 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))])
]
TestPoints: array[7, Point] =
[(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)]
for poly in Polys:
echo &"Is point inside figure {poly.name}?"
for p in TestPoints:
echo &" ({p.x:3},{p.y:3}): {poly.contains(p)}"</syntaxhighlight>
{{out}}
<pre>Is point inside figure Square?
( 5, 5): true
( 5, 8): true
(-10, 5): false
( 0, 5): false
( 10, 5): true
( 8, 5): true
( 10, 10): false
Is point inside figure Square hole?
( 5, 5): false
( 5, 8): true
(-10, 5): false
( 0, 5): false
( 10, 5): true
( 8, 5): true
( 10, 10): false
Is point inside figure Strange?
( 5, 5): true
( 5, 8): false
(-10, 5): false
( 0, 5): false
( 10, 5): true
( 8, 5): true
( 10, 10): false
Is point inside figure Hexagon?
( 5, 5): true
( 5, 8): true
(-10, 5): false
( 0, 5): false
( 10, 5): true
( 8, 5): true
( 10, 10): false</pre>
=={{header|OCaml}}==
{{Trans|C}}
<
type polygon = {
Line 2,014 ⟶ 2,898:
print_newline()
) test_points;
;;</
=={{header|Perl}}==
<
use List::Util qw(max min);
Line 2,054 ⟶ 2,938:
return ($m_blue >= $m_red) ? 1 : 0;
}</
Testing:
<
sub point
{
Line 2,095 ⟶ 2,979:
( point_in_polygon($tp, $rp) ? "INSIDE" : "OUTSIDE" ) . "\n";
}
}</
=={{header|Phix}}==
<!--<syntaxhighlight lang="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>
<span style="color: #008080;">function</span> <span style="color: #000000;">rayIntersectsSegment</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">point</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">segment</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">segment</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">point</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">m_red</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m_blue</span>
<span style="color: #000080;font-style:italic;">-- ensure {aX,aY} is the segment end-point with the smallest y coordinate</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">aY</span><span style="color: #0000FF;">></span><span style="color: #000000;">bY</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;">=</span><span style="color: #000000;">aY</span> <span style="color: #008080;">or</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;">=</span><span style="color: #000000;">bY</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">--
-- Consider a ray passing through the top or left corner of a diamond:
-- /
-- --- or -
-- ^ \
-- In both cases it touches both edges, but ends up outside in the
-- top case, whereas it ends up inside in the left case. Just move
-- the y co-ordinate down a smidge and it'll work properly, by
-- missing one line in the left/right cases and hitting both/none
-- in the top/bottom cases.
--</span>
<span style="color: #000000;">pY</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">0.000001</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;"><</span><span style="color: #000000;">aY</span> <span style="color: #008080;">or</span> <span style="color: #000000;">pY</span><span style="color: #0000FF;">></span><span style="color: #000000;">bY</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pX</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pX</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">aX</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">bX</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m_red</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">bY</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">)/(</span><span style="color: #000000;">bX</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">m_red</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inf</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">aX</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">pX</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m_blue</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">pY</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aY</span><span style="color: #0000FF;">)/(</span><span style="color: #000000;">pX</span><span style="color: #0000FF;">-</span><span style="color: #000000;">aX</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">m_blue</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inf</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">m_blue</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">m_red</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">point</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rayIntersectsSegment</span><span style="color: #0000FF;">(</span><span style="color: #000000;">point</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">instr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">flag</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"in"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"out"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">flag</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">flag</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">expected</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">"*** ERROR ***"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">instar</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">flag</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008000;">"* "</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">flag</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">test_points</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">--constant NAME = 1, POLY = 2, EXPECTED = 3</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">test_polygons</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"square"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"square hole"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"strange"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"exagon"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}}</span>
<span style="color: #0000FF;">}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tp</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n%12s:"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test_points</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %s, %-4s"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">),</span><span style="color: #000000;">instr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">),</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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\n\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<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;">" "</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">poly</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_polygons</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<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: #000000;">instar</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">({</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10.5</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">},</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,325 ⟶ 3,106:
********** ********** **** ******
********** ********** * ****
</pre>
=={{header|PHP}}==
<syntaxhighlight lang="php">
<?php
function contains($bounds, $lat, $lng)
{
$count = 0;
$bounds_count = count($bounds);
for ($b = 0; $b < $bounds_count; $b++) {
$vertex1 = $bounds[$b];
$vertex2 = $bounds[($b + 1) % $bounds_count];
if (west($vertex1, $vertex2, $lng, $lat))
$count++;
}
return $count % 2;
}
function west($A, $B, $x, $y)
{
if ($A['y'] <= $B['y']) {
if ($y <= $A['y'] || $y > $B['y'] ||
$x >= $A['x'] && $x >= $B['x']) {
return false;
}
if ($x < $A['x'] && $x < $B['x']) {
return true;
}
if ($x == $A['x']) {
if ($y == $A['y']) {
$result1 = NAN;
} else {
$result1 = INF;
}
} else {
$result1 = ($y - $A['y']) / ($x - $A['x']);
}
if ($B['x'] == $A['x']) {
if ($B['y'] == $A['y']) {
$result2 = NAN;
} else {
$result2 = INF;
}
} else {
$result2 = ($B['y'] - $A['y']) / ($B['x'] - $A['x']);
}
return $result1 > $result2;
}
return west($B, $A, $x, $y);
}
$square = [
'name' => 'square',
'bounds' => [['x' => 0, 'y' => 0], ['x' => 20, 'y' => 0], ['x' => 20, 'y' => 20], ['x' => 0, 'y' => 20]]
];
$squareHole = [
'name' => 'squareHole',
'bounds' => [['x' => 0, 'y' => 0], ['x' => 20, 'y' => 0], ['x' => 20, 'y' => 20], ['x' => 0, 'y' => 20], ['x' => 5, 'y' => 5], ['x' => 15, 'y' => 5], ['x' => 15, 'y' => 15], ['x' => 5, 'y' => 15]]
];
$strange = [
'name' => 'strange',
'bounds' => [['x' => 0, 'y' => 0], ['x' => 5, 'y' => 5], ['x' => 0, 'y' => 20], ['x' => 5, 'y' => 15], ['x' => 15, 'y' => 15], ['x' => 20, 'y' => 20], ['x' => 20, 'y' => 0]]
];
$hexagon = [
'name' => 'hexagon',
'bounds' => [['x' => 6, 'y' => 0], ['x' => 14, 'y' => 0], ['x' => 20, 'y' => 10], ['x' => 14, 'y' => 20], ['x' => 6, 'y' => 20], ['x' => 0, 'y' => 10]]
];
$shapes = [$square, $squareHole, $strange, $hexagon];
$testPoints = [
['lng' => 10, 'lat' => 10],
['lng' => 10, 'lat' => 16],
['lng' => -20, 'lat' => 10],
['lng' => 0, 'lat' => 10],
['lng' => 20, 'lat' => 10],
['lng' => 16, 'lat' => 10],
['lng' => 20, 'lat' => 20]
];
for ($s = 0; $s < count($shapes); $s++) {
$shape = $shapes[$s];
for ($tp = 0; $tp < count($testPoints); $tp++) {
$testPoint = $testPoints[$tp];
echo json_encode($testPoint) . "\tin " . $shape['name'] . "\t" . contains($shape['bounds'], $testPoint['lat'], $testPoint['lng']) . PHP_EOL;
}
}</syntaxhighlight>
{{out}}<pre>{"lng":10,"lat":10} in square 1
{"lng":10,"lat":16} in square 1
{"lng":-20,"lat":10} in square 0
{"lng":0,"lat":10} in square 1
{"lng":20,"lat":10} in square 0
{"lng":16,"lat":10} in square 1
{"lng":20,"lat":20} in square 0
{"lng":10,"lat":10} in squareHole 0
{"lng":10,"lat":16} in squareHole 1
{"lng":-20,"lat":10} in squareHole 0
{"lng":0,"lat":10} in squareHole 0
{"lng":20,"lat":10} in squareHole 0
{"lng":16,"lat":10} in squareHole 1
{"lng":20,"lat":20} in squareHole 0
{"lng":10,"lat":10} in strange 1
{"lng":10,"lat":16} in strange 0
{"lng":-20,"lat":10} in strange 0
{"lng":0,"lat":10} in strange 0
{"lng":20,"lat":10} in strange 0
{"lng":16,"lat":10} in strange 1
{"lng":20,"lat":20} in strange 0
{"lng":10,"lat":10} in hexagon 1
{"lng":10,"lat":16} in hexagon 1
{"lng":-20,"lat":10} in hexagon 0
{"lng":0,"lat":10} in hexagon 1
{"lng":20,"lat":10} in hexagon 0
{"lng":16,"lat":10} in hexagon 1
{"lng":20,"lat":20} in hexagon 0
</pre>
=={{header|PicoLisp}}==
<
(de intersects (Px Py Ax Ay Bx By)
Line 2,354 ⟶ 3,253:
(when (apply intersects Edge (car Pt) (cdr Pt))
(onOff Res) ) )
Res ) )</
Test data:
<pre style="height:20em;overflow:scroll">(de Square
Line 2,451 ⟶ 3,350:
=={{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
Line 2,533 ⟶ 3,432:
FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow</
=={{header|Python}}==
<
from pprint import pprint as pp
import sys
Line 2,637 ⟶ 3,536:
for p in testpoints[3:6]))
print (' ', '\t'.join("%s: %s" % (p, ispointinside(p, poly))
for p in testpoints[6:]))</
'''Sample output'''
Line 2,693 ⟶ 3,592:
'''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),
Line 2,719 ⟶ 3,618:
print ' ', ',\n '.join(str(e) for e in p.edges) + '\n )),'
print ' ]'
_convert_fortran_shapes()</
=={{header|R}}==
<
count <- 0
for(side in polygon) {
Line 2,765 ⟶ 3,664:
}
}
}</
<
point <- function(x,y) list(x=x, y=y)
Line 2,779 ⟶ 3,678:
}
pol
}</
<
pts <- list(point(0,0), point(10,0), point(10,10), point(0,10),
Line 2,806 ⟶ 3,705:
p$x, p$y, point_in_polygon(polygons[[polysi]], p), names(polygons[polysi])))
}
}</
=={{header|Racket}}==
Straightforward implementation of pseudocode
<syntaxhighlight lang="scheme">
#lang racket
(module pip racket
(require racket/contract)
(provide point)
(provide seg)
Line 2,824 ⟶ 3,723:
(struct point (x y) #:transparent)
(struct seg (Ax Ay Bx By) #:transparent)
(define ε 0.000001)
(define (neq? x y) (not (eq? x y)))
Line 2,835 ⟶ 3,734:
(eq? Pyo By))
ε 0))])
(
(define Ay2 (if (< Ay By) Ay By))
(define Bx2 (if (< Ay By) Bx Ax))
(define By2 (if (< Ay By) By Ay))
(cond [(or (> Py (max Ay By)) (< Py (min Ay By))) #f]
[(> Px (max Ax Bx)) #f]
[
[
(if (>= blue red) #t #f))])])))
(define (point-in-polygon? point polygon)
Line 2,886 ⟶ 3,791:
(test-figure square "square")
(test-figure exagon "exagon")
</syntaxhighlight>
{{out}}
Line 2,908 ⟶ 3,813:
testing (point 10.0 10.0): #f
</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>constant ε = 0.0001;
sub ray-hits-seg([\Px,\Py], [[\Ax,\Ay], [\Bx,\By]] --> Bool) {
Py += ε if Py == Ay | By;
if Py < Ay or Py > By or Px > (Ax max Bx) {
False;
}
elsif Px < (Ax min Bx) {
True;
}
else {
my \red = Ax == Bx ?? Inf !! (By - Ay) / (Bx - Ax);
my \blue = Ax == Px ?? Inf !! (Py - Ay) / (Px - Ax);
blue >= red;
}
}
sub point-in-poly(@point, @polygon --> Bool) {
so 2 R% [+] gather for @polygon -> @side {
take ray-hits-seg @point, @side.sort(*.[1]);
}
}
my %poly =
squared =>
[[[ 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]]],
squaredhole =>
[[[ 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]]],
strange =>
[[[ 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.0], [ 2.5, 2.5]],
[[ 2.5, 2.5], [ 0.0, 0.0]]], # conjecturally close polygon
exagon =>
[[[ 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]]];
my @test-points =
[ 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];
for <squared squaredhole strange exagon> -> $polywanna {
say "$polywanna";
my @poly = %poly{$polywanna}[];
for @test-points -> @point {
say "\t(@point.fmt('%.1f',','))\t{ point-in-poly(@point, @poly) ?? 'IN' !! 'OUT' }";
}
}</syntaxhighlight>
{{out}}
<pre>squared
(5.0,5.0) IN
(5.0,8.0) IN
(-10.0,5.0) OUT
(0.0,5.0) OUT
(10.0,5.0) IN
(8.0,5.0) IN
(10.0,10.0) OUT
squaredhole
(5.0,5.0) OUT
(5.0,8.0) IN
(-10.0,5.0) OUT
(0.0,5.0) OUT
(10.0,5.0) IN
(8.0,5.0) IN
(10.0,10.0) OUT
strange
(5.0,5.0) IN
(5.0,8.0) OUT
(-10.0,5.0) OUT
(0.0,5.0) OUT
(10.0,5.0) IN
(8.0,5.0) IN
(10.0,10.0) OUT
exagon
(5.0,5.0) IN
(5.0,8.0) IN
(-10.0,5.0) OUT
(0.0,5.0) OUT
(10.0,5.0) IN
(8.0,5.0) IN
(10.0,10.0) OUT</pre>
=={{header|REXX}}==
Line 2,913 ⟶ 3,926:
Code was added to facilitate easier specification of polygon sides by just specifying their ''vertices'' instead of specifying their ''line segments''.
<
call points 5 5, 5 8, -10 5, 0 5, 10 5, 8 5, 10 10
A= 2.5; B= 7.5
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'
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
in$out: procedure expose point. poly.;
return # // 2 /*ODD is inside. EVEN is outside.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
intersect: procedure expose point. poly.; parse arg ?,s; sp= s + 1
epsilon= '1e' || (-digits() %
Px= point.?.x;
Py= point.?.y; Ay=
if Ay>By then parse value Ax Ay Bx By with Bx By Ax Ay
if Py=Ay | Py=By then Py= Py + epsilon
if Py<Ay | Py>By | Px>max(Ax, Bx) then return 0
if
if Ax\=Bx then
else
if Ax\=Px then
else return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
points: wx= 0; wy= 0;
wx= max(wx, length(xx) );
wy= max(wy, length(yy) );
end /*j*/
call value point.0, j-1 /*define the number of points. */
return /* [↑] adjust J (for DO loop)*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
poly: @= 'POLY.';
n= 0
do j=1 for arg(); n= n + 1;
call value @ || n'.X', xx ;
if n//2 then iterate; n= n + 1 /*Inside? Then skip this point.*/
call value @ || n'.X', xx ;
end /*j*/
n= n + 1 /*POLY.0 is # segments(sides).*/
call value @ || n'.X', Fx; call value @ || n".Y", Fy;
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
test: say; do k=1 for point.0;
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*/
return /* [↑] format the output nicely*/</syntaxhighlight>
{{out|output|text= when using the default inputs:}}
<pre>
[square] point: 5, 5 is inside
Line 2,997 ⟶ 4,009:
[hexagon] point: 8, 5 is inside
[hexagon] point: 10, 10 is outside
</pre>
=={{header|Rust}}==
{{trans|Python}}
<syntaxhighlight lang="rust">use std::f64;
const _EPS: f64 = 0.00001;
const _MIN: f64 = f64::MIN_POSITIVE;
const _MAX: f64 = f64::MAX;
#[derive(Clone)]
struct Point {
x: f64,
y: f64,
}
#[derive(Clone)]
struct Edge {
pt1: Point,
pt2: Point,
}
impl Edge {
fn new(pt1: (f64, f64), pt2: (f64, f64)) -> Edge {
Edge {
pt1: Point { x: pt1.0, y: pt1.1 },
pt2: Point { x: pt2.0, y: pt2.1 },
}
}
}
struct Polygon {
edges: Vec<Edge>, // Polygon has to be created with counter-clockwise coordinates
}
fn pt_in_polygon(pt: &Point, poly: &Polygon) -> bool {
let count = poly.edges
.iter()
.filter(|edge| ray_intersect_seg(pt, edge))
.count();
count % 2 == 1
}
fn ray_intersect_seg(p: &Point, edge: &Edge) -> bool {
let mut pt = p.clone();
let (mut a, mut b): (&Point, &Point) = (&edge.pt1, &edge.pt2);
if a.y > b.y {
std::mem::swap(&mut a, &mut b);
}
if pt.y == a.y || pt.y == b.y {
pt.y += _EPS;
}
if (pt.y > b.y || pt.y < a.y) || pt.x > a.x.max(b.x) {
false
} else if pt.x < a.x.min(b.x) {
true
} else {
let m_red = if (a.x - b.x).abs() > _MIN {
(b.y - a.y) / (b.x - a.x)
} else {
_MAX
};
let m_blue = if (a.x - pt.x).abs() > _MIN {
(pt.y - a.y) / (pt.x - a.x)
} else {
_MAX
};
m_blue >= m_red
}
}
fn main() {
let p = |x, y| Point { x, y };
let testpoints = [p(5.0, 5.0), p(5.0, 8.0), p(-10.0, 5.0), p(0.0, 5.0), p(10.0, 5.0), p(8.0, 5.0), p(10.0, 10.0)];
let poly_square = Polygon {
edges: vec![
Edge::new((0.0, 0.0), (10.0, 0.0)),
Edge::new((10.0, 0.0), (10.0, 10.0)),
Edge::new((10.0, 10.0), (0.0, 10.0)),
Edge::new((0.0, 10.0), (0.0, 0.0)),
],
};
let poly_square_hole = Polygon {
edges: vec![
Edge::new((0.0, 0.0), (10.0, 0.0)),
Edge::new((10.0, 0.0), (10.0, 10.0)),
Edge::new((10.0, 10.0), (0.0, 10.0)),
Edge::new((0.0, 10.0), (0.0, 0.0)),
Edge::new((2.5, 2.5), (7.5, 2.5)),
Edge::new((7.5, 2.5), (7.5, 7.5)),
Edge::new((7.5, 7.5), (2.5, 7.5)),
Edge::new((2.5, 7.5), (2.5, 2.5)),
],
};
let poly_strange = Polygon {
edges: vec![
Edge::new((0.0, 0.0), (2.5, 2.5)),
Edge::new((2.5, 2.5), (0.0, 10.0)),
Edge::new((0.0, 10.0), (2.5, 7.5)),
Edge::new((2.5, 7.5), (7.5, 7.5)),
Edge::new((7.5, 7.5), (10.0, 10.0)),
Edge::new((10.0, 10.0), (10.0, 0.0)),
Edge::new((10.0, 0.0), (2.5, 2.5)),
],
};
let poly_hexagon = Polygon {
edges: vec![
Edge::new((3.0, 0.0), (7.0, 0.0)),
Edge::new((7.0, 0.0), (10.0, 5.0)),
Edge::new((10.0, 5.0), (7.0, 10.0)),
Edge::new((7.0, 10.0), (3.0, 10.0)),
Edge::new((3.0, 10.0), (0.0, 5.0)),
Edge::new((0.0, 5.0), (3.0, 0.0)),
],
};
print!("\nSquare :");
for pt in &testpoints {
print!(" {:?}", pt_in_polygon(pt, &poly_square));
}
print!("\nSquare with hole:");
for pt in &testpoints {
print!(" {:?}", pt_in_polygon(pt, &poly_square_hole));
}
print!("\nStrange polygon :");
for pt in &testpoints {
print!(" {:?}", pt_in_polygon(pt, &poly_strange));
}
print!("\nHexagon :");
for pt in &testpoints {
print!(" {:?}", pt_in_polygon(pt, &poly_hexagon));
}
println!();
}</syntaxhighlight>
{{out}}
<pre>
Square : true true false false true true false
Square with hole: false true false false true true false
Strange polygon : true false false false true true false
Hexagon : true true false false true true false
</pre>
=={{header|Scala}}==
{{trans|D}}
<
case class Edge(_1: (Double, Double), _2: (Double, Double)) {
Line 3,047 ⟶ 4,200:
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))
Line 3,067 ⟶ 4,220:
{{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|
Line 3,143 ⟶ 4,296:
^ ( cnt \\ 2 = 0 ) not
]
].</
'''Testing'''
<
points := {
Line 3,187 ⟶ 4,340:
].
' ' displayNl.
]</
=={{header|Tcl}}==
<
proc point_in_polygon {point polygon} {
Line 3,247 ⟶ 4,400:
} {
puts "$point in $poly = [point_in_polygon $point $poly]"
}</
=={{header|Ursala}}==
Line 3,254 ⟶ 4,407:
value if it's outside, using the algorithm described above.
For points on the boundary the result is unspecified.
<
in =
Line 3,260 ⟶ 4,413:
@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&-</
This test program tries it on a couple of examples.
<
examples =
Line 3,268 ⟶ 4,421:
in* <
((0.5,0.6),<(0.,0.),(1.,2.),(1.,0.)>),
((0.5,0.6),<(0.,0.),(1.,1.),(1.,0.)>)></
output:
<pre><true,false></pre>
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<syntaxhighlight lang="vbnet">Imports System.Math
Module RayCasting
Private square As Integer()() = {New Integer() {0, 0}, New Integer() {20, 0}, New Integer() {20, 20}, New Integer() {0, 20}}
Private squareHole As Integer()() = {New Integer() {0, 0}, New Integer() {20, 0}, New Integer() {20, 20}, New Integer() {0, 20}, New Integer() {5, 5}, New Integer() {15, 5}, New Integer() {15, 15}, New Integer() {5, 15}}
Private strange As Integer()() = {New Integer() {0, 0}, New Integer() {5, 5}, New Integer() {0, 20}, New Integer() {5, 15}, New Integer() {15, 15}, New Integer() {20, 20}, New Integer() {20, 0}}
Private hexagon As Integer()() = {New Integer() {6, 0}, New Integer() {14, 0}, New Integer() {20, 10}, New Integer() {14, 20}, New Integer() {6, 20}, New Integer() {0, 10}}
Private shapes As Integer()()() = {square, squareHole, strange, hexagon}
Public Sub Main()
Dim testPoints As Double()() = {New Double() {10, 10}, New Double() {10, 16}, New Double() {-20, 10}, New Double() {0, 10}, New Double() {20, 10}, New Double() {16, 10}, New Double() {20, 20}}
For Each shape As Integer()() In shapes
For Each point As Double() In testPoints
Console.Write(String.Format("{0} ", Contains(shape, point).ToString.PadLeft(7)))
Next
Console.WriteLine()
Next
End Sub
Private Function Contains(shape As Integer()(), point As Double()) As Boolean
Dim inside As Boolean = False
Dim length As Integer = shape.Length
For i As Integer = 0 To length - 1
If Intersects(shape(i), shape((i + 1) Mod length), point) Then
inside = Not inside
End If
Next
Return inside
End Function
Private Function Intersects(a As Integer(), b As Integer(), p As Double()) As Boolean
If a(1) > b(1) Then Return Intersects(b, a, p)
If p(1) = a(1) Or p(1) = b(1) Then p(1) += 0.0001
If p(1) > b(1) Or p(1) < a(1) Or p(0) >= Max(a(0), b(0)) Then Return False
If p(0) < Min(a(0), b(0)) Then Return True
Dim red As Double = (p(1) - a(1)) / (p(0) - a(0))
Dim blue As Double = (b(1) - a(1)) / (b(0) - a(0))
Return red >= blue
End Function
End Module</syntaxhighlight>
{{out}}
<pre>
True True False True False True False
False True False False False True False
True False False False False True False
True True False False False True False
</pre>
=={{header|Wren}}==
{{trans|Java}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
class RayCasting {
static intersects(a, b, p) {
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
if (p[1] > b[1] || p[1] < a[1] || p[0] >= a[0].max(b[0])) return false
if (p[0] < a[0].min(b[0])) return true
var red = (p[1] - a[1]) / (p[0] - a[0])
var blue = (b[1] - a[1]) / (b[0] - a[0])
return red >= blue
}
static contains(shape, pnt) {
var inside = false
var len = shape.count
for (i in 0...len) {
if (intersects(shape[i], shape[(i + 1) % len], pnt)) inside = !inside
}
return inside
}
static square { [[0, 0], [20, 0], [20, 20], [0, 20]] }
static squareHole { [[0, 0], [20, 0], [20, 20], [0, 20], [5, 5], [15, 5], [15, 15], [5, 15]] }
static strange { [[0, 0], [5, 5], [0, 20], [5, 15], [15, 15], [20, 20], [20, 0]] }
static hexagon { [[6, 0], [14, 0], [20, 10], [14, 20], [6, 20], [0, 10]] }
static shapes { [square, squareHole, strange, hexagon] }
}
var testPoints = [[10, 10], [10, 16], [-20, 10], [0, 10], [20, 10], [16, 10], [20, 20]]
for (shape in RayCasting.shapes) {
for (pnt in testPoints) Fmt.write("$7s ", RayCasting.contains(shape, pnt))
System.print()
}</syntaxhighlight>
{{out}}
<pre>
true true false true false true false
false true false false false true false
true false false false false true false
true true false false false true false
</pre>
=={{header|zkl}}==
{{trans|
<
fcn rayHitsSeg([(Px,Py)],[(Ax,Ay)],[(Bx,By)]){ // --> Bool
Line 3,290 ⟶ 4,550:
})
.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)),
Line 3,340 ⟶ 4,600:
pointInPoly(testPoint,polywanna) and "IN" or "OUT");
}
}</
{{out}}
<pre>
|