Re: [xsl] XSLT code that implements the Point-in-a-Polygon problem

["director@xxxxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

Roger,

I'm enjoying reading/experimenting with this code.

Minor things: It looks like you could dispense with $N, no? Data types: 
the function should take doubles as input (with error checks for odd 
inputs) and return a boolean, no? And in XSLT 3.0 you could use 
xsl:iterate, which could facilitate optimization. It also looks like you 
don't need to end $polygon by repeating the starting coordinate. At 
least I didn't in the tests I ran (all successful), including a bowtie 
polygon.

Border point results are uneven. In polygon (0,0), (2,2), (2,0) 
coordinates (1,1) and (2,2) were detected as outside, but (2,1) as 
inside.

I like it. Add a license so we know if/how this can be reused.

jk
Joel Kalvesmaki
Text Alignment Network
http://textalign.net


On 2020-12-10 12:23, Roger L Costello costello@xxxxxxxxx wrote:
> Hi Folks,
>
> I implemented XSLT code to determine if a point p is inside or outside
> a polygon. See below. Admittedly, the tests that I've done thus far
> are really simple. See the template rule. I would appreciate it if you
> see a bug in the code or see where the code can be improved, you would
> let me know please. /Roger
>
> <?xml version="1.0" encoding="UTF-8"?>
> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
>     xmlns:xs="http://www.w3.org/2001/XMLSchema";
>     xmlns:f="function"
>     exclude-result-prefixes="#all"
>     version="2.0">
>
>     <xsl:output method="text" />
>
>     <!--
>         Given a point p, does p reside in the polygon with N edges?
>         This program solves the Point-in-a-Polygon problem.
>     -->
>
>     <!--
>         The following code implements in XSLT the C code
>         shown in Solution 1 at this URL:
>         
> http://www.eecs.umich.edu/courses/eecs380/HANDOUTS/PROJ2/InsidePoly.html
>     -->
>     <xsl:function name="f:iterate-Over-All-Polygons" as="xs:string">
>         <xsl:param name="polygon" as="xs:string+" />
>         <xsl:param name="N" as="xs:integer" />
>         <xsl:param name="p" as="xs:string" />
>         <xsl:param name="counter" as="xs:integer" />
>         <xsl:param name="p1" as="xs:string" />
>         <xsl:param name="i" as="xs:integer" />
>
>         <xsl:variable name="p_x" select="xs:double(tokenize($p, '
> ')[1])" as="xs:double" />
>         <xsl:variable name="p_y" select="xs:double(tokenize($p, '
> ')[2])" as="xs:double" />
>
>
>         <xsl:variable name="p1_x" select="xs:double(tokenize($p1, '
> ')[1])" as="xs:double" />
>         <xsl:variable name="p1_y" select="xs:double(tokenize($p1, '
> ')[2])" as="xs:double" />
>
>         <xsl:choose>
>             <xsl:when test="$i le $N">
>                 <!-- p2 = polygon[i % N] -->
>                 <xsl:variable name="p2" select="$polygon[($i mod $N) +
> 1]" as="xs:string"/>
>                 <xsl:variable name="p2_x"
> select="xs:double(tokenize($p2, ' ')[1])" as="xs:double" />
>                 <xsl:variable name="p2_y"
> select="xs:double(tokenize($p2, ' ')[2])" as="xs:double" />
>                 <!-- if (p.y > MIN(p1.y,p2.y)) -->
>                 <xsl:choose>
>                     <xsl:when test="$p_y gt min(($p1_y, $p2_y))">
>                         <!-- if (p.y <= MAX(p1.y,p2.y)) -->
>                         <xsl:choose>
>                             <xsl:when test="$p_y le max(($p1_y, 
> $p2_y))">
>                                 <!-- if (p.x <= MAX(p1.x,p2.x)) -->
>                                 <xsl:choose>
>                                     <xsl:when test="$p_x le
> max(($p1_x, $p2_x))">
>                                         <!-- if (p1.y != p2.y) -->
>                                         <xsl:choose>
>                                             <xsl:when test="$p1_y ne 
> $p2_y">
>                                                 <!-- xinters =
> (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x -->
>                                                 <xsl:variable
> name="xinters" select="($p_y - $p1_y)*($p2_x - $p1_x) div ($p2_y -
> $p1_y) + $p1_x" as="xs:double" />
>                                                 <!-- if (p1.x == p2.x
> || p.x <= xinters) -->
>                                                 <xsl:choose>
>                                                     <xsl:when
> test="$p1_x eq $p2_x or $p_x le $xinters">
>                                                         <!-- counter++ 
> -->
>                                                         <!-- p1 = p2 
> -->
>                                                         <xsl:sequence
> select="f:iterate-Over-All-Polygons($polygon, $N, $p, $counter + 1,
> $p2, $i + 1)" />
>                                                     </xsl:when>
>                                                     <xsl:otherwise>
>                                                         <!-- p1 = p2 
> -->
>                                                         <xsl:sequence
> select="f:iterate-Over-All-Polygons($polygon, $N, $p, $counter, $p2,
> $i + 1)" />
>                                                     </xsl:otherwise>
>                                                 </xsl:choose>
>                                             </xsl:when>
>                                             <xsl:otherwise>
>                                                 <!-- p1 = p2 -->
>                                                 <xsl:sequence
> select="f:iterate-Over-All-Polygons($polygon, $N, $p, $counter, $p2,
> $i + 1)" />
>                                             </xsl:otherwise>
>                                         </xsl:choose>
>                                     </xsl:when>
>                                     <xsl:otherwise>
>                                         <!-- p1 = p2 -->
>                                         <xsl:sequence
> select="f:iterate-Over-All-Polygons($polygon, $N, $p, $counter, $p2,
> $i + 1)" />
>                                     </xsl:otherwise>
>                                 </xsl:choose>
>                             </xsl:when>
>                             <xsl:otherwise>
>                                 <!-- p1 = p2 -->
>                                 <xsl:sequence
> select="f:iterate-Over-All-Polygons($polygon, $N, $p, $counter, $p2,
> $i + 1)" />
>                             </xsl:otherwise>
>                         </xsl:choose>
>                     </xsl:when>
>                     <xsl:otherwise>
>                         <!-- p1 = p2 -->
>                         <xsl:sequence
> select="f:iterate-Over-All-Polygons($polygon, $N, $p, $counter, $p2,
> $i + 1)" />
>                     </xsl:otherwise>
>                 </xsl:choose>
>             </xsl:when>
>             <xsl:otherwise>
>                 <xsl:message>Number of times a horizontal ray
> eminating from p to the right intersects the line segments making up
> the polygon = <xsl:value-of select="$counter" /></xsl:message>
>                 <!--
>                     if (counter % 2 == 0)
>                         return(OUTSIDE);
>                     else
>                         return(INSIDE)
>                 -->
>                 <xsl:choose>
>                     <xsl:when test="($counter mod 2) eq
> 0"><xsl:text>OUTSIDE</xsl:text></xsl:when>
>                     
> <xsl:otherwise><xsl:text>INSIDE</xsl:text></xsl:otherwise>
>                 </xsl:choose>
>             </xsl:otherwise>
>         </xsl:choose>
>
>     </xsl:function>
>
>     <xsl:function name="f:InsidePolygon" as="xs:string">
>         <xsl:param name="polygon" as="xs:string+" />
>         <xsl:param name="N" as="xs:integer" />
>         <xsl:param name="p" as="xs:string" />  <!-- p1 = polygon[1] -->
>
>         <xsl:variable name="counter" select="0" as="xs:integer" />
>         <xsl:variable name="p1" select="$polygon[1]" as="xs:string" />
>         <xsl:variable name="i" select="1" as="xs:integer" />
>
>         <xsl:sequence select="f:iterate-Over-All-Polygons($polygon,
> $N, $p, $counter, $p1, $i)" />
>
>     </xsl:function>
>
>     <xsl:template match="/">
>         <xsl:variable name="polygon" as="xs:string+">
>             <xsl:sequence select="'0 0'" />
>             <xsl:sequence select="'4 0'" />
>             <xsl:sequence select="'4 4'" />
>             <xsl:sequence select="'0 4'" />
>             <xsl:sequence select="'0 0'" />
>         </xsl:variable>
>         <xsl:variable name="N" select="5" as="xs:integer" />
>
>         <xsl:variable name="p" select="'1 1'" as="xs:string" />
>         <xsl:sequence select="f:InsidePolygon($polygon,$N, $p)" />
>
>         <xsl:variable name="p" select="'-1 1'" as="xs:string" />
>         <xsl:sequence select="f:InsidePolygon($polygon,$N, $p)" />
>
>         <xsl:variable name="p" select="'0 0'" as="xs:string" />
>         <xsl:sequence select="f:InsidePolygon($polygon,$N, $p)" />
>
>         <xsl:variable name="p" select="'0.2 0.5'" as="xs:string" />
>         <xsl:sequence select="f:InsidePolygon($polygon,$N, $p)" />
>
>     </xsl:template>
>
> </xsl:stylesheet>