Re: find polygon

(Regarding my solution of explicit polygon of perimiter of convex
hull of given set of points, not what the OP really wanted which
was pologon using *all* points which in most cases wouldn't be
perimeter of convex hull but would have some notches that intruded
into the convex hull, but nevermind:)
From: "Bartc" <b...@xxxxxxxxxx>
If you're allowed to delete vertices then there's an easier way:
delete all except three non-coincident points. That will give a
triangle.

In most cases the perimiter of the convex hull isn't a triangle, so
this won't solve my alterate problem. Never mind, you've proposed a
third problem, find *any* polygon that uses *some* of the given
points, nevermind that the other points are totally ignored.

As given there are several ways of connecting the points in this
example. How do you know your hexagon (which doesn't include all
the points) is the right one?

If the goal is to produce a polygon that matches the perimiter of
the convex hull and doesn't have any straight edges, then all
points interior to the convex hull must be deleted, and all points
interior to a straight edge of the convex hull perimeter must be
deleted, and I believe that's sufficient to guarantee exactly one
solution when not all points lie in a straight line (and no
solution at all when all points are colinear).

If the goal is to use *all* points, yet avoid straight angles at
vertices, see my other reply where I proposed ways to do that.

If you care neither about convex hull nor using all points, then of
course your solution is quick and dirty, providing that you can
find an efficient algorithm for finding a subset of three
non-colinear points. What algorithm do you propose for that?? How
about the first step of my convex-hull algorithm (other followup in
thread), namely finding most extreme point in each of the compass
directions, which in most cases yields three or four or even more
no-three-colinear points? When it yields only two points, anything
faster than brute force for finding a third point not colinear to
first two? Actually brute force from the start is probably fastest:
Pick two different points, and define an affine transformation that
moves the two points to both lie on the X axis. Then step through
the remaining points, applying that transformation to each, until
you find one whose transformation-result has nonzero Y coordinate.
.

Relevant Pages

  • Re: the smallest circle that can enclosed a convex hull
    ... The square of the radius is rho /4 - rho is to be maximize. ... compute the maximal in-circle of the polygonal convex hull of a set of points in the plane ... % Now think of it as a set of slack variables, ...
    (comp.soft-sys.matlab)
  • Another Difficult Combinatorial Geometry Problem
    ... in the plane is decomposable into a union of 3 or fewer convex sets. ... local non-convexity lie in the kernel of the set and in the planar, ... planar 3-convex sets. ... convex hull is a triangle or pentagon are relatively straightforward ...
    (sci.math.research)
  • Generalized convex perimeter of an n-d object
    ... One could define a "convex perimeter" of any bounded set of points S ... in the plane as p_2= the perimeter of the convex hull of S. ... Note that this generalized convex perimeter is a sort of dual to what ...
    (sci.math)
  • Re: convex hull
    ... > hull, then will the convex hull, defined in this manner, of S be convex ... What if S is the three-element set consiting of the vertices of a triangle? ...
    (sci.math)
  • Re: The Peace Quilt
    ... �How does the binding get put on all those concave and convex ... straight edges. ...
    (rec.crafts.textiles.quilting)