Give a simple polygon, polygons are arranged in a clockwise or counterclockwise
The internal equivalent distance is reduced or the exterior amplification polygon is actually made from a series of parallel sides that are parallel to a series, and the distance is a line segment of L.
The periphery is the original polygon, and the inner side is a new polygon.
Algorithm structure
Adjacent two edges, L1 and L2 of the polygon, hand over the PI point
Do parallel to L1 and L2, the parallel line spacing is l, and is located on the two edges of the polygon, hand in Qi
We have to calculate the coordinates of Qi
Figure,
PIQi vector, obviously equal to the two adjacent elements of the parallel quadranggery and the sum
The direction of V1 and V2 vector is the direction in which the side of the polygon is formed, and it can be represented by the vertices.
The length of V1 and V2 vectors is the same, equal to the division of the SIN value of the parallel line spacing L and the two line segment angles.
That is: Qi = Pi (V1 V2)
Qi = pi l / sin θ * (Normalize (V2) NORMALIZE (V1))
SIN θ = | v1 × v2 | / | v1 | / | v2 |
calculation steps:
(1) Get the polygonal vertex array PLIST;
(2) calculate DPLIST [VI 1-Vi];
(3), unitification NormalizedPlist, get NDP [DPI]; (store with the same array)
⑷, sinα = DP (i 1) x dp (i);
⑸, qi = pi d / sinα (NDPI 1-NDPI)
⑹, this one can calculate all vertices.
Note that the order of the NDPI 1-NDPI can be obtained in the order of the NDPI 1-NDPI.
The code implemented with SWIFT is as follows, and it can be run directly in Playground.
Import Foundation
Class Point2d {
Var x: double = 0
Var Y: double = 0
Init (_ x: double, _ y: double) {Self.x = x; self.y = y}
INIT (Point: Point2D) {x = Point.x; y = point.y}
}
// Func = (inout Left: Point2D, Right: Point2D) {Left.x = Right.x; Left.y = Right.y;}
Func (Left: Point2D, Right: Point2D) -> Point2D {RTURN POINT2D (Left.x Right.x, Left.y Right.y)}
Func - (Left: Point2D, Right: Point2D) -> Point2D {Return Point2d (Left.x-Right.x, Left.y-right.y)}
Func * (Left: Point2D, Right: Point2D) -> Double {Return Left.x * Right.x Left.y * right.y}
Func * (Left: Point2D, Value: double) -> Point2D {return Point2D (Left.x * Value, Left.y * value)}
// Custom vector diagram operation symbol,
INFIX OPERATOR ** {}
Func ** (Left: Point2D, Right: Point2D) -> Double {return left.x * right.y - left.y * right.x}
VAR PLIST = [POINT2D] // Original vertex coordinates, initialization assignment var DPLIST = [Point2D] // side vector DPLIST [i 1] - dplist [i] is calculated in the initdplist function in the initdplist function.
VAR ndplist = [point2d] // Unit weight side vector, calculate the skin material after the InitndPlist function, when actually use, you can save them with DPLIST
VAR newlist = [Point2D] // New Polyline vertices, in the compute function, assign
// Initialize the vertex queue
Func initplist () {
PLIST = [Point2D (0, 0),
Point2D (0,100),
Point2D (100, 100),
Point2D (50, 50),
Point2D (100, 0),
]
}
// Initialize DPLIST two vertices
Func initdplist () -> void {
Print ("Calculate DPLIST")
Var Index: INT
For index = 0; index DPList.Append (PLIST [INDEX == PLIST.COUNT-1? 0: INDEX 1] -pl [index]); Print ("DPLIST [\ (index)] = (\ (DPLIST [INDEX] .x), \ (dplist [index] .y)") } } // Initialize NDPLIST, unitization two vertical vessels Func InitndPlist () -> void { Print ("Start Calculation NDPLIST") Var index = 0; For; Index Ndplist.append (dplist [index] * (1.0 / sqrt (dplist [index] * dplist [index]))); Print ("NDPLIST [\ (index)] = (\ (ndplist [index] .x), \ (ndplist [index] .y)") } } / / Calculate the new vertices, pay attention to the parameter is negatively contracted inward, it is exporting Func ComputeLine (dist: double) -> void { Print ("Start Calculation of New Vertices") Var index = 0 Let count = plist.count; For; Index Var Point: Point2D Let StartIndex = index == 0? count-1: index-1 Let endIndex = index Let sina = ndplist [startIndex] ** ndplist [endindex] Letle length = dist / sina Let Vector = ndplist [endindex] -ndplist [startIndex] Point = PLIST [INDEX] Vector * Length NewList.Append (Point); Print ("NewList [\ (index)] = (\ (Point.x), \ (Point.y))") } } // The order of the entire algorithm Func Run () -> void { INITPLIST (); Initdplist () Initndplist () ComputeLine (-5) / / negative number is contraced, positive number is expansion. Need to note that the algorithm itself does not detect how much the contraction will be intersected, that is not a demonstration intention of this code. } Run ()
