Please refer to the strawberry fields problem on this page AnalysisThink of each strawberry as a point on an XY plane. Then we can find out the concave hull which is the smallest polygon that contains all the ponits or strawberries. Assume for some given strawberry field, the concave hull is something like this Now walk through the vertices of the concave hull in succsession. For each pair of successive vertexes, find the point of intersection that is outside the concave hull. This will now result in an updated polygon as shown. Finally pick the largest edge and from the two edges, one of which succeeds the largest edge and the other which precedes it, pick the larger one. Form a rectangle between the largest edge and the selected succeessive or preceding edge. This is depicted here. Now choose all points of the concave polygon that lie outside the rectangle that we just derived. Add to this set of points, a point that would have been derived as a result of deriving the rectangle. Repeat the process of forming the rectangle till all points of concave polygon are covered. For the sample, the final result is shown. AlgorithmThe steps of the algorithm are enumerated below.
0 Comments
|
MeI am a 3D graphics software engineer. Archives
December 2011
Categories
All
|