# Compute the Area of a Polygon

# Compute the Area of a Polygon

codeonwort + 2 comments Oops. It can be concave :D

sidproquo + 0 comments ahh...I see now why using the semi-perimeter approach won't work here, considering that the polygons can be concave as well

xdavidliu + 0 comments there's a neat trick to get the area even when it's concave.

see this site, which has very nice intuitive explanation https://www.mathsisfun.com/geometry/area-irregular-polygons.html

for people from the future: if the above link is no longer working, here's the basic gist. For every adjacent pair of points in the polygon, we "integrate" the line connecting the two points, with a + sign for going left to right and a - sign for the other way (or you can choose the other direction, as long as you're consistent and take the absolute value at the end).

Make sure to "complete the cycle", e.g. there should be N pairs of points "integrated" this way, not N-1, if the polygon has N points.

timbrown + 0 comments The problem states that 0 <= x,y <= 1000 But some problems (e.g. 3) have values like: 880 1015

karoyakani + 0 comments sol :: Fractional a => [[a]] -> a sol ps = (/2) . abs . sum $ zipWith op ps (last ps: ps) where op p q = head p*last q - last p*head q

caasi + 2 comments The sample input is in clockwise order but all the test cases are in counter-clockwise order. :|

lestarcdog + 2 comments It shouldn't matter if you walk the vertices in a cw or ccw fashion. Just take the absolute value of the area.

Rhaseven7h + 3 comments Pick any node as anchor, and calculate triangle areas from there.

scepticulous + 2 comments Shouldnt the 'simple formular' described on wikipedia also be correct, or am I missing a constraint?

I am just wondering, because I my solution is based on that and it is failing in roughly 1/3 of the test cases.

shengliang_song + 1 comment A = abs (0.5 * sum(x(i)*y(i+1) - x(i+1)*y(i), i, 0, n-1))

I implemented the above formular in clisp. Passed all tests.

scepticulous + 1 comment Hmm, that seems to be the algorithm I am using. Can you spot an error in this snippet:

;;;; points includes the first tuple as last element ;;;; to make sure that connection is included as well (defn polygon-area-parts [points] (let [n (count points)] (loop [pos 0 deltas []] (if (= pos (- n 1)) deltas (let [[x_i y_i] (nth points pos) [x_j y_j] (nth points (inc pos)) entry (- (* x_i y_j) (* x_j y_i))] (recur (inc pos) (conj deltas entry))))))) (defn polygon-area [points] (->> (polygon-area-parts points) (reduce + 0) (#(Math/abs %1)) (#(/ %1 2))))

shengliang_song + 1 comment I convert x to double-float type.

(defun ft (x) (coerce x 'double-float))

replace (/ y 2) ==> (* 0.5 y) //not sure "/" is a integer divison or not.

2.What is in your points list? (passed 1/3; assume this is correct.)

I create a newlist by copy the 1st point and append to the end.

sq_points = (p0,p1,p2,p3)

new_points = (p0,p1,p2,p3,p0); compute p0,p1; and pop p0

new_points = (p1,p2,p3,p0); compute p1,p2; and pop p1

new_points = (p2,p3,p0); compute p2,p3; and pop p2

new_points = (p3,p0); compute p3,p3

sum all above.

scepticulous + 0 comments Thank you for your time. The division really was the issue. Clojure uses fractions so (println (/ 1 3)) will print 1/3 and not 0.333. Using (* 0.5 ) instead made all the tests pass.

:)

Rhaseven7h + 0 comments *Yes, that's it, just condensed in a formula.*See my Gists repo for a Haskell solution

**BEWARE: There are SPOILERS there for this and other challenges in that link.**

pacefist4 + 0 comments thanks, good formula.

Lol, clojure prints the result of

(/ 671767 2)

as

`671767/2`

but not`335883.5`

. That's why I had to cast the result to double.ProofOfPizza + 0 comments Thx for this link. After learning this formula the code was almost the same as the last excercise, just change the lambda in the zipWith

import Control.Monad areaOfPolygon :: (Eq a, Floating a) => [(a,a)] -> a areaOfPolygon points | points == [] = 0.0 | otherwise = let shiftedPoints = [points] >>= (\x -> tail x ++ [head x]) areas = zipWith (\(x1,y1) (x2,y2) -> (x1*y2 - x2*y1)/2) points shiftedPoints in sum $ areas main :: IO () main = do _ <- getLine inputdata <- getContents let input = [(read (words str !! 0) :: Float, read (words str !! 1) :: Float ) | str <- lines inputdata] print $ areaOfPolygon input

sharon_shmorak + 1 comment I don't want to read any spoilers, nor do I want to practice here my math skills and knowledge base. I will be perfectly satisfied with practicing writing functional code in scala. Can someone please just tell me if there is a feneral formula I need to apply to get the area or does the challange lies in dividing the polygon to simpler shapes with simple formula?

sharon_shmorak + 0 comments I found the answer I was lokking for. Given all points of the polygon there is a simple formula that works for all given test cases:here is the formula

abratashov + 0 comments Elixir solution 'Area of a Polygon'

defmodule Solution do def array_xy do IO.read(:stdio, :all) |> String.split("\n") |> Enum.drop(1) |> Enum.drop(-1) |> Enum.map(fn(pair) -> pair |> String.split |> Enum.map(&String.to_integer(&1)) end) end def left_rotate([h|t]), do: t ++ [h] def create_pairs(array) do array |> Enum.map(fn(x) -> List.duplicate(x, 2) end) |> List.flatten |> left_rotate |> left_rotate |> Enum.chunk_every(2) end def shoelace_formula_of_polygon_area(array) do res = array |> Enum.chunk_every(2) |> Enum.map(fn([[x1, y1], [x2, y2]]) -> x1*y2-x2*y1 end) |> Enum.reduce(0, fn(v, acc) -> acc + v end) |> abs 0.5*res end def main do array_xy |> create_pairs |> shoelace_formula_of_polygon_area |> IO.inspect(limit: :infinity) end end Solution.main

Benjamin_A_Luna + 0 comments My complete F# solution. I must say that this was a hard one.

let getpoint a = let a = Console.ReadLine().Split() (a.[0] |> double, a.[1] |> double) [<EntryPoint>] let main argv = let n = Console.ReadLine() |> int let points = [for i = 1 to n do yield getpoint 0] let rec GetArea1 (l: List<double * double>) i = if i < l.Length-1 then (fst l.[i] * snd l.[i+1]) + GetArea1 l (i+1) else fst l.[i] * snd l.[0] let rec GetArea2 (l: List<double * double>) i = if i < l.Length-1 then (snd l.[i] * fst l.[i+1]) + GetArea2 l (i+1) else snd l.[i] * fst l.[0] let area = (GetArea1 points 0) - (GetArea2 points 0) Console.WriteLine(abs (area / 2.0)) 0

murtaught + 0 comments There is a little error in this problem's statement. Condition N >= 4 is violated in test cases.

johnwang + 0 comments I used float instead of double and I could'nt figure out what was wrong.

jessecalato + 0 comments open System let readPair() = match Console.ReadLine().Split([|' '|]) |> Array.map Int32.Parse |> Array.toList with | x::y::[] -> x, y | _ -> failwith "Invalid pair" let readPairs n = let rec readPairs n r = match n with | 0 -> r | _ -> readPairs (n - 1) (readPair()::r) readPairs n [] let dist p1 p2 = let (x1, y1), (x2, y2) = p1, p2 sqrt (((float (x2 - x1)) ** 2.0) + ((float (y2 - y1)) ** 2.0)) let findArea pairs = let constructMatrix pairs = let (firstPair, rest) = match pairs with | x::xs -> x, xs | _ -> failwith "Wrong" pairs @ [firstPair] let rec calc pairs acc = match pairs with | (x1, y1)::(x2, y2)::rest -> let (a1, a2) = acc let acc' = (a1 + (x1 * y2), a2 + (x2 * y1)) calc ((x2, y2)::rest) acc' | _ -> let (a1, a2) = acc float ((abs (a1 - a2))) / 2.0 let matrix = constructMatrix pairs calc matrix (0, 0) let findPerimeter pairs = let rec f firstPair previousPair pairs acc = match previousPair, pairs with | p1, p2::rest -> f firstPair p2 rest (acc + (dist p1 p2)) | _, [] -> acc + (dist previousPair firstPair) match pairs with | p::rest -> f p p rest 0.0 | _ -> failwith "Wrong" let runTestCase() = Console.ReadLine() |> Int32.Parse |> readPairs |> findArea |> (printfn "%A") runTestCase()

Sort 16 Discussions, By:

Please Login in order to post a comment