CODEWITHSUNDEEP
javageometry
Shiladittya Chakraborty
Shiladittya Chakraborty

Reputation: 4418

Overlapping check between two polygon

I have a two polygon shape draw using HTML5 canvas(GWT). I have all the points for two polygon shape. Means I have the list of points for draw this type of polygon.

Below image showing two polygon intersect or overlapping each other. Now I am searching for a solution how to find two polygon "intersect or not" using java? I am using pure java programming without using any third library.

enter image description here

I have another issue. For explaining this issue I am attaching another image below.

enter image description here

This is the another case when one Polygon inside of another Polygon. In this scenario how to calculate minimum distance between two polygon in negative?

Upvotes: 1

Views: 836

Answers (2)

user1196549
user1196549

Reputation:

You can use the sweepline paradigm.

Consider the horizontal lines passing through the vertexes of either polygons. Two consecutive lines cut out slabs (trapezoids).

enter image description here

As the slabs are simple, convex polygons, checking them for intersection is straightforward: it suffices to detect overlap of the bases (mind the case where they form an X cross).

Now the whole process can be decomposed as

  • sorting the vertices of both polygons by increasing ordinates; for every vertex, remember to what polygon it belongs and what are its neighbors with a higher ordinate (none, one or two);

  • scanning the vertices by increasing ordinate, while maintaining a list of the edges that are intersected (it is called the active list). Every time you move to another vertex, update the active list;

  • testing the slabs for intersection.

Upvotes: 1

user4894180
user4894180

Reputation:

Using Postgis Api Using You get Information That Two Polygon intersect or not . Find Following Link As Reference http://www.postgis.net/docs/ST_Intersection.html

Upvotes: 2

Related Questions