The input file which contains the data of the polygons is typed as follows.
Data entered are shown inside the braces
Enter 4 if there are no voids
(3) <<-- means following
data is hole.
Enter coordinates of 2 points
( 2 3 10 6)
Enter 1 if the hole is not closed
(1)
Again enter 2 points
(10 6 2 8)
Enter 1 if not closed
(1)
Again enter 2 points
(2 8 2 3) <<-- means hole is closed
Enter 1 if not closed
(2)
Enter 1 if you want to enter
further holes' data
(2) <<-- means no further holes
The following is for the outline
Enter the points of the line of
first edge
(1 1 11 6)
Enter 1 if outline is not closed
(1)
Enter second edge
(11 6 1 12)
Enter 1 if outline is not closed
(1)
Enter the next edge
(1 12 1 1) <<-- means
polygon is closed
Enter 1 if it is not closed
(2)
This same procedure is followed
for the second polygon also.
The following picture is the polygon represented
As described in the "Logic behind
this project"
the heart of this logic is Point
Membership Classification and hence Line
Membership classification .
Each edge is broken first according to where they
get intersected with the edges
of the other polygons.Each linked list node
of the one supporting the polygon
is given flags such as void or line,voidonline,linestatus etc.,
For each edge the LMC is done as to find whether
that line segment is
"in(0) or on(1 for same sense & -1 for opposite sense)
or out(2)" of the other polygon.
Finally edge picking is done as to chose what edge for what operation.
picking all 2s and 1s if that edge is not onon with an edge of a hole and picking all -1s for those edges which are onon with hole's edge is for UNION
In the above if we replace 2 by 0 we get the edges for INTERSECTION
Picking all those edges of linestatus 2/0 of one polygon and 0/2 for the other polygon and all 1s if that edge is onon with edge of hole and picking those with -1s if they are not onon with edge of hole gives firstpolygon-secondpolygon/secondpolygon-firstpolygon in the order specified above.
| To Operate on | A union B | A int B | A - B | B-A | |
 |
 |
 |
 |
 | |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
|
---->> The code is written in C language which uses a linked lists of linked lists. So this supports any type of polygons with any type of configurations.
---->> Every edge of the polygon and its all statusses are not lost so that it is very easy to stictch.
---->> Can be converted in to more flexible and user friendly as this has the flexibility to handle any type of complexity.
---->> The main target reached was the ability to support any concave polygons which may result in holes and patches of polygons while during the operation and after that to store them to carry out further operations.
---->> Presently the points are to be added from the left bottom corner of the polygon and every thing in anticlockwise direction.
---->> Control doesn't know whether the polygon is closed or open.It assumes it as closed.
---->> It now supports all the polygons with
1 hole which now is a must to start the operation as right now it has some
problem with traversing of pointers in the linked lists.
Link to C code
C Code
Input file to Second operation
Thanks
I thank Dr.Amitabha Mukherjee Instructor to this course whose guidance fully helped me in development of Logic and the Code.
Also I would like to thank my classmates especially G.Saravanakumar
& K.N.S.Sudheer and my friend Swaroop who guided me in writing
the program and who clarified my doubts whenever I got it.