0

I am searching for an algorithm which calculates, from a list of lines, the area a given point (P) is in. The lines are stored with x and y coordinates, the resulting area schould be stored as a polygon which may has holes in it.

Here two images to illustrate what I mean:

enter image description here

enter image description here

Many CAD applications use such algorithms to let the user hatch areas. I don't know how to call such a method so I don't really know what to search for.

Edit 1: To clearify what I'm looking for:

I don't need an algorithm to calculate the area of a polygon, I need an algorithm which returns the polygon which is formed by lines around P. If P is outside any possible polygon, the algorithm fails.

(I also edited the images)

Edit 2: I read the accepted answer of this possible duplicate and it seams I'm looking for a point location algorithm. I also stumpled across this site which does exactly explains what I'm looking for and more important it led me to the open-source CGAL library which provides the functionality to do such things. Point 4.6 of the CGAL manual gives an example how to use this library to form a region from a bunch of line segments.

Community
  • 1
  • 1
pwks
  • 71
  • 6
  • If you triangulate your polygon, then you have successfully decomposed it into a shape for which we know how to compute the area. All that remains is summing the areas of each triangle. This will involve finding the intersection points of the lines that bound `P`, so line-line intersection. – AndyG Mar 29 '14 at 18:38
  • I don't have a polygon which I could trianglate - I just have lines which may form a polygon. I need an algorithm which gives that polygon (if it exists). – pwks Mar 29 '14 at 18:44
  • 1
    I think this is a duplicate http://stackoverflow.com/questions/5851700/vector-graphics-flood-fill-algorithms – amdn Mar 29 '14 at 21:29
  • It's also a duplicate of http://stackoverflow.com/questions/13847933/locating-bounding-2d-entities/13850355. – Codie CodeMonkey Mar 31 '14 at 18:57
  • @Codie - It's a duplicate (with a great answer). Someone should mark my question as a duplicate. – pwks Apr 02 '14 at 19:00
  • Done, thanks for the complement about the answer. – Codie CodeMonkey Apr 02 '14 at 19:15

1 Answers1

1

One way to do it is to imagine a line from P to infinity. For each polygon test each edge to see if it crosses the line. Count up how many lines cross. If its even then the point is outside the polygon, if its odd then the point is inside the polygon.

This is a fairly standard mathematical result. If you want to get a little deeper into the subject have a look at https://en.wikipedia.org/wiki/Winding_number.

I did a fairly similar things earlier this week Detecting Regions Described by Lines on HTML5 Canvas this calculates a the polygon around a point given a set of lines. You can see a working example at the jsfiddle mentioned in the answer the difference is that it uses infinite mathematical lines rather than line segments, but it could easily be modified for this example.

An outline algorithm

First construct two data-structures one of line-segments one of intersection-points of line-segments. In each record which two lines give each intersection, so you can flip from one to the other. You can get this by pair-wise intersection of line-segments.

It might be easiest to cut the segments at the intersection points so each segment only have two solutions on it, one at each end. We assume we have done this.

Prune the data-structures, remove all line-segments with no intersections and only one segment - these cannot contribute.

Find possible starting lines. You could calculate the distance from each line to the point and take the smallest. You could check for intersections with a line from the point to infinity.

Walk around the polygon anti-clockwise. With you starting line find the most anti-clockwise end. At that point find the most anti-clockwise segment. Follow that and repeat. It may happen that closed loop is formed, in which case discard all the segments in the loop. Continue until you get back to the starting point.

Check if the polygon actually encloses the point. If so we are done. If not discard segments in the polygon and start again.

Community
  • 1
  • 1
Salix alba
  • 7,536
  • 2
  • 32
  • 38