Problem 44694. Monte Carlo integration: area of a polygon
The area of a polygon (or any plane shape) can be evaluated by Monte Carlo integration. The process involves 'random' sampling of (x,y) points in the xy plane, and testing whether they fall inside or outside the shape. That is illustrated schematically below for a circle.
^
Steps:
- Define a 2D region within which to sample points. In the present problem you must choose the rectangular box (aligned to the axes) that bounds the specified polygon.
- By a 'random' process generate coordinates of a point within the bounding box. In the present problem a basic scheme using the uniform pseudorandom distribution available in MATLAB must be employed. Other schemes in use include quasi-random sampling (for greater uniformity of coverage) and stratified sampling (with more attention near the edges of the polygon).
- Determine whether the sampled point is inside or outside the polygon. Due to working in double precision, it is extremely unlikely to sample a point falling exactly on the edge of the polygon, and consequently if it does happen it doesn't really matter whether it's counted as inside or outside or null.
- Repeat steps 2–3 N times.
- Based upon the proportion of sampled points falling within the polygon, report the approximate area of the polygon.
Inputs to your function will be N, the number of points to sample, and polygonX & polygonY, which together constitute an ordered list of polygon vertices. N will always be a positive integer. polygonX & polygonY will always describe a single, continuous outline; however, the polygon may be self-intersecting.
For polygons that are self-intersecting, you must find the area of the enclosed point set. In the case of the cross-quadrilateral, it is treated as two simple triangles (cf. three triangles in the first figure below), and the clockwise/counterclockwise ordering of points is irrelevant. A self-intersecting pentagram (left & middle of the second figure below) will therefore have the same area as a concave decagon (right).
^
EXAMPLE
% Input N = 1000 polygonX = [1 0 -1 0] polygonY = [0 1 0 -1] % Output A = 2.036
Explanation: the above polygon is a square of side-length √2 centred on the origin, but rotated by 45°. The exact area is hence 2. As the value of N is moderate, the estimate by Monte Carlo integration is moderately accurate (an error of 0.036 in this example, corresponding to 509 of the 1000 sampled points falling within the polygon). Of course, if the code were run again then a slightly different value of A would probably be returned, such as A=1.992 (corresponding to 498 of the 1000 sampled points falling within the polygon), due to the random qualities of the technique.
Solution Stats
Problem Comments
-
1 Comment
Monte Carlo Integration improves its results as we increase the number of samples, and the test suite should probably consider this. Step 4 of the algorithm, according to the problem's description, claims the process needs to be repeated 2N or 3N times, but the test suite requires that we test it only N times.
For instance, in test #4, the Axis Aligned Bounding Box has area 4 and our N=1. Therefore, for a single random point, the resulting area will be 0 or 4. And as such, the test suite only tests for 0 and 4 as valid areas. However, suppose we repeated this process three times, as the problem's description states. In that case, it's improbable that we would get three 0s or three 4s. In 75% of cases, one or two results would be different, [0 0 4] or [4 0 4], resulting in an area of 4/3 or 8/3. Curiously, by repeating this process twice, we might reach the correct value of 2 for [0 4] and [4 0].
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
2451 Solvers
-
1365 Solvers
-
14011 Solvers
-
Matrix with different incremental runs
125 Solvers
-
Find third Side of a right triangle given hypotenuse and a side. No * - or other functions allowed
178 Solvers
More from this Author32
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!