Anonymous user
Ray-casting algorithm: Difference between revisions
smalltalk
(→{{header|Tcl}}: Use the better algorithm from the top of the page to fix the error) |
(smalltalk) |
||
Line 364:
end program Pointpoly</lang>
=={{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>).
<lang smalltalk>Object subclass: Segment [
|pts|
Segment class >> new: points [ |a|
a := super new.
^ a init: points
]
init: points [ pts := points copy. ^self ]
endPoints [ ^pts ]
"utility methods"
first [ ^ pts at: 1]
second [ ^ pts at: 2]
leftmostEndPoint [
^ (self first x > self second x) ifTrue: [ self second ] ifFalse: [ self first ]
]
rightmostEndPoint [
^ (self first x > self second x) ifTrue: [ self first ] ifFalse: [ self second ]
]
topmostEndPoint [
^ (self first y > self second y) ifTrue: [ self first ] ifFalse: [ self second ]
]
bottommostEndPoint [
^ (self first y > self second y) ifTrue: [ self second ] ifFalse: [ self first ]
]
slope [
(pts at: 1) x ~= (pts at: 2) x
ifTrue: [ ^ ((pts at: 1) y - (pts at: 2) y) / ((pts at: 1) x - (pts at: 2) x) ]
ifFalse: [ ^ FloatD infinity ]
]
doesIntersectRayFrom: point [ |p A B|
(point y = (pts at: 1) y) | (point y = (pts at: 2) y)
ifTrue: [ p := Point x: (point x) y: (point y) + 0.00001 ]
ifFalse: [ p := point copy ].
A := self bottommostEndPoint.
B := self topmostEndPoint.
(p y < A y) | (p y > B y) | (p x > (self rightmostEndPoint x))
ifTrue: [ ^false ]
ifFalse: [ (p x < (self leftmostEndPoint x))
ifTrue: [ ^true ]
ifFalse: [ |s|
s := Segment new: { A . point }.
(s slope) >= (self slope)
ifTrue: [ ^ true ]
]
].
^false
]
].
Object subclass: Polygon [
|polysegs|
Polygon class >> new [ |a| a := super new. ^ a init. ]
Polygon class >> fromSegments: segments [ |a|
a := super new.
^ a initWithSegments: segments
]
Polygon class >> fromPoints: pts and: indexes [ |a|
a := self new.
indexes do: [ :i |
a addSegment: ( Segment new: { pts at: (i at: 1) . pts at: (i at: 2) } )
].
^ a
]
initWithSegments: segments [
polysegs := segments copy. ^self
]
init [ polysegs := OrderedCollection new. ^ self ]
addSegment: segment [ polysegs add: segment ]
pointInside: point [ |cnt|
cnt := 0.
polysegs do: [ :s | (s doesIntersectRayFrom: point)
ifTrue: [ cnt := cnt + 1 ] ].
^ ( cnt \\ 2 = 0 ) not
]
].</lang>
'''Testing'''
<lang smalltalk>|points names polys|
points := {
0@0 . 10@0 . 10@10 . 0@10 .
2.5@2.5 . 7.5@2.5 . 7.5@7.5 .
2.5@7.5 . 0@5 . 10@5 .
3@0 . 7@0 . 7@10 . 3@10
}.
names := { 'square' . 'square hole' . 'strange' . 'exagon' }.
polys := OrderedCollection new.
polys add:
(
Polygon fromPoints: points
and: { {1 . 2}. {2 . 3}. {3 . 4}. {4 . 1} }
) ;
add:
(
Polygon fromPoints: points
and: { {1 . 2}. {2 . 3}. {3 . 4}. {4 . 1}. {5 . 6}. {6 . 7}. {7 . 8}. {8 . 5} }
) ;
add:
(
Polygon fromPoints: points
and: { {1 . 5}. {5 . 4}. {4 . 8}. {8 . 7}. {7 . 3}. {3 . 2}. {2 . 5} }
) ;
add:
(
Polygon fromPoints: points
and: { {11 . 12}. {12 . 10}. {10 . 13}. {13 . 14}. {14 . 9}. {9 . 11} }
).
{ 5@5 . 5@8 . -10@5 . 0@5 . 10@5 . 8@5 . 10@10 }
do: [ :p |
1 to: 4 do: [ :i |
('point %1 inside %2? %3' %
{ p . names at: i. (polys at: i) pointInside: p }) displayNl
].
' ' displayNl.
]</lang>
=={{header|Tcl}}==
| |||