1

enter image description here

I want to calculate the Intersection area of circle and a polygon(not self intersecting). is there any good generalized algorithm.

Note: What I have tried: At first I try to solve the problem with Ray casting algorithm, where I will find the points in the circle and then identify the area. But it seems harder for me as the situation got harder and with complex test cases.

Input Specification : center(x,y) and radius of the circle. vertex of the polygon( {x1,y1} , {x2,y2} , {x3,y3} ... ).

UPDATE: The more I think I become confused. is it really possible to calculate this ?

user3712917
  • 121
  • 1
  • 2
  • 13
  • The page you are referring to uses JavaScript. Is your question how to transform the code there to C++? – Christian Hackl Feb 21 '15 at 17:31
  • If you can cast a ray into a circle, the answer is trivial. Can you do that? – BWG Feb 21 '15 at 17:32
  • The link you give provides a solution to a different problem, the decision whether there is an intersection or not. Is that what you search actually or do you want to compute the area where circle and polygon overlap? – Ulrich Eckhardt Feb 21 '15 at 17:33
  • Thanks @UlrichEckhardt , Actually I was googling cbout the solution of Intersection area of polygon and circle" and found this page. Now I have updated the post. and again thanks to clearfy me... – user3712917 Feb 21 '15 at 17:39
  • Actually Ray casting algorithm, works in a different manner, It just count odd even intersection. My final observation is this problem can not/ may not be solvable by ray casting algorithm. @BWG – user3712917 Feb 21 '15 at 17:42
  • 1
    I have updated the problem statement @ChristianHackl – user3712917 Feb 21 '15 at 17:42
  • @user3712917: Thanks for actually taking the time and removing the unnecessary tag. – Christian Hackl Feb 21 '15 at 17:44
  • @user3712917 Dude, of course i'ts solvable by raycasting. Raycasting is literally built for this purpose. – BWG Feb 21 '15 at 17:57
  • Then please answer it with your ray casting procedure. ... @BWG – user3712917 Feb 21 '15 at 18:51
  • @user3712917 Never mind, i didn't know what you were asking. – BWG Feb 21 '15 at 19:13
  • Any restrictions on the polygon? For example, is it always convex? Or at least not self-intersecting? At first sight, this looks like it might be pretty painful to calculate... Have to give it some thought. – Reto Koradi Feb 21 '15 at 19:49
  • the polygon is not self intersecting. Thanks for your question. It made the question more specific. I have also updated the problem statement. @RetoKoradi – user3712917 Feb 21 '15 at 19:54

1 Answers1

-1

There are two steps. First, notice that this problem is easy for triangles - as there are no gotchas. Second, notice that you can break up any N-polygon into N triangles. This makes the situation much easier.

Any circle is described by the formula x^2 + y^2 = r^2. So you can get the area to the axis for any region of the line through integration.

I'll fill this out more tomorrow, I'm going out now.

Community
  • 1
  • 1
will
  • 10,260
  • 6
  • 46
  • 69