File Exchange

image thumbnail

Polygon Clipper

version 1.0 (39.7 KB) by

Given two arbitrary polygons, the routine calculates the resulting polygon ...

4.41667
25 Ratings

27 Downloads

Updated

View License

The Polygon Clipper (based on the gpc-library) is used to performe algebraic operations on two polygons.

Given two arbitrary polygons (which may self intersect, may contain holes, may be constructed of several contours) the Polygon Clipper is used to calculate the resulting polygon for the operations diff, union, AND, XOR.

All polygons are specified as structures as described in the example.m-file.

Credit for the gpc-library goes to Alan Murta (s. ReadMe.txt).

Comments and Ratings (36)

Hanz

Hanz (view profile)

I have been using the polygon clipper for my research, and it's been very helpful. I was wondering though, what type of clipping algorithm is being implemented, since in the c file, it just mentions that you're implementing a new algorithm. May I get to know the complexity of the code, and how it relates to other clipping algorithms, such as the Sutherland Hodgman clipping? Thank you very much

I was able to compile on linux 64 bit, but I am not sure how to upload the compiled file.

Sam Tong

Could someone please share their recompiled file for 64 bit? I don't have c compiler on windows machine.

John Trimper

Brian Hannan

Hi Sebastian,

According to Alan Murta's documentation, the clipper supports simultaneous operations on >2 polygons. Is this feature supported in your code? Also, do you know how I can use the clipper library functions CleanPolygons and the clipper's StrictlySimple property with your code? Thanks.

lyes

lyes (view profile)

Good tool. Thank you very much.

For the Issue of 64 bit compatibility , you should recompile the c files as follows :
mex *.c -compatibleArrayDims -output PolygonClip

It is preferable that you do this , NOT in your current working folder. Then copy the PolygonClip.mexw64 in your working folder to use it.

Trey

Trey (view profile)

Ilya

Ilya (view profile)

Awesome, thanks

Veena

Veena (view profile)

Firstly, this is a fantastic tool. I've used it over and over again. I've been on a 32 bit machine till now and it's worked wonderfully.
Now, however, i've moved to 64 bit, and i'm in trouble.. i need to recompile. While i try to go through the process, I wanted to throw this request out there: Would anyone be willing to share the 64 bit version of this mex file? That would be incredibly useful to me (and I would guess others as well).

Petra

Petra (view profile)

I got problems on a 64bit system. After compiling the an example.m the example.exe started perfectly on the computer where I compiled the file. When I am trying to start the example.exe on a different computer the example.exe doesn't run. I guess that there is one library file missing from the mex compiler. Do you know what library file(s) is missing?
Thanks for sharing this great tool

Ajay

Ajay (view profile)

Any suggestions for polygon clipping in 3D?
Thanks for posting, very easy to use!

lzeeysjp

Great tool. Works like a charm here.

One question:
I would like to calculate the area of a polygon returned after clipping.

Has someone already written a function to do that?
It is not working using Matlab's polyarea, since the format is different and holes have to be considered.

lzeeysjp

Sebastian Hölz

Just a quick update ... I just installed a 64bit system and was able to get a working 64bit mex file (on Win7) with the following commands:

>> mex -c *.c
>> mex *.obj -output PolygonClip.mexw64

Mexing of course requires that you have a C-compiler running on your system. Prior to issuing the above commands you have to make sure that this compiler is selecte using:
>> mex -setup
I did some testing and could not find any memory leaks.

Cheers

Sebastian

Martin

Martin (view profile)

Kate

Kate (view profile)

Lian -- I had a similar problem when my polygons contained NaNs. After I fixed that, the problem went away. Perhaps yours is similar?

Sebastian -- Thank you very much!

Guys, does anyone know how to fix this issue:

Bugs
----
    ??? 1) It seems that the routine is sometimes passing back empty arrays (0 vertex). This should be handled. ???

Andrew T

Hi Lian,

Please see this page:

http://www.cs.man.ac.uk/~toby/alan/software/gpc_faq.htm

GPC is the C clipping library behind PolygonClipper. What you are experiencing is not due to a shortcoming of MATLAB or Hölz' MEX code, but is instead due to a known limitation of the underlying clipping algorithm implementation.

I had the same problem you are having (I only encountered it in certain cases), and I fixed it by snapping all polygon vertices to a grid before clipping, as Murta suggests.

Btw, thank you Sebastian Hölz, you have saved me the trouble of trying to write my own GPC interface!

Lian Duan

To be honest, this is a really waste of time. This programm is tested on windows XP with matlab 2008b, MAC and Linux with matlab 2009. They are all having the same error as I have put out in the last post. Users be aware of this. After 2 days of trying to fix this problem, I am now give up and have to look for an alternative programme. I am not sure if the author check these posts or not. If you do, I could send you my programe for your debugging. Thanks. Lian

Lian Duan

Dear Sebastian Hölz:

Hi, these programmes are very handy.

However, I have got this error after calling the mex function repeatedly.

there might be a memory leak in the code.

Thanks.

Lian
 
------------------------------------------------------------------------
       Segmentation violation detected at Fri Oct 1 12:53:00 2010
------------------------------------------------------------------------

Configuration:
  MATLAB Version: 7.9.0.529 (R2009b)
  MATLAB License: 161051
  Operating System: Darwin 10.4.0 Darwin Kernel Version 10.4.0: Fri Apr 23 18:28:53 PDT 2010; root:xnu-1504.7.4~1/RELEASE_I386 i386
  Window System: The X.Org Foundation (10402000), display /tmp/launch-9KjGVS/org.x:0
  Current Visual: 0x24 (class 4, depth 24)
  Processor ID: x86 Family 6 Model 7 Stepping 6, GenuineIntel
  Virtual Machine: Java 1.6.0_20-b02-279-10M3065 with Apple Inc. Java HotSpot(TM) 64-Bit Server VM mixed mode
  Default Encoding: US-ASCII

Fault Count: 1

Register State:
  rax = 47837790 rbx = 00000000
  rcx = 47837790 rdx = 00000001
  rsi = 14783779 rdi = 03d55a00
  rbp = 17afb5c0 rsp = 17afb5a0
  r8 = 478fc0a0 r9 = 478fc0a4
  r10 = 0000001b r11 = 1478377a
  r12 = 00000002 r13 = 00000001
  r14 = 00000000 r15 = 00000000
  rip = 057ae10b flg = 00010206
  cs = 00000027 fs = 00000010
  gs = 00000048

Stack Trace:
  [0] PolygonClip.mexmaci64:add_left~ + 59 bytes
  [1] PolygonClip.mexmaci64:gpc_polygon_clip~ + 2469 bytes
  [2] PolygonClip.mexmaci64:mexFunction~ + 211 bytes
  [3] libmex.dylib:mexRunMexFile + 90 bytes
  [4] libmex.dylib:Mfh_mex::runMexFileWithSignalProtection(int, mxArray_tag**, int, mxArray_tag**) + 137 bytes
  [5] libmex.dylib:Mfh_mex::dispatch_file(int, mxArray_tag**, int, mxArray_tag**) + 276 bytes
  [6] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [7] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [8] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [9] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [10] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [11] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [12] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [13] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [14] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [15] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [16] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [17] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [18] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [19] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [20] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [21] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [22] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [23] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [24] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [25] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [26] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [27] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [28] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [29] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [30] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [31] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [32] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [33] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [34] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [35] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [36] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [37] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [38] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [39] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [40] libmwm_interpreter.dylib:inCallFcnFromReference + 205 bytes
  [41] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 1980 bytes
  [42] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [43] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [44] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [45] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [46] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [47] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [48] libmwm_interpreter.dylib:inCallFcnFromReference + 205 bytes
  [49] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 1980 bytes
  [50] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [51] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [52] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [53] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [54] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [55] libmwm_interpreter.dylib:inEvalPcodeHeaderToWord(_memory_context*, int, mxArray_tag**, _pcodeheader*, Mfh_mp*, unsigned int) + 244 bytes
  [56] libmwm_interpreter.dylib:inEvalStringWithIsVarFcn(_memory_context*, char const*, EvalType, int, mxArray_tag**, inDebugCheck, _pcodeheader*, int*, bool (*)(void*, char const*), void*, bool, bool) + 1714 bytes
  [57] libmwm_interpreter.dylib:inEvalCmdWithLocalReturn(char const*, int*, bool, bool, bool (*)(void*, char const*)) + 145 bytes
  [58] libmwbridge.dylib:evalCommandWithLongjmpSafety(char const*) + 94 bytes
  [59] libmwbridge.dylib:mnParser + 681 bytes
  [60] libmwmcr.dylib:mcrInstance::mnParser_on_interpreter_thread() + 41 bytes
  [61] libmwmcr.dylib:boost::function0<void>::operator()() const + 38 bytes
  [62] libmwmcr.dylib:mcr::runtime::InterpreterThread::Impl::NoResultInvocationRequest::run() + 21 bytes
  [63] libmwmcr.dylib:mcr::runtime::InterpreterThread::Impl::invocation_request_handler(long) + 41 bytes
  [64] libmwuix.dylib:uix_DispatchOrProcess(_XEvent*, _XtAppStruct*, int, bool) + 457 bytes
  [65] libmwuix.dylib:ws_ProcessPendingEventsHelper(int, int, bool) + 593 bytes
  [66] libmwmcr.dylib:mcr::runtime::InterpreterThread::Impl::process_events(boost::shared_ptr<mcr::runtime::InterpreterThread::Impl> const&) + 46

Works great. (Malab 7.4.0, XP 32 bit)
Thanks for sharing

Saiful

Saiful (view profile)

Ok, at last I was able to make it work. But because of Mex, its operation is very slow. Can any of you please forward me to a function totally developed in Matlab? Thanks!

Saiful

Saiful (view profile)

i am also having trouble to work on windows xp pro 64 bit. can any of you please post a solution? Thanks....

Sam Cape

I'm having problems getting this to work on xp pro 64 bit. Any suggestions?

Dominic

For me the installation also worked flawlessly under 64bit Linux - as the code itself - great work!

Just a quick note...Mac OSX 10.5 Matlab Release 2008a
 Compiled and ran example first time using exactly
the instructions from ReadMe.txt
(cut and pasted them to matlab command window)
Compiler used gcc version 4.0.1 (Apple Inc. build 5465)
(default on my system)
Thanks for terse and sufficient instructions.

Stanley

Stanley (view profile)

Very good.

Ramtin S

Good work. Have not seen any problems with it so far

moho atc

yes yes

Gerald Dalley

Worked well the first time and is reasonably fast. Thanks! It compiled fine for me on 64-bit Linux using Matlab 7.2.

Jaeyoung Jung

This polygon clipper works very well and easy to use, also has good quality!!

je che

Took a lot of work to run on my linux machine. The problem is that the
gpc_mexfile sources use '//' to begin the comments, and this is not part
of the C standard. This probably means the programs were written on a
Windows machine, which uses Microsoft Visual C++ to compile C code.
'//' is the comment prefix in standard C++. Microsoft appears to
believe that C++ is a perfect superset of C, which isn't true.

I removed all the lines beginning with // from those two source files
and the mex command in the readme gave worked fine.

Also, it won't run unless I had the older gcc-3.3 package installed.

Also, the zip file ships with Example.m which doesn't work. PolyClipper_example.m does work. Looks like a great function, though, if these things get tidied up.

Emily Hinz

An extremely useful and easy to use set of routines. Thank you!

Murray Thomson

Worked first time. Very easy to use. Did exactly what I needed. (And not an easy thing to program for yourself, as I found out the hard way!)

Pancho Blu

Just what I needed. I have been racking my brains for days to get to a point where my program starts to work, but this one is much better and faster!. Thanks a lot.

Updates

Changes according to suggestions of je che (3.8.2006)
- Removed file "Example.m", which somehow slipped into the zip-file.
- Changed comment style in "gpc_mexfile.*"

Catching error with empty hole field (xyz.hole=[];), minor changes.

Memory hole fixed in the mexfile (gpc_mexfile.c), which could lead to segmentation violation.

MATLAB Release
MATLAB 7.0.1 (R14SP1)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video