Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Basically the problem boils down to:<BR> 1) Determine all of the polygons enclosing some space which don't contain any other polygon. In your above example, you have 3 shapes/cycles/polygons that do not contain any others: the quadrilateral containing S, the quadrilateral containing E, and the triangle below the 2 of them. <BR> 2) Determine if S and E are on opposite inside/outside of any of these polygons.<BR></p> <p>For part 1, you have to build a graph:</p> <p>Create an array of intersection points of your given line, this is N^2. Remember which 2 lines each intersection point came from. These intersection points are the vertexes of your graph.</p> <p>Two vertexes are "connected" if they are from the same line and there is no other intersection point between them. Don't rely on the accuracy of floating point to determine this, obviously.</p> <p>Now you wish to find the polygons in your layout. A graph may in general contain an exponential number of cycles. However, each edge may only border 2 "inner" polygons, so we are only interested in a polynomial subset of the cycles. So pick an edge, then find the next edge in the polygon, and keep repeating until you get back to where you started or determine that the first edge wasn't part of a polygon.</p> <p>So suppose you are coming from edge E = (U, V), and want to find the next edge in the polygon (sharing the same vertex V).<BR> 1) Create a vector T as U - V.<BR> 2) Create the set of edges A that are adjacent to vertex V. Remove E from that set.<BR> 3) If the set is empty, then the edge isn't part of a polygon.<BR> 4) For each edge (Q, V) in A, construct a vector R as Q - V. (Remember Q and V represent points in the 2D plane).<BR> 5) Normalize R : divide it by it's length to create a vector of length 1. <BR> 6) Determine CrossProductValue(T, R).<BR> 7) The edge in A with the least CrossProductValue is the next edge in one the adjacent polygons. The edge in A with the largest CrossProductValue is the next edge in the other polygon.<BR></p> <pre><code>CrossProductChecker(2D T, 2D R) { return (T.x*R.y - T.y*R.x); // cross product for 2 dimensions } </code></pre> <p>So use this to find your polygons. Lookup the relation between cross products and sinusoids to get an idea how this works.</p> <p>============</p> <p>Now that you have all of your polygons, all there is to do is check if there is one that S is inside of and E is outside of, or the other way around.</p> <p>The easy way to do this is to draw a line from S to E. If it intersects any polygon (cycle from above) an even number of times, they are both inside or both outside the polygon so keep checking.</p> <p>If the line intersects a cycle an odd number of times, then one is inside the polygon and one is outside, so you can say that there is no path.</p>
    singulars
    1. This table or related slice is empty.
    1. POCheck connection between two points on 2D plane
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDanielV
    1. USDanielV
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POCheck connection between two points on 2D plane
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COSo it seems your way to build polygons will also be NP. Am I correct? If not - please, clarify
      singulars
      1. PO
      1. USAlma Do
    2. COPlease use the term "superpolynomial". Anyway, we aren't building every polygon. We are only building polygons that don't contain another, the "inner" polygons. Since each edge can only touch 2 of these inner polygons, and there is a polynomial number of edges O(N^2), then there are a polynomial number of inner polygons.
      singulars
      1. PO
      1. USDanielV
 

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