1

For my d3 project, I have a series of adjacent polygons, and I want to compute a new polygon that is the outside border of all the smaller polygons put together.

I have merged all the points of several connected polygons into one array to create one large polygon. But this includes all the interior edges as well as the exterior ones. I would like to remove the inner edges of this merged polygon, so that I only have a single shape representing the outside border of the area, but I can't find a proper algorithm that does this.

I found this, but it requires that the vertices of the polygon already be explicitly known; all I have is a set of points, with no distinction between outer and inner.

Once I've removed the inner points of the resulting polygon, I'd like to draw a line with "cardinal" interpolation around the outer points. This is why I must keep the integrity of the points rather than converting the polygon to arcs and using something like topojson.mesh!

Here's a screenshot to explain more clearly:

Screenshot

All of the vertex-points (corners of the red lines) of the green polygons were concatenated into one array of points. I want to figure out how to remove the inner points so that I can then apply a "cardinal" interpolated line around the remaining, outer points.

Community
  • 1
  • 1
ridicter
  • 69
  • 7
  • By "points" do you mean the black dots or the line segments endpoints? – xan Jan 11 '14 at 13:35
  • @Clive, and others I don't know why persons who put the question on hold complain about it, if I, the person who wrote the answer, and presumably know better the technical area in question, am not complaining? – VividD Jan 11 '14 at 13:36
  • @Qantas 94 Heavy, can you please reinstantiete this question, The reason for closing is inaccurate? Too many fine questions get closed. I answered this question in several paragraphs. It is very unlikely that this question will get more that lets say three answers. – VividD Jan 11 '14 at 13:50
  • @davidkonrad, could you please reinstantiete this question, the reason for closing looks inaccurate. Too many fine questions get closed. I answered this question in several paragraphs. It is very unlikely that this question will get more than, let's say, three answers. The quy needed direction what part of an API (this is D3 library API) he should take a look. – VividD Jan 11 '14 at 13:52
  • @xan, yes, good question, i see your point that line segment endpoints would look a kind of more appropriate choice here. – VividD Jan 11 '14 at 14:02
  • Anyway, it looks this question will be closed and deleted... Too bad... – VividD Jan 11 '14 at 14:23
  • @VividD The question is broad/unclear as it stands but can be improved if the asker can clarify. I don't get the sense it's looking for convex hull but it could be. Sounds more like connect-the-outer-points but I'm still not sure which points and which definition of outer. – xan Jan 11 '14 at 17:13
  • @xan, sorry, ignore the black dots – ridicter Jan 11 '14 at 17:19
  • This is definitely a valid D3 question, that got a good answer, which was accepted by the poster. I'll edit the question to make it more useful for people in the future searching for similar problems, but the hold should be removed. – AmeliaBR Jan 11 '14 at 17:49

1 Answers1

7

Mathematicians would say that you need to compute convex hull:

enter image description here

D3 offers interface for such algorithm.

Documentation is here. You have to read it carefully.

There is an example of usage here. Its not the same as you want, but you can get familiar with the interface by studying it.

You can probably find other examples of using D3 convex hull algorithm on the net.

Once you understand documentation and examples, you should be all set to apply your new knowledge to your problem.

If you have some other problem with code integration, you can open another question.

Hope this helps.

VividD
  • 10,456
  • 6
  • 64
  • 111
  • Thanks for the answer. I didn't even know where to start. Bummer that it was closed. – ridicter Jan 11 '14 at 17:12
  • Thanks, this doesn't deal with convex polygons, which I guess is significantly more complicated. But it gets me started. – ridicter Jan 12 '14 at 06:01
  • Search fore Polygon union on google, and here, and on math sites. – VividD Jan 13 '14 at 01:50
  • Also, maybe you can create a list of segments of all polygons, and remove ones that are mentioned more than once, and what remains is your union poligon. :) – VividD Jan 13 '14 at 01:51