32
3
Consider a potentially self-intersecting polygon, defined by a list of vertices in 2D space. E.g.
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
There are several ways to define the area of such a polygon, but the most interesting one is the even-odd rule. Taking any point in the plane, draw a line from the point out to infinity (in any direction). If that line crosses the polygon an odd number of times, the point is part of the polygon's area, if it crosses the polygon an even number of times, the point is not part of the polygon. For the above example polygon, here are both its outline as well as its even-odd area:
The polygon will not in general be orthogonal. I've only chosen such a simple example to make it easier to count the area.
The area of this example is 17
(not 24
or 33
as other definitions or area might yield).
Note that under this definition the area of the polygon is independent of its winding order.
The Challenge
Given a list of vertices with integer coordinates defining a polygon, determine its area under the even-odd rule.
You may write a function or program, taking input via STDIN or closest alternative, command-line argument or function argument and either return the result or print it to STDOUT or closest alternative.
You may take input in any convenient list or string format, as long as it's not preprocessed.
The result should either be floating point number, accurate to 6 significant (decimal) digits, or a rational result whose floating point representation is accurate to 6 significant digits. (If you produce rational results they are likely going to be exact, but I can't require this, as I don't have exact results for reference.)
You must be able to solve each of the test cases below within 10 seconds on a reasonable desktop machine. (There is some leeway in this rule, so use your best judgement. If it takes 20 seconds on my laptop I'll give you the benefit of the doubt, if it takes a minute, I won't.) I think this limit should be very generous but it is supposed to rule out approaches where you just discretise the polygon on a sufficiently fine grid and count, or use probabilistic approaches like Monte Carlo. Be a good sportsman and don't try to optimise of these approaches such that you can meet the time limit anyway. ;)
You must not use any existing functions related directly to polygons.
This is code golf, so the shortest submission (in bytes) wins.
Assumptions
- All coordinates are integers in the range
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - There will be at least
3
and at most50
vertices. - There won't be any repeated vertices. Neither will any vertices lie on another edge. (There may be collinear points in the list, though.)
Test Cases
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
Can we reformat the input to suit our needs, by replacing the delimiters and such? – AJMansfield – 2015-03-12T02:19:43.950
1Specifically, I would like to replace the delimiters in a way that makes the list a valid PostScript User Path, so I can parse the whole thing with one
upath
operator. (It is actually an extremely simple 1:1 conversion between the seperators.}, {
just becomeslineto
, and the comma between the x and y is removed, and the opening and closing braces are replaced with a static header and footer...) – AJMansfield – 2015-03-12T02:31:16.9501@AJMansfield I usually don't mind using convenient, native list representations, but using
upath
andlineto
sounds like you're actually preprocessing the input. I.e. you're not taking a list of coordinates but an actual polygon. – Martin Ender – 2015-03-12T09:27:39.677Can we assume that the polygons are generic enough that there are no triple (or higher) intersections? – Matt Noonan – 2015-03-13T03:43:17.600
Do you have a reference about the consistency of the even-odd rule? Drawing the line in different directions will result in different number of crossing times. – Ray – 2015-03-13T06:28:53.230
1@MattNoonan Oh, that's a good point. Yes you may assume that. – Martin Ender – 2015-03-13T09:36:32.207
2
@Ray While the direction may affect the number of crossings, it will only ever increase or decrease by 2, preserving the parity. I'll try to find a reference. For a start, SVG uses the same definition.
– Martin Ender – 2015-03-13T09:38:17.580By the way, the even-odd rule works because of the following: starting outside the polygon and moving from left to right, top to bottom, perform rasterization as follows: every time you cross a boundary line of the polygon switch from "drawing" to "not drawing" (or vice versa) until having exited the polygon. Any given horizontal print will cross the boundary line exactly an even number of times (the shape is closed, so this statement is mathematically true). Ergo, any odd number of crossings is inside the polygon. – Draco18s no longer trusts SE – 2017-07-11T17:28:31.807
I don't want to bump this unnecessarily, but technically you are drawing a ray, since lines are bi-infinite but rays are semi-infinite. – boboquack – 2018-02-19T06:35:35.663
1
Mathematica 12.0 has a new built-in function for this:
– alephalpha – 2019-04-16T04:16:43.123CrossingPolygon
.