2
$\begingroup$

I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example:

Example Paths

Basics

  • 4 separate paths (A,B,C,D) which are a collection of vertices (A1,A2,...)
  • Area desired is represented by green

Edge Cases

  • As shown with B, a path might have segments that don't contribute to a filled shape
  • As shown with C, a path might be completely enclosed by other paths and therefore should basically be ignored.
  • As shown with D, paths may create independent shapes
  • As shown with A and B, it should be a union of all the shapes

My first question is if an algorithm for this already exists. If it does, it would save me a lot of effort :). I tried searching around but I don't even know how to describe this problem concisely.

Assuming one doesn't exist for this exact purpose I have to move on to figuring it out myself. I'm assuming the right data structure for the job is a graph. I'm thinking I will add points for each intersection (highlighted in red) as I insert paths into the graph.

Then "all I need" is an algorithm for tracing around the outside of each shape because calculating the area of those irregular polygons will be simple. Does something like that already exist? My primary hangups when I think about how to do this are:

  • What vertex do I "start" at?
  • How do I account for multiple shapes (D as well as A,B,C)?
  • How do I account for the parts of shapes like formed by A1,A5,A5 where I'll be visiting that intersection point multiple times?

I'm not necessarily looking for a complete solution, I'd love thoughts on if you think I'm approaching this the best way so far and if you have any ideas/suggestions on how to achieve this.

Thanks in advance!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The Shoelace formula gives your the area. $\endgroup$
    – plop
    Aug 8, 2020 at 19:20
  • $\begingroup$ (@plop well, the example is not a simple polygon.) $\endgroup$
    – greybeard
    Aug 9, 2020 at 1:26
  • $\begingroup$ There is line sweep. $\endgroup$
    – greybeard
    Aug 9, 2020 at 1:30
  • $\begingroup$ It's unlikely you'll find an algorithm for this problem, because it's a multistep one... At first you need to find all intersection points and split all the edges, which contain them. Then you'll need to find all simple polygons, then check their pairwise containment. Also this is not graph theory problem, I'd say it's computational geometry problem $\endgroup$
    – HEKTO
    Aug 9, 2020 at 22:32

2 Answers 2

Reset to default
1
$\begingroup$

With the help from some of the hints on this post and elsewhere, I came up with a solution.

The Data Structure

The data structure is relatively simple. It is a collection of Nodes that are connected by Edges.

The Data Structure

Each node stores the coordinates of where it lies in space and each segment is represented by two directional edges, one in each direction. Each intersection of line segments is broken up with a new Node. Note the coordinates of the intersections are left off the diagram but are included in the data structure.

The Algorithm

Find All Cycles

    1. Pick any edge and choose the next edge that is closest to clockwise from the edge you entered the node on.
    1. Record whether the angle between the connecting edges is a reflex angle (> 180 degrees) or not.
    1. Record the series of nodes visited
    1. Mark the edge as used
    1. Follow that new edge to the next node and repeat until reaching the first node again.

At the end, the cycle will have the points that it is composed of and a count of reflex and non-reflex angles. If there are more reflex angles, it is considered to be an outside cycle and is thrown out. Otherwise, it is included in a preliminary list of polygons to include in the final result.

Repeat this cycle finding process until every edge has been used.

Filter Polygons

Filter out any resulting polygons that are entirely inside another. This can be done by testing only the first point of one polygon to see if it's inside another. That's because we know we will never have any intersecting polygons.

Calculate the Area of Each Remaining Polygon

At this point, we just need to calculate the area of each polygon and add them together for our solution.

Some Details

It's important to note that in the case where we get to a node and the only remaining edge is the returning edge, it counts as a 360 degree angle and therefore a reflex angle.

Also, it's important to note that each angle of each cycle must be counted towards the reflex and non-reflex count, including the first and last. Otherwise, a plus sign arrangement of simple paths (+) will result in a valid polygon.

Example

All of the cycles from my original example are represented here:

enter image description here

For more information on my process and a walk through of the algorithm, you can see my case study.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is good self-answer, but it's not about Computer Science. People here used to care a lot about computational complexity, and you don't talk about it. For example, the famous Bentley-Ottmann algorithm (en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm) can be used to compute all the intersection points... That's why you got some comments about sweeping. $\endgroup$
    – HEKTO
    Aug 14, 2020 at 5:37
  • $\begingroup$ I did consider determining the computational complexity of it, but it isn't particularly relevant for me right now. I definitely appreciate the link to the Bentley-Ottmann algorithm, it will definitely come in handy if performance becomes a problem for me. $\endgroup$
    – drewag
    Aug 14, 2020 at 6:01
  • $\begingroup$ Also, @HEKTO side note, I don't know why you have to say it's not computer science. Perhaps your goal is to keep people like me (definitely more of an engineer than a scientist) off this stack exchange? It certainly doesn't make me feel welcome. I think I put a lot of effort into this post, especially considering very few people will ever see it. I'm sorry it doesn't fit your narrow definition of computer science. $\endgroup$
    – drewag
    Aug 14, 2020 at 6:03
  • $\begingroup$ I'm trying to help you, and I've actually upvoted your question. A notion of a problem in CS is more narrow than in engineering - it should be minimal, self-contained, formalized etc. There is a number of such subproblems, which can be extracted from your question - ideally we should research them separately. $\endgroup$
    – HEKTO
    Aug 14, 2020 at 16:41
  • $\begingroup$ @HEKTO: IMO, this is a narrow view of computer science. The Weiler-Atherton algorithm and variants certainly deserve a chapter in a Computational Geometry book. Hopefully, Computer Science sometimes cares about solutions that are implementable and not just of theoretical interest. $\endgroup$
    – user16034
    May 4, 2022 at 7:32
0
$\begingroup$

If the polygons are overlapping, you can't spare a union algorithm that will "merge" the overlaps. https://en.wikipedia.org/wiki/Boolean_operations_on_polygons. This involves the detection of intersections between the sides and a topological reorganization. Nothing really easy.

It is likely that an simpler technique is possible if you consider decomposing the domain in slices defined by horizontal lines though all vertices (this takes a sort on the vertex ordinates). Also consider the lines through the intersections. These can be obtained by a standard line intersection algorithm (https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm). Then the problem reduces to the union of trapezia in every slice, with no intersecting sides. It is easy to merge two overlapping trapezia into one.

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ It seems you won't be able to calculate the arrangement area looking only at each horizontal slice locally. An example - a simple (not self-intersecting) polyline (not a polygon), which should have zero area (according to the OP picture). $\endgroup$
    – HEKTO
    May 5, 2022 at 0:42
  • $\begingroup$ @HEKTO: that's right. I worked with assumption of polygons. $\endgroup$
    – user16034
    May 5, 2022 at 6:30

Your Answer

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

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