Ray-casting algorithm: Difference between revisions
→{{header|Go}}: Add PNPoly solution, add some clarifications to existing solutions.
m (→{{header|REXX}}: expanded the expression of the five points.) |
(→{{header|Go}}: Add PNPoly solution, add some clarifications to existing solutions.) |
||
Line 1,229:
=={{header|Go}}==
'''Segment solution, task algorithm'''
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.)
<lang go>package main
import (
"math"▼
"fmt"
▲ "math"
)
Line 1,316 ⟶ 1,319:
}
var tpt = []xy{
var tpt = []xy{{5, 5}, {5, 8}, {-10, 5}, {0, 5}, {10, 5}, {8, 5}, {10, 10}}▼
// test points common in other solutions on this page
// test points that show the problem with "strange"
{1, 2}, {2, 1},
}
func main() {
Line 1,336 ⟶ 1,344:
{8 5} true
{10 10} false
{1 2} true
{2 1} true
square hole:
{5 5} false
Line 1,344 ⟶ 1,354:
{8 5} true
{10 10} false
{1 2} true
{2 1} true
strange:
{5 5} true
Line 1,352 ⟶ 1,364:
{8 5} true
{10 10} false
{1 2} true
{2 1} false
exagon:
{5 5} true
Line 1,360 ⟶ 1,374:
{8 5} true
{10 10} false
{1 2} false
{2 1} false
</pre>
'''Closed polygon solution'''
<lang go>package main
Line 1,455 ⟶ 1,471:
{2 1} false
</pre>
'''PNPoly algorithm'''
This solution replaces the <code>rayIntersectsSegment</code> function above with the expression from the popular PNPoly algorithm described at https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html. The expression is not only simpler but more accurate.
This solution is preferred over the two above.
<lang>package main
import "fmt"
type xy struct {
x, y float64
}
type closedPoly struct {
name string
vert []xy
}
func inside(pt xy, pg closedPoly) bool {
if len(pg.vert) < 3 {
return false
}
in := rayIntersectsSegment(pt, pg.vert[len(pg.vert)-1], pg.vert[0])
for i := 1; i < len(pg.vert); i++ {
if rayIntersectsSegment(pt, pg.vert[i-1], pg.vert[i]) {
in = !in
}
}
return in
}
func rayIntersectsSegment(p, a, b xy) bool {
return (a.y > p.y) != (b.y > p.y) &&
p.x < (b.x-a.x)*(p.y-a.y)/(b.y-a.y)+a.x
}
var tpg = []closedPoly{
{"square", []xy{{0, 0}, {10, 0}, {10, 10}, {0, 10}}},
{"square hole", []xy{{0, 0}, {10, 0}, {10, 10}, {0, 10}, {0, 0},
{2.5, 2.5}, {7.5, 2.5}, {7.5, 7.5}, {2.5, 7.5}, {2.5, 2.5}}},
{"strange", []xy{{0, 0}, {2.5, 2.5}, {0, 10}, {2.5, 7.5}, {7.5, 7.5},
{10, 10}, {10, 0}, {2.5, 2.5}}},
{"exagon", []xy{{3, 0}, {7, 0}, {10, 5}, {7, 10}, {3, 10}, {0, 5}}},
}
var tpt = []xy{{1, 2}, {2, 1}}
func main() {
for _, pg := range tpg {
fmt.Printf("%s:\n", pg.name)
for _, pt := range tpt {
fmt.Println(pt, inside(pt, pg))
}
}
}
=={{header|Haskell}}==
| |||