3

Have a bit of a tough question, which I realize there may not be an easy solution to. Figured what better place to ask.

I'm attempting to transform a polygon into a series of arbitrary points with arbitrary radii (circles!) that best represent the area covered by the polygon.

Minor over- and underflow is acceptable, as is circle-overlap, in hopes of achieving an efficient solution (i.e. fewest possible points, no gaps).

Ideally, a given poly would be represented by a few large circles, and several smaller circle on the perimeters.

Essentially, the problem is that I have a dynamic number of polys that get hit on geo-spatial queries given a specific gps coordinate, however, we are required to move to a system wherein I will not be able to utilize a point-within-poly query, but will have to rely on point-within-distance queries.

Hopefully someone has at least attempted something similar, and, if not, hopefully someone is willing to throw some ideas around!

Open to most languages, but this needs to be done programmatically!

Update per clarification in comments:

My point is that I feed indexes to the system and I get alerted when they are hit. I don't perform any queries on this system myself (black box), so I wouldn't have control enough to negate a query. That's the reason I need to transform the poly to a representation of points.

Improve this question
11
  • A slight generalization (that nevertheless may greatly streamline your queries) is to represent a polygon in terms of the set difference between two unions of circles: this lets you, for instance, start with a circle that wholly encloses the polygon and then remove circular regions from it (and add more back in) in order to approximate the polygon. This is a 2D version of constructive solid geometry whose only primitives are disks.
    – whuber
    Commented Aug 21, 2013 at 21:05
  • Well, as far as queries go, it would be a 3rd party system, which I have little control over. I'm only forced use point-with-radius as the index. As far as that system is concerned we aren't even dealing with polygons anymore. Point being, I'm not sure if this transformation would benefit me, as I am not able to utilize circle subtraction. Circles are only meant to represent distance in my problem. If that makes sense.
    – derrrrrick
    Commented Aug 21, 2013 at 21:39
  • Circle subtraction corresponds to negating a query: surely you can do that!
    – whuber
    Commented Aug 21, 2013 at 21:58
  • 1
    Haha, sorry, my point was that I feed indexes to the system and I get alerted when they are hit. I don't perform any queries on this system myself, so I wouldn't have control enough to negate a query. That's the reason I need to transform the poly to a representation of points in the first place :)
    – derrrrrick
    Commented Aug 21, 2013 at 22:01
  • 1
    It seems important to include that last information in the question itself so that readers understand what you need. Just to be clear: are you saying that your "indexes" consist of disks, that all you can do is get an alert when a probe point hits a disk (and presumably that alert identifies the disk(s) it hit), and you wish to construct a system to be alerted whenever a probe falls within an arbitrary polygon? Also, is it possible to pre-process probe point coordinates (such as projecting or unprojecting them) before they are sent to this system?
    – whuber
    Commented Aug 22, 2013 at 11:59

2 Answers 2

Reset to default
1

I found this article on Circle Packing. It has code that runs in the Processing Language. This might provide insight to help you code in your language of choice.R-Bloggers

Improve this answer
5
  • Have you given any thought to the extraordinarily large number of circles it such a solution would require?! You need, at a minimum, to modify this approach to allow circles to overlap.
    – whuber
    Commented Aug 22, 2013 at 17:22
  • Seems the OP doesn't need 100% coverage, some overlap and gap is acceptable. We don't know what the polygons are like either.
    – klewis
    Commented Aug 22, 2013 at 18:05
  • Nevertheless, circle packing (without overlap) is not the way to go: it will result in far more circles than are reasonable, no matter what the polygon's shape may be (unless the polygon is originally a disc).
    – whuber
    Commented Aug 22, 2013 at 19:42
  • 1
    Considered circle-packing already, and yes overlap is inherently necessary regardless of the solution. If a probe hits on a point of overlap, which of the two discs that hit is irrelevant.
    – derrrrrick
    Commented Aug 22, 2013 at 20:34
  • 1
    @klewis Thanks for your suggestion. Circle packing was the first route I pursued. The variability of poly shapes/sizes as well as the modifications necessary to include overlap, overflow, and necessary optimizations to use as few discs as possible, it didn't feel suitable.
    – derrrrrick
    Commented Aug 22, 2013 at 20:46
1

The buzzword IMO is Alpha Shapes and CGAL is the LIB you can get, but not easy to use?

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.