[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Find the Concave Polygon

Posted on 2004-08-26
16
Medium Priority
?
355 Views
Last Modified: 2012-06-21
Hi Math Experts,

Here's my question

How do you calculate the concave boundary of a set of x,y coordinates that passes through the maximum number of points?

I was able to find lots of documentation online for finding the CONVEX boundary for a set of points, but I can't seem to find

anything on CONCAVE boundaries.

-CPOsosky

0
Comment
Question by:CPOsosky
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 6
  • 2
  • +1
16 Comments
 
LVL 13

Accepted Solution

by:
SteH earned 1200 total points
ID: 11904387
This might be because the convex hull is unambigiuos whereas the concave hull is not. You need to develop some ideas on when to use points lying inside the convex hull or which of them.

A first idea is to use a point inside if it is nearer to one of the boundary than the next on the boundary. Try expermenting.
0
 
LVL 84

Expert Comment

by:ozo
ID: 11904781
Couldn't you find a concave boundary that passes through all the points?
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11904789
This is basically a traveling salesman problem. If you find the shortest path through all the points, that path will necessarily be a polygon (i.e., no intersecting edges). I think you'll find numerous techniques for constructing such polygons if you look at algorithms for traveling salesman problems.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 13

Expert Comment

by:SteH
ID: 11904796
It might pass through all points and some even several times. But is this still a hull?
0
 
LVL 13

Expert Comment

by:SteH
ID: 11904805
A hull doesn't need to pass through all points. And it has to be closed unlike the traveling salesman.
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11904812
>> Couldn't you find a concave boundary that passes through all the points?

Yes. It's really just a TSP, as I just indicated in my other comment. Sometimes it's very frustrating to have other comments pop up while writing your own. I don't see a solution to that problem, however.
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11904841
Well, I'm talking about a closed trip traveling salesman problem. A minimum length cycle through all the points will necessarily be a polygon with no intersecting edges.
0
 
LVL 13

Expert Comment

by:SteH
ID: 11904896
@rjkimble
But a concave boundary or hull doesn't need to pass through all points. Just all points need to be within. And thats the problem for it: When to choose a point to be part of the boundary or just contained.
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11904999
Here's a link to a page about the traveling salesman problem with lots of other links:

http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html

@SteH

The original question is looking for a boundary that passes through the maximum number of points. Well, a shortest-length Hamiltonian circuit will necessarily be a polygon that passes through ALL the points (can't do better than that) and whose edges don't intersect. Traveling salesman problems are all about finding such cycles. Although finding a solution to a TSP is hard, finding Hamiltonian circuits whose edges don't intersect is quite straightforward. Such techniques abound in the literature of traveling salesman problems.
0
 
LVL 13

Expert Comment

by:SteH
ID: 11910360
I agree that if you want to find a polygon through all points it is a TSP, no doubt. And reading the question again I get some doubt about the meaning of it. The maximum number of points are definitly all. But why not saying through all points then, if there wasn't a choice to choose less. And if you are talking about boundaries it is not very intuitive to use all points for their boundary. And it contradicts what one would use the word boundary for, generally and not "math scienctificly" speaking.
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11913012
To tell the truth, I have no idea what CPOsosky is looking for. I hope he responds and gives a bit more detail. Nonetheless, it's pretty simple to create a polygon through all the points, and if that's what he's after, we have provided sufficient information for him to do so.
0
 
LVL 13

Expert Comment

by:SteH
ID: 11913052
I think he is looking for the green shape in http://ksfltd.com/products.htm#6. The yellow one is the convex hull and the green a concave one.
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11913161
Excellent reference. I see your point. If that's the case, I have no good ideas offhand. I suspect that's a fairly complicated problem.
0
 

Author Comment

by:CPOsosky
ID: 11913377
Steh's reference is exactly what I'm looking for.

The problem is the arbitrary shape of the concave polygon that leads to multiple solutions.

The left side of the green figure could have just as easily been drawn using several of the internal points,

creating several "dents" on the left side.

-CPOsosky
0
 
LVL 9

Expert Comment

by:rjkimble
ID: 11913494
I suspect that you have a bit of a challenge. My cursory search for concave hull returns only that reference, and those Russian mathematicians/programmers are pretty clever folks -- I suspect that the algorithm they're using hasn't been published anywhere, and reinventing it could be tricky.
0
 

Author Comment

by:CPOsosky
ID: 11931588
Since the consensus seems to be that there's no easy solution to this problem,

I'm going to go ahead and close out the question.

Points go to Steh for effort.

Thanks everyone!

-CPOsosky
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

656 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question