How to store vertex indices from a triangulation.

Willie Maddox

unread,

May 17, 2013, 5:54:41 PM5/17/13

to cgal-bindi...@googlegroups.com

Hello,

I have a simple question for you guys. In the code below, I am performing a simple Delaunay triangulation on a set of 6 points. I can view the indicies by calling "print t" (or by calling "t.write_to_file("dummy.txt")).

What I want to do is store the indices from memory directly into a list. (e.g. [[4,0,3],[1,2,3],[5,6,4],...,[2,1,6]])

Any Ideas on how this can be done?

Thanks,

-Will Maddox

##### BEGIN PYTHON SCRIPT #####

from CGAL.CGAL_Kernel import Point_2

from CGAL.CGAL_Triangulation_2 import Delaunay_triangulation_2

points=[]

points.append( Point_2(1,0) )

points.append( Point_2(4,5) )

points.append( Point_2(9,8) )

points.append( Point_2(7,4) )

points.append( Point_2(5,1) )

points.append( Point_2(10,1) )

t=Delaunay_triangulation_2()

t.insert(points)

print t

##### END PYTHON SCRIPT #####

##### BEGIN OUTPUT #####

7 10 2

1 0

5 1

4 5

9 8

7 4

10 1

4 0 3

1 2 3

5 6 4

0 1 3

6 1 0

2 5 3

3 5 4

6 0 4

2 6 5

2 1 6

3 6 7

5 3 9

7 6 8

1 0 4

3 7 9

6 1 8

2 0 5

0 2 4

2 5 9

4 8 1

##### END OUTPUT #####

Philipp Moeller

unread,

May 17, 2013, 6:03:51 PM5/17/13

to cgal-bindi...@googlegroups.com

On May 17, 2013 11:54 PM, "Willie Maddox" <willie...@gmail.com> wrote:
>
> Hello,
>
> I have a simple question for you guys. In the code below, I am performing a simple Delaunay triangulation on a set of 6 points. I can view the indicies by calling "print t" (or by calling "t.write_to_file("dummy.txt")).
>
> What I want to do is store the indices from memory directly into a list. (e.g. [[4,0,3],[1,2,3],[5,6,4],...,[2,1,6]])
>
> Any Ideas on how this can be done?

A CGAL triangulation doesn't really have something like indices. The file writer generates them manually. Your best bet is to have a look at the code an emulate this behavior.

IIRC it hashes all Vertex_handles and maps those into a continuous range. Then for each cell you iterate over the vertices and look up this id in the hash map.

HTH,
Philipp

Willie Maddox

unread,

May 17, 2013, 6:31:39 PM5/17/13

to cgal-bindi...@googlegroups.com

A CGAL triangulation doesn't really have something like indices. The file writer generates them manually. Your best bet is to have a look at the code an emulate this behavior.

IIRC it hashes all Vertex_handles and maps those into a continuous range. Then for each cell you iterate over the vertices and look up this id in the hash map.

That is fine. I don't mind generating them manually. I figured I would have to do that anyway. But how? I've spent the last few days digging into the CGAL-bindings and CGAL source code trying many different approaches, but no joy.

I have been able to get the coordinate information for each face using:

[t.triangle(f) for f in t.finite_faces()]

Can something like this not be done for the indices? Maybe using t.incident_vertices for each Face_handle?

By the way, what does "IIRC" stand for?

Thanks,

Will

Sebastien Loriot (GeometryFactory)

unread,

May 20, 2013, 3:38:13 AM5/20/13

to cgal-bindi...@googlegroups.com

Here is an example:

from CGAL.CGAL_Kernel import Point_2
from CGAL.CGAL_Triangulation_2 import Triangulation_2
from CGAL.CGAL_Triangulation_2 import Triangulation_2_Vertex_circulator
from CGAL.CGAL_Triangulation_2 import Triangulation_2_Vertex_handle

points=[]
points.append( Point_2(1,0) )
points.append( Point_2(3,2) )

points.append( Point_2(4,5) )
points.append( Point_2(9,8) )
points.append( Point_2(7,4) )

points.append( Point_2(5,2) )
points.append( Point_2(6,3) )
points.append( Point_2(10,1) )

t=Triangulation_2()
t.insert(points)

map={}
i=0

for p in t.finite_vertices():
map[p]=i
i+=1

for c in t.finite_faces():
print map[ c.vertex(0) ], map[ c.vertex(1) ], map[ c.vertex(2) ]

There was a stupid typo that was preventing this from working that is
now fixed.

Sebastien.

> --
> You received this message because you are subscribed to the Google
> Groups "CGAL Bindings discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to cgal-bindings-di...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

Willie Maddox

unread,

May 20, 2013, 2:27:50 PM5/20/13

to cgal-bindi...@googlegroups.com

Sebastian,

This method makes sense. However, when I run it, it breaks at:

for c in t.finite_faces():
print map[ c.vertex(0) ], map[ c.vertex(1) ], map[ c.vertex(2) ]

Here is the script followed by the output and the error:

from CGAL.CGAL_Kernel import Point_2

from CGAL.CGAL_Triangulation_2 import Delaunay_triangulation_2

from CGAL.CGAL_Triangulation_2 import Delaunay_triangulation_2_Vertex_handle

from CGAL.CGAL_Triangulation_2 import Delaunay_triangulation_2_Vertex_circulator

points=[]

points.append( Point_2(1,0) )

points.append( Point_2(4,5) )

points.append( Point_2(9,8) )

points.append( Point_2(7,4) )

points.append( Point_2(5,1) )

points.append( Point_2(10,1) )

t=Delaunay_triangulation_2()

t.insert(points)

Map = {}

i = 0

for p in t.finite_vertices():

print p

Map[p] = i

i += 1

print '-------------------'

for m in Map:

print m

print '-------------------'

for c in t.finite_faces():

print c.vertex(0)

print c.vertex(1)

print c.vertex(2)

for c in t.finite_faces():

print Map[c.vertex(0)], Map[c.vertex(1)], Map[c.vertex(2)]

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233C8> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23038> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23410> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23428> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23440> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23458> >

-------------------

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23038> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23410> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23428> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23440> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A23458> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233C8> >

-------------------

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233F8> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233E0> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233F8> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233E0> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233F8> >

<CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233E0> >

Traceback (most recent call last):

File "C:\Users\maddoxw\workspace2\CGAL-bindings-examples\src\delaunay_triangulation_prog1.py", line 42, in <module>

print Map[c.vertex(0)], Map[c.vertex(1)], Map[c.vertex(2)]

KeyError: <CGAL.CGAL_Triangulation_2.Delaunay_triangulation_2_Vertex_handle; proxy of <Swig Object of type 'SWIG_Triangulation_2::CGAL_Face_handle< CGAL_DT2,Point_2 >::Vertex_handle *' at 0x02A233F8> >

It appears that the memory addresses between vertices in finite_vertices are different from those in finite_faces.

To what "stupid typo" are you referring? Maybe it needs to be fixed on my end?

Also, are the Vertex_handle and Vertex_circulator imports necessary?

Thanks for your time,

-Will

> an email to cgal-bindings-discuss+unsub...@googlegroups.com.

Sebastien Loriot (GeometryFactory)

unread,

May 21, 2013, 1:22:39 AM5/21/13

to cgal-bindi...@googlegroups.com

Did you pull the last commit?

Sebastien.

> > an email to cgal-bindings-di...@googlegroups.com
> <javascript:>.

> > For more options, visit https://groups.google.com/groups/opt_out

> <https://groups.google.com/groups/opt_out>.

> >
> >
>
> --
> You received this message because you are subscribed to the Google
> Groups "CGAL Bindings discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to cgal-bindings-di...@googlegroups.com.

Willie Maddox

unread,

May 21, 2013, 3:03:08 PM5/21/13

to cgal-bindi...@googlegroups.com

Sebastien,

I just did. And it works like a charm. Thank You!!!

I am curious. What file(s) did you update? I would like to compare them so I can learn what to do if a similar problem arises in the future.

Thanks,

-Will

> > an email to cgal-bindings-discuss+unsub...@googlegroups.com

> <javascript:>.
> > For more options, visit https://groups.google.com/groups/opt_out
> <https://groups.google.com/groups/opt_out>.
> >
> >
>
> --
> You received this message because you are subscribed to the Google
> Groups "CGAL Bindings discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to cgal-bindings-discuss+unsub...@googlegroups.com.

Sebastien Loriot (GeometryFactory)

unread,

May 22, 2013, 9:09:57 AM5/22/13

to cgal-bindi...@googlegroups.com

Not really helpful but see:

see
http://code.google.com/p/cgal-bindings/source/diff?spec=svnfef3e0e70ee4a1258e0cf865cf322e0c3f102f58&r=fef3e0e70ee4a1258e0cf865cf322e0c3f102f58&format=side&path=/SWIG_CGAL/common.i

Sebastien.

> > > an email to cgal-bindings-di...@googlegroups.com
> <javascript:>

> > <javascript:>.
> > > For more options, visit
> https://groups.google.com/groups/opt_out
> <https://groups.google.com/groups/opt_out>
> > <https://groups.google.com/groups/opt_out
> <https://groups.google.com/groups/opt_out>>.
> > >
> > >
> >
> > --
> > You received this message because you are subscribed to the Google
> > Groups "CGAL Bindings discuss" group.
> > To unsubscribe from this group and stop receiving emails from it,
> send

> > an email to cgal-bindings-di...@googlegroups.com

> <javascript:>.
> > For more options, visit https://groups.google.com/groups/opt_out
> <https://groups.google.com/groups/opt_out>.
> >
> >
>
> --
> You received this message because you are subscribed to the Google
> Groups "CGAL Bindings discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to cgal-bindings-di...@googlegroups.com.

Reply all

Reply to author

Forward