Finding intersection between two polygons

limzykenneth

I'm looking for an algorithm to find the intersecting polygon between two polygons, given their vertices' coordinates. The algorithm should return a new set of coordinates belonging to the intersecting polygon consisting of the intersection points and the points inside each shape.

I have only gotten as far as getting the coordinates (finding the intersection and finding which points from one shape resides in the other). The problem I'm facing now is that I got all these points but I don't know their order (I find the intersecting points first then the contained ones but not sure how to discern their order).

I wonder if anyone knew any sets of algorithm that I can use that can achieve what I want or maybe there's a library I can look at. Javascript is preferred but any other languages are fine, I don't mind translating as I'm just looking for the right algorithm.

Thanks in advance.

kfrajer

If you have a triangle and a square and only one triangle's vertice is inside the other figure, then you want this vertex and the two intersections, right? This assumes none of the square vertices are inside the triangle.

For the polygons, is there a restriction for them to be regular? Number of vertices limit or any number? Not familiar with any specific algorithm but just good points to consider in this quest...

Kf

limzykenneth

No assumptions about the polygons are made, ie. the polygons can have any number of vertices (>3 obviously), they may or may not be regular, and they may intersect in any orientation or not at all. That is because the polygons are to be drawn by a user by specifying points so anything can happen.

There is however one restriction which I'm not sure if relevant or not: any lines of the polygon cannot intersect any other lines of the same polygon. I have additional checks for that so it won't happen.

koogs

the intersecting polygon between two polygons

there might be more than one intersection!

kfrajer

I can imagine more like finding one intersecting point and then walking around the inner edge starting from this intersection to describe this polygon. There was some code or an attempt done by @Chrisir recently to try to identify random irregular shapes from a picture. The project shifted to python.... I didn't explore the full solution but it is more of an idea.

Irregular shapes aka. anything drawn by an user... very challenging. If I were a user testing your program, I could do a little 6 vertex start or a spiral (a rectangle coiled into itself) of a 100 points.

Kf

Chrisir

Hm.

When you have a green shape and a second blue shape. Now when you simulate a flood fill on a hidden canvas eg for the blue you can detect where the canvas is already green before making this pixel blue....

Those is your intersection

quark

This article looks promising since it will work with bot convex and concave polygons.

limzykenneth

Thanks all for the response!

I eventually did find something that I can use that does exactly what I want. The solution is here and a demo is available here

This implementation that I found will return all polygons that are result of the intersections and also work when shapes self intersect. The only downside is if the polygons have a lot of vertices, say maybe >20, it slows down significantly.

For now I can just simplify the user's drawing so I can use it but hopefully I can optimize that code or even run it on the GPU, but that's a project for another day. ;)

quark

Here is another JS library you might try

jeremydouglass

If the goal is a vector based representation of the intersection (e.g. for continued editing) them the algorithm you shared seems like the best solution.

However, if the goal is just visually highlight the intersections, then that js-intersect demo is massively inefficient at high point counts (as you observed), especially if it is re-running every time a point is added to ongoing drawing / editing. By contrast, masking is basically instantaneous regardless of the number of points, because it is a single linear pixel pass. Render the two shapes to separate layers, then create an intersection mask, then colorize the mask when you draw it as a third layer.

So for example if a free drawing creates a dozen intersection areas, you could display them with masking in real time (no lag), then allow clicking on a mask area to trigger the intersect algorithm only for that mask zone (e.g. flood fill algorithm) -- which then gives you the selected intersect-polygon only when you need it. But these kinds of optimizations might only matter if you have lots and lots of intersections and if real-time performance is an issue.

limzykenneth

@jeremydouglass That is exactly what I observed, at high point count real time performance is an issue. I'm currently exploring moving away from real time calculation and do one off calculations instead.

That being said, I don't really need the points themselves so I'm seriously considering the intersection mask method, the only thing I'm worried about that method is memory based bottle neck. I'm already drawing to two 1024x1024 p5.Graphics, it sounds like I may need to create additional 1024x1024 p5.Graphics for each polygon that is drawn. That may crash the app on mobile devices because for previous versions my p5.Graphics size was 2048x2048 and that crash left and right on me (I have other computation intensive stuff on the page).

jeremydouglass

additional 1024x1024 p5.Graphics for each polygon that is drawn

Interesting! Without knowing more about what your application is for and how it works I can't be sure -- how many polygons there are, and what info you need to recover from and intersection, but --

Couldn't you just loop through your polygons, render one into PGraphics buffer, then map that buffer onto PGraphics intersectionMap (eg with blendMode(ADD)), clear the buffer, and move on to the next polygon in the loop? When the loop is done you have the a single flat map of all intersections.

If you need intersection ids, another approach that would work for up to 32 overlapping polygons (or 64 if you use longs) is to push each polygon mask into a 2D array of ints (such as pixels[]) as a bit channel - bit 0, 1, 2 etc. correspond to shape 0, 1, 2 etc. Now you can check your intersect map for any shape (bit channel), or for the intersection count at any given location (total number of on bits in that int) using Integer.bitCount(int).

quark

The problem of using images is that the accuracy of an intersection coordinates is limited to the screen resolution. Also if you want the shape of the intersection you need not just the intersection coordinates but a list of them in order, which you won't get from a pixel array.

If you need the actual coordinates to calculate the intersection shape or to modify the original shapes then the only practical way is using mathematics.

jeremydouglass

I agree that point math is necessary to get a new editable polygon, @quark -- I was suggesting keeping an intersection map for display and as a first-pass optimization for display and selection performance.

Assuming that:

1. the user has drawn two or more polygons and is clicking to select an intersection, which will then become another polygon
2. calculating the intersections of many polygons all the time in the background is expensive / slow
3. during live drawing the intersection list needs to be constantly updated so that they can be:
   • displayed live on the screen
   • selected.

Pixel mapping might be one way to separate the display problem (which can be fast) and the selection problem, and narrow the selection problem (to make it faster):

1. make intersection display cheap and fast
2. when an intersection-selection must be generated as a new polygon using mathematics, make that a targeted operation that runs on as few polygons as possible, and only during the click frame.

So it might run something like this:

1. every frame of shape editing the sketch rebuilds a fast, cheap pixel-based intersection map at screen resolution
2. user clicks one of the displayed intersections to edit it as a new polygon
3. the map tells us that the click point is contained by polygon 3 and 40, and that region can be highlighted instantly -- cheaper than looping through 40 polygons and running "contains" on the selection point
4. the polygon intersection algorithm runs for only on 3 and 40 based on their point data and generates a new polygon.

limzykenneth

Couldn't you just loop through your polygons, render one into PGraphics buffer, then map that buffer onto PGraphics intersectionMap (eg with blendMode(ADD)), clear the buffer, and move on to the next polygon in the loop? When the loop is done you have the a single flat map of all intersections.

@jeremydouglass Can you elaborate on that a bit? When drawing with blendMode(ADD), what fill should I be using? I thought blendMode(ADD) would just add the color values of each pixels together and clamp them to 255?

One detail I didn't mentioned before is that the reason I want the intersections is because I wanted to make sure that the user's drawing is not overlapping each other too many times. I tried implementing pixel masking with just one pre-initialized buffer to avoid object creation overhead but hit a dead end when trying to detect if there are intersections in said buffer.

What I did was to iterate the pixels array and try finding a non 0 value indicating an existing pixel thus existing intersection but the sheer size of the pixels array make this impossible. Having the user click on the intersection is not really an option and this is an automated check so it should run without user interaction.

@quark I've also tried going back to optimise the intersection library I found and managed to shave off several miliseconds of each points by not calculating some square roots but hit another performance bottle neck when calculating arc tangents. If I can somehow improve that arc tangents' speed, I may be in for a shot for using pure maths only for realtime.

quark

There is however one restriction which am not sure if relevant or not: any lines of the polygon cannot intersect any other lines of the same polygon. I have additional checks for that so it won't happen.

This is incredibly important. Working with non self-intersecting shapes makes for much simpler maths.

How many shapes?
How many vertices per shape?

Approximate values are good enough.

How is the shape /vertex data, stored?

Can you pan and/or zoom the image in between creating shapes?

It should not be necessary to use square roots or arctangents to calculate the actual intersections so they must be used for something else.

limzykenneth

@quark It's not going to be unrestricted but at this point I can't say how many shapes or vertices yet. Approximately maybe 15 shapes and average of 10 points each (differs for each shape).

The vertex data are stored as an array of objects in the form:

[{
  x: 1.002,
  y: 4.815
},{
  ...
}]

No panning or zooming.

I've just traced the call stack and found square roots and arc tangents. They seemed like some polar coordinates conversion of some sorts, didn't decipher the algorithm myself.

jeremydouglass

Okay, I misunderstood -- thought this was a live drawing application, like Illustrator, and your goal was e.g. to draw two shapes, then make any intersecting region editable as a third shape. Clearly not.

Could you briefly explain what is happening? There are several (1? 2? 20?) polygons already drawn in the past by the user on a very large (HD? 4K?) display surface and the user is now clicking points to build a new polygon, but after closing the new polygon (or during drawing?) then a check routine runs to confirm that there are not more than n (2? 5?) intersection regions with any previous polygon (or just the last one?) -- and if the check fails then the polygon is... (deleted?).

limzykenneth

@jeremydouglass Sorry it's a bit hard to explain clearly and unfortunately due to a NDA I cannot show the app itself. I'll attempt to clear up how the app works in the simplest form.

We start with a square canvas of arbitrary size (final size determined by window size). The user then can click on the canvas to create a new vertex and each time they click, a new vertex is added to the shape.

When the user double clicks or click back at the original point, the shape is "ended" and the next click starts a new shape.

That's the drawing part simplified. There are other modes which lets the user drag and draw while the app simplify as it goes but the shape structure is the same: an array of vertices.

Next, either when creating a new vertex or when "ending" a shape, an algorithm will run and determine if the shape (with the new vertex or with the ending line) is self intersecting, if so reject the step (don't add the new vertex or don't "end" the shape).

All the above are done and running smoothly. The user will then rinse and repeat creating however many shapes that's allowed, which will be decide later so just assume a good amount ~15-20 for now.

What I want to implement now is as the user is drawing, their shapes could be overlapping another shape they have already drawn on the canvas, however, I don't want them to overlap each other for more than 4 times. If the new vertex creates a shape that creates an overlap with 4 other shapes, ie. overlap 5 times, I want the overlap to be drawn on canvas in red to let the user know where the shape overlapped more than 4 times. The user will then be unable to finish the shape by double clicking or clicking on the first point.

jeremydouglass

When you say "for more than four times" do you mean...?

1. more than for different regions (pentagon is overlapping a different rectangle on each corner)
2. up a depth of four (like one corner of a square is overlapping a stack of four other squares all in the same place)

limzykenneth

@jeremydouglass 2

MuddyGardener

@jeremydouglass I am new to Processing and am trying to understand your initial suggestion, from your July 28th post above

Render the two shapes to separate layers, then create an intersection mask, then colorize the mask when you draw it as a third layer.

Here's my puzzle. As far as I have learned (which is not very far), there isn't a direct layer concept in Processing, in the same way as there is in Photoshop or GIMP. And when I search this site for definitions about layers, I don't get any hits that seem to help.

Are you meaning that you create a pixel array (or something like that), that acts as a layer, and you compare it with the story-so-far 'layer' via some value logic to determine the intersection? That makes sense to me but I'm just wondering if there is a direct layer concept that I haven't run into yet.

Can you advise what concepts I should learn about to make sure I've understood what you've said?

tx

jeremydouglass

@MuddyGardener -- "layer" in this case is a just a pixel buffer -- either a PImage if you just want to manipulate pixel data, or a PGraphics if you want to draw to it. You can then display PGraphics pg with image(pg, 0, 0);. A PGraphics initializes as transparent. If you create one that is the same size as your sketch screen, drawing into it and then using image() to display it on top of other content acts something like a Photoshop layer.

You can show/ hide layers by controlling display (for example: if(visible){ image(pg, 0, 0); } ). If you want to create a stack of layers, you can create a PImage[] layers or PGraphics[] layers array -- or an ArrayList<PGraphics> layers -- and then loop through them in draw, displaying each one. Use an array of flags to control complex show/hide behaviors.

If you want even more layer properties, such as per-layer data-independent transparency, tint, attaching filters, or independent orientation settings etc. etc., then you should create a Layer class that packages this metadata up with a PGraphics pg, create a Layer[] layers stack or ArrayList<Layer> layers. To display the layers, loop through the array in your draw loop, calling image(layers[i].pg, 0, 0) -- or your class display method of choice if you have written one, like image(layers[i].display(), 0, 0)

jeremydouglass

ps @limzykenneth I hope that you solved your problem from August!

If so, I'd be curious whether the approach of maintaining a single flat height map of the combined shapes in a pixel buffer worked out for you, or if there was a more performant / elegant approach.

MuddyGardener

thanks @jeremydouglass - makes sense!