Finns det någon som har en idé om en sätt att beräkna en generell yta från ett antal givna punkter (3 eller flera), T.ex. genom att man vill beräkna ett rums yta från en ritning via t.ex. en digitizer. Ytan definieras av hörnpunkter, och är sällan av formen av en rektangel, utan formen kan vara hur som helst.

Förutsätter att det är plana ytor du menar.
För trianglar finns herons formel (googla)

En bra källa är
http://mathworld.wolfram.com/Area.html

En idé bara?

Det är mycket lätt att räkna ut arean av en triangel, utifrån dess hörnpunkter (t.ex. med Heron's formel som föreslogs, men det finns andra, enklare sätt).

Problemet är ju när det är en mer komplex figur. Första frågan är om det är en konvex figur?
Det innebär att det aldrig går "inåt"; att om man drar ett streck mellan hörn i och hörn i+j så kommer man aldrig hamna utanför figuren.

Om vi säger att du har n hörn så kan du dela upp figuren i n-2 deltrianglar, och beräkna arean för var och en av dem.


Är den inte konvex så blir det värre, men det borde gå att lösa på något liknande sätt, fast då genom att ta bort arean för de trianglar som ligger fel.

Här kommer exempelkod för att splitta upp en area i trianglar. Tyvärr hade jag inte läst Niklas inlägg när jag skrev koden så den tar inte hand om konkava fallet...men det kanske är något att utgå ifrån...

<code>
private void button2_Click(object sender, System.EventArgs e)
{
System.Collections.ArrayList list=new ArrayList();
System.Collections.ArrayList triangles=new ArrayList();
Triangle triangle;

list.Add(new Point(0,0));
list.Add(new Point(6,-1));
list.Add(new Point(8,0));
list.Add(new Point(6,3));
list.Add(new Point(3,3));

int l=list.Count;
while (list.Count>3)
{
l=list.Count;
triangle=new Triangle();
triangle.A=(Point)list[l-1];
triangle.B=(Point)list[l-2];
triangle.C=(Point)list[l-3];
triangles.Add(triangle);
list.RemoveAt(l-2);
}
triangle=new Triangle();
triangle.A=(Point)list[0];
triangle.B=(Point)list[1];
triangle.C=(Point)list[2];
triangles.Add(triangle);

foreach (object t in triangles)
{
triangle=(Triangle)t;
Console.WriteLine(triangle.ToString());
}
}

public class Triangle
{
public Point A;
public Point B;
public Point C;

public Triangle()
{
}

public Triangle(Point a,Point b, Point c)
{
A=a;
B=b;
C=c;
}

public float Area()
{
// Todo
return 1;
}

public override string ToString()
{
return "(" + A.ToString() + " , " + B.ToString() + " , " + C.ToString() + ") Area=" + Area().ToString();
}
}
</code>

Du kan loopa genom koordinaterna och beräkna ytan för polygonen.

ett ex i VB

<code>
Option Explicit

Sub main()

Dim Xcoords() As Double
Dim Ycoords() As Double

ReDim Xcoords(3)
ReDim Ycoords(3)

Xcoords(0) = 2.512
Ycoords(0) = 18.123
Xcoords(1) = 19
Ycoords(1) = 44
Xcoords(2) = 31
Ycoords(2) = 20
Xcoords(3) = 17
Ycoords(3) = 10

Debug.Print calcArea(Xcoords, Ycoords)

End Sub



Public Function calcArea(Xs() As Double, Ys() As Double) As Double
Dim i As Integer
Dim res As Double

If UBound(Xs) - LBound(Xs) < 2 Then Exit Function
If UBound(Xs) <> UBound(Ys) Then Exit Function

i = LBound(Xs)
Do While i < UBound(Xs)
res = res + (Xs(i + 1) - Xs(i)) * (Ys(i + 1) + Ys(i))
i = i + 1
Loop

res = res + (Xs(0) - Xs(i)) * (Ys(0) + Ys(i))

calcArea = Abs(res / 2)

End Function
</code>


//
Janne

Det verkar som båda metoderna ger sig på att bestämma det i fallet konvexa polygoner.
Fungerar verkligen Jan Bulérs metod?
Känns som att det kommer komma negativa och positiva delar även i en konvex figur, ser inte riktigt hur det skulle kunna gå ihop. (Kan dock vara så att jag tänker i fel banor - jag väljer att utgå från en vanlig triangeluppdelning)


Jag vet en metod för att klara det lite allmänare fallet, men vetefan om jag orkar gå in på det här. Det involverar bl.a. determinanter.

Kan bara visa ett mycket enkelt exempel på hur en icke-konvex (tror inte begreppet konkav existerar i sammanhanget) figur ser ut:
<code>
_____ ______
| \ | |
| \| |
| |
|___________|
</code>

Trots att det är en mycket enkel figur så kan man inte lösa den med de givna metoderna. Lösningen är att dela upp den i andra trianglar än de lätta varianterna (t.ex. att sammanbinda punkt 1, i och i+1).

Notera också att det finns ytterligare en komplexitet som inte uppstår i det här problemet: en figur som korsar sig själv.

Jan,

Är du säker på att den koden är rätt? Omskrivet så att det passar min kod ovan så får jag det att bli så här:
<code>
public float Area() // Arean av en triangel
{
float res=0;

res+=(B.X-A.X)*(B.Y-A.Y);
res+=(C.X-B.X)*(C.Y-B.Y);
res+=(A.X-C.X)*(A.Y-C.Y);
res/=2;
return System.Math.Abs(res);
}
</code>
Det verkar dock inte bli rätt för polygonen beskriven av punkterna :
(0,0)
(6,-1)
(8,0)
(6,3)
(3,3)
Enligt din kod skulle arean bli 27.5, men "manuellt" får jag det till 20.5...

Om man för varje triangel tog en punkt inuti trianglen, t ex "tyngdpunkten" eller "centrum", så kunde man med en InsidePolygon-funktion avgöra om punkten ligger inne i polygonen eller ej. Detta skulle man då kunna använda för att hantera situationen med icke-konvexa polygoner och då igonera dessa trianglar som ligger utanför polygonen.

Exempel på InsidePolygon-algoritm:
http://www.alienryderflex.com/polygon/

<b>>Detta skulle man då kunna använda för att hantera situationen med icke-konvexa polygoner och då igonera dessa trianglar som ligger utanför polygonen.</b>

Nja.. tror att det inte riktigt går. Grejen e att då krävs det att varje hål kan representeras av exakt en triangel, och det gör det inte i den här metoden.

Den metoden jag har sett som funkar bäst är genom användning av orientering (för vilket man behöver determinanter).

Tyvärr är det ganska komplicerat och jag kommer inte riktigt ihåg hur det funkar.

En annan metod man skulle kunna använda är ju en approximativ metod. Skapa kvadrater med sida d. Räkna antalet som är helt innanför och såna som är helt utanför. Kan man t.ex. göra med den metod som Hultan länkar till (applicera i alla fyra hörnen). Kolla skillnaden och kalla den x.
I teorin låter du nu d gå mot 0 (=> x->0), eller i praktiken: Gör d mindre och mindre, men stanna när x<epsilon.

Jag är rudis på den matematik Ni hänvisar till, Men vad tror ni om detta ?

Rita polygonen på en Form med API CreatePolygonRgn och fylla den
med en känd färg.Sedan räknar man hur många pixel som har den färgen ?

Hur man sedan översätter skalan får jag tänka ut i natt !:-)

Det är i stort sett den metod jag menar när jag pratar om en approximativ metod, fast att man då gör det själv, men det spelar ju ingen roll.

Skillnaden där blir att man behåller pixelstorleken, och förstorar polygonen istället. Den är inte lika snabb numeriskt, och förmodligen aningen långsammare än samma metod rent matematisk, men om det är enstaka ytor lär det ju inte spela någon roll.

Sen finns det ju alltid såna funktioner i CAD-program, så om såna finns tillgängliga lär det ju inte va några problem...

Hittade detta som kanske går att bygga på
http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=47983&lngWId=1

Per,

Du har skrivit

res+=(B.X-A.X)*(B.Y-A.Y);

men det ska vara

res+=(B.X-A.X)*(B.Y+A.Y);

+ inte - i den andra parantesen, det är lika på alla dina rader i ditt tidigare ex.

Jag har tagit beräkningen från en bok där det var beskrivet hur man räknar ytan på en polygon.

//
Janne

Men frågan kvarstår: är det för alla polygoner eller bara för konvexa?

Länken i SvenPons inlägg var också till konvexa polygoner.

Med tanke på tillämpningen så är det nog intressant med bara den typen.

Niklas,

"Kan bara visa ett mycket enkelt exempel på hur en icke-konvex (tror inte begreppet konkav existerar i sammanhanget) figur ser ut:

(din figur)

Trots att det är en mycket enkel figur så kan man inte lösa den med de givna metoderna"

Om du provar att sätta in koordinater t ex

5,0--------5,3 5,7----5,9
| \ | |
| \ | |
| 2,7 |
| |
0,0--------------------- 0,9

Prova att köra den med mitt exempel men med följande main sub

<code>
Sub main()

Dim Xcoords() As Double
Dim Ycoords() As Double
ReDim Xcoords(6)
ReDim Ycoords(6)

Xcoords(0) = 0
Ycoords(0) = 0

Xcoords(1) = 0
Ycoords(1) = 9

Xcoords(2) = 5
Ycoords(2) = 9

Xcoords(3) = 5
Ycoords(3) = 7

Xcoords(4) = 2
Ycoords(4) = 7

Xcoords(5) = 5
Ycoords(5) = 5

Xcoords(6) = 5
Ycoords(6) = 0

Debug.Print calcArea(Xcoords, Ycoords) 'Resultatet blir 42 vilket är korrekt

End Sub
</code>


//
Janne

Ja, det verkar stämma; Har du en närmare förklaring till hur det går till i boken?

Har lite svårt att se precis hur formeln konstrueras, och varför den fungerar. Om man till exempel ökar alla y(i) med 1, så borde ju (Ys(i+1)+Ys(i)) öka med 2. Förklaringen måste då bli att alla "återvändande" kanter kommer påverkas lika mycket.

Fast om man ökar en skalning med absoluta belopp så tar det ju i allmänhet inte ut varandra. Troligtvis gör det det iom att den ökar sammanlagt lika mycket i en riktning som i motstående.

Funderar dock fortfarande på hur formeln konstruerats.

Jag har boken på jobbet men om jag inte kommer ihåg fel så stod formeln beskriven så här.


2A = SUM{ (X[i+1] - X[i]) * (Y[i+1] + Y[i])}


SUM ska egentligen vara ett sigma-tecken

Det var även med ett litet basicprogram (inte VB) som exempel. Boken jag har är en exempelbok jag har till en gammal programerbar räknare jag hade en gång i tiden (snart 20 år sedan) men det är många bra exempel i boken. Jag kan fixa mer text från boken när jag kommer till jobbet.


Jag sökte även på Dr. Maths hemsida www.drmath.com och hittade bl a följande.

Two dimensions: Polygons
The area of a polygon whose vertices are P1, P2, .., Pn is given by the expression

K = [(x1y2 + x2y3 + x3y4 + ... + xny1) - (x2y1 + x3y2 + x4y3 + ... + x1yn)]/2.


Här finns det också en del info
www.vb-helper.com/howto_polygon_area.html
www.efg2.com/Lab/Graphics/PolygonArea.htm
astronomy.swin.edu.au/~pbourke/geometry/polyarea
www.acm.org/jgt/papers/Sunday02/FastArea.html
mathworld.wolfram.com/ConvexPolygon.html

och mycket mer finns om man söker på polygon AND area

//
Janne

Har lagt upp ett omarbetat exempel på Polygonberäkning i FilArean

Tacksam om Ni mattesnille kan kolla om den räknar rätt. Programarkivet:Polygon beräkna Area

>Du har skrivit
>res+=(B.X-A.X)*(B.Y-A.Y);
>men det ska vara
>res+=(B.X-A.X)*(B.Y+A.Y);

Tack, det missade jag. Nu börjar jag förstå hur det fungerar, helt plötsligt. Om man skriver det så här :

A=(X[i+1] - X[i]) * (Y[i+1] + Y[i]) / 2

så ser man ju tydligt att detta är arean under linjen (ned till x-axeln), eftersom (Y[i+1] + Y[i]) / 2 motsvarar "medelhöjden" på linjen, eller om man så vill; y-värdet för mittpunkten på linjen. (X[i+1] - X[i]) motsvarar förstås bredden. (X[i+1] - X[i]) teckenvänds ju beroende på vilken koordinat som kommer först så areor som ligger "under" figuren kommer att subtraheras bort när hela polygonen har beräknats.

Arean av rektangeln nedan motsvarar exakt arean under den sneda linjen som representerar en linje i polygonen.

<pre>

Y ^
|
|
| /|
| / |
--/--- (Y[i+1] + Y[i]) / 2
|/ |
/ |
| |
| |
------------------> X

(X[i+1] - X[i])

</pre>

Toppen - problemet är ju löst ! Många tack till allas för en strålande insats.

Jag skall nu gå vidare med detta projektet och koppla in en diqitizer för att hämta koordinaterna via t.ex wintab-driver. Om någon redan har en lösning för detta så är jag tacksam för en kontakt. Kanske någon som vill göra en lösning - jag är beredd att betala för det.