1
$\begingroup$

I have just discussed with student and he told me him task, and I think it is interesting. The task. There are file with points like:

Point0: x=1; y=4;
Point1: x=199; y=45;
Point2: x=42; y=333;
Point3: x=444; y=444;
...
PointN: x=nnn; y=mmm;

You should find polygons and draw them. Each polygon present as internal I mean something like this:

---------
| -----  |
| |    | |
| |----| | 
|        |
|--------|

And question what algorithm can you advice to use in this case? I understand this is from graph theory , but want opinion of other. Thanks.

  • 0
    Any polygon, or just quadrilaterals? FWIW, it's easy to figure out if three points determine a triangle.2010-12-08
  • 0
    Also, google "convex hull". Otherwise, I'm having trouble understanding your question. Do you want to find a polygon that contains all your points? Or a set of polygons? Or something else with other constraints?2010-12-08

5 Answers 5

2

Use the Convex Layers algorithm of Bernard Chazelle, which is optimal: $\mathcal{O}(n \log n)$ time.

See here: http://www.cs.princeton.edu/~chazelle/pubs/ConvexLayers.pdf

Here is a snapshot of part of the first page of the paper:

alt text

  • 0
    Oh, Thanks I try to learn this algorithm.2010-12-08
0

This is not an answer, since the problem statement is kind of vague, here is what I assume it is.Assuming a polygon immediately inside a polygon to be the child of the polygon (and similarly for parent)

maximize the number of points utilized to draw polygons such that

1. each polygon contains only one child polygon (no siblings)
2. each polygon has only one immediate parent (doesn't lie in the intersection of 2 or more parents)

Of course, outermost and innermost polygons do not need to satify conditions 2 and 1 respectively.

Again J.M.'s question is important - do you mean polygons or quadrilateral?

  • 0
    You know, you could have just edited this answer instead of posting another one...2010-12-08
  • 0
    now I know:) there no way to delete though.2010-12-08
0

If what I posted below is a correct assumption, then you could think of a solution on these lines.

  1. find centroid of all points in set S (expensive)
  2. obtain farthest points from the centroid.
  3. use these to draw the outermost polygon.
  4. remove from this points from set S
  5. repeat step 1 until (no more inner polygons can be drawn)
0

There are several algorithms for curve reconstruction from point samples. See for instance http://www.cse.ohio-state.edu/~tamaldey/curverecon.htm and http://valis.cs.uiuc.edu/~sariel/research/CG/applets/Crust/Crust.html

0

I will use Convex_hull

Thanks to all for answers.

  • 0
    There is something better than Convex hull (which is $\mathcal{O}(n^2 \log n)$, while optimal is $\mathcal{O}(n \log n)$) in the worst case. See my answer.2010-12-08