2D shape matching

Given two similar 2D polygons with vertices with known cartesian coordinates, is there software available (preferably something which will run without MatLab) that can match the vertices.  Note that there is not necessarily a one to one relationship for each vertex.  Note that the software could be medical or otherwise.  I just need to feed in ASCII coords for the vertices and output the little vectors which would join each vertex.
bartlettpAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

jkrCommented:
0
bartlettpAuthor Commented:
I was hoping for a Windows based program and a program which does not need Matlab because I do not have Matlab.  Any choices?
0
jkrCommented:
Implement it ;o)

Hey, this is a programming zone, if you are just looking for a ready made app, this is the wrong place. You'll find a description of the algorithm at http://en.wikipedia.org/wiki/Shape_context

You'll find source code and documentation at http://www.cs.princeton.edu/~min/evofunc/

A free compiler can be downloaded at http://msdn.microsoft.com/vstudio/express/ - VS2005 is available from http://www.microsoft.com/downloads/details.aspx?FamilyID=7b0b0339-613a-46e6-ab4d-080d4d4a8c4e&DisplayLang=en ("Microsoft® Visual Studio® 2005 Express Editions Service Pack 1")
0
Big Business Goals? Which KPIs Will Help You

The most successful MSPs rely on metrics – known as key performance indicators (KPIs) – for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

bartlettpAuthor Commented:
Thanks jkr
I am new to this site so sorry if I am technically in the wrong zone.  My thinking however was that a programmer/developer would know if my problem had already been solved.  I will follow the links you have kindly provided and if it works then I will obviously award the points to you.

Cheers
0
jkrCommented:
Well, the above at http://www.cs.princeton.edu/~min/evofunc/ is a library that addresses this issue directly, so you could make use of it. I also doubt that you will find an app out there that matches exactly your requirements, so customizations are most likely to be required anyway.

>> I am new to this site

No prob, welcome! ;o)
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Infinity08Commented:
>> that can match the vertices

Can you elaborate on exactly what you mean by "match vertices" ?

Do you want to find a convex polygon ? Does the polygon need to run through all vertices ? Does it need to "encircle" all vertices ? Is there a certain ordering among the vertices ?
0
bartlettpAuthor Commented:
Thanks for the reply Infinity08.

I will elaborate on the whole issue:

I have a network of 2D polygons with each polygon having a unique identifier (numbered 1 to 200,000 say). In fact the network represents the land parcels or the pattern of settlement in my home town.
 
I have another network of 2D polygons again with unique identifiers 1 to 200,000.  In general terms the networks look very similar, they share the same x, y cartesian coordinate system and each corresponding polygon looks similar but may be slightly distorted.  This distortion arises because one dataset is old land mapping data while the other has been rigorously controlled by GPS observations, recalculated and is new data.

I want to map each polygon from one network into the other by some form of shape matching.  Then I want to visualise in AutoCAD a series of vectors which shows how each corresponding vertex in the old polygon network maps across to the second network.

I can distil my networks down to ascii files which contain a unique I.D. then a series of clockwise ordered x,y coordinate pairs representing the vertices of my polygons.  One complication is that while there is a one to one relationship between the unique identifiers, each corresponding polygon does not necessarily have precisely the same number of vertices.  This is particularly the case where the arcs for curved land parcel boundaries have been represented by lots of tiny straight lines (I call this stroked arcs).

I hope this helps.
0
bartlettpAuthor Commented:
By the way

The end result I'm after is the vector field (or at least the start and end coordinates of the vectors)representing all the thousands (maybe milions) of vertex matches.  I will then use this vector field to act on other layers of data eg raster aerial images or perhaps CAD linework representing pipe networks along roadways (similar to "rubber sheeting" in GIS/CAD terminology.
0
Infinity08Commented:
Ok, so the polygon with id x in the old data will correspond to the polygon with the same id x in the new data, correct ?

So, we can descend a level, and just need to compare two polygons, which might have a different amount of vertices, and probably has the vertices at different coordinates.

Now, the point is to match up each vertex in the old polygon with one or more vertices in the new polygon. Am I still understanding it right ?

In that case, the links jkr posted are a good starting point ...

If I got it wrong, then please point out where ;)
0
bartlettpAuthor Commented:
Hi Infinity08
Yep, your understanding is correct.  My idea would be to have two ASCII data sets with each dataset having a start character like a % or $ then a first line being the ID of the polygon then a line saying how many vertices the polygon has, then lines with pairs of x,y cordinates for the vertices then an end/start character like a % or $ and so on.  I would feed the data through some algorithm like jkr's suggests and for each pair of polygons compared, out would pop start and end coordinates for each vector joining an "old" vertex to a "new" vertex.

Obviously if the "old" and "new" polygons had the same number of vertices and if the vertices all started at the same location eg top left corner, then this would be a no brainer - I could use some straightforward spreadsheet calculations to get the result I want.  Unfortunately this is not the case and the best I can do is to generate the vertices in a clockwise way and associate the group of coordinates to a particular polygon ID.
0
bartlettpAuthor Commented:
I accessed the links provided and I think that you are on the right track.  Unfortunately the maths is very complex so I think it will be a while before I can get to an implementation stage.

Thanks
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.