Databases
StackOverflow2013
Postsdbo
POHow to intersect two polygons?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to intersect two polygons?
    primarykey
    data
    text
    <p>This seems non-trivial (it gets asked quite a lot on various forums), but I absolutely need this as a building block for a more complex algorithm.</p> <p><em>Input</em>: 2 polygons (A and B) in 2D, given as a list of edges <code>[(x0, y0, x1, y2), ...]</code> each. The points are represented by pairs of <code>double</code>s. I do not know if they are given clockwise, counter-clockwise or in any direction at all. I <em>do</em> know that they are not necessarily convex.</p> <p><em>Output</em>: 3 polygons representing A, B and the intersecting polygon AB. Either of which may be an empty (?) polygon, e.g. <code>null</code>.</p> <p><em>Hint for optimization</em>: These polygons represent room and floor boundaries. So the room boundary will normally fully intersect with the floor boundary, unless it belongs to another floor on the same plane (argh!).</p> <p>I'm kind of hoping someone has already done this in c# and will let me use their strategy/code, as what I have found so far on this problem is rather daunting.</p> <p><strong>EDIT</strong>: So it seems I'm not entirely chicken for feiling faint at the prospect of doing this. I would like to restate the desired output here, as this is a special case and might make computation simpler:</p> <p><em>Output</em>: First polygon minus all the intersecting bits, intersection polygons (plural is ok). I'm not really interested in the second polygon, just its intersection with the first.</p> <p><strong>EDIT2</strong>: I am currently using the <a href="http://www.cs.man.ac.uk/~toby/gpc/" rel="noreferrer">GPC (General Polygon Clipper)</a> library that makes this really easy!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USmvw
    1. USDaren Thomas
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to intersect two polygons?
      1. USLucas Jones
      1. VTFavorite
    2. VO
      singulars
      1. POHow to intersect two polygons?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to intersect two polygons?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is more complicated than you might think. How do you plan to represent the resulting shape? Bear in mind that the two inputs could (a) not intersect at all, (b) intersect partially, resulting in a convex or concave closed shape, (c) intersect wholly, resulting in a shape with TWO boundaries (i.e., donut) where you must find a way to represent the inside and outside of the shape.
      singulars
      1. POHow to intersect two polygons?
      1. USJon Seigel
    2. COIndeed, Jon is right. Your problem is not well-stated; the resulting set *might not be a polygon*, and therefore the output of the function ought not to be a polygon. What do you want to do in the case where the resulting shape is not connected? Imagine for example a C-shaped poly intersecting an I shaped poly, resulting in a colon.
      singulars
      1. POHow to intersect two polygons?
      1. USEric Lippert
    3. COthanks, will have to think hard about this and come up with a solution. Didn't think of it that way before...
      singulars
      1. POHow to intersect two polygons?
      1. USDaren Thomas
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload