self-intersecting polygon

[Sallygreen]

anyone know "how can I calculate the area of a self-intersecting polygon?" how the orientation of any polygon affect its area??

[zaza]

What's a "self-intersecting polygon"? A polygon which has a loop in it? I would have thought that you would then just redefine your polygon such that it is still one enclosed space but with two vertices at the same point, and miss out the bit that has been cut off by the loop.

As for your second question, think about it! Does your polygon get a different area if you rotate the paper you drew it on? Or is that not what you meant?

[Sallygreen]

[QUOTE=zaza]What's a "self-intersecting polygon"?
a "self-intersecting polygon" is not a simple polygon(convex or concave), you can imagine it as 2 or more triangular connected at some point

As for your second question, think about it! Does your polygon get a different area if you rotate the paper you drew it on? Or is that not what you meant?

I mean how the sign of the area of concave or convex polygon change with the orientation which could be clockwise or counterclockwise direction

[NickThissen]

All I can imagine by a self intersecting polygon is simply two polygons stuck together at one vertex, so if that is indeed the case you can simply calculate the areas of the two polygons and add them up.

About the orientation, that depends on how you calculate it. If you use some theorem like Green's theorem then the orientation is important.

Green's theorem says that the line integral over a closed curve C can be evaluated as a double integral over the enclosed surface D:

If you choose L and M so that the 'dM/dx - dL/dy' in the above equation is 1, then it gives you simply the double integral over (1)dA which is the area of the enclosed surface.

So that can be used to calculate the area of any closed (simple, eg non intersecting) curve (and in the case that it's not simple, eg self intersecting, you can split it up into curves that are).

If you use this method, the orientation of the curve C determines the sign of the area of D. But I doubt you are using this (or are you?) so I think we're going to need more information about how you are calculating the area.



EDIT
I see, you are asking how to calculate the area so you don't know yet?

In that case it depends on the shape of the polygon. If the polygon is regular in some kind (eg, equal lengths, constant radius, etc) then there are certain formulas that allow you to find the area instantly.
If the polygon is irregular, you can also cut it up into triangles for example and find each area of the triangles.

Or, you can use Green's theorem (which might or might not be much too complicated depending on your situation). If you can choose M and L above just so that dM/dx - dL/dy = 1, then the line integral over the edge of your polygon gives the area of the polygon.
However, since it is a polygon, that line integral can become very tricky, since a polygon is not a smooth curve, and you will have to cut the line integral up into smooth components (Green's theorem only holds for (piecewise) smooth curves).

[Sallygreen]

All I can imagine by a self intersecting polygon is simply two polygons stuck together at one vertex, so if that is indeed the case you can simply calculate the areas of the two polygons and add them up.

About the orientation, that depends on how you calculate it. If you use some theorem like Green's theorem then the orientation is important.

Green's theorem says that the line integral over a closed curve C can be evaluated as a double integral over the enclosed surface D:

If you choose L and M so that the 'dM/dx - dL/dy' in the above equation is 1, then it gives you simply the double integral over (1)dA which is the area of the enclosed surface.

So that can be used to calculate the area of any closed (simple, eg non intersecting) curve (and in the case that it's not simple, eg self intersecting, you can split it up into curves that are).

If you use this method, the orientation of the curve C determines the sign of the area of D. But I doubt you are using this (or are you?) so I think we're going to need more information about how you are calculating the area.


DIT
I see, you are asking how to calculate the area so you don't know yet?

In that case it depends on the shape of the polygon. If the polygon is regular in some kind (eg, equal lengths, constant radius, etc) then there are certain formulas that allow you to find the area instantly.
If the polygon is irregular, you can also cut it up into triangles for example and find each area of the triangles.

yeah I know that

Or, you can use Green's theorem (which might or might not be much too complicated depending on your situation). If you can choose M and L above just so that dM/dx - dL/dy = 1, then the line integral over the edge of your polygon gives the area of the polygon.
However, since it is a polygon, that line integral can become very tricky, since a polygon is not a smooth curve, and you will have to cut the line integral up into smooth components (Green's theorem only holds for (piecewise) smooth curves).

I have used this formula for Irregular polygon cos I am not interesting in regular one The (signed) area of a planar non-The (signed) area of a planar non-self-intersecting polygon with vertices (x_1,y_1), ..., (x_n,y_n) is
A=1/2(|x_1 x_2; y_1 y_2|+|x_2 x_3; y_2 y_3|+...+|x_n x_1; y_n y_1|),

this formula is working for any polygon except for self-intersecting polygon, , also I know how to find its area manually by summing of each of the triangles which comprises the polygon so just the thing I need is if there is any formula to find its area to make it easy to build a code for it???

[NickThissen]

Never saw that formula but I suppose it's valid... If that is the case, what stops you from cutting the self-intersecting polygon up into two non-self-intersecting polygons? If you want to do it in code you just need some way to find out at which vertex it is intersecting, and how to 'label' the vertices so that you get two non intersecting polygons.

Something like this:


As you can see, the second 'polygon' (which is now actually two polygons) has one vertex more (the intersection point) and the numbers are labelled differently so you can still use your formula.

[Sallygreen]

Never saw that formula but I suppose it's valid...

THis formula from http://mathworld.wolfram.com/PolygonArea.html

If that is the case, what stops you from cutting the self-intersecting polygon up into two non-self-intersecting polygons?

for some self-intersecting polygon we might need to cut it to more than 3 non-self-intersecting polygons

If you want to do it in code you just need some way to find out at which vertex it is intersecting, and how to 'label' the vertices so that you get two non intersecting polygons.

Something like this:


As you can see, the second 'polygon' (which is now actually two polygons) has one vertex more (the intersection point) and the numbers are labelled differently so you can still use your formula.

this way seems to be complicated to be coded

[jemidiah]

Yup, splitting up the polygon would be complicated to code. Dealing with multiple intersections wouldn't be difficult with recursion I think.

That's a nifty formula I'll have to remember. I wish the page included a proof. Anywho, the area of a self-intersecting polygon is pretty complicated. I'd be surprised if you found a "silver bullet" as a professor of mine once put it--a simple formula.


Thinking on it more... I don't think the code would be as complicated as you might think. The intersection detection operation could be brute forced pretty quickly and the vertex addition bit could also be done simply. Breaking it up into proper functions would make it work in I'd guess 50 lines.


Edit: I'm not sure why you keep asking the same type of question about orientation. The standard definition (which would be consistent with your formula) is given on the page you linked.

[Sallygreen]

Edit: I'm not sure why you keep asking the same type of question about orientation. The standard definition (which would be consistent with your formula) is given on the page you linked.

Sorry for that, I guess the asked it twise for different matter the first time for the signed area, and the second one for the inward normal, I would be grateful if you could send me the link which explain the dependence of inward normal on the direction i mean if clockwise direction then the normal will be inward, to get more details

[jemidiah]

The dependence of orientation (clockwise/counterclockwise) on normal direction (inward/outward) depends entirely on your convention. Consider a 2D vector pointing right from the origin. There are two very valid normals: the up vector, and the down vector. Which one your algorithm gives you depends on if you convert <a, b> into <b, -a> or <-b, a>--it depends on your own convention. In my other post I described which operation gives you which orientation. Or you can draw it out yourself on paper using an example polygon and example vertices. It should be pretty obvious from that which direction your algorithm will give you.