I hope this is the right forum to ask this question.

I want to experiment with procedurally generating some buildings, and as a first step I want to generate a 2D shape to use as a foundation for the building.

My plan would be to create a union of an arbitrary (but probably quite small) amount of shapes. It seems simple enough, but I wonder what algorithms there are available for breaking up such a union into simple line shapes? (that can be used to place walls)

  • $\begingroup$ Here is a good tutorial for OpenGL on how to create outlines for arbitrary objects using the stencil buffer: learnopengl -> stencil-testing. I think this technique can be translated to other APIs like DirectX or Vulkan. However, it is a bit more complicated than the answer of pmw1234 and probably too much for your use case. $\endgroup$
    – wychmaster
    Mar 28, 2021 at 11:34

1 Answer 1


Draw it twice, first time at full size and the color you want for the outline, draw it filled. The second time you draw it scaled down in both the x and y directions. The second time you draw it the color is the same as the background color, and draw it filled again. What will be left is the outline. Is this what you had in mind?

Per your comment, I add more info:

Generating an array of exterior edges can be done in a few ways. The easiest one to implement (but also the slowest) is to count the number polygons that share a given edge. The exterior is all the edges which only have a single polygon using that edge. And the two vertices that make up that edge become part of the array of "lines"( an actual line can be computed from two vertices). Also, this will count "holes" as part of the exterior. For example if a building surrounds a courtyard, then the courtyard would be counted as exterior.

This can be implemented by creating an array of unique vertices, then each polygon is formed by indexing into the list. (just like indexed triangle draw lists). Finally pick a single polygon off the list, takes its first edge, and search all the other polygons for that edge.

Another method using a doubly connected edge list is given here.

  • $\begingroup$ That would solve it as in it would draw the outline. Although in my case (kind of an edge case I guess) I want an array of lines that together form the outline $\endgroup$
    – munHunger
    Mar 29, 2021 at 5:56
  • $\begingroup$ I updated my answer per your comment. $\endgroup$
    – pmw1234
    Mar 29, 2021 at 14:47

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.