Determine if a polygon is concave or not (Views: 29)
Problem/Question/Abstract: How to determine if a polygon is concave or not Answer: I would check the area of 3 triangle points of the polygon. It should always be positive. Here is the code: function TriXYArea(PBegin, PMiddle, PEnd: TXYPoint): TDouble; begin TriXYArea := (PBegin.y + PMiddle.y) / 2 * (PMiddle.x - PBegin.X) + (PMiddle.y + PEnd.y) / 2 * (PEnd.x - PMiddle.X) + (PBegin.y + PEnd.y) / 2 * (PBegin.x - PEnd.X); end; If the polygon is clockwise oriented (the Gauss integral is positive), it should work like this: function IsConvex(Poly: array of TXYPoint); var i: Integer; First, Mid, Last: TXYPoint; begin Result := False; for i := 1 to High(Poly) do begin if i < High(Poly) then begin First := Poly[i - 1]; Mid := Poly[i]; Last := Poly[i + 1]; end else begin First := Poly[i - 1]; Mid := Poly[i]; Last := Poly[0]; end; if TriXYArea(First, Mid, Last) < 0 then exit; end; Result := True; end; If you only want to use the angle, here is the function: function TriXYAngle(PBegin, PMiddle, PEnd: TXYPoint): TDouble; var AC, ACX, ACG, TR: TDouble; begin TriXYAngle := 1E38; TR := TriXYArea(PBegin, PMiddle, PEnd); AC := TriXYCos(PBegin, PMiddle, PEnd); ACX := ArcCos(AC); ACG := ACX / Pi * 180; if Tr >= 0 then TriXYAngle := +ACG; if Tr < 0 then TriXYAngle := 360 - ACG; if AC = 1E38 then TriXYAngle := 1E38; end; |