Point in Polygon

wrf.pl

% Tail-recurse through the list until the last one. Replace the last with an
% empty list.
without_last([_], []).
without_last([Head|Tail], [Head|List]) :- without_last(Tail, List).

% Appends the tail of a list to its head. The old head becomes the new last
% element of the list. The new head is the previous second element.
rotate_left([Head|Tail], List) :- append(Tail, [Head], List).

rotate_right(List, [Head|Tail]) :-
    last(List, Head),
    without_last(List, Tail),
    !.

zip([], [], []).
zip([H1|T1], [H2|T2], [[H1, H2]|T]) :- zip(T1, T2, T).

% Succeeds if the given point [X, Y] lies inside the polygon described by the
% given list of point pairs (XYs); fails if the point lies outside.
%
% First pairs up each point with the preceeding point by rotating the list
% right and zipping up the point-pairs. Then tests each point pair against the
% given [X, Y]. An odd number of successful tests means inside; even means outside.
%
% https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html
point_in_polygon(XYs, [X, Y]) :-
    rotate_right(XYs, Rotated),
    zip(XYs, Rotated, Zipped),
    convlist({X, Y}/[[[X1, Y1], [X2, Y2]], Test]
            >>((Y1 > Y, Y2 =< Y; Y1 =< Y, Y2 > Y),
            Test is (X2 - X1) * (Y - Y1) / (Y2 - Y1) + X1,
            X < Test),
        Zipped,
        Tests),
    length(Tests, NumberOfTests),
    0 =\= NumberOfTests mod 2.