Menu
I have a set of points in the plane and I want to find all convex polygons without including a point inside them.
For example I want to find all triangles, all four sized polygons, all four five sized polygons and so on until is possible to find them without including a point inside them.
In the image, row a corresponds to convex polygons of size 3. While column 1 and 2 show correct examples of what I want, column 3 shows a triangle including two points inside of it, which I dont want.
Rows b and c show examples of polygons of size 4 and 5.
b3 shows an example of a non convex polygon
I wonder if there is a function in MATLAB or any other language or if someone knows about an algorithm that can do it.
The algorithm could receive, beside the points, the size of the polygons to search, it would return all possibly correct polygons or empty if does not contain any polygon of that size.
I appreciate the help.
426
in = inpolygon( xq , yq , xv , yv ) returns in indicating if the query points specified by xq and yq are inside or on the edge of the polygon area defined by xv and yv . [ in , on ] = inpolygon( xq , yq , xv , yv ) also returns on indicating if the query points are on the edge of the polygon area.
Draw a horizontal line to the right of each point and extend it to infinity. Count the number of times the line intersects with polygon edges. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon.
Y = polyconf(p,X) evaluates the polynomial p at the values in X . p is a vector of coefficients in descending powers. [Y,DELTA] = polyconf(p,X,S) takes outputs p and S from polyfit and generates 95% prediction intervals Y ± DELTA for new observations at the values in X .
Step 1: Perform a Delaunay-Triangulation of the points.
Step 2:
151
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
